Bison-Flex 笔记

Bison-Flex 笔记

FLEX

什么是 FLEX ？它是一个自动化工具，可以按照定义好的规则自动生成一个 C 函数 yylex() ，也成为扫描器（ Scanner ）。这个 C 函数把文本串作为输入，按照定义好的规则分析文本串中的字符，找到符合规则的一些字符序列后，就执行在规则中定义好的动作（ Action ）。例如在规则中可以这样定义：如果遇到一个换行字符 \n ，那么就把行计数器的值加一。

Flex 文件就是一个文本文件，内容包括定义好的一系列词法规则。文件的命名习惯上以小写字母 l(L) 来作为文件后缀。如果为了清晰，也可以用 .flx 或者 .flex 作为文件的后缀名。 Flex 文件完成后，就执行下列命令：

$ flex example.flex

这个命令执行后将生成一个 C 文件，默认文件名为 lex.yy.c 。这个 C 文件主要内容就是函数 yylex() 的定义。

如果要直接将这个文件编译成为一个可执行程序，还有一些要注意的地方。如果在 Flex 文件中没有提供 main() 函数的定义，那么这个 C 文件中不会有 main() 函数。此时单独编译这个 C 文件的时候，一定要加上 -lfl 的连接库参数；若提供了 main() 函数，就不必要提供这个连接库参数了。连接库 libfl 提供了一个缺省的 main 函数。缺省的 main() 函数中只是简单地调用 yyflex() 函数，而自己提供的 main() 函数则可以根据需要加入许多其他的处理代码。

Flex 文件

词法规范定义文件给出了单词构成规则。词法文件在习惯上用字母 l( 即 L 的小写 ) 来作为后缀。 Flex 文件由三个部分组成。或者说三个段。三个段之间用两个 %% 分隔。

定义段 (definitions)

%%

规则段 (rules)

%%

用户代码段 (user code)

定义段 (definitions section)

定义段包含着一些简单名字的定义 (name definitions) ，旨在简化扫描器的规范。定义名字的方法如下 :

name definition

名字可以由字母或下划线开头，后跟零个或多个字母、数字、下划线、或短横线。名字的定义则从其后的第一个非空白字符 (non-white-space) 开始直到行尾。下面是一个例子，定义了一个名字 DIGIT ，其定义就是指一个数字，如下所示：

DIGIT [0-9]

当在后面引用这个名字时，用一对花括号 ({}) 括住该名字即可。它会被展开成一对圆括号括住的该名字的定义 , 即 :

{name} 展开成 (definition)

例如：

{DIGIT}+"."{DIGIT}*

就等价于：

([0-9])+"."([0-9])*

定义段中还可以加入启动条件 (start conditions) 的声明。顾名思义，启动条件就如同 C 语言中的条件编译一样，根据指定的启动条件去激活一条规则，并用这条规则去匹配读入的字符。关于启动条件，后面还有更详细的介绍。

规则段 (rules section)

规则由模式 (pattern) 和动作 (action) 两个部分组成。模式 就是一个正则表达式， FLEX 加入了一些自己的扩展。而动作 一般就是一些 C 语句。模式指出了一个单词是如何构成的，当分析出一个符合该规则的单词时，就执行相应的动作。

模式一定要位于一行的开头处，不能有缩进。而动作的开头一定要与模式在同一行。当动作是用一对花括号 {} 括起来时，可以将左花括号放在与规则相同的行，而其余部分则可以从下一行开始。

用户代码段 (user code)

所有用户代码都被原样拷贝到文件 lex.yy.c 中。在这里可以定义一些辅助函数或代码，供扫描器 yylex() 调用，或者调用扫描器（一般来说就是 main() 了）。这一部分是可有可无的。如果没有的话， Flex 文件中第二个 %% 是可以省略的。

在定义段或者规则段中，任何一行有缩进的文本 或者包含在一对 %{ 和 %} 之间的文本 ，都被原样拷贝到最后生成的 C 代码文件中（当然 %{ 和 %} 会被移走）。在书写时 %{ 和 %} 都必须在一行的开始处，不能缩进。

在规则段中，第一条规则之前的任何未缩进的文本或者在 %{ 和 %} 之间的文本，可以用来为扫描器声明一些本地变量和代码。一旦进入扫描器的代码，这些代码就会被执行。规则段内其他的缩进的文本或者 %{ 和 %} 之间的文本还是被原样拷贝输出，但是他们的含义是尚未有明确定义，很可能引起编译时（ compile-time ）错误（这一特性是为了与 POSIX 兼容而提供的）。

在定义段中，没有缩进的注释也会被原样拷贝到最后生成的 C 代码文件中，例如以 /* 开始的一行注释，直到遇到 */ ，这中间的文本会被原样拷贝输出。

模式及其分类

模式采用正则表达式来书写。正则表达式大致可以分为如下几类（从上到下，优先级依次递减）：

（ 1 ）单字符匹配

* ‘x’ 匹配字符 x 。

* ‘.’ 匹配任意一个字符（字节），除了换行符。

* ‘[xyz]’ 匹配单个字符，这个字符是方括号中给出的字符类（ character class ）中的一个。

* ‘[abj-oZ]’ 匹配单个字符，这个字符是方括号中给出的字符类中的一个。与上一方式的区别是指定字符类时用到了一个范围表示法： j-o ，这表示按照 26 个英文字母的顺序，从字母 j 开始一直到字母 o 共 6 个字母。这里减号（ - ）表示范围。如果减号本身也要作为一个匹配字符时，最好用转义字符（ \ ）去除其特殊含义。由于花括号（ {} ）在模式中用来引用名字，以及作为模式定义之后的动作（ Action ）定义块的首尾界定符，因此如果要在字符类中匹配花括号，必须用转义字符（ \ ）去除其特殊含义。下面这个例子定义了一个所有可打印字符的字符类：

[[:alnum:][:blank:]]\t+\-*/&!_'?@^`~$\\()%|.;[\]\{\}:,#<>=]

* ‘[^A-Z]’ 匹配单个字符，这个字符必须是方括号中给定字符类以外的字符。在方括号内开始处的特殊符号（ ^ ）表示否定。当字符 ^ 不在字符类的开始处时，并不具有特殊含义，而是一个普通字符。

* ‘[^A-Z\n]’ 匹配单个字符，这个字符不可以是方括号中给出的字符类中的字符。与上一方式的不同在于，这里多了一个换行符，也就是说所匹配的字符不能是 26 个大写字母，也不能是换行符。

根据上面的描述，在表达字符分类时，除了直接用字符以及字符范围来表达外，还有一种叫做字符类表达式 的，也有同样的作用，常见的一些表达式如下：

[:alnum:] [:alpha:] [:blank:] [:cntrl:] [:digit:] [:graph:]

[:lower:] [:print:] [:punct:] [:space:] [:upper:] [:xdigit:]

每一个表达式都指示了一个字符分类，而且其名称与标准 C 函数 isXXXX 的名字对应。例如， [:alnum:] 就指示了那些经由函数 isalnum() 检查后返回 true 的字符，也就是任何的字母或者数字。注意，有些系统上没有给出 C 函数 isblank() 的定义，所以 flex 自己定义了 [:blank:] 为一个空格或者一个 tab 。

下面所举的几个例子，都是等价的：

[[:alnum:]]

[[:alpha:][:digit:]]

[[:alpha:]0-9]

[a-zA-Z0-9]

应该注意字符类表达式的写法。一个字符类表达式是由一对 [: 和 :] 包住的，作为一个整体，在书写时不可与外层的 [] 混淆。

（ 2 ）重复模式的匹配

* ‘r*’ r 是一个正则表达式，特殊字符 `*' 表示 0 个或多个。因此这个模式表示匹配 0 个或多个 r 。

* ‘r+’ r 是一个正则表达式，特殊字符 `+' 表示 1 个或多个。因此这个模式表示匹配 1 个或多个 r 。

* ‘r?’ r 是一个正则表达式，特殊字符 `?' 表示 0 个或 1 个。因此这个模式表示匹配 0 个或 1 个 r 。（从另一个角度看，就是说模式 r 是可选的）

* ‘r{2,5}’ r 是一个正则表达式， {2,5} 表示 2 个到 5 个。因此这个模式表示匹配 2 个到 5 个 r 。也就是说可以匹配 `rr' ， `rrr' ， `rrrr' ， `rrrrr' 四种重复的模式。

* ‘r{2,}’ r 是一个正则表达式， {2,} 省略了第二个数字，表示至少 2 个，不设上限。因此这个模式表示匹配 2 个及以上个 r 。也就是说至少可以匹配 `rr' ，还可以匹配 `rrr' ， `rrrr' 等无限多种重复的模式。

* ‘r{4}’ r 是一个正则表达式， {4} 只有一个数字，表示 4 个。因此这个模式确切地匹配 4 个 r ，即 `rrrr' 。

（ 3 ）名字替换

* ‘{name}’ 这里 name 就是在前面的定义段给出的名字。这个模式将用这个名字的定义来匹配。

（ 4 ）平凡（ plain ）文本串的匹配

* ‘“[xyz]\″foo”’ 这个模式用来确切地匹配文本串： [xyz]\″foo 。注意最外层的单引号所包含的是整个模式表达式，也就是说，当希望匹配字串 [xyz]\″foo 时，在书写规则时该字串必须用双引号括住。

（ 5 ）特殊单字符的匹配

* ‘\x’ 当 x 是一个 `a' ， `b' ， `f' ， `n' ， `r' ， `t' 或 `v' 时，它就解释为 ANSI-C 中的 \x 。否则就仍然作为一个普通字符 x （一般用于诸如 `*' 字符的转义字符）。

* ‘\0’ 匹配一个 NUL 字符（ ASCII 码值为 0 ）。

* ‘\123’ 匹配一个字符，其值用八进制表示为 123 。

* ‘\x2a’ 匹配一个字符，其值用十六进制表示为 2a 。

（ 6 ）组合模式的匹配

* ‘(r)’ 匹配规则表达式 r ，圆括号可以提高其优先级。

* ‘rs’ 匹配规则表达式 r ，其后紧跟着表达式 s 。这称为联接 (concatenation) 。

* ‘r|s’ 或者匹配规则表达式 r ，或者匹配表达式 s 。

* ‘r/s’ 匹配模式 r ，但是要求其后紧跟着模式 s 。当需要判断本次匹配是否为“ 最长匹配（ longest match ）时，模式 s 匹配的文本也会被包括进来，但完成判断后开始执行对应的动作（ action ）之前，这些与模式 s 相配的文本会被返还给输入。所以动作（ action ）只能看到模式 r 匹配到的文本。这种模式类型叫做尾部上下文（ trailing context ）。（有些‘ r/s’ 组合是 flex 不能识别的；请参看后面 deficiencies/bugs 一节中的 dangerous trailing context 的内容。）

* ‘^r’ 匹配模式 r ，但是这个模式只出现在一行的开始处。也就是说，刚开始扫描时遇到的，或者说在刚扫描完一个换行字符后紧接着遇到的。

* ‘r$’ 匹配模式 r ，但是这个模式只在一行的尾部。也就是说，该模式就出现在换行之前。这个模式等价于 r/\n 。注意， flex 中的换行（ newline ）的概念，就是 C 编译器中所使用的 \n ， flex 也采用同样的符号和解释。在 DOS 系统中，可能必须由你自己滤除输入中的 \r ，或者明确地在模式中写成 r/\r\n 来代替 r$ 。（在 unix 系统中换行是用一个字节 \n 表示的，而 DOS/Windows 则采用两个字节 \r\n 来表示换行。）

（ 7 ）有启动条件（ Start Condition ）的模式匹配

* ‘<s>r’ 匹配模式 r ，但需要启动条件 s （后面后关于启动条件的讨论）。模式‘ <s1,s2,s3>r’ 是类似的，匹配模式 r ，只要有三个启动条件 s1 ， s2 ， s3 中的任一个即可。（启动条件简单来说，类似于 C 语言中的条件编译，满足了某个条件才启动这个模式参与匹配，否则不会启动该模式参与匹配。）

* ‘<*>r’ 匹配模式 r ，在任何启动条件下都参与匹配，即使是排斥性的条件。

[ 上述还需要从实践中体会其含义 ]

（ 8 ）文件尾匹配

* ‘<<EOF>>’ 匹配文件尾，即遇到了文件尾部。一般说来，都应该在模式中加入文件尾模式。这样可以有机会在文件扫描完成时增加一些额外的处理。

* ‘<s1,s2><<EOF>>’ 在有启动条件 s1 或者 s2 的情况下，匹配文件尾部。

一些常见规则的编写（待续）

（ 1 ）双引号字符串。

[\"]({SAFECHAR}|{RESTCHAR}|[_])*[\"]

这里需要注意的地方是中间的重复模式的写法： (r)* 。 r 可以是一个组合模式。中间的两个名称 SAFECHAR 和 RESTCHAR 是在定义段给出的两个字符类。

[ 此处应在实用中不断添加 ]

=========================================

创建一个简单的扫描器

下列例子来自于 Flex 的手册。并在 Windows+Cygwin+bison+flex+gcc 的环境下编译运行。

(1) 编辑 Flex 语法文件 。

/* name: example.flex */

int num_lines = 0, num_chars = 0;

%%

\n ++num_lines; ++num_chars;

. ++num_chars;

%%

int main()

{

yylex();

printf("# of lines = %d, # of chars = %d\n", num_lines, num_chars);

return 0;

}

(2) 生成扫描器的 C 文件 。

$ flex example.flex

The output is lex.yy.c

(3) 编译生成的 C 文件 。

编译时失败，出现了如下的问题：

# gcc -g -Wall -lfl -o scan lex.yy.c

lex.yy.c:959: warning: 'yyunput' defined but not used

/cygdrive/c/DOCUME~1/ADMINI~1.78B/LOCALS~1/Temp/ccHwCWNb.o: In function `main':

/cygdrive/c/home/sandbox/flex_exam_1/example.l:9: multiple definition of `_main'

/usr/lib/gcc/i686-pc-cygwin/3.4.4/../../../libfl.a(libmain.o):(.text+0x0): first defined here

/cygdrive/c/DOCUME~1/ADMINI~1.78B/LOCALS~1/Temp/ccHwCWNb.o: In function `yylex':

/cygdrive/c/home/sandbox/flex_exam_1/lex.yy.c:692: undefined reference to `_yywrap'

/cygdrive/c/DOCUME~1/ADMINI~1.78B/LOCALS~1/Temp/ccHwCWNb.o: In function `input':

/cygdrive/c/home/sandbox/flex_exam_1/lex.yy.c:1041: undefined reference to `_yywrap'

collect2: ld returned 1 exit status

上述消息指出两个问题：

（ 1 ）函数 yywrap 没有定义。

（ 2 ）自定义函数 main 与连接库 fl 中的定义冲突了。

第一个问题的解决办法是在第一段（定义段）中加上一个选项指令：

%option noyywrap

第二个问题的解决办法就是用 gcc 编译时不连接 fl 库，如下所示：

# flex example.flex

# ls

example.flex lex.yy.c

# gcc -g -Wall -o scan lex.yy.c

lex.yy.c:977: warning: 'yyunput' defined but not used

# ls

example.flex lex.yy.c scan.exe

# ./scan.exe

789

234

345# of lines = 2, # of chars = 11

修改过的代码如下：

%option noyywrap <==== 防止出现 yywrap 的问题

%{

int num_lines = 0, num_chars = 0;

%}

%%

\n ++num_lines; ++num_chars;

. ++num_chars;

%%

int main()

{

yylex();

printf("# of lines = %d, # of chars = %d\n",

num_lines, num_chars);

return 0;

}

更改扫描器 yylex() 的名字

我们还可以更改 Flex 自动生成的词法分析函数 yylex() 的名字、参数以及返回值，也就是说 yylex 这个名字仅仅是一个默认的名称，是可以改成其他名称的。方法很简单，只需要对宏 YY_DECL 做一个重定义即可：

#define YY_DECL float lexscan (float a, float b)

上述的宏定义就表明：当运行 Flex 生成 C 代码时，词法分析函数的名字叫做 lexscan （不再是 yylex 了），有两个浮点型参数 a 和 b ，函数的返回值是浮点型。

如果与 Bison 联用的话，还是不要更改的好，因为 Bison 要求词法分析函数的名称是 yylex 。 [ 应该也是可以改的，但其实际的方法还需在实践中得来。 ]

词法分析函数 yylex() 会使用全局变量 yyin 读取字符。

一些思考

（ 1 ）在 H248 协议的 BNF 文本中，需要分析很多的数字，有十六进制的，有十进制的，有长的数字也有短的数字。虽然在 H248 协议看来，各种不同的数字有着不同的意义，但是在 Flex 词法扫描器看来，它们有什么不同呢？特别是同样的一个 0xab 这样的只有两位数字的十六进制数，在 H248 协议和 BISON 看来，其有不同的含义和类型，但是在 Flex 看来却没有什么不同。假设 Bison 分别将其定义为 Token_A 和 Token_B ，那么当 Flex 分析出这么一个单词时，返回给 Bison 的数字类型是 A 还是 B ？

（ 2 ）在 H248 协议中，有一种表达式是由多个参数组成的，其中每个参数至多出现一次，且参数间次序是任意的。此外其中有两个参数是必须的。这种情况下如何给出 Bison 文法规则定义呢？

文法分析概览

利用 BNF 写出的文法规则，可以用来对输入的文本进行文法分析。一条 BNF 文法规则，左边是一个非终结符（ Symbol 或者 non-terminal ），右边则定义该非终结符是如何构成的，也称为产生式（ Production ），产生式中可能包含非终结符，也可能包含终结符（ terminal ），也可能二者都有。在所有文法规则中，必有一个开始的规则，该规则左边的部分叫做开始符号（ start symbol ）。一个规则的写法如下：

Symbol := Production

下面是一个 BNF 文法定义的例子。 FN 是 fractional number 的意思， DL 是 digit list 的意思， S 是 start symbol 。

S := '-' FN | FN

FN := DL | DL '.' DL

DL := D | D DL

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

一个非终结符可能有多个产生式，相互间用竖线（ | ）隔开。

每一条 BNF 产生式，都有自己的启动集（ start set ）。启动集里的元素就是每个 Production 中的第一个部分，比如上例 S 规则的启动集就是 {'-'} 以及 {FN} 。

利用 BNF 文法来分析目标文本，其分析方法比较流行的有几种，下面作一概述 [Garshol 03] 。

LL(k) 分析

LL 分析又称为自顶向下的分析（ top-down parsing ），也有叫递归下降分析（ recursive-descent parsing ）。也是最简单的一种分析方式。它工作的方式类似于找出一个产生式可以从哪一个终结符开始。

当分析时，从起始符号开始，比较输入中的第一个终结符和启动集，看哪一个产生式规则被使用了。当然，两个启动集之间不能拥有同一个终结符。如果有的话，就没有办法决定选择哪个产生式规则了。

Ll 文法通常用数字来分类，比如 LL(1) ， LL(0) 等。这个数字告诉你，在一个文法规则中的任何点可以允许一次察看的终结符的最大数量。 LL(0) 就不需要看任何终结符，分析器总是可以选择正确的产生式规则。它只适用于所有的非终结符都只有一个产生规则。只有一个产生规则意味着只有一个字符串。 [ 不用看当前的终结符是什么就可以决定是哪一个产生规则，说明这个规则是为一个固定的字符串所写的。 ] 这种文法是没有什么意义的。

最常见也是比较有用的事 LL(1) 文法。它只需要看一个终结符，然后就可以决定使用哪一个产生规则。而 LL(2) 则可以查看两个终结符，还有 LL(k) 文法等等。对于某个固定的 k 值，也存在着根本不是 LL(k) 的文法，而且还很普遍。

下面来分析一下本章开头给出的例子。首先看下面这条规则：

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

上述规则有十个产生式，每个产生式的启动集是一个数字终结符构成的集合 {'0'} 、 {'1'} 、…… 、 {'9'} 。这是一个很好的 LL(1) 文法，因为我们只要看一个终结符，就可以选择一个正确的产生式。例如，如果看到一个终结符，其内容是 3 ，那么就采用上面第四个产生式，即 D := '3' 。

接下来分析 DL 规则。

DL := D | D DL

上述规则有两个产生式，启动集是 {D} ， {D} 。很不幸，两个产生式的启动集相同。这就表示只看第一个输入中的第一个终结符不能选择正确的产生式。

然而可以通过欺骗来绕过这个问题：如果输入中第二个终结符不是一个数字，那么就选择第一个产生式，但如果两者都是数字就必须选择第二个产生式。换句话说，这意味着这是一条好的 LL(2) 文法规则。实际上这里有些东西被简化了。

再分析下 FN 规则吧。它的情况更糟糕。

FN := DL | DL '.' DL

它有两条产生式，而且启动集相同，均为 {DL} 。然而这次不像 DL 规则那么幸运了。咋一看，似乎通过 LL(2) 可以分辨应该使用哪一个产生式。但是很不幸，我们无法确定在读到终结符 ('.') 之前，需要读多少个数字才算是 DL 符号的最后一个数字。 [ 想想吧，分析器这么工作着：读入第一个终结符，一看是相同的 DL 符号，那么就读第二个终结符吧；读入第二个终结符，两者合起来一看，还是一样的 DL 符号；读入第三个终结符，前三个终结符合起来看，仍然是相同的 DL 符号。但是 DL 符号表指示数字表示没有长度限制的。 ] 没有任何一个给定的 k 值，这都不符合 LL(k) 文法，因为数字表总能突破这个 k 的长度。

最后看看启动符号规则。有点意外，它产生规则的选择很简单。

S := '-' FN | FN

它有两个产生规则，两者的启动集是 {'-'} 和 {FN} 。因此，如果输入中第一个终结符是 '-' ，那么就选择第一个产生式，否则选择第二个产生式。所以这是一个 LL(1) 文法。

从上述的 LL 分析看，只有 FN 和 DL 规则引起了问题。但是不必绝望。大部分的非 LL(k) 文法都可以容易地转换为 LL(1) 文法。下面以当前的这个例子来看看如何转换有问题的 FN 和 DL 。

对于 FN 符号来说，它的两个产生式都开始于 DL ，但是第二个产生式其后续的是一个小数点终结符 ('.') ，以及另外一个数字表。那么这很容易解决：可以将 FN 改变为一个产生式，其以 DL 开始，后跟一个 FP （ fractional part ）符号。而 FP 符号则定义成或者为空，或者为小数点后跟着一个数字表，如下所示：

FN := DL FP

FP := @ | '.' DL

上述 @ 符号表示为空。现在 FN 文法没有任何问题了，因为它现在只有一个产生式。而 FP 也不会有问题，因为它的两个产生式的启动集是不同的：前者是输入的尾端，后者是小数点终结符。

DL 符号就不是好啃的核桃了，原因在于其递归和至少需要一个 D 符号。解决方案就是，给 DL 一个产生式，由一个 D 后跟一个 DR （ digit rest ）构成；而 DR 则有两个产生式，一个是 D DR （表示更多的数字），一个是 @ （表示没有更多的数字）。最后本章开头的例子被转换成下面的一个完全的 LL(1) 文法了：

S := '-' FN | FN

FN := DL FP

FP := @ | '.' DL

DL := D DR

DR := @ | D DR

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

LR 分析

Lr 分析也叫自底向上的分析（ bottom-up parsing ），或者叫移进 - 归约分析（ shift-reduce parsing ），相比 LL 分析难度更大些。它的基本原理是，首先收集输入，直到它发现可以据此利用一个符号对收集到的输入序列进行归约。可以与数学里面解方程式时的消元法进行类比。这听起来似乎很难。下面还是以一个例子来澄清。例子中将分析字符串 3.14 ，看看是怎样从文法产生出来的。

S := '-' FN | FN

FN := DL | DL '.' DL

DL := D | D DL

D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

首先从输入中读入 3 。

3

然后看看是否可以将其归约为一个符号（ Symbol ，即非终结符）。实际上可以归约，就是说用 D 符号的产生式可以得到当前读入的字符串（这也是成为产生式的原因）。

很快发现，从 DL 符号可以产生符号 D ，于是又可以归约成 DL 。（实际上还可以进一步地归约成 FN ，于是这里就产生了歧义，到底应该归约成哪一个呢？这表明这个文法定义是二义性的，我们在这里就忽略这个问题，直接选择 DL 作为归约结果吧。）接着从输入中读入一个小数点，并试图进行归约：

D ==> 规约到 DL

DL ==> 读入下一个字符

DL . ==> 规约到？

但是这次的归约尝试失败了，因为没有任何符号的定义可以产生这种形式的字符串。也就是说，这种形式不能规约到任何符号。

所以接着我们读入下一个字符 1 。这次可以将数字 1 归约到 D 符号。接着再读入一个字符 4 。 4 可以归约到 D ，继续归约到 DL 。这两次的读入和规约形成了 D Dl 这个序列，而这个序列可以归约到 DL 。

DL . ==> 读入下一个字符 1

DL . 1 ==> 1 归约到 D

DL . D ==> 读入下一个字符 4

DL . D 4 ==> 4 归约到 D

DL . D D ==> 4 继续归约到 DL

DL . D DL ==> D DL 归约到 DL

察看文法我们可以很快地注意到， FN 能产生 DL . Dl 这种形式的序列，所以可以做一个归约。然后注意到 FN 可以从 S 符号产生，所以可以归约到 S ，然后停止，整个分析结束。

DL . DL ==> 归约到 FN

FN ==> 规约到 S

S ==> 分析结束

可能你已经注意到，我们经常可以选择是否现在就做归约，还是等到读入更多的符号后再作不同的归约。移进 - 归约分析算法有很多不同的变种，按照复杂度和能力递增的顺序是： LR(0) ， SLR ， LALR 和 LR(1) 。 LR(1) 通常需要一个巨大的分析表，在实践上不具有实用性，因此 LALR 是最常使用的算法。 SLR 和 LR(0) 对于大部分的程序语言来说还不够强大。

Bison 分析器的算法 ¹

Bison 适合上下文无关文法（ Context-free grammar ），并采用 LALR(1) 算法 [Donnelly 06] 的文法。

当 bison 读入一个终结符（ token ），它会将该终结符及其语意值一起压入堆栈。这个堆栈叫做分析器堆栈 （ parser stack ）。把一个 token 压入堆栈通常叫做移进 （ shifting ）。

例如，假设一个中缀计算器已经读入 '1 + 5 * ' ，下一个准备读入的是 '3' ，那么这个栈里就有四个元素，每个元素都是移进的一个终结符。

但堆栈并不是每读入一个终结符就分配一个栈元素给它。当已经移进的后 n 个终结符和组（ groupings ）与一个文法规则相匹配时，它们会被根据那个规则结合起来。这叫做归约（ reduction ）。栈中的那些终结符和组会被单个的组（ grouping ）替换。那个组的符号就是那个规则的结果。执行该规则的相应的动作（ Action ）也是归约处理的一部分，这个动作会计算这个组的语意值。

例如，如果中缀计算器的分析器堆栈包含： 1 + 5 * 3 ，并且下一个输入字符是换行符，那么上述后 3 个元素可以按照下面规则归约到 15 ：

expr: expr '*' expr;

于是堆栈中就只包含下面三个元素了： 1 + 15 。此刻，另一个规约也可以执行，其结果是一个单值 16 。然后这个新行终结符就可以被移进了。

分析器通过移进和归约尝试着缩减整个输入到单个的组。这个组的符号就是文法中的起始符号（ start-symbol ）。

终结符预读

Bison 分析器并不总是在后 n 个终结符与组匹配某一规则时立即就进行归约。这种策略对于大部分语言来说并不合适。相反，当可以进行归约时，分析器有时会“ 预读” （ looks ahead ）下一个终结符来决定做什么。

当一个终结符被读进来后，并不会立即移进堆栈，而是首先作为一个预读终结符 （ look-ahead token ）。此后，分析器开始对栈上的终结符和组执行一个或多个归约，而预读终结符仍然放在一边。当没有归约可做时，这个预读终结符才会被移进堆栈。这并不表示所有可能的归约都已经做了，这要取决于预读终结符的类型，一些规则可能选择推迟它们的使用。 </