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

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

bison token insert parsing

0

Lex - Boycott Slack - see bio · 技术社区 · 11 年前

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 回复 | 直到 11 年前

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();
}

笔记

这是 lemon 解析器生成器。 柠檬 最初是为了创建 sqlite SQL解析器,但正是为了方便“推送”接口而在各种项目中使用。 bison 的push解析器支持是最新的,非常受欢迎。
我不疯狂 INT_VAL ; 对于联合标记,我更喜欢小写,但我试图将差异最小化。