多读书多实践，勤思考善领悟

高效解析器 Lex&YACC(Flex&Bison) 使用教程

后端 c c++ lex yacc 2023/05/27

本文于416天之前发表，文中内容可能已经过时。

一、简介

只要在Unix环境中写程序，必定会邂逅神秘的Lex&YACC，就如GNU/Linux用户所熟知的Flex&Bison，这里的Flex就是由Vern Paxon实现的一个Lex，Bison则是GNU版本的YACC。在此我们将统一称呼这些程序为Lex和YACC。新版本的程序是向上兼容的(译注：即兼容老版本)，所以你可以用Flex和Bison来尝试下我们的实例。

这些程序实用性极广，但如同你的C编译器一样，在其主页上并没有描述它们，也没有关于怎样使用的信息。当和Lex结合使用时，YACC实在是棒极了，但是Bison的主页上并没有描述Bison如何跟Lex结合使用以生成代码的相应说明。

二、Lex & YACC能为你做什么？

如果使用得当，这些程序(指LEX&YACC)可以让你轻易的解析复杂的语言，当你需要读取一个配置文件时，或者你需要编写一个你自己使用的语言的编译器时，这对于你来说是莫大的裨益。
本文档能提供给你一些帮助，你将发现你再也不用手工写解析器了，Lex & YACC就是为你量身打造的利器。

先来看一个示例，简单计算器：

2.1 简单计算器

计算器实现整数的 +、-、*、/、% 五种简单运算。

1. 词法分析程序 cal.l

1
2
3
4
5
6
7
8
9
10
11
%{
#include "cal.tab.h"
extern int yylval;
%}

%%
[0-9]+  { yylval = atoi(yytext); return NUMBER; }
[ \t]   ;       /* ignore white space */
\n  return 0;   /* logical EOF */
.   return yytext[0];
%%

代码中定义了四条规则，前面的部分就是模式，处于一行的开始位置，后面部分是动作，也就是，输入中匹配到了这个模式的时候，对应进行什么动作（就像机器人接受到了什么样的指令，然后会执行相应的动作一样）

  • 第一个模式，匹配连续一个或者多个数字，匹配到之后就返回标签NUMBER。
  • 第二个模式，匹配空格，没有任何操作，忽略所有空格。
  • 第三个模式，匹配一个换行符，匹配到之后结束匹配。
  • 第四个模式，匹配出了\n之外的字符，返回该字符。

总体来说，匹配到连续数字，则返回NUMBER；忽略空格；换行结束；匹配到任何其他字符返回字符。

2. 语法分析程序 cal.y

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
%{
#include <stdio.h>
int yylex(void);
%}
%token NAME NUMBER
%%
statement:  NAME '=' expression
    |   expression      { printf("= %d\n", $1); }
    ;

expression: expression '+' NUMBER   { $$ = $1 + $3; }
    |   expression '-' NUMBER   { $$ = $1 - $3; }
    |   expression '*' NUMBER   { $$ = $1 * $3; }
    |   expression '/' NUMBER   { $$ = $1 / $3; }
    |   expression '%' NUMBER   { $$ = $1 % $3; }
    |   NUMBER          { $$ = $1; }
    ;
%%
int main()
{
    yyparse();
    return 0;
}

int yyerror(char *s)
{
    printf("%s/n",s);
    return 0;
}

int yywrap() 
{ 
   return 1;
}

3. 编译运行过程

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 1.  编译lex文件，生成lex.yy.c文件 */
C:\flex>flex cal.l

/* 2. 编译yacc文件，生成cal.tab.h 与cal.tab.c文件 */
C:\flex>bison -d cal.y

/* 3. 链接生成的.c 文件，并生成相应的可执行文件 cal */
C:\flex>gcc -o cal cal.tab.c lex.yy.c

/* 4. 运行可执行文件cal，计算简单表达式  */
C:\flex>cal
32*10-20+150/3
= 150

三、Lex

Lex会生成一个叫做『词法分析器』的程序。这是一个函数，它带有一个字符流传入参数，词法分析器函数看到一组字符就会去匹配一个关键字(key)，采取相应措施。

3.1 Lex 的结构规范

lex源文件扩展名.l，分为三个段：定义段、规则段、用户子程序段

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 定义段 */
%{
...
%}
...

%%
    /* 规则段 */
...

%%
    /* 用户子程序段 */
...

三个段用 %% 进行分隔。

1. 定义段

定义段包括文字块、定义、内部表声明、起始条件和转换。
C语言的注释、头文件包含等一般就放在%{  %}之间，这一部分的内容会被直接复制到输出文件的开头部分。
例如：

1
2
3
4
%{
#include "cal.tab.h"
extern int yylval;
%}

2. 规则段

规则段为一系列匹配模式和动作，模式一般使用正则表达式书写，动作部分为C代码：

1
2
3
4
模式1 {动作1 （C代码）}

例如：
[0-9]+  { yylval = atoi(yytext); return NUMBER; }

在输入和模式1匹配的时候，执行动作部分的代码。
C代码被逐字拷贝到生成的C文件中。

当lex扫描程序运行时，它把输入与规则段的模式进行匹配。
➢ 每次发现一个匹配（被匹配的输入称为标记（token））时就执行与那种模式相关的C代码。
➢ 如果模式后面跟着 | 符号，则该模式将使用与文件中下一个模式相同的C代码。
➢ 当输入字符不匹配模式时，词法分析程序的动作就好像它匹配上了代码ECHO的模式，ECHO将标记的拷贝写到输出。

3. 用户子程序段

这里为C代码，会被原样复制到c文件中，一般这里定义一些辅助函数等，如动作代码中使用到的辅助函数。
如果重新定义input()、unput()、output()、或者yywrap()，新的版本或者支持子程序，都可以放在这里。

词法分析器所做的，就是在输入中寻找字符的模式（pattern）。
在词法分析器中，我们要给定我们需要识别的模式，因此需要使用一种方式来描述模式，这就是常用的正则表达式。

3.2 Lex的常规表达式

lex模式是由编辑程序和实用程序使用的正则表达式的扩展版本。正则表达式由常规字符（代表它们本身）和元字符（在一种模式中具有特殊含义）组成。

1. 用 Lex 定义常规表达式

字符 含义
A-Z, 0-9, a-z 构成了部分模式的字符和数字。
. 匹配任意字符，除了 \n。
- 用来指定范围。例如：A-Z 指从 A 到 Z 之间的所有字符。
[ ] 一个字符集合。匹配括号内的 任意 字符。如果第一个字符是 ^ 那么它表示否定模式。例如: [abC] 匹配 a, b, 和 C中的任何一个。
* 匹配 0个或者多个上述的模式。
+ 匹配 1个或者多个上述模式。
? 匹配 0个或1个上述模式。
$ 作为模式的最后一个字符匹配一行的结尾。
{ } 指出一个模式可能出现的次数。 例如: A{1,3} 表示 A 可能出现1次或3次。
\ 用来转义元字符。同样用来覆盖字符在此表中定义的特殊意义，只取字符的本意。
^ 否定。
| 表达式间的逻辑或。
“<一些符号>” 字符的字面含义。元字符具有。
/ 向前匹配。如果在匹配的模版中的“/”后跟有后续表达式，只匹配模版中“/”前 面的部分。如：如果输入 A01，那么在模版 A0/1 中的 A0 是匹配的。
( ) 将一系列常规表达式分组。

下面将逐一详细讲解;

元字符

➢ .
. 匹配除了换行符 \n 之外的任意单个字符
例如

1
.   return yytext[0];

➢ []
[] 匹配括号中字符的任意一个。
用“-”（短划线）指示字符的范围，例如[0-9]指10个数字中的任意一个。
如果开括号之后的第一个字符是短划线或者闭括号，那么它就不能被解释为元字符。
如果第一个字符是抑扬字符“ ^ ”，那么它的含义就变为匹配括号内字符以外的任意字符。
除了以“ \ ”开始的C转义序列被识别以外，其他的元字符在方括号中没有特殊含义。\

例如

1
2
[A-Z]+  {printf("get word:%s\n", yytext);} // 匹配大写字母，出现1次以上
[^A-Z]+  {printf("get word:%s\n", yytext);} // 匹配除了大写字母外的其他字符，出现1次以上

➢ *
* 匹配前面正则表达式的零次或者多次出现。

例如

1
[A-Z]*  {printf("get word:%s\n", yytext);} // 匹配大写字母，出现0次或者多次

➢ +
+ 匹配前面正则表达式的一次或者多次出现。

例如

1
[A-Z]+  {printf("get word:%s\n", yytext);}// 匹配大写字母，出现1次以上

➢ ?
? 匹配前面正则表达式的零次或者一次出现。例如： -?[0-9]+ 指具有可选的前导或者一元减号的数字

例如

1
[A-Z]?  {printf("get word:%s\n", yytext);} // 匹配大写字母，出现零次或者一次

➢ {}
{} 意味着根据括号内部的不同而不同。单个数字{n}意味着前面的模式重复n次。例如： [A-Z]{3} 表示任意3个大写字母。

如果大括号包含的由逗号分开的两个数字{n,m}，那么它们是前面模式重复的最小数和最大数。例如：A{1,3}表示字母A出现1次到3次。

如果第二个数字丢失就意味着无穷大，所以{1，}意味着 + ； {0，}意味着 * 。

如果大括号包含一个名字，它指示用那个名字来替换。

例如

1
2
3
[A-Z]{3}  {printf("get word:%s\n", yytext);} // 匹配大写字母，出现3次
[A-Z]{3,}  {printf("get word:%s\n", yytext);} // 匹配大写字母，出现3次以上
[A-Z]{3,6}  {printf("get word:%s\n", yytext);} // 匹配大写字母，出现3~6次

➢ \
\ 转义符号，如果后面的字符是小写字母，那么它就是C转义序列。 例如制表位：\t

一些实现允许采用如“\123” 和 “\x3f” 这种形式的八进制和十六进制字符。

否则，“\” 引用后面的字符，所以 * 匹配一个 * 号。

转义字符表\

转义字符 意义 ASCII码值（十进制）
\a 响铃(BEL) 007
\b 退格(BS) ，将当前位置移到前一列 008
\f 换页(FF)，将当前位置移到下页开头 012
\n 换行(LF) ，将当前位置移到下一行开头 010
\r 回车(CR) ，将当前位置移到本行开头 013
\t 水平制表(HT) （跳到下一个TAB位置） 009
\v 垂直制表(VT) 011
\ 代表一个反斜线字符’\’ 092
\’ 代表一个单引号（撇号）字符 039
\” 代表一个双引号字符 034
\? 代表一个问号 063
\0 空字符(NULL) 000
\ddd 1到3位八进制数所代表的任意字符 三位八进制
\xhh 1到2位十六进制所代表的任意字符 二位十六进制

➢ ()
() 将一系列正则表达式归组。 * + {} 中的每一个都直接作用于它左侧的表达式，而且 | 通常同时影响左侧和右侧的内容。圆括号可以改变这种情况，

例如：

1
2
(abc){3}  {printf("get word:%s\n", yytext);} // 连续出现3次 abc
(ab|cd){3}  {printf("get word:%s\n", yytext);} // 出现3次："ab" 或 "cd"

➢ |
| 匹配前面的或者随后的表达式。
例如：

1
(ab|cd){1}  {printf("get word:%s\n", yytext);} // 出现1次："ab"或 "cd"

➢ “…”
“…” 逐字匹配引号内的每个字符。不同于“\”的元字符会失去它的含义。
和 () 不同的是，引号内的都是普通字符，没有特殊含义。

例如：“/” 匹配两个字符 /

1
2
(\\){1}  {printf("get word:%s\n", yytext);} // 出现1次："\"
"\\"{1}  {printf("get word:%s\n", yytext);} // 出现1次："\\"

➢ /
/ 只有当有后面的表达式跟随时才匹配前面的表达式。

例如： 0/1 匹配字符串01中的0 但是不匹配字符串0或者02中的任何字符。

每个模式只允许有一个/ ，并且模式不能同时包含 / 和 $

➢ ^
^作为正则表达式的第一个字符，它匹配行的开始；
^在方括号[] 中用于否定。

1
2
^[A-Z]* {printf("get word:%s\n", yytext);} // 行开始的所有大写字母串
[^A-Z]*  {printf("get word:%s\n", yytext);} // 匹配非大写字母的字符串

➢ $
$作为正则表达式的最后一个字符，它匹配行的结束

1
[A-Z]*$ {printf("get word:%s\n", yytext);} // 行末尾的大写字母串

➢ <>
<> 位于模式开头的尖括号内的一个或者一列名字，使那个模式只应用于指定的起始状态。
匹配词（word）的开始（<）和结束（>）。例如正则表达式<the>能够匹配字符串”for the wise”中的”the”，但是不能匹配字符串”otherwise”中的”the”。

➢ <<EOF>>
<<EOF>> 只用于flex中，这个特殊模式匹配文件的结尾。

2. 常规表达式举例

常规表达式 含义
joke[rs] 匹配 jokes 或 joker。
A{1,2}shis+ 匹配 AAshis, Ashis, AAshi, Ashi。
(A[b-e])+ 匹配在 A 出现位置后跟随的从 b 到 e 的所有字符中的 0 个或 1个。

3. 标记声明举例

标记 相关表达式 含义
数字(number) ([0-9])+ 1个或多个数字
字符(chars) [A-Za-z] 任意字符
空格(blank) “ “ 一个空格
字(word) (chars)+ 1个或多个 chars
变量(variable) (字符)+(数字)(字符)(数字)*  

3.3 简单示例

一个非常简单的例子(example1)如下:

1
2
3
4
5
6
7
%{
#include <stdio.h>
%}
%%
stop printf("Stop command received\n");
start printf("Start command received\n");
%%

第一部分，位于%{和%}对之间直接包含了输出程序(stdio.h)。我们需要这个程序，因为使用了printf函数，它在stdio.h中定义。

第二部分用’%%’分割开来，所以第二行起始于’stop’，一旦在输入参数中遇到了’stop’，接下来的那一行(printf()调用)将被执行。

除此之外，还有’start’，其跟stop的行为差不多。

我们再次用’%%’结束代码段。

为了编译上面的例子，只需要执行以下命令：

1
2
lex example1.l
cc lex.yy.c -o example -ll

flex，执行以下命令：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
C:\flex>flex example1.l

C:\flex>gcc lex.yy.c -o example -L C:\Qt\GnuWin32\lib -lfl

C:\flex>example
aa
aa
stop
Stop command received

start
Start command received

^Z

注意：如果你用flex，则就将lex命令用flex代替，还需要将’-ll’选项改成’-lfl’。在RedHat 6.x以及SuSe中需要这样做。

这样，Lex将生成’example1’这个文件。运行该文件，它将等待你输入一些数据。每次你输入一些不匹配的命令(非’stop’和’start’)，它会将你输入的字符再次输出。你若输入’stop’，它将输出’Stop command received’。

用一个EOF(^D)来结束程序。

也许你想知道，它是怎么运行的，因为我们并没有定义main()函数。这个函数(指main())已经在lib1(liblex)中定义好了，在此我们选用了编译选项’-ll’

3.4 匹配中的正则表达式示例

这个实例(example2)本身并没什么用处，下一个实例也不会提及正则表达式。但这里它展示了如何在Lex中使用正则表达式，这在后面将非常有用。

1
2
3
4
5
6
7
%{
#include <stdio.h>
%}

%%
[0123456789]+ printf("NUMBER\n");
[a-zA-Z][a-zA-Z0-9]* printf("WORD\n");

该Lex文件描述了两种token匹配：WORDs和NUMBERs。正则表达式非常恐怖，但是只需要稍花力气便可以加以理解。

其中NUMBER匹配“[0123456789]+”可以写成“[0-9]+”。

WORD匹配就有点复杂：[a-zA-Z][a-zA-Z0-9]*

第一部分仅仅匹配一个’a’到’z’或’A’到’Z’之间的字符，也即一个字母。接着该字母后面需要连上0个或多个字符，这些字符可以是字母，也可以是数字。这里为何用’’? ’+’表示至少1次的匹配。一个WORD只有一个字符也可以很好的匹配，在第一部分我们已经匹配到了一个字符，所以第二部分可以是0个匹配，所以用’’。

用这种方式，我们就模仿了很多编程语言中对于一个变量名的要求，即要求变量名『必须』以字母开头，但是可以在后续字符中用数字。也就是说’temperature1’是一个正确的命名，但是’1temperature’就不是。

像example1一样编译example2，并输入一些文本，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$ ./example2
foo
WORD

bar
WORD

123
NUMBER

bar123
WORD

123bar
NUMBER
WORD

你也许会疑惑，所有的输出中的空格是从哪来的？理由很简单：从输入而来，我们不在空格上匹配任何内容，所以它们又输出来了。

Flex主页上有正则表达式的详细文档。很多人觉得perl正则表达式主页的说明非常有用，但是Flex并不实现perl所实现的所有东西。

你只需要确保不写一些形如’[0-9]*’的空匹配即可，你的词法分析器(由Flex生成)将不明就里的开始不断的匹配空字符。

3.5 复杂一点的类C语法示例

假定我们需要解析一个形如下面的文件：

1
2
3
4
5
6
7
8
9
logging{
category lame-servers { null; };
category cname { null; };
};

zone "." {
type hint;
file "/etc/bind/db.root";
}

我们在此见到了很多token：

  • WORD: 如’zone’和’type’
  • FILENAME：如“/etc/bind/db.root”
  • QUOTE: 如包含文件名的引号
  • OBRACE：{
  • EBRACE: }
  • SEMICOLON: ;

example3相应的Lex文件如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
%{
#include <stdio.h>
%}

%%
[a-zA-Z][a-zA-Z0-9]* printf("WORD ");
[a-zA-Z0-9\/.-]+ printf("FILENAME ");
\" printf("QUOTE ");
\{ printf("OBRACE ");
\} printf("EBRACE ");
; printf("SEMICOLON ");
\n printf("\n");
[ \t]+ /* ignore whitespace */;
%%

当输入我们的文件到Lex生成的example3中，我们得到：

1
2
3
4
5
6
7
8
WORD OBRACE
WORD FILENAME OBRACE WORD SEMICOLON EBRACE SEMICOLON
WORD WORD OBRACE WORD SEMICOLON EBRACE SEMICOLON
EBRACE SEMICOLON
WORD QUOTE FILENAME QUOTE OBRACE
WORD WORD SEMICOLON
WORD QUOTE FILENAME QUOTE SEMICOLON
EBRACE SEMICOLON

3. 6 Lex深入学习

.l文件 的结构

1
2
3
4
5
Definition section(定义段)
%%
Rules section（规则段）
%%
C code section （用户子程序段）

下面以一个单词统计程序详细说明。

1. Definition Section(定义段)

这块可以放C语言的各种各种include，define等声明语句，但是要用%{ %}括起来。
可以放预定义的正则表达式：minus “-” 还要放token的定义，方法是：代号 正则表达式。然后到了规则段就可以通过{代号} 来引用正则表达式

1
2
3
4
5
6
7
8
9
10
11
%{
#include <stdio.h> // include
int wordCount = 0;  // 定义全局变量 单词计数器
%}
// 预定义代号表
chars [A-za-z\_\'\.\"]
numbers ([0-9])+
delim [" "\n\t]
whitespace {delim}+  // 使用前面的代号 来 定义代号
words {chars}+  // 使用前面的代号 来 定义代号
%%

2. Rules section（规则段）

在这里放置的rules就是每个正则表达式要对应的动作，一般是返回一个token
这里的动作都是用{}扩起来的，用C语言来描述，这些代码可以做你任何想要做的事情

1
2
3
4
{words} { wordCount++; /* wordCount 加1 */ }
{whitespace} { /* 空白，什么也不做*/ }
{numbers} { /* 这里可以加入如果遇到数字的处理逻辑*/ }
%%

3. C code section （用户子程序段）

Lex 编程的第三段，也就是最后一段覆盖了 C 的函数声明（有时是主函数）。注意这一段必须包括 yywrap() 函数。 Lex 有一套可供使用的函数和变量。 其中之一就是 yywrap。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* main函数 */
void main()
{
    yylex(); //这一函数开始分析。 它由 Lex 自动生成。
    printf(" No of words: %d\n", wordCount);
}

/*这一函数在文件（或输入）的末尾调用。 如果函数的返回值是1，就停止解析。
 因此它可以用来解析多个文件。 代码可以写在第三段，这就能够解析多个文件。
 方法是使用 yyin 文件指针指向不同的文件，直到所有的文件都被解析。 
 最后，yywrap() 可以返回 1 来表示解析的结束。*/
int yywrap()
{
    return 1;
}

4.编译运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
c:\>flex wordcount.l 

c:\>gcc -o wordcount lex.yy.c

c:\>wordcount
yes
12
but
---99
---
^Z
 No of words: 2

c:\>wordcount < text.txt  #运行程序，将输入流重定向为要分析的文件
------ No of words: 2

5. 常用的全局变量和宏

lex.yy.c中，有很多全局变量、函数、宏。这里之处部分最常用的

FILE *yyin:
FILE *yyout： 这是Lex中本身已定义的输入和输出文件指针。这两个变量指明了lex生成的词法分析器从哪里获得输入和输出到哪里。默认：键盘输入，屏幕输出。

char *yytext：指向当前识别的词法单元（词文）的指针

int yyleng：当前词法单元的长度。

yylineno 提供当前的行数信息。（lexer不一定支持。）

ECHO：Lex中预定义的宏，可以出现在动作中，相当于fprintf(yyout, “%s”,yytext)，即输出当前匹配的词法单元。

REJECT： 指示简析器对当前规则不做处理，而是采用第二匹配规则。
因为解析器在通常情况下，每个被匹配的对象只会对一个动作生效。REJECT指示解析器，会寻找下一个最配的规则来做处理。下面的规则会把输入的”abcd”处理后输出”abcd|abc|ab|a|abcd”。

1
2
3
4
5
6
> a |
> ab |
> abc |
> abcd {ECHO;printf("|");REJECT;}
> %%
>

BEGIN 开始一个条件处理块

int yylex()：词法分析器驱动程序，用Lex翻译器生成的lex.yy.c内必然含有这个函数。它自动移动文件指针
yyin 和 yyout 。
在定义模式动作时，可以用 return 语句来结束 yylex分析函数。return 需要返回一个整数。
由于 yylex() 函数的运行环境都是以全局变量的方式来保存，因此在下一次调用 yylex() 时，yylex()可以从上次扫描的断点处继续扫描。若用户未定义相应的return语句，则yylex()继续分析被扫描的文件，直到碰到文件结束标识符EOF。
在读取到EOF时，yylex() 函数调用 int yywrap() 函数，若yywrap()返回非0值，则yylex() 函数结束返回0；否则，yylex()继续对yyin指向的文件扫描。

int yywrap()：词法分析器遇到文件结尾时会调用yywrap()来决定下一步怎么做：
若yywrap()返回0，则继续扫描
若返回1，则返回报告文件结尾的0标记。
由于词法分析器总会调用yywrap，因此辅助函数中最好提供yywrap，如果不提供，则在用C编译器编译lex.yy.c时，需要链接相应的库，库中会给出标准的yywrap函数（标准函数返回1）。

yymore()这一函数告诉 Lexer 将下一个标记附加到当前标记后。
`yymore()’ 告诉解析器下一次匹配的规则，满足的部分将会添加到当前yytext值得后面而不是替换它。 例如，指定的输入”mega-kludge”经过下面的程序处理后将会输出”mega-mega-kludge”。

1
2
3
4
>%%
> mega- ECHO; yymore();
> kludge ECHO;/* 这时，yytext的值为mega-kludge */
>

yyless(int n) 返回当前匹配项除了开始的n个字符内的所有的内容到输入缓存区，解析器处理下一个匹配时，它们将会被重新解析。yyless将会导致yytext与yyleng的调整。（yyleng将会等于=n） 如输入”createtable”被下面的程序处理后，将会输出”createtableatetable”. 因为前n=3个字符foo外的字符atetable被重新返回到输入缓存区，再次解析。

1
2
3
4
5
>createtable ECHO; yyless(3);
> [a-zA-Z]+ ECHO;
>\n return 0;
> %%
>

unput(c) 将字符c放回到输入流中，该字符可以重新被解析。下面的动作将当前的匹配值附上括号后重新进行匹配。

1
2
3
4
5
6
7
8
9
10
11
>{
> int i;
>/* Copy yytext because unput() trashes yytext */
> char *yycopy = strdup( yytext );
>unput( ')' );
> for ( i = yyleng - 1; i >= 0; --i )
> unput( yycopy[i] );
> unput( '(' );
> free( yycopy );
> }
>

注意: 由于每次unput()将指定的字符添加到输入源的开头，所以将字符串添加到输入源开头必须从后道前处理。一个比较重要的潜在问题是使用unput()的时候，如果采用了%pointer指针模式保存yytext,unput会破坏yytext的内容，从最右边的字符开始将会破坏左边的一个字符。如果在unput()后要用到yytext,你首先必须复制一份yytext,或者用%array模式来保存yytext. 最后不能尝试放一个EOF标志输入流的结束。

input() 从输入源中读取下一个字符。
下面例子将会吃掉C语言注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
> %%
>"/*" {
>  register int c;
>  for ( ; ; ) {
>   while ( (c = input()) != '*' &&>c != EOF ); /* eat up text of comment */
>    if ( c == '*' ) {
>     while ( (c = input()) == '*' );
>      if ( c == '/' ) break; /* found the end */
>    }
>    if ( c == EOF ) {
>      error( "EOF in comment" );
>      break;
>   }
>  }
> }
>

yyterminate() 可以在动作内部返回描述区域中使用，它将终止解析器并返回0给解析器调用者，表示操作完成。缺省情况下，到达文件结束位置也会被调用，它是一个宏，并且可能重定义。

6. 条件模式

LEX提供控制模式在一定状态下使用的功能，称为条件模式。LEX首先在定义部份通过 “%start/x/s 条件名” 来定义条件句。在规则部份可通过宏 “BEGIN(条件名)” 来激活条件。”BEGIN(INITIAL)” 或 “BEGIN(0)” 将休眠所有的条件模式，使分析器回到开始状态。

下面是postgresql里面的一段LEX代码，解析SQL里面的comments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
... ...
op_chars        [\~\!\@\#\^\&\|\`\?\+\-\*\/\%\<\>\=]
... ...
/* C-style comments
 *
 * The "extended comment" syntax closely resembles allowable operator syntax.
 * The tricky part here is to get lex to recognize a string starting with
 * slash-star as a comment, when interpreting it as an operator would produce
 * a longer match --- remember lex will prefer a longer match!  Also, if we
 * have something like plus-slash-star, lex will think this is a 3-character
 * operator whereas we want to see it as a + operator and a comment start.
 * The solution is two-fold:
 * 1. append {op_chars}* to xcstart so that it matches as much text as
 *    {operator} would. Then the tie-breaker (first matching rule of same
 *    length) ensures xcstart wins.  We put back the extra stuff with yyless()
 *    in case it contains a star-slash that should terminate the comment.
 * 2. In the operator rule, check for slash-star within the operator, and
 *    if found throw it back with yyless().  This handles the plus-slash-star
 *    problem.
 * Dash-dash comments have similar interactions with the operator rule.
 */
xcstart         \/\*{op_chars}*
xcstop          \*+\/
xcinside        [^*/]+
... ...
%%
... ...
{xcstart}       {
                    /* Set location in case of syntax error in comment */
                    SET_YYLLOC();
                    yyextra->xcdepth = 0;
                    BEGIN(xc);
                    /* Put back any characters past slash-star; see above */
                    yyless(2);
                }

<xc>{xcstart}   {
                    (yyextra->xcdepth)++;
                    /* Put back any characters past slash-star; see above */
                    yyless(2);
                }

<xc>{xcstop}    {
                    if (yyextra->xcdepth <= 0)
                        BEGIN(INITIAL);
                    else
                        (yyextra->xcdepth)--;
                }

<xc>{xcinside}  {
                    /* ignore */
                }

<xc>{op_chars}  {
                    /* ignore */
                }

<xc>\*+         {
                    /* ignore */
                }

<xc><<EOF>>     { yyerror("unterminated /* comment"); }
... ...

<INITIAL,STRING,QUOTE> 将会在 “INITIAL”, “STRING”, “QUOTE”三者之一的条件下被激活。

开始条件在定义段被申明，在’%s’ 或 ‘%x’后跟随着名字列表。 %s申明了包含的开始条件，%x申明了排他的开始条件。开始条件被BEGIN动作激活。直到下一个BEGIN动作，满足开始条件名称的规则将会被规则，不满足启动条件的规则将不会被执行。
如果是包含条件，没有开始条件的规则也会被激活执行，如果时排他条件，只有满足开始条件的规则才会被执行。

1
2
3
4
%s example
%%
<example>foo   do_something();
bar            something_else();

等同于

1
2
3
4
%x example
%%
<example>foo   do_something();
<INITIAL,example>bar    something_else();

上面的程序中如果没有<INITIAL,example>，在example条件下bar规则将永远不会被激活。如果使用，将会导致只能在exmaple开始条件下激活，而INITIAL条件下不会被激活。而第一个程序中在任何条件下bar都被会激活。因为第一个程序用example时%s，时包含条件。也可以通过特殊开始条件<\>来配置任何开始条件，上面的程序还可以写为：*

1
2
3
4
%x example
%%
<example>foo   do_something();
<*>bar    something_else();

YY_START 开始条件的名字实际上时一个整形值并且能够被保存，可以使用 YY_START 宏来访问当前的开始条件。YYSTATE 是 YY_START 的别名（AT&T lex使用了YYSTATE）。

下面的代码能够是被C语言注释并且统计行数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
%x comment foo
%%
        int line_num = 1;
        int comment_caller;

"/*"         {
             comment_caller = INITIAL;
             BEGIN(comment);
             }

...

<foo>"/*"    {
             comment_caller = foo; /* comment_caller = foo ==》comment_caller = YY_START */
             BEGIN(comment);
             }

<comment>[^*\n]*        /* eat anything that's not a '*' */
<comment>"*"+[^*/]*   /* eat up '*'s not followed by '/'s */
<comment>\n             ++line_num;
<comment>"*"+"/"        BEGIN(comment_caller);

开始条件范围

前面条件模式的代码中，会有许多相同开始条件的处理。使用开始条件范围可以简化重复操作。

1
2
<SCs>{
}

SCs 是一个或开始条件的列表。在这个开始条件范围内，每个规则将会自动具有前缀 ‘‘ 直到 ‘}’ 与开始的 ‘{‘ 匹配. 例如

1
2
3
4
5
6
<comment>  {
  [^*]*        /* eat anything that's not a '*' */
  "*"+[^*/]*   /* eat up '*'s not followed by '/'s */
  \n             ++line_num;
  "*"+"/"        BEGIN(comment_caller);
}

等价于

1
2
3
4
<comment>[^*]*        /* eat anything that's not a '*' */
<comment>"*"+[^*/]*   /* eat up '*'s not followed by '/'s */
<comment>\n             ++line_num;
<comment>"*"+"/"        BEGIN(comment_caller);

条件嵌套

开始条件也可以嵌套，下面时三个管理开始条件堆栈的参数。

void yy_push_state(int new_state) 将当前的开始条件压栈，切换到 new_state 与使用 ‘BEGIN new_state’类似。
void yy_pop_state() 从栈顶弹出，类似于 BEGIN.
int yy_top_state() 返回栈顶值，不改变栈内容。

开始条件栈动态增长，没有固定限制，如果内存用尽，程序自会终止。

7. 多输入缓存区

YY_BUFFER_STATE yy_create_buffer( FILE *file, int size )
void yy_switch_to_buffer( YY_BUFFER_STATE new_buffer )
void yy_delete_buffer( YY_BUFFER_STATE buffer )
void yy_flush_buffer( YY_BUFFER_STATE buffer )

四、YACC

yacc是开发编译器的一个有用的工具,采用LR（1）（实际上是LALR(1)）语法分析方法。
LR(k)分析方法，括号中的k（k >=0）表示向右查看输入串符号的个数。LR分析法正视给出一种能根据当前分析栈中的符号串和向右顺序查看输入串的k个符号就可唯一确定分析器的动作是移进还是规约和用哪个产生式规约。
这种方法具有分析速度快，能准确，即使地指出出错的位置，它的主要缺点是对于一个使用语言文法的分析器的构造工作量相当大，k愈大构造愈复杂，实现比较困难。

一个LR分析器有3个部分组成：

  • 总控程序，也可以称为驱动程序。
    对所有的LR分析器总控程序都是相同的。
  • 分析表或分析函数。
    不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作(ACTION)表和状态转换(GOTO)表两个部分，它们都可用二维数组表示。
  • 分析栈，包括文法符号栈和相应的状态栈。
    它们均是先进后出栈。 分析器的动作由栈顶状态和当前输入符号所决定(LR(0)分析器不需要向前查看输入符号)。
    LR分析器工作过程如下 :
    其中SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表内容按关系GOTO[Si，X] = Sj确定，该关系式是指当栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。X为终结符或非终结符。 ACTION[Si，a]规定了栈顶状态为Si是遇到输入符号a应执行的动作。

YACC可以解析输入流中的标识符(token)，这就清楚的描述了YACC和LEX的关系，YACC并不知道『输入流』为何物，它需要事先就将输入流预加工成标识符，虽然你可以自己手工写一个Tokenizer，但我们将这些工作留给LEX来做。

YACC用来为编译器解析输入数据，即程序代码。这些用编程语言写成的程序代码一点也不模棱两可——它们只有一个意思。正因为如此，YACC才不会去对付那些有歧义的语法，并且会抱怨shift/reduce或者reduce/reduce冲突。更多的关于模糊性和YACC『问题』可以在『冲突』一章中找到。

4.1 yacc语法结构

yacc语法包括三部分：定义段、规则段和用户子例程段

1
2
3
4
5
6
7
8
9
...定义段...

%%

...规则段...

%%

...用户子例程段...

各部分由以两个百分号开头的行分开，尽管某一个部分可以为空，但是前两部分是必须的，第三部分和前面的百分号可以省略。

1. 符号

yacc 语法由符号组成，即语法的“词”。符号是一串不以数字开头的字母、数字、句点和下划线。符号error专用于错误恢复，另外，yacc对任何符号都不会附加“先验”的意义。

由词法分析程序产生的符号叫做终结符号或者标记。定义在规则左侧的叫做非终结符号或者非终结。标记也可能是字面上引用的字符，通常遵循约定：标记大写，非终结符号小写。

2. 定义段

定义段包括文字块，逐字拷贝到生成的C文件开头部分的C代码，通常包括声明和#include行。可能有%union %start %token %type %left %right 和 %nonassoc声明。

也可以包含普通的C语言风格的注释，所有这些都是可选的，在简单的语法分析程序中，定义段可能完全是空的。

如在定义部分定义标志：

1
%token INTEGER

当运行yacc后，会产生头文件，里面包含该标志的预定义，如：

1
2
3
4
5
#ifndef YYSTYPE 
#define YYSTYPE int 
#endif 
#define INTEGER 258 
extern YYSTYPE yylval;

lex使用该头文件中的标志定义。Yacc调用lex的yylex()来获得标志（token），与标志对应的值由lex放在变量yylval中。yylval的类型由YYSTYPE决定，YYSTYPE缺省类型是int。如：

1
2
3
4
[0-9]+ { 
yylval = atoi(yytext); 
return INTEGER; 
}

标志0-255被保留作为字符值，一般产生的token标志从258开始。如：

1
[-+] return *yytext; /* return operator */

返回加号或减号。注意要把减号放在前面，避免被认作是范围符号。
对于操作符，可以定义%left和%right：%left表示左相关（left-associative），%right表示右相关（right-associative）。可以定义多组%left或%right，在后面定义的组有更高的优先级。如：

1
2
%left ‘+’ ‘-‘
%left ‘*’ ‘/’

上面定义的乘法和除法比加法和减法有更高的优先级。
改变YYSTYPE的类型。如这样定义TTSTYPE：

1
2
3
4
5
6
%union
{ 
     int iValue; /* integer value */ 
     char sIndex; /* symbol table index */ 
     nodeType *nPtr; /* node pointer */ 
};

则生成的头文件中的内容是：

1
2
3
4
5
6
7
typedef union
{ 
     int iValue;      /* integer value */ 
     char sIndex;    /* symbol table index */ 
     nodeType *nPtr; /* node pointer */ 
} YYSTYPE; 
extern YYSTYPE yylval;

可以把标志（token）绑定到YYSTYPE的某个域。如：

1
2
%token <iValue> INTEGER 
%type <nPtr> expr

把expr绑定到nPtr，把INTEGER绑定到iValue。yacc处理时会做转换。如：

1
expr: INTEGER { $$ = con($1); }

转换结果为：

1
yylval.nPtr = con(yyvsp[0].iValue);

其中yyvsp[0]是值栈（value stack）当前的头部。

定义一元减号符有更高的优先级的方法：

1
2
3
4
%left GE LE EQ NE '>' '<' 
%left '+' '-' 
%left '*' 
%nonassoc UMINUS

%nonassoc的含义是没有结合性。它一般与%prec结合使用表示该操作有同样的优先级。如：

1
expr: '-' expr %prec UMINUS { $$ = node(UMINUS, 1, $2); }

表示该操作的优先级与UMINUS相同，在上面的定义中，UMINUS的优先级高于其他操作符，所以该操作的优先级也高于其他操作符计算。

3. 规则段

规则段由语法规则和包括C代码的动作组成。

规则中目标或非终端符放在左边，后跟一个冒号（：），然后是产生式的右边，之后是对应的动作（用{}包含）。如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
%token INTEGER
%%
program: program expr '\n' { printf("%d\n", $2); } 
              ;
expr: INTEGER { $$ = $1; }  
         | expr '+' expr { $$ = $1 + $3; } 
         | expr '-' expr { $$ = $1 - $3; } 
;

%%
int yyerror(char *s) 
{ 
     fprintf(stderr, "%s\n", s); 
     return 0; 
}

其中，1表示右边的第一个标记的值，2表示右边的第二个标记的值，依次类推。$$表示归约后的值。

4. 用户子例程段

yacc 将用户子例程段的内容完全拷贝到C文件中，通常这部分包括从动作调用的例程。
该部分是函数部分。当yacc解析出错时，会调用函数yyerror()，用户可自定义函数的实现。
main函数是调用yacc解析入口函数yyparse()。如：

1
2
3
4
5
int main(void) 
{ 
     yyparse(); 
     return 0; 
}

5. 动作

动作 是yacc与在语法中规则相符时执行的C代码，动作一定是C复合语句。

动作有4种可能：

  • 移进：
    当Sj = GOTO[Si，a]成立，则把Sj移入到状态栈，把a移入到文法符号栈。其中i，j表示状态号。
  • 规约：
    当在栈顶形成句柄为β时，则用β归约为相应的非终结符A，即当文法中有 A–>β的产生式，而β的长度为r（即|β| = r）,则从状态栈和文法符号栈中自栈顶向下去掉r个符号，即栈指针SP减去r。并把A移入文法符号栈内，再把满足Sj = GOTO[Si，A]的状态移进状态栈，其中Si为修改指针后的栈顶状态。
  • 接受acc:
    当规约到文法符号栈只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是‘#’，则为分析成功。
  • 报错：
    当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子。

通过使用后面跟有数字的美元符号，动作可以查阅在规则中与符号有关的值,冒号后面跟的第一个符号是数字1，例如：

1
2
date：month  '/'  day   '/'  year  
           { printf ("date %d-%d-%d  found",$1,$3,$5);}

而名字，$$是指冒号左边符号的值，符号值可以有不同的C类型。

4.2 递归处理

递归处理有左递归和右递归。
左递归形式：

1
2
list: item 
    | list ',' item;

右递归形式：

1
2
list: item 
     | item ',' list

使用右递归时，所有的项都压入堆栈里，才开始规约；而使用左递归的话，同一时刻不会有超过三个项在堆栈里。

1. 歧义和冲突

由于语法有歧义或者包含冲突，yacc对于语法规范的翻译可能会失败。一些情况下，语法确实有歧义，也就是说对于一个单独的输入字符串有两种可能的分析而且yacc处理不了。

另外一些情况，语法并无歧义，但yacc使用的语法分析技术不足以分析这个语法。

  • 移进/归约冲突
    当一个输入字符串有两种可能的分析时，而且其中一个分析完成一个规则（归约选项），而另一个却没有（移进选项）时，移进/归约冲突便发生了。
    例如：
1
2
3
4
%%  
e: ‘X’  
     |e  '+'   e  
         ;

对于输入字符串“X+X+X” ，有两种可能的分析： “（X+X）+X”或者“X+(X+X)”，采用归约选项使得语法分析程序使用第一个分析，而采用移进选项则使用另一个。

  • 归约/归约冲突
    当同样的标记可以完成两个不同的规则时，就会发生归约/归约冲突。
    例如：
1
2
3
4
%%  
prog:    proga | progb  
proga:       'X' ;  
progb:       'Y' ;

一个“X”可能是proga，也可能是progb。

大多数归约/归约冲突没这么明显，但是几乎在任何情况下它们在语法中都表现为错误。

  • If-Else 的冲突
    当有两个IF一个ELSE时，该ELSE和哪个IF匹配是一个问题。有两种匹配方法：与第一个匹配和与第二匹配。现代程序语言都让ELSE与最近的IF匹配，这也是yacc的缺省行为。
    虽然yacc行为正确，但为避免警告，可以给IF-ELSE语句比IF语句更高的优先级：
1
2
3
4
%nonassoc IFX 
%nonassoc ELSE
stmt: IF expr stmt %prec IFX 
       | IF expr stmt ELSE stmt

4.3 特殊字符

由于yacc处理符号标记而不是文本，它的输入字符集比起lex来说就简单的多，下面列出了yacc所使用的特殊符号的列表：

%
具有两个%标记的行将yacc语法分成了几部分；
定义段的所有声明都是以%开始，包括%{ %} %union %start %token %type %left %right 和 %nonassoc声明。

\
反斜线符号是废弃的百分号同义词，在动作中，C语言字符串中有其通常作用。

$
在动作中，美元符号引入一个值引用，举例来说，$3表示规则右端第3个符号的值。

‘
文字标记由一个单引号结束，例如 ‘z’ 。

<>
在一个动作的值引用中，可以不考虑尖括号包围起来的默认类型。

“
有些yacc版本在文字标记中将单引号和双引号同等对待，这样使用根本不方便。

{}
动作中C代码在大括号中。

;
除了后面紧接着是以竖线开头的规则外，规则部分每个都是以分号结束。

|
当连续两个规则具有相同的左端，第二个规则可用一个 | 代替符号和冒号。

:
在每一条规则里，左端的每个符号后面都跟着一个冒号。

_
符号可以包括和字母、数字以及句点在一起的下划线。

.
符号可以包括与字母、数字、下划线一起的句点。

=
早期版本使用，现已不推荐。

4.3 Yacc 源程序的风格

建议按照如下风格来写：

  1. 终端符名全部用大写字母，非终端符全部用小写字母；
  2. 把语法规则和语义动作放在不同的行；
  3. 把左部相同的规则写在一起，左部只写一次，而后面所有规则都写在竖线“|”之后；
  4. 把分号“；”放在规则最后，独占一行；
  5. 用制表符来对齐规则和动作。

4.4 一个简单的温度控制器

假定我们有一个温度计，我们要用一种简单的语言来控制它。关于此的一个会话、如下：

1
2
3
4
5
heat on
Heater on!
heat off
Header off!
target temperature set!

我们需要识别的标识符为heat, on/off(STATE), target, temperature, NUMBER。

LEX的tokenizer(example4)为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
%{
#include <stdio.h>
#include "y.tab.h"
%}

%%
[0-9]+ return NUMBER;
heat return TOKHEAT;
on|off return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
\n /* ignore end of line */;
[ \t]+ /* ignore whitespace */
%%

有两个重点需要注意：
第一，我们包含了『y.tab.h』；
第二，我们不再打印输出了，我们返回标识符的名字。之所这样做是因为我们将这些返回传送给了YACC，而它对于我们屏幕上的输出并不感冒。 『y.tab.h』中定义了这些标识符。

但是y.tab.h从哪里来？它由YACC从我们编写的语法文件中生成，语法文件非常简单，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
commands: /* empty */
| commands command
;

command: heat_switch | target_set ;

heat_switch:
TOKHEAT STATE
{
	printf("\tHeat turned on or off\n");
};

target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
	printf("\tTemperature set\n");
};

第一部分，我们称之为根(root)。它告诉我们有一个『commands』，并且这些『commands』由单个的『command』组成。正如你所见到的那样，这是一个标准的递归结构，因为它又再次包含了『commands』。这意味着该程序可以一个个的递减一系列的命令。参见『LEX和YACC内部工作原理』一章，阅读更多的递归细节。

第二个规则定义了『command』的内容。我们只假定两种命令。

一个heat_switch由HEAT标识符组成，它后面跟着一个状态，该状态在LEX中定义，为『on』或『off』。

target_set稍微有点复杂，它由TARGET标识符、TEMPERATURE以及一个数字组成。

前面的那个例子只有YACC文件的语法部分，起始在YACC文件中还有其它内容，完整的YACC文件如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
%{
#include <stdio.h>
#include <string.h>

//在lex.yy.c里定义，会被yyparse()调用。在此声明消除编译和链接错误。
extern int yylex(void); 

// 在此声明，消除yacc生成代码时的告警
extern int yyparse(void); 

int yywrap()
{
	return 1;
}

// 该函数在y.tab.c里会被调用，需要在此定义
void yyerror(const char *s)
{
	printf("[error] %s\n", s);
}

int main()
{
	yyparse();
	return 0;
}
%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

%%
commands: /* empty */
| commands command
;

command: heat_switch | target_set ;

heat_switch:
TOKHEAT STATE
{
	printf("\tHeat turned on or off\n");
};

target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
	printf("\tTemperature set\n");
};
%%

函数yyerror()在YACC发现一个错误的时候被调用，我们只是简单的输出错误信息，但其实还可以做一些更漂亮的事情，参见文档尾的『进阶阅读』部分。

yywrap()函数用于不断的从一个文件中读取数据，当遇到EOF时，你可以再输入一个文件，然后返回0，你也可以使得其返回1，暗示着输入结束。更多细节，参见『YACC和LEX内部如何工作的？』一章。

接着，这里有一个main()函数，它基本什么也不做，只是调用一些函数。

最后一行简单的定义了我将使用的标识符，如果调用YACC时，使用『-d』选项，那么它们会输出到y.tab.h中。

编译并运行恒温控制器：

1
2
3
lex example4.l
yacc –d example4.y
cc lex.yy.c y.tab.c –o example4

在此，情况有所改变，我们现在调用YACC来编译我们的程序，它创建了y.tab.c和y.tab.h. 我接着再调用LEX。 编译时，我们去除了『-ll』编译选项，因为此时我们有了自己的main()函数，并不需要libl来提供。

注意：如果在编译过程中报错说找不到『yylval』，那么在example4.l的#include <y.tab.h>下面加上：

1
extern YYSTYPE yylval；

具体细节在『LEX和YACC内部工作原理』中解说。

一个简单的会话：

1
2
3
4
5
6
7
8
9
10
$ ./example4
heat on
Heat turned on or off
heat off
Heat turned on or off
target temperature 10
Temperature set
target humidity 20
error: parse error
$

4.5 扩展恒温器，使得其可以接受参数

我们已经可以正确的解析温度计命令了，并且能对一些错误做标记。但也许一些狡猾的人会猜疑说，该解析器并不知道你应该做什么，也没有处理一些你输入的数值。

让我们来添加能读取新的温度参数的功能。为达到此目的，我们得知道LEX中的NUMBER匹配要转化成一个数值，然后才能为YACC所接收.

每当LEX匹配到了一个目标字串，它就将该匹配文本赋值给『yytext』，YACC则依次在『yylval』中来查找一个值，在example5中，我们可以得到一个明晰的方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
%{
#include <stdio.h>
#include "y.tab.h"
%}

%%
[0-9]+ yylval = atoi(yytext); return NUMBER;
heat return TOKHEAT;
on|off yylval = !strcmp(yytext, "on"); return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
\n /* ignore end of line */
[ \t]+ /* ignore whitespace */
%%

如你所见，我们在yytext中用了atoi()，并将结果存储在yylval中，使得YACC可以『看见』它。 同理，我们再处理STATE匹配，将其与『on』比较，若想等，则将yylval设置为1。

接下来，我们就得考察YACC如何来应对。我们来看看新的temperature target规则设置：

1
2
3
4
5
target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
    printf("\tTemperature set to %d\n", $3);
};

为得到规则中第三部分的值(NUMBER)，我们用『$3』来表示，每次yylex()返回时，yylval的值便依附到了终结符上，其值可以通过『$-常数』来获取。

为更进一步加深理解，我们来看『heat_switch』规则：

1
2
3
4
5
6
7
8
heat_switch:
TOKHEAT STATE
{
    if ($2)
        printf("\tHeat turned on\n");
    else
        printf("\tHeat turned off\n");
}

如果现在运行example5，它将输出你所输入的数据。

4.6 解析一个配置文件

让我们再次回顾先前提到的那个配置文件：

1
2
3
4
5
6
zone "./www" {
	type hint;
	name foo;
	hello "/hello/world";
	file "/etc/bind/db.root";
};

之前我们已经将LEX文件写好了，接下来只需要编写YACC语法文件，并且对词法分析器做一些修改，使得其可以返回一些值给YACC。
example6中的词法分析器如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
%{
#include <stdio.h>
#define YYSTYPE char *
extern YYSTYPE yylval; // 必须放在#include "y.tab.h"前面
#include "y.tab.h"
%}
%%
zone return ZONETOK;
file return FILETOK;
[a-zA-Z][a-zA-Z0-9]* yylval = strdup(yytext); return WORD;
[a-zA-Z0-9\/.-]+ yylval = strdup(yytext); return FILENAME;
\" return QUOTE;
\{ return OBRACE;
\} return EBRACE;
; return SEMICOLON;
[ \t]+ /* ignore whitespace */;
\n /* ignore EOL */;
%%

细心的话，你会发现yylval已经改变了！我们不再认为它是一个整数，而是假定为一个char*类型数据。为保持简单性，我们调用strdup并因此耗费了很多内存。但这并不影响你解析这个文件。

我们需要保存字符串的值，在此我们处理的都是一些命名，文件名以及区域命。在下一章，我们将解说如何对付一些复杂类型的数据。

为通知YACC关于yylval的新类型，我们在YACC的语法文件中添加一行：

1
#define YYSTYPE char *

下面是完整的YACC文件，语法比较复杂，建议结合代码画AST树来帮助理解（原文这里的代码有不少问题，下面是修正后的代码，对语法也简化了一点点）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
%{
#include <stdio.h>
#include <string.h>

#define YYSTYPE char *
extern YYSTYPE yylval;
//int yydebug = 1; // debug

extern int yylex(void);
extern int yyparse(void);

int yywrap()
{
	return 1;
}

void yyerror(const char *s)
{
	printf("[error] %s\n", s);
}

int main()
{
	yyparse();
	return 0;
}
%}

%token SEMICOLON ZONETOK OBRACE EBRACE QUOTE FILENAME WORD FILETOK

%%
commands:
| commands command SEMICOLON
;

command:
zone_set
;

zone_set:
ZONETOK quotedname zonecontent
{
	printf("Complete zone for '%s' found\n", $2);
};

zonecontent:
OBRACE zonestatements EBRACE
;

quotedname:
QUOTE FILENAME QUOTE
{
	$$ = $2;
};

zonestatements:
| zonestatements zonestatement SEMICOLON
;

zonestatement:
statements | FILETOK quotedname
{
	printf("A zonefile name '%s' was encountered\n", $2);
};

statements:
| WORD statement
{
	$$ = $2; // seems unnecessary
	printf("statements, key: %s, value: %s\n", $1, $2);
};

statement:
WORD | quotedname
;

%%

我们执行example6的输出文件：

1
2
# 将配置文件的内容保存到sample.conf文件中，方便测试
$ cat sample.conf | ./example6

输出为：

1
2
3
4
5
   statements, key: type, value: hint
statements, key: name, value: foo
statements, key: hello, value: /hello/world
 A zonefile name '/etc/bind/db.root' was encountered
Complete zone for './www' found

五、生成C++代码的解析器

虽然LEX和YACC的历史要早于C++，但是还是可以用它们来生成一个C++解析器。但我们用LEX来生成C++的词法分析器，YACC并不知道如何直接来处理这些，所以我们不打算这么做。

我认为比较好的做法是，要做一个C++解析器，就需要LEX生成一个C文件，并且让YACC来生成C++代码。但当你这么做的时候，在这个过程中你将会遇到问题，因为C++代码默认情况下并不能找到C的函数，除非你将那些函数定义为extern “C”。

为达此目的，我们在YACC代码中编写一个C开头：

1
2
3
4
5
6
7
8
9
extern “C”
{
    int yyparse(void);
    int yylex(void);
    int yywrap()
    {
        return 1;
    }
}

如果你想声明并改变yydebug函数，你得这样做：

1
2
3
4
5
6
extern int yydebug;
int main()
{
    yydebug = 1;
    yyparse();
}

这是因为C++中的一个关于定义的规则，即不允许yydebug的多处定义。

你还可能发现，你需要在你的LEX文件中重复#define YYSTYPE，这是由于C++中严格的类型检查(机制)造成的。

按照如下方式来编译：

1
2
3
4
5
6
# Makefile
example_cpp:
	lex -o $@.yy.c $@.lex
	cc -c $@.yy.c -o $@.yy.o
	yacc -dtv $@.yy -o $@.cpp
	g++ $@.yy.o $@.cpp -o $@.out

由于-o选项的存在，y.tab.h现在变成example_cpp.hpp，记住这点。

总结： 不要自寻烦恼的在C++中编译你的词法分析器，让它呆在C的领地里。在C++中编写解析器时，(也得)确保向编译器解释清楚，即你的C函数都有一个extern “C”声明。

六、Lex和YACC内部工作原理

在YACC文件中，你定义了你自己的main()函数，它在某个点上调用了yyparse()。YACC会创建你的yyparse()函数，并在y.tab.c中结束该函数。

yyparse()函数读取一个『标识符/值对』(token/value pairs)流，这些流需要事先就提供，这些流可以是你自己手写的代码提供的，也可以是LEX生成的。在我们的示例中，我们把这个工作丢给了LEX。

LEX生成的yylex()函数从文件参数FILE *file中读取字符(文件名为yyin)。如果不设置成yyin，则默认为标准输入，它会输出到yyout中，如果不加设置，就是stdout。你可以在yywrap()函数中修改位于文件尾的yyin.yywrap()函数。这些修改使得你可以打开另一些文件，并继续解析。

如果是这种情况，那么就让yywrap()返回0，如果你想在该文件上结束解析，就让它返回1。

每次yylex()调用都会返回一个整数值，该值代表了一个标识符类型(token type)。它告诉YACC，已经读取了这种标识符。该标识符可以有一个值，它应该存放在yylval变量中。

yylval的默认类型为int，但是你可以修改其类型，通过在YACC文件中#define YYSTYPE。

词法分析器需要能够访问yylval，为达到此效果，(yylval)必须在词法分析器(lexer)中被声明为一个外部变量(extern variable)。原来的YACC忽略了这点，并没有为你干这项工作，所以，你必须添加以下代码到你的词法分析器中，就在#include <y.tab.h>下面：

1
extern YYSTYPE yylval;

当今多数人使用的Bison已经为你把这事自动做好了。

6.1 标识符的值(token values)

在前面我已经说过，yylex()需要返回它遇到了一个什么标识符类型，并将其值存储在yylval中。当这些标识符在%token命令中定义时，它们就被赋予了一些数字ID，从256开始。

由于这个事实，(我们)可以将所有的ascii字符当作标识符。假定你要写一个计算器，到现在为止，我们可能已经这样写了其词法分析器：

1
2
3
4
5
6
[0-9]+ yylval = atoi(yytext); return NUMBER;
[ \n]+ /* eat whitespace */
- return MINUS;
\* return MULT;
\+ return PLUS;
…

YACC文件可能是这样：

1
2
3
4
5
exp : NUMBER
| exp PLUS exp
| exp MINUS exp
| exp MULT exp
…

没有必要弄这么复杂。用字符作为速记法来作为标识符的数字ID，我们可以这样来重写我们的词法分析器：

1
2
3
[0-9]+ yylval = atoi(yytext); return NUMBER;
[ \n]+ /* eat whitespace */
. return (int) yytext[0];

最后一行匹配任何的单个字符，否则就是不匹配字符。

而YACC的语法文件则是这样:

1
2
3
4
exp : NUMBER
| exp '+' exp
| exp '-' exp
| exp '*' exp

这样更加简短而直观，你就不必在文件头用%token来定义那些ascii字符了。
另一方面，这样构造还有一些好处，它可以匹配所有丢给它的东西，而避免了将那些不匹配的输入输出到标准输出的默认行为。如果用户在当前计算器上输入一个’^’字符，将会导致一个解析错误，而不是将其输出到标准输出中。

6.2 递归：’right is wrong’

递归是YACC一个极其重要的特性。没有递归的话，你就确定一个文件是由一系列独立的命令组成还是由语句组成。由于YACC自身的特性，它只对第一个规则或那个你将其设计为『起始规则』的规则感兴趣。起始规则用’%start’符号标记。

YACC中的递归以两种形式出现，左递归和右递归。左递归是你应该经常使用的，它们看起来如下：

1
2
commands ： /* empty */
| commands command

这是在说，一个command要么为空，要么它包含了更多的commands，后面再跟一个command。YACC的这种工作方式意味着它现在可以轻易的剔除单个的command群并一步步简化(处理)。
拿上面的例子和下面的右递归做比较：

1
2
commands : /* empty */
| command commands

但是这样做开销有点大，如果(commands)是%start规则(即起始规则)，那么YACC会将所有的commands保存在你的栈数据中(file on the stack)，这将耗费大量内存。所以，在解析长的语句时，务必使用左递归，例如整个文件。但有时难以避免右递归，不过，如果你的语句并不太长，你就没有必要越轨使用左递归。

如果你有一些东西来终结(因此而分割)你的commands，右递归就非常适合了，但开销还是有点大:

1
2
commands : /* empty */
| command SEMICOLON commands

正确的做法是使用左递归(这也不是我发明的)：

1
2
commands : /* empty */
| commands command SEMICOLON

本文档的早期版本错误的使用了右递归。Markus Triska友好的提示我们这点(错误)。

6.3 高级yylval: %union

现在，我们需要定义yylval的类型。但是这并不一直恰如其当。我们可能会多次这样做，因为需要处理多种数据类型。回到我们假定的那个恒温器，可能你想选择控制一个加热器，例如：

1
2
3
4
heater mainbuilding
Selected ‘mainbuilding’ heater
Target temperature 23
‘mainbuilding’ heater target temperature now 23

这样的话，就要求yylval是一个union，它可以存储字符串，也可以存储整数，但并不是同时存储。
回忆之前我们讲过，我们提前通知YACC哪种yylval类型会要处理是通过定义YYSTYPE来实现。同样，我们可以定义YYSTYPE为一个union，YACC中有一种简便的方法来实现，即%union语句。

在example4基础上，我编写example7的YACC语法：

1
2
3
4
5
6
7
8
9
%token TOKHEATER TOKHEAT TOKTARGET TOKTEMERATURE
%union
{
int number;
char *string;
}
%token <number> STATE
%token <number> NUMBER
%token <string> WORD

我们定义了union，它只包含一个整数和一个字符串。接着使用了一个扩展的%token语法，我们向YACC解释了应该获取union哪个部分的标识符。
在本例中，我们让STATE标识符用一个整数(来表示)，这跟之前一样。NUMBER同理，我们之前用来读取温度。
但是WORD有所改变，它声明为需要一个字符串。
词法解析器文件有所改变：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
%{
#include <stdio.h>
#include "y.tab.h"
%}

%%

[0-9]+ yylval.number=atoi(yytext); return NUMBER;
heater return TOKHEATER;
heat return TOKHEAT;
on|off yylval.number =! strcmp(yytext,"on"); returnSTATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
[a-z0-9]+ yylval.string = strdup(yytext); return WORD;
\n /* ignore end of line */
[ \t]+ /* ignore whitespace */

%%

正如你所见，我们不再直接访问yylval，我们添加了一个后缀来说明我们要访问那个部分。我们不再需要在YACC语法文件中来干这个工作，YACC在这里耍了下魔法：

1
2
3
4
5
6
heater_select:
TOKHEATER WORD
{
    printf("\tSelected heater '%s'\n", $2);
    heater = $2;
};

由于上面的%token声明，YACC自动选择了union中的’string’成员。注意这里$2中存储的一份拷贝，在后面它会告诉用户发送命令到哪个heater（需要在C文件头定义char *heater）：

1
2
3
4
5
6
target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
    printf("\tHeater '%s' temperature set to %d\n", 
            heater, $3);
};

6.4 自定义YY_INPUT指向字符串而非标准输入

很多情况下，我们不希望从标准输入解析，而希望解析给定的字符串。实现方法是自定义实现YY_INPUT，具体做法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* LEX 文件 */
extern int lex_custom_input(char* buf, unsigned long *num_read,int max_read);
#undef YY_INPUT
#define YY_INPUT(b,r,s) lex_custom_input(b,&r,s)

/* C 文件 */
static int g_read_offset;
#define MAX_TEXT_LEN 1024
static char s_text_buf[MAX_TEXT_LEN];

int lex_custom_input(char* buf, unsigned long *num_read,int max_read)
{
    int num_to_read = max_read;
    int remain = strlen(s_text_buf) - g_read_offset;

    num_to_read = num_to_read>remain ? reamin:num_to_read;
    memcpy(buf, s_text_buf + g_read_offset, num_to_read);

    *num_read = num_to_read;
    g_read_offset += num_to_read;

    return 0;
}

七、调试

YACC中有许多调试反馈信息。这些调试信息的代价有点高，所以你需要提供一些开关来打开它。

当调试你的语法时，在YACC命令行中添加—debug和—verbose选项，在你的C文件头中添加以下语句：

1
int yydebug = 1;

这将生成一个y.output文件，其中说明了所创建的那个状态机。
当你运行那个生成的二进制文件，它将输出很多运行时信息。里面包含当前所运行的状态机以及读取到的一些标识符。

Peter Jinks写了一篇关于调试的文章，他在其中讲述了一些常见得错误以及如何修正这些错误。

7.1 状态机

YACC解析器在内部运行的是一个『状态机』，该状态机可以有多种转台。接着有多个规则来管制状态间的相互转化。任何内容都是从『root』规则开始。

在example7的y.output文件中：

1
2
3
4
5
6
state 0
ZPONETOK , and go to state 1
$default reduce using rule 1 (commands)
commands go to state 29
command go to state 2
zone_set go to satte 3

默认情形下，这个状态机从『commands』规则开始递减演化，这也是我们之前的那个递归规则，它定义了『commands』并从单个的『command』进行构造，后面跟着一个分号，然后可能再跟着更多的『commands』。

这个状态机不断递减演化，直到它遇到某些它能理解的东西，在本例中，为一个ZONETOK，也即单词『zone』。然后转化到状态1，在此，进一步处理一个zone command:

1
2
3
4
state 1
zone_set -> ZONETOK .quotedname zonecontent (rule 4)
QUOTE , and go to state 4
Quotedname go to state 5

第一行中有一个『.』，它用来说明我们所处的位置：即刚刚识别到了一个ZONETOK，目前正在寻找一个『quotedname』。显然，一个『quotedname』会以QUOTE开始，它将我们转化到状态4。
为进一步跟踪，用在『调试』章节中提到的标志来编译example7。

7.2 冲突：『shift/reduce』以及『reduce/reduce』

一旦YACC警告你出现了冲突，那么你的麻烦来了。要解决这些问题显得是一种技巧形式，它会教会很多关于你的语言的东西。比你想知道的要多的多的内容。

问题萦绕于如何来翻译一系列标识符。假定我们定义了一种语言，它需要接受一下两种命令：

1
2
delete heater all
delete heater number1

为达到此目的，我们的语法为：

1
2
3
4
5
6
7
8
9
10
11
delete_heaters :
TOKDELETE TOKHEATER mode
{
    Deleteheaters($3);
}
mode : WORD
delete_a_heater:
TOKDELETE TOKHEATER WORD
{
    delete($3);
}

也许你已经嗅到了麻烦的味道。状态机从读取单词『word』开始，接着它根据下一个标识符觉得转换到何种状态。接下来的标识符可以是『mode』，它指定了如何来删除heater，或者是将要删除的heater。
然而这里的麻烦是，对于这两个命令，下一个标识符都将是一个WORD。YACC因此也无法决定下一步该干嘛。这回导致一个『reduce/reduce』警告，而下一个警告就是『delete_a_heater』节点在状态转化图中永远也不能达到。
这种情况的冲突容易解决(例如，重命名第一个命令为『delete all heater』，或者将『all』作为一个分开的标识符)，但有时，(要解决冲突)却非常困难。 通过『–verbose』参数生成的y.output文件可以提供给你极大的帮助。

八、参考资料

GNU YACC(Bison)有一个非常棒的.info文件，在其中很好的记录了YACC的语法。其中只提到了一次LEX，然而它还是很棒的。你可以用Emacs中那个非常好的『pinfo』工具阅读.info文件。同时，在Bison的主页上可以获得它：Bison手册。
FLEX有一个不错的主页。如果你粗略了解了FLEX所作所为，那将是非常有益的。FLEX的手册也可以联机获取。
在这些关于YACC和LEX的介绍之后，你可能觉得你想需要更多的信息。下面的书籍也相当不错：

  • 《Bison—The Yacc-Compitible Parser Generator》——Charles Donnelly && Richard Stallman.
  • 《Lex & Yacc》——John R. Levine, Tony Mason ,Doug Brown.
  • 《Compilers: Principles, Techniques, and Tools》——By Alfred V.Aho,Ravi
转载声明：商业转载请联系作者获得授权,非商业转载请注明出处 © Ljjyy.com
Copyright © 2019-2024 Ljjyy.com | 关于我们 | 网站地图 | 时间轴