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.

Advertisements
lex 与 yacc 学习笔记(一)

一个有关“lex 与 yacc 学习笔记(一)”的想法

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

发表评论

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