代码之家  ›  专栏  ›  技术社区  ›  Lex - Boycott Slack - see bio

Bison解析器扩展规则而不是缩减规则

  •  0
  • Lex - Boycott Slack - see bio  · 技术社区  · 10 年前

    Bison规则是否可能扩展而不是减少,从而转化为更多令牌?问了一个不同的方法:是否可以在解析器输入中的下一个标记之前插入要解析的额外标记?

    下面是一个示例,我可能希望这样做:

    假设我需要一个能够理解三种令牌类型的解析器。数字(为简单起见,仅为正整数-INT)、单词(任意数量的字母,大写或小写STRING)和某种其他符号(让我们毫无理由地使用感叹号-EXC)

    假设我有一个规则,它将一个单词后面跟着一个数字,然后跟着一个感叹号。这个规则产生一个整数类型,现在让我们假设它只是将其输入加倍。该规则还允许自己是它解析的整数。

    我还有一条规则,可以接受一行中任意数量的字符(开始规则)。

    Bison解析器如下所示:(quicktest.y)

    %{
    #include <stdio.h>
    %}
    
    %union {
        int INT_VAL;
    }
    
    %token STRING EXC
    %token <INT_VAL> INT
    %type <INT_VAL> somenumber
    
    %%
    
        start: somenumber           {printf ("Result: %d\n", $1);}
             | start somenumber     {printf ("Result: %d\n", $2);}
             ;
    
        somenumber: STRING INT EXC           {$$ = $2 *2;}
                  | STRING somenumber EXC    {$$ = $2 *2;}
                  ;
    
    %%
    
    main(int argc, char ** argv){
    
        yyparse();
    
    }
    
    yyerror(char* s){
        fprintf(stderr, "%s\n", s);
    }
    

    可以使用如下的flex lexer生成令牌:(quicktest.l)

    %{
        #include "quicktest.tab.h"  
    %}
    
    %%
    
    [A-Za-z]+               {return STRING;}
    [1-9]+                  {yylval.INT_VAL = atoi(yytext); return INT;}
    "!"                     {return EXC;}
    .                       {}
    

    这可以通过以下命令构建:

    bison -d quicktest.y
    flex quicktest.l
    gcc -o quicktest quicktest.tab.c lex.yy.c -lfl -ggdb
    

    我现在可以输入如下内容:

    double double 2 ! !
    

    得到结果8

    现在,如果我希望用户能够避免在一行中有很多感叹号,如下所示:

    a b c d e f 2 ! ! ! ! ! !
    

    我希望能够允许他们输入以下内容:

    a b c d e f 2 !*6
    

    因此,我可以为这样的令牌添加一个flex表达式,它只需提取所需的感叹号数量:

    !\*[1-9]+               {
                                char *number = malloc(sizeof(char) * (strlen(yytext)-1));
                                strcpy(number, yytext+2);
                                yylval.INT_VAL = atoi(number);
                                free(number);
                                printf("Multiple exclamations: %d\n", yylval.INT_VAL);
                                return REPEAT_EXC;
                            }
    

    但我该如何实现事情中野牛的一面呢?

    我可以这样添加令牌类型:

    %token <INT_VAL> REPEAT_EXC
    

    然后也许是某种规则?

        repeat_exc: REPEAT_EXC      {/*expand into n exclamation marks (EXC tokens)*/}
                  ;
    

    Bison以任何方式支持这一点吗?

    如果不是,我应该如何实施?

    当lexer收到repeat-EXC表达式时,我是否应该让它返回n次EXC令牌?(如果可能的话,我宁愿避免这种情况,因为这需要flex代码保持某种状态的记录,它可能处于重复感叹号状态,也可能处于正常状态。这样一来,lexer就不那么容易维护了。)

    1 回复  |  直到 10 年前
        1
  •  1
  •   Community CDub    5 年前

    这在上下文无关的语法中是不可能的。

    这在传统的lexer中并不难做到,但正如您所说,它需要lexer保持状态。更简单的方法是使用 push parser ,其中解析器是从lexer调用的,而不是相反。[注1]

    野牛手册没有很好地解释API;如果您声明一个纯push解析器,那么您得到的接口是:

    int yypush_parse(yypstate*, int, const YYSTYPE*);
    

    或者,如果启用了位置跟踪:

    int yypush_parse(yypstate*, int, const YYSTYPE*, YYLTYPE*);
    

    为了显示push_parser接口,我对示例做了相当小的修改。首先,解析器;唯一的区别是 %define 用于声明推送解析器的指令;消除 main (lexer现在是顶级的) yyerror 使用显式 void 返回类型。[注2]

    %{
        #include <stdio.h>
        void yyerror(char* msg);
    %}
    
    %define api.pure full
    %define api.push-pull push
    %union {
        int INT_VAL;
    }
    
    %token STRING EXC
    %token <INT_VAL> INT
    %type <INT_VAL> somenumber
    
    %%
    
        start: somenumber           {printf ("Result: %d\n", $1);}
             | start somenumber     {printf ("Result: %d\n", $2);}
             ;
    
        somenumber: STRING INT EXC           {$$ = $2 *2;}
                  | STRING somenumber EXC    {$$ = $2 *2;}
                  ;
    
    %%
    
    void yyerror(char* s){
        fprintf(stderr, "%s\n", s);
    }
    

    lexer有一些更实质性的变化,但我不认为最终结果更难阅读或维护。甚至可能更容易。

    • PARSE 将具有指定类型标记和值的令牌发送到 yyparse ; 宏 PARSE_TOKEN 发送没有语义值的令牌。

    • 这个 %options 行从编译步骤中删除几个警告

    • 已添加分析器状态的初始化。( %% 在本例中,在lexer函数的顶部插入任何规则之前 yypush_parse ,因此它们可以用于声明和初始化局部变量。)

    • 这个 INT 规则已更改为允许 10 为有效整数。

    • 这个 !*<int> 已添加规则。

    • 这个 <<EOF>> 已添加规则。(对于lexer驱动的推送解析来说,这是一个很好的锅炉板。)

    • A. 主要的 已添加函数,该函数调用 yylex .

    (哦,我改变了一条规则,以避免重复新的行。)

    %{
      #include "push.tab.h"  
      #define PARSE(tok,tag,val) do { \
        YYSTYPE yylval = {.tag=val};  \
        int status = yypush_parse(ps, tok, &yylval); \
        if (status != YYPUSH_MORE) return status; \
      } while(0)
      #define PARSE_TOKEN(tok) do { \
        int status = yypush_parse(ps, tok, 0); \
        if (status != YYPUSH_MORE) return status; \
      } while(0)
    %}
    %option noyywrap nounput noinput
    
    %%
                             yypstate *ps = yypstate_new ();
    
    [A-Za-z]+               {PARSE_TOKEN(STRING);}
    [1-9][0-9]*             {PARSE(INT,INT_VAL,atoi(yytext));}
    "!*"[1-9][0-9]*         {int r = atoi(yytext+2);
                             while (r--) PARSE_TOKEN(EXC);
                            }
    "!"                     {PARSE_TOKEN(EXC);}
    .|\n                    {}
    <<EOF>>                 {int status = yypush_parse(ps, 0, 0);
                             yypstate_delete(ps);
                             return status; 
                            }
    
    %%
    
    int main(int argc, char** argv) {
      return yylex();
    }
    

    笔记

    1. 这是 lemon 解析器生成器。 柠檬 最初是为了创建 sqlite SQL解析器,但正是为了方便“推送”接口而在各种项目中使用。 bison 的push解析器支持是最新的,非常受欢迎。

    2. 我不疯狂 INT_VAL ; 对于联合标记,我更喜欢小写,但我试图将差异最小化。