flex and bison 2015

bison-examples的说明

运用Bison构造编译器的示例代码包bison-examples

本压缩包围绕2个小型编程语言：L-expr（简单的表达式语言）、L-asgn（赋值语句序列语言），给出如何利用Flex和Bison构造编译器，其中涉及程序位置跟踪、符号表的管理、抽象语法树的构造、错误信息管理等。

1. L-expr语言的文法

input ::= ε  | input line
line ::= EOL | expr EOL
expr ::= NUMBER 
            | expr PLUS expr    # PLUS     – ‘+’加号
            | expr MINUS expr    # MINUS – ‘-’减号
            | expr MULT expr    # MULT     – ‘*’乘号
            | expr DIV expr        # DIV     – ‘/’除号
            | MINUS expr        # MINUS – ‘-’负号
            | expr EXPON expr    # EXPON – ‘^’乘幂
            | LB expr RB        # LB, RB – ‘(’, ’)’ 左右括号

2. L-asgn语言的文法

input   ::= ε | input line
line    ::= EOL 
            | asgnexp ';' EOL
asgnexp ::= IDENTIFIER ASGN exp # ASGN  - ‘=’赋值号
expr    ::= NUMBER
            | IDENTIFIER        # IDENTIFIER – 标识符
            | expr PLUS expr    # PLUS  – ‘+’   加号
            | expr MINUS expr   # MINUS – ‘-’减号
            | expr MULT expr    # MULT  – ‘*’乘号
            | expr DIV expr     # DIV   – ‘/’ 除号
            | MINUS expr        # MINUS – ‘-’负号
            | expr EXPON expr   # EXPON – ‘^’乘幂
            | LB expr RB        # LB, RB – ‘(’, ’)’ 左右括号

在L-asgn语言中，标识符代表变量，标识符需要先赋值再使用。如果程序使用了未赋值的变量，则需要给出警告并默认初值为0。

3. bison-examples.zip的文件目录结构说明。

|- README           对本压缩包的说明文档
|- Makefile         用于构造语言的词法、语法分析器并将它们编译成可执行文件
|- run.sh           以./run.sh x y命令启动bin子目录下的x编译器编译test子目录下的y程序
|- config           存放语言的词法和语法文法文件
    |- expr.lex     L-expr的Flex词法规范。
                    以-oexpr.lex.c选项执行flex，会根据该文件生成词法分析器expr.lex.c
    |- expr.y       L-expr的Yacc语法规范，它利用Yacc提供的优先级声明来消除文法的二义性。该语法规范内嵌有边分析边对表达式求值的语义动作。
                    以-b expr -o expr.tab.c选项执行Bison，会根据该文件生成语法分析器expr.tab.c以及词法、语法分析都需使用的符号声明头文件expr.tab.h
    |- expr1.y      L-expr的Yacc语法规范，它通过增加文法非终结符，将文法改写成无二义的文法。可以用Bison处理该文件，生成expr1.tab.h(.c)。该语法规范内嵌有边分析边对表达式求值的语义动作。
    |- exprL.y      L属性定义举例：L-expr的Yacc语法规范，在规则中嵌入打印行号的语义动作，行号通过全局变量传递。
    |- exprL1.y     L属性定义举例：L-expr扩展语言略(每行开始增加行号)的Yacc语法规范，在规则中嵌入打印源程序中所给行号的语义动作。
    |- midrule.y    L属性定义举例：使用$<val>N引用语义值栈中任意位置的语义值，N可以为正整数、0、负整数，<val>为所引用的语义值的类型。
    |- asgn.lex     L-asgn的Flex词法规范。
    |- asgn.y       L-asgn的Yacc语法规范。该语法规范内嵌有边分析边对赋值语句求值的语义动作。
    |- asgn1.y      L-asgn的Yacc语法规范，它与asgn.y的区别在于引入一个表示双目运算符的非终结符op。
    |- asgn2ast.y   L-asgn的Yacc语法规范。该语法规范内嵌有边分析边构造抽象语法树的语义动作。
    |- asgn_err.lex L-asgn的Flex词法规范，它与asgn.lex的区别在于引入统计尚未匹配的左括号数的全局量lparen_num，以便在词法分析的过程中进行括号匹配跟踪。
    |- asgn_err.y   L-asgn的Yacc语法规范。它与asgn_err.lex协作，支持对不合法的L-asgn程序的分析，提供错误恢复以及错误信息的记录并在分析结束时集中输出。
|- include          存放用户自定义的头文件
    |-util.h        存放一些实用的宏、类型声明、函数声明，如动态分配相关的宏定义(如NEW, NEW0)；线性表、线性表迭代器的数据结构的定义以及相关接口函数的声明。
    |-common.h      编译器需要使用的一些公共的声明和定义，如符号表的结构、错误信息的结构、错误容器（或称错误工厂）的结构、语法树及其结点的结构定义，相关函数的声明等等
    |-op.h          保存所处理的运算符及其对应的文本信息的配置文件
    |-errcfg.h      保存所处理的错误类别及其对应的提示信息的配置文件
|- src              存放源程序文件
    |-list.c        线性表的接口函数的实现（采用链式结构存储）、线性表迭代器Iterator的接口函数的实现
    |-symtab.c      符号表的接口函数的实现（采用链地址结构的Hash表存储）
    |-error.c       错误信息及其管理的接口函数的实现
    |-ast.c         抽象语法树相关的接口函数的实现
    |- expr.1ex.c, expr.tab.h, expr.tab.c, expr1.tab.c 利用Bison和Flex处理config目录下的expr.lex, expr.y, expr1.y生成的词法、语法分析器的源代码文件。
    |- asgn.1ex.c, asgn.tab.h, asgn.tab.c, asgn1.tab.c, asgn2ast.tab.c 利用Bison和Flex处理config目录下的asgn.lex, asgn.y, asgn1.y, asgn2ast.y生成的词法、语法分析器的源代码文件。
    |- asgn_err.1ex.c, asgn_err.tab.h, asgn_err.tab.c 利用Bison和Flex处理config目录下的asgn_err.lex, asgn_err.y生成的词法、语法分析器的源代码文件。
|- bin              存放可执行文件
    |- expr, expr1, asgn, asgn1, asgn2ast, asgn_err 执行make或者make expr ( 或expr1, asgn, asgn1, asgn2ast, asgn_err)后得到的L-expr、L-asgn语言的编译器的可执行文件
|- test             存放测试程序
    |- expr.in      一个合法的L-expr程序
    |- asgn.in      一个合法的L-asgn程序
    |- asgn_err.in  一个不合法的L-asgn程序

4. 如何使Flex和Bison生成的分析器能跟踪程序位置

bison-examples中config/asgn.lex和asgn.y给出了如何使生成的分析器能跟踪程序位置的示例。这里简述要点：

  • Bison生成的分析器缺省地用YYLTYPE结构类型（在生成的*.tab.h中定义）来存储位置，其中包含first_line、first_column、last_line、last_column四个int域；并且引入YYLTYPE类型的全局变量yylloc保存当前记号的位置信息。

  • 在asgn.lex的声明段，增加如下代码：

      %{int yycolumn = 1;

  #define YY_USER_ACTION yylloc.first_line = yylloc.last_line = yylineno; \
  yylloc.first_column = yycolumn; yylloc.last_column = yycolumn+yyleng-1; \
  yycolumn += yyleng;
  %}
  %option yylineno
  • 在asgn.lex的规则段，在处理一个新行时增加对yycolumn修改的语义动作；
  • Bison会按缺省的位置跟踪方法为生成的分析器跟踪位置信息，见Bison manual 3.6 Tracking Locations。在asgn.y的语义动作中，可以通过@$.first_line、@1.last_column来访问位置信息，其中@$表示产生式左部符号(LHS, left-hand side)对应的位置信息，@1表示产生式右部符号(RHS, right-hand side) 对应的位置信息。

5. 利用预编译指令灵活处理诸如错误类别等的可配置信息

在bison-examples中使用预编译指令灵活处理错误类别以及操作符等可配置的信息，并根据实际的配置信息生成相关类型和全局变量等。这里以操作符为例，简述处理方法：

  • include/op.h为操作符的配置文件，其中每个操作符对应于如下形式的一行条目 opxx(PLUS, " + " )

  • 在include/common.h中有如下代码段：

      enum {
  #define opxx(a, b) OP_##a,
  #include "op.h"
      OPLAST
  };

    该代码段将由op.h里的配置信息产生枚举常量，如PLUS对应的为OP_PLUS

  • 在src/ast.c中有如下代码段：

      char *opname[]={
  #undef opxx
  #define opxx(a, b) b,
  #include "op.h"
      "Undefined Op"
  };

    该代码段将由op.h里的配置信息来初始化操作符名称数组opname的取值。

  • 用户可以在op.h中增加更多的操作符，而无须在修改枚举类型和opname的定义。 有关错误类型和对应的错误提示信息可以在include/errcfg.h中配置，在include/common.h和src/error.c中有相应的枚举类型、错误信息数组的定义。

6. 引入宏NEW和NEW0来简化对各类结点的动态创建和清0操作的代码编写

    #define NEW(p)     ((p) = malloc(sizeof *(p)))
    #define NEW0(p) memset(NEW(p), 0, sizeof *(p))

若要构建结点类型为A的结点，则可以：

    A *p, *q;
    NEW(p);            // 创建A类型的结点，使p指向A类型的结点
    NEW0(q);        //创建A类型的结点并将所创建的结点清0，使q指向该结点

7. 引入设计模式和工厂模式

  • 引入设计模式来创建各类AST结点、错误信息结点等
  • 引入“工厂模式”这一常用设计模式来创建各类AST结点、错误信息结点等

8. 在Yacc文法描述文件中处理L属性定义

  • 在.y文件中，翻译规则可以内嵌语义动作代码，如config/exprL.y中有如下片段：

      input   : …
          | input 
                { lineno ++; 
                  printf("Line %d:\t", lineno);
                }
          line

    每个用一对花括号括起的内嵌语义动作也视为一个文法符号（匿名符号），故上例中右部input {…} line共计3个文法符号，line对应的语义值通过$3引用。

  • 可以在翻译规则的内嵌语义动作代码中设置该文法符号对应的语义值，如config/exprL1.y中有如下片段：

      line   : ...
          | NUMBER { ...
                      $<val>lineno = $1;
                        //$<val>$ = $1;
     }[lineno]
    exp EOL { ...
          printf("Line %d: %g\n", (int)$<val>lineno, $3);
                      ...                    
                  }

    其中：

    • [lineno]为嵌入在NUMBER和exp之间的语义动作命名,从而该语义动作对应的文法符号名为lineno。若上述代码片段中去掉[lineno]，则上述内嵌的语义动作对应的文法符号是匿名的。
    • $<val>lineno = $1; 是在设置lineno文法符号的语义值，<val>是lineno文法符号的语义值类型。$<val>lineno也可以换成$<val>$。后者可以在未指定语义动作对应的文法符号名时引用该语义值单元。
    • 规则最右边的语义动作中的$<val>lineno是在引用第2个文法符号（即lineno）的语义值，这里$<val>lineno可以换成$<val>2。

  • 可以在一个翻译规则的语义动作代码中使用存储在栈中任意固定相对位置的语义值，如config/midrule.y中有如下片段：

          exp: a_1 a_2 { $<val>$ = 3; } { $<val>$ = $<val>3 + 1; } a_5
      sum_of_the_five_previous_values
      {
          USE (($1, $2, $<foo>3, $<foo>4, $5));
          printf ("%d\n", $6);
      }
      sum_of_the_five_previous_values:
      {
          $$ = $<val>0 + $<val>-1 + $<val>-2 + $<val>-3 + $<val>-4;
              }

其中，sum_of_the_five_previous_values文法符号对应的规则中$<val>0、 $<val>-1、$<val>-2、$<val>-3、$<val>-4分别表示栈中a_5、{ $<val>$ = $<val>3 + 1; }、{ $<val>$ = 3; }、a_2、a_1文法符号的语义值。

附 Bison生成的分析器源码中使用的一些表及其含义

以下内容来自Bison-2.4.1源码中src/tables.h里的注释：

YYTRANSLATE = vector mapping yylex's token numbers into bison's token numbers.

YYTNAME = vector of string-names indexed by bison token number.

YYTOKNUM = vector of yylex token numbers corresponding to entries in YYTNAME.

YYRLINE = vector of line-numbers of all rules. For yydebug printouts.

YYRHS = vector of items of all rules. This is exactly what RITEMS contains. For yydebug and for semantic parser.

YYPRHS[R] = index in YYRHS of first item for rule R.

YYR1[R] = symbol number of symbol that rule R derives.

YYR2[R] = number of symbols composing right hand side of rule R.

YYSTOS[S] = the symbol number of the symbol that leads to state S.

YYDEFACT[S] = default rule to reduce with in state s, when YYTABLE doesn't specify something else to do. Zero means the default is an error.

YYDEFGOTO[I] = default state to go to after a reduction of a rule that generates variable NTOKENS + I, except when YYTABLE specifies something else to do.

YYPACT[S] = index in YYTABLE of the portion describing state S. The lookahead token's type is used to index that portion to find out what to do. If the value in YYTABLE is positive, we shift the token and go to that state. If the value is negative, it is minus a rule number to reduce by. If the value is zero, the default action from YYDEFACT[S] is used.

YYPGOTO[I] = the index in YYTABLE of the portion describing what to do after reducing a rule that derives variable I + NTOKENS. This portion is indexed by the parser state number, S, as of before the text for this nonterminal was read. The value from YYTABLE is the state to go to if the corresponding value in YYCHECK is S.

YYTABLE = a vector filled with portions for different uses, found via YYPACT and YYPGOTO.

YYCHECK = a vector indexed in parallel with YYTABLE. It indicates, in a roundabout way, the bounds of the portion you are trying to examine. Suppose that the portion of YYTABLE starts at index P and the index to be examined within the portion is I. Then if YYCHECK[P+I] != I, I is outside the bounds of what is actually allocated, and the default (from YYDEFACT or YYDEFGOTO) should be used. Otherwise, YYTABLE[P+I] should be used.

YYFINAL = the state number of the termination state.

YYLAST ( = high) the number of the last element of YYTABLE, i.e., sizeof (YYTABLE) - 1.

results matching ""

    No results matching ""