Compilers 笔记(一)

开始学习 coursera 上关于 compilers 的东西,做一些笔记留作参考。

compilers 的组件包括:lexical analysis,parsing,semantic action、optimization 与 generator。传统 compilers 实现重在前面,但是现在词法分析和语法分析都有很多现成的工具了,比如 lex/yacc 或者 boost::spirit::lex 与 boost::spirit::qi。在词法分析的时候通常使用 regex 来进行匹配,但是我们通常需要一些扩展来使得词法分析不具有歧义性(比如我们通常会定义什么是 keyword、什么是 identifier,但是这两个 RE 之间存在交集):

  • 贪婪匹配,即每次使用 RE 中能匹配最长的 input 的
  • 优先级,比如 keyword 优先级高于 identifier

那么一个好的 lexical analysis 算法应该只需要单次遍历字符串,每个字符使用的操作越少越好。通常为了实现 RE,会使用有限状态自动机(FSA),从 RE 转换到 non-deterministic FSA 比较容易(但是匹配时一般需要记住所有可能的状态),之后往往会将 non-deterministic FSA 转换成为 deterministic FSA(查表即可),这样匹配时效率会更高。

lexical analysis 将字符串的 stream 处理成为了 token 的 stream(token 就是 lexeme + token class),parser 将其 parse 成为所谓的 parse tree。这部分 parsing 需要 grammar 来协助,这引入了更为 powerful 的 context-free grammar,这时如果给出 tree 之后进行 in-order traversal 就得到了我们观察到 token stream,但是问题是我们观测到 token stream 怎么重构出 tree。这里就连最简单的语法都可能导致一些问题,比如四则运算的顺序,比如嵌套的 if-then-else,我们总可以通过一定的策略修改语法,体现出优先级(比如将 +* 分成两个 production 来描述,+ 的那个只能 handle +,但必须通过 * 的那个进去,这样就导致 * 会优先被处理;又比如 if 里面细分为 matched 和 unmatched 版本,要求 unmatched 版本的 then 从句里面只能是 matched version)。但是这样往往会将语法弄得非常的复杂,通常的工具都是建议使用带歧义的语法,然后通过一些声明来帮助 parser 找到唯一的 parse tree,比如结合律、优先级等等。

一个有意思的事情是如何实现一个 parsing 的算法,比较容易的想法是 top-down parsing。通常我们会有若干个 production,我们为每个 production 创建一个函数,如果 parsing 成功返回 true,否则返回 false,这样我们使用这个 grammar 的 parser 的时候依次调用每个 production 看是否匹配上就 ok 了,值得注意的是因为每个 production 并不注意处理完后 token 的位置,往往我们得在调用者那里保留原始的位置,这样一旦某个 production fail 就能回退。每个 production 都有几条 rule,这个 production 的实现其实也很类似,依次每个 rule 去尝试就行了,注意某些 rule 可能引用了别的 production,这样就变成了递归调用,因此我们只需要提供一些 terminal 的 parser 就能形成我们最简单的 parsing 算法。这也被称为 recursive descent parsing。这个算法要求语法不存在 left recursion,比如 X \gets X0,这样可以不断的调用自己,类似的多个 production 的互指也能导致这个情况。解决这个问题的方法是重写语法避免 left recursion。

RD parsing 的一个问题是我们可能会尝试很多次才能找到匹配的 production,为此我们希望能够用某种方式加快找到正确 rule 的,这势必会对语法产生一些限制,我们知道 RD 可能同时有几个 production 能匹配到当前 input,这是因为语法并没有要求每个 rule 读入下个输入的类型不同,为此我们引入所谓的 LL(k) 语法(left-to-right leftmost grammar),往往 k = 1(实现方便,只需要看下一个 input token)。这相当于要求每个 production/rule 匹配下一个 input token 必须是不同的,这样我们根据下一个 input token 就能选择合适的 production/rule(如果没有这个 token,说明是非法匹配)。这个算法需要向前看一个 token 做 prediction,因此叫 predicative parsing,它首先为每个 non-terminal 建立一个 table,表示输入为什么 token 时用什么 rule 来匹配,看这一个 rule 的结果就知道 parsing 是否成功了。如果用户给出的语法并不满足 LL(k),我们可以将其重写(left factor),将具有相同前缀的 rule 合并,跟上一个新的 production 处理不同的后缀即可。实现 parsing 的时候我们不再使用 recursive call,我们可以使用一个 stack 来帮助我们:我们将展开的 production 放在栈里面,每次从栈顶取一个出来,如果是 nonterminal,根据 input 就能展开成新的序列(并不消耗 input),我们将新的序列压栈;如果栈顶是 terminal,我们就跟 input 匹配,成功从栈顶拿走消耗掉对应的 input 就行了。这样如果匹配完 input 之后栈空则说明成功 parse 了。

剩下的问题其实就是如何构造一个合适的跳转表了,为此我们引入 first set 和 follower set 的概念,前者表示一个 production 其可能的第一个 input,为了求出这个 set,我们可以依次看对应 rule 第一个是否为 terminal,是的话将对应 token 加入这个 set,否则看对应的 production 的 first set,我们可以得到这些 set 的相互关系;后者我们应该观察被考虑的 production 出现在哪些 production 里面,这样我们就知道它后面可能是哪些 terminal,或者后面一个 production 的 first set。由此,我们就能确定所有的 production 的两类 set。在构造 predicative table 的时候我们对于每个 production 因为我们知道对应第一个可能出现的 token 是什么,我们只需要将对应的 rule 去掉输入 token 那部分之后放在表内即可。比较特殊的情况是如果 follower set 里面包含最后的结束符,我们需要将对应的跳转弄成空串。如果构造这个表格出现一个空可以填两个结果,往往是语法不满足 LL(k) 的限制。实际上这个限制太强,导致实际中很少有满足这个要求的 CFG,比如存在 left recursion、有歧义等等都会违背 LL(k)。

那么还有没有别的 parsing 策略呢?当然是有的!使用 top-down 的方法的核心是我们一个一个可能来试(虽然 predicative parsing 试图避免这个事情,却对语法产生了较强的约束),我们是否可以 bottom-up 的来考虑这个问题呢?top-down 的本质是在做 derivation,我们是否可以反其道而行之(称为 reduction),即读入一部分数据后(shift),通过 reduction 建立一个 parse tree 的子树(直观来说就是将 terminal 合并成为了 production),这样在后面读入新的 token 后不断的 reduce 成为更大的树,这个算法称为 shift-reduce,可以看出来我们实际上是沿着 right-most derivation 的逆过程来完成对 parse tree 的重构的!

回到实现上来看这个想法的实现过程我们可以考虑将 shift 读入的 token 放在一个 stack 上,导致我们产生 reduction 的时候相当于从栈内取出若干个 token 或者已经 reduce 过的 production 进行进一步的 reduce 并将结果放回栈内。那么现在问题就是我们是否能只通过栈顶元素就能判断当前的栈内信息能会退到 start symbol?我们称这种 reduction 为所谓的 handle,如果我们每次都能找到正确的 handle,从而就能在合适的时候调用 reduce。这种算法可能出现问题的是两种冲突:shift-reduce conflict 指某个情况下既可以选择读入更多的输入也可以选择 reduce;另一种情况称为 reduce-reduce conflict 表示同时可以做两种 reduce。那么识别 handle 的一个重要的 trick 就是需要注意到栈上的数据构成的 prefix,这对我们决定后面的处理步骤非常重要。

对于前缀的处理比较常见的做法就是构造一个 NFA,我们可以如下构造一个 NFA 来帮助我们分析 viable prefix。我们提供一个新的 start symbol,并将其指向原先的 start symbol,这个 item 作为我们的 NFA 的起点,之后我们构造 NFA 的规则如下,如果是一个 terminal 开始的 rule,就只能通过这个 token shift(移动当前位置);如果是 production 就需要在碰到它时跳到它结束的地方,或者跳到这个 production 对应展开的节点上,我们需要 NFA 的原因是我们也不知道某个 production 会如何展开,这需要 epsilon 跳转。使用这个 NFA 只要是定义过的跳转就是合法的,否则是非法的。实际使用的时候这个 NFA 需要转换成为确定性的自动机,比较简单的就是将状态的集合作为 DFA 的状态,这里 DFA 状态就被称为 LR(0) items。

一般说来下面介绍的算法能处理的语法称为 SLR grammar,它是 LALR grammar 的子集,而 LALR 又是 LR 的子集,LR 是 unambiguous grammar 的子集。这个 LR(0) 是如下利用以上的概念的:借助 DFA 处理 stack,看看当前状态是啥,如果这个 DFA 包含可用的 reduction 就使用,否则看看是否存在 shift 下一个 token t 的 item,有就按照下一个输入的 token 做 transition。这样这个算法可能存在前面讨论的一些冲突情况。为了消解这些冲突,我们可以使用所谓的 SLR(减少冲突)。我们只需要要求 reduce 的情况是要求当前的输入的确是使用的 reduction X 的 follower。这个也就是我们确定 handler 的启发式规则,如果某个语法满足我们就称其为 SLR(1) grammar。通常 SLR 不能解决比如 +* 混合具有歧义的语法,但是这种情况相当于有两个 item 满足产生 shift-reduce conflict,通过优先级就能很好的处理这种情况的语法,也就是说 precedence declaration 的本质是帮助消解冲突。

那么一些基本的改进包括,我们不必每次重新把 DFA 从头到尾过一遍,我们可以在栈里面多记录走到这里 DFA 的状态,这样万一需要 reduce,我们只需要将 DFA 从之前一个那里走一步到新入栈的 production 即可。另外一些细节包括,我们需要为 DFA 建立一个跳转表,同时定义两种 action(对应 shift 和 reduce),这个 action 我们也能做成一个 table,这是基于每个 DFA 状态和 terminal 做的,表示当前状态为 s 下一个 token 是 a 时的行为,我们知道这个很简单,如果有 shift 的 item,我们查跳转表获得下一个状态,然后调用 shift 类型的 action;否则在满足 reduction 且产生的 production 的 follower 里面包含 a 时,且这个 production 不是 S’ 时进行 reduction(最后这个条件如果不满足表示已经 parse 结束了),

有了这部分知识后,我会继续看看 dragon book 上的相关章节加以巩固。之后继续 compiler 相关的学习。

—————-
And they did eat and drink, he and the men that were with him, and tarried all night; and they rose up in the morning, and he said, Send me away to my master.

Compilers 笔记(一)

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:

lex 与 yacc 学习笔记(二)

lex 与 yacc 学习笔记(一)

前面“谴责”了一下 lex 与 yacc,不过说实在的从来没有仔细研究过这两个玩意,躺着也中枪的它们肯定很冤枉,不少指责可能是站不住脚的,为了弥补一下,这里将他们的 manual 仔细研读了一下。看看遗漏了什么重要的 feature 了没…

lex 语法

lex 的文件分为三个部分,前面的例子可以看出来一个是 %{ %} 里面的,这是一些定义或者预处理命令,之后是一段在 %% 与 %% 之间的,这是一些规则,一般是 pattern 后面加上 semantic action,最后是一些额外的代码。除此以外还有一些 %top{} 可以用来把一部分代码挪到最开始的(跟 %{ %} 的作用类似?)。pattern 部分除了 RE 一些常见用法以外,另外还支持一些 predicate,所谓的 predicate 就是一种“状态”,某些 pattern 可以导致我们进入这些状态,某些会使我们返回。lex 默认的 predicate 是 INITIAL,我们可以用 %s 或者 %x 表示一个 inclusive 或者 exclusive 的 predicate,之后我们可以用 BEGIN 进入指定的状态,我们可以在 pattern 前面使用 <> 表示对应的 predicate,对 inclusive predicate 而言,没有标 predicate 时表示 INITIAL 或者该 predicate 满足时也会匹配其他的 pattern,而 exclusive 表示没标就不会在 predicate 不满足时进行匹配(即 include 还是 exclude 那些没 predicate 的 pattern)。

lex 提供一些函数供我们操纵匹配过程中的一些问题,比如 yytext 标定的是匹配上的字符串,yyleng 表示字符串长度(关于 yytext 究竟是指针还是数组,可以用 %pointer 和 %array 控制,前者是默认的)。lex 提供了一些 action,如 ECHO、REJECT 和前面说的 BEGIN,另外 | 也算是一个 action,表示跟下一个 pattern 共用 action。除了 putchar 和 unput 之类,我们还有 yymore 要求 lex 将这次匹配上的部分保留,这样下次某个规则匹配上的结果会添加到 yytext 里面。对应还有 yyless 表示去掉几个字符放回输入。

生成的 scanner 一般是返回 int yylex(),我们可以通过 YY_DECL 重定义,这个 scanner 总是对 yyin 这个 FILE* 进行操作,我们可以将其改成别的,如文件什么的,默认是 stdin。可以用 yyrestart 设置,也可以直接赋值。默认情况下使用 YY_INPUT 定义的函数读取 yyin 的内容。

如果建立的 scanner 支持多文件,比如 cpp 就会根据 include 读取别的输入,我们就需要建立多个 buffer,并且在多个之间进行切换,比如可以用 yy_create_buffer 创建,yy_switch_to_buffer 切换,yy_delete_buffer 释放等。我们可以用 YY_CURRENT_BUFFER 拿到当前使用的。

另外我们可以用 %option 给传递一些选项,常用的包括 reentrant 产生 reentrant parser,noxxxx 可以去掉一些不用的函数,outfile 和 header-file 可以指定输出文件。

虽说 lex 对 C++ 有一定的支持,但没用什么简化的东西。所谓 reentrant parser 主要是把 scanner 本身移到一个结构中,然后调用 yylex 传递 scanner 让不同的线程能互相不干扰。

最后小小的解释一下 yylex 干的事情,它从给定的 FILE* 读出字符,根据正则表达式规则进行匹配,匹配上后执行一些 action,这些 action 可以返回(表示 lexer 找到的 token 类型),也可以继续(如果我们只是简单的做一些词法分析就结束的话)。理想情况下进入 lexer 的是字符流,进入 parser 的是 token 流。下面是一个简单的 word count 的 lexer,这里由于我们不需要返回(计数就行了),所以调用 yylex() 之后并不会在文件结束前返回,而会一直执行到最后。

%{
extern int w, c, l ;
%}
%%
[^ \t\n]+  {++ w ; c+= yyleng ;}
\n         {++ l ; ++ c ;}
.          {++ c ;}
%%

这是驱动对应 lexer 的程序

#include <stdio.h>
int yylex () ;
int w, c, l ;

int
main (int argc, char* argv[]) {
  yylex () ;
  printf ("%d %d %d\n", l, w, c) ;
  return 0 ;
}

如果需要根据 yylex 解析出来的 token 类型来做,我们就需要额外定义一些东西,注意这个地方最好是将值设为大于 255,这样对某些情况(如 lexer 仅仅把一部分字符处理为 token,剩下的交给 parser 处理的时候),前面的字符可能还需要也被 yylex 返回,具有更好的兼容性。那么这时如果没有 yacc 产生的 token 编号,我们就得自己来

#ifndef WC_SIMPLE_H
#define WC_SIMPLE_H

#define ID_WORD 1000
#define ID_EOL  1001
#define ID_CHAR 1002

#endif

然后把规则稍微改一下

%{
#include "wc-simple.h"
%}
%%
[^ \t\n]+  { return ID_WORD ;}
\n         { return ID_EOL  ;}
.          { return ID_CHAR ;}
%%

这样就把数数这部分交给驱动来做了

#include <stdio.h>
#include "wc-simple.h"

int c = 0, w = 0, l = 0 ;

int yylex () ;
extern int yyleng ;

int
count (int tok) {
  switch (tok) {
  case ID_WORD:
    ++ w ; c += yyleng; break ;
  case ID_EOL:
    ++ l ; ++ c ; break ;
  case ID_CHAR:
    ++c ; break ;
  default:
    return 0 ;
  }
  return 1 ;
}

int
main (int argc, char** argv) {
  int tok = EOF ;
  do {
    tok = yylex () ;
    if (!count (tok))
      break ;
  } while (EOF != tok) ;
  printf ("%d %d %d\n", l, w, c) ;

  return 0 ;
}

lex 与 yacc 的接口

事实上,yacc 干活就是建立在 lex 的抽象上,它会 poll 这个 yylex 函数,获得 token 或者一般字符,直到返回 0 表示没有输入。当然我们可以手工写一些实现 yylex,但是既然有了 lex 我们又何必自己跟自己过不去呢?下面我们写一个简单的 reverse Polish 计算器,即使用后缀表达式的计算器,首先定义 CFG(context free grammar)

%{
#define YYSTYPE double
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

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

%token NUM

%%

input:

  | input line
  ;

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

exp:
    NUM         {$$ = atof (yytext) ;}
  | exp exp '+' {$$ = $1 + $2 ;}
  | exp exp '-' {$$ = $1 - $2 ;}
  | exp exp '*' {$$ = $1 * $2 ;}
  | exp exp '/' {$$ = $1 / $2 ;}
  | exp exp '^' {$$ = pow ($1, $2) ;}
  | exp 'n'     {$$ = -$1 ;}
  ;

%%

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

这里我们定义了一个 token,其实 token 也就是 CFG 里面的 terminal,位于 parse tree 最末端的组成成分,这里仅仅包括数字,我们假定使用 lex 解决这个问题,那么这时候 NUM 就需要对应一个编号,我们可以用 bison -d 在生成的 parser 实现(.c 文件)的同时也生成一个头文件(.h)。这个头文件可以被 lex 的源文件所包含

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

%%

[0-9]+        {return NUM ;}
[ \t]         /* ignore */
.             {return *yytext ;}
\n            {return '\n' ;}
<<EOF>>       {return 0;}

%%

这里稍微注意一点的是,我们仅仅简单的忽略空格和 tab,对换行我们也直接返回,这样便于 parser 里面的规则匹配上,否则,我们也需要为每个这些东西给与一个新的 token id。. 这条规则不能包含 \n 那条。

之后我们的驱动程序就可以直接调用 yyparse,而 yyparse 就会调用 yylex 分析构造语法树,最后产生结果。下面是我们的驱动程序

#include "rpcalc-parser.h"

int
main (int argc, char* argv[]) {
  return yyparse () ;
}

下面是执行结果

$ cat rpcalc.txt
1 1 +
3 2 -
3 2 * 5 -
3 2 5 * -
$ cat rpcalc.txt | ./rpcalc 
        =2
        =1
        =1
        =-7

有兴趣的话,可以把 NUM 的规则写的更完善一点,让他能解析浮点数。

——————
And when the morning arose, then the angels hastened Lot, saying, Arise, take your wife, and your two daughters, which are here; lest you be consumed in the iniquity of the city.

lex 与 yacc 学习笔记(一)