lex 与 yacc 学习笔记(二)

yacc 语法

前面的例子我们能看出和 lex 类似,我们首先有个 prologue 段,用来引入需要的头文件,定义需要的东西,这会原封不动的放在生成的 .c 文件中,然后在 %} 结束后是一段定义 token 的区域,这部分还可以表达结合律(使用 %left、%right 表示结合的优先顺序),按照书写的前后表示优先(后面的优先),之后 %% 之间的区域是表示 CFG 的区域,它是一些 rule,每条 rule 包括一个 head(: 之前),以及 body(使用 | 分割的,称为 product)。最后用 %% 分割的部分和 lex 一样是放一些程序,会插入到最后。

yacc 的 prologue 比 lex 复杂很多,这是因为 yacc 有时为了存放计算结果会使用 %union 声明一个 union 供后面的程序使用。这样就引入了各个 prologue 表意上的区别,一般分为 %code top、%code requires,%code provides 与 %code 分别表示放在最前面的部分(include 系统头文件、定义宏)、依赖的东西(include 自定义的头文件,可能 union 中会使用,定义的结构,定义 YYSTYPE 或者 YYLTYPE 会使用到东西,一切应该进入 implementation 的东西)、提供的东西(函数前向声明,一切还应该进入 header 的东西)和其他一些东西。

匹配规则包括 symbol(用引号表示的)、terminal 表示 token 或者 nonterminal,我们除了可以用 %token <> 表示一些 token 与 union 中哪些部分对应,%type <> 表示一些 nonterminal 的 type,YYSTYPE 表示的是 semantic action 对应的类型,比较常见的就是类似前面例子中的 double,同时也可以用自定义的一些 union(不止一种 type),这时我们需要 #define 对应的 YYSTYPE。为了在 semantic action 里面表示匹配上部分的值,除了利用 $n 这种靠位置来的标记,还可以在匹配上的部分后面用中括号跟一个名字,这样就能用 $name 表示。如果使用 $0 或者负数,则表示在 stack 里面前面的某些值(比如某个空的 expr 可以用 $0 表示前面某个 rule 匹配到的值)。可以在 $n 之间插入 <> 表示 union 中某个 type。

某些情况下我们希望在匹配的 pattern 当中插入一些 semantic action,可以直接在打断的 patten 之间插入 {} 代码段,为了给某些 mid-rule 的 action 提供 destructor,我们只能借助 yacc 提供的 nonterminal 的 destructor,这是通过 %type 声明后,再接上 %destructor {…} nonterminal-name 添加析构。这样一旦通过这部分 pattern 成功构造了某些结构,而在随后的 pattern 里面 parsing fail 了,我们就能自动的调用析构。另外一种方式是使用 nonterminal 自己的名字来 refer,比如 exp 就能用 $exp 来获得对应的值,但在有歧义的时候不能这么用。

为了在 parsing 的同时维护当前 parsing 的位置,我们需要 YYLTYPE 这个结构,我们可以自定义,但是需要提供 first_line、first_column、last_line 和 last_column 等成员,并且在 parsing 的过程中更新这些值(对象名为 yylloc)。对应的结构我们可以用 @ 开头和前面 $ 类似的一些变量来记录对应的值,如 @$ 就合 $$ 类似,后者表示当前 production 的值,那么前者就是解析这个 production 对应的 yylloc,为此,我们可以用 @$.first_line 等类似的值更新位置信息,这样一旦出错就能显示哪些地方出错了。作为一个例子,下面是对原计算器的改进版本

%{
#include "ltcalc-parser.h"
%}

external YYLTYPE yylloc ;
%%

[0-9]*(\.[0-9]*)?(e[+-]?[0-9]+)? {
                                    yylloc.first_column = yylloc.last_column ;
                                    yylloc.last_column += yyleng ;
                                    return NUM ;
                                 }
[ \t]                            {
                                    yylloc.first_column = yylloc.last_column ;
                                    ++ yylloc.last_column ;
                                 }
.                                {
                                    yylloc.first_column = yylloc.last_column ;
                                    ++ yylloc.last_column ;
                                    return *yytext ;
                                 }
\n                               {
                                    ++ yylloc.last_line ;
                                    ++ yylloc.first_line ;
                                    yylloc.first_column = 0 ;
                                    yylloc.last_column = 0 ;
                                    return '\n' ;
                                 }
<>                          {return 0;}

%%

对应的 parser 可以这样写

%{
#define YYSTYPE double
#include
#include
#include

extern char* yytext ;
int yylex () ;
void yyerror (const char*) ;
%}

%token NUM
%left '-' '+'
%left '*' '/'
%left NEG
%right '^'

%%

input:

  | input line
  ;

line:
    '\n'
  | exp '\n'    {printf ("\t=%.10g\n", $1) ;}
  ;

exp:
    NUM                {$$ = atof (yytext) ;}
  | exp '+' exp        {$$ = $1 + $3 ;}
  | exp '-' exp        {$$ = $1 - $3 ;}
  | exp '*' exp        {$$ = $1 * $3 ;}
  | exp '/' exp        {
                         if ($3)
                           $$ = $1 / $3 ;
                         else {
                           $$ = $1 ;
                           fprintf (stderr, "%d.%d-%d.%d: division by zero",
                                    @3.first_line, @3.first_column,
                                    @3.last_line, @3.last_column) ;
                         }
                       }
  | exp '^' exp        {$$ = pow ($1, $3) ;}
  | '-' exp %prec NEG  {$$ = -$1 ;}
  | '(' exp ')'        {$$ = $2 ;}
  ;

%%

void
yyerror (const char* s) {
  fprintf (stderr, "%s\n", s) ;
}

还有一种办法传递这些信息是在 lexer 里面通过 %option bison-locations 传递 yylloc_param(这是个指针),然后类似的更新。觉得似乎还不如这样快捷 -,-b

bison 可以用 % 加上一些别的东西,比如 %require 可以要求使用的 bison 版本满足某个条件,前面也看见了 %left、%right 表示的结合律结合的顺序,也可以用 %nonassoc 表示不满足结合律,%type 为 nonterminal 指明类型,%start 表示 start symbol,通过 %locations 可以打开对 yylloc 的支持(默认如果发现使用了相关的变量也会打开)。

yacc 的 C 语言接口

yyparse 是主要的函数,返回 0 表示 parsing 成功。通常我们使用 YYACCEPT 和 YYABORT 这两个宏。如果希望给 yyparse 增加参数可以使用 %parse-param 增加。通过 yyerror 产生出错信息

其他

bison 提供了 C++ 的接口,这时 parser 被封装成一个类 parser,YYSTYPE 变成了 yy::parser::semantic_type,location tracking 方面变得简单,直接调用一些成员函数即可,其中 parse() 成员函数用来执行 parse。后面我们会比较一下 yacc 和 spirit::qi 实现的差异和优缺点。

——————-
And Lot said to them, Oh, not so, my LORD:

Advertisements
lex 与 yacc 学习笔记(二)

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s