星期六, 十月 14, 2006
Exercises for Chapter 2
2.1 Consider the context-free grammar
S → S S + | S S * | a
a) Show how the string aa+a* can be generated by this grammar
b) Construct a parse tree for the string
c) What language is generated by this grammar? Justify your answer.
应该是任意数目a和+＊相互交叉，但是+*的数目之和永远比a少1，另外+*不可能出现在字符串的最开始，但可以出现在最后。
最简单的情况a，+*比a少一，不管采用哪一种产生式，永远是多了2个a,再多了一个+或者*，因此还是a比+*多一个。
2.2 What language is generated by the following grammars? In each case justify your answer.
a) S → 0 S 1 | 0 1
任意个0后跟相同数目的1，S -> 0 1 ，如果用它去替换 S → 0 S 1中右边的S，得到 0 0 1 1 ，继续替换，每次前面增加一个0，后面同时增加一个1
b) S → + S S | - S S | a
类似于第一题，但是+-只能出现字符串最开始，而不能出现在最后
c) S → S ( S ) S | ε
任意括号组合
1. S可以是一个括号，因为S可以取ε，则S → S ( S ) S 得到 S → S ( S ) ，第一个S可以取ε，S → ( S ), S可以取ε，S → ()
2. S可以是两个括号，因为S可以取ε，则S → S ( S ) S 得到 S → S ( S )，S → S( ),此时如果S取一个括号，则得到两个括号
3.同理,S可以取任意多个的括号连接
4.S → ( S )可以取得一层嵌套，又根据S → ( S )，依次可以知道可以任意增加嵌套，每一层内部根据3可以得到任意数目的嵌套
5.因此，任意嵌套、任意数目的括号可以得到
该文法具有二义性，例如，对token字符串()()，可以有两棵解析树：
d) S → a S b S | b S a S | ε
相同的数目的a b任意组合，因为字符串可以为空，或者是ab,ba，这个时候ab的数目还是一样。不管选择S → a S b S还是b S a S，总是在原先的S上插入a和 b，因此ab字符的数目永远一样，由于可以选择，a或者b在前，所以可以任意组合，只要字符数目一样
e) S → a | S + S | S S | S * | ( S )
任意数目的连续的a中间(可以用括号括起）穿插+或者*，其中+和*不连续。可以看作一个+或者*的表达式，其中+和*的操作数可以是任意数目的a或者是()括起的子表达式。但是*可以出现在结尾。这个文法显然是具有二义性的，例如字符串aaaaa就可以有很多解析树。同样aa+aaa+aaaaa这样的字符串也可以有很多解析树。
2.3 which of the grammar in Exercise 2.2 are ambiguous?
如上
2.4 Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct.
a) Arithmetic expressions in postfix notation.
expr → expr expr + | expr expr - | expr expr * | expr expr /| (expr) | digit
对后缀表达式来说，不可能产生结合性的问题，也没有优先级的问题，对四则运算总是两个操作数加上一个操作符，例如12+3+，3肯定属于它后面一个加号所要应用的操作数，不可能属于前面一个加号，优先级问题也一样。
b) Left-associative lists of identifiers separated by commas.
list → list , id | id
c) right-associative lists of identifiers separated by commas.
list → id , list | id
d) Arithmetic expressions of integers and identifiers with the four binary operators +,-,*,/
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → integer | id | (expr)
e) Add unary plus and minus to the arithmetic operators of (d).
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → + integer | - integer | integer | id | (expr)
*2.5 a) Show that all binary string generated by the following grammar hava values divisible by 3. Hint. Use induction on the number of nodes in a parse tree.
num → 11 | 1001 | num 0 | num num
写出计算数字值的语意动作
num → 11 {num.value = 3;} （1）
| 1001 {num.value = 9;} （2）
| num 0 {num2.value = num1.value*2;} （3）
| num num {num3.value = num1.value*2n + num2.value;} （4）
<1>
我们可以看到，如果一个字符串是通过（1）产生的，那么则为3，所以num为3的倍数，如果一个字符串是通过（2）产生的，即为9，所以也是3的倍数
<2>
现在假设现有的任何num字符串全部都是3的倍数，那么还有两种方法可以产生新的字符串
产生式(3) :由于现有所有的num都是3的倍数，因此num1.value是3的倍数，num1.value*2也是3的倍数，也就是说用产生式（3）产生的所有新的字符串都是3的倍数
产生式(4):由于现有所有的num都是3的倍数，因此num1.value和num2.value都是3的倍数，因此num1.value*2n也是3的倍数（n代表num2的长度），num1.value*2n + num2.value也是3的倍数，也就是说用产生式（4）产生的所有新的字符串都是3的倍数
<3>
从<1>得知，（1）和（2）产生的字符串都是3的倍数，从<2>得知，任何在3倍数的字符串基础上产生的新字符串都是3的倍数，所以所有该文法产生的字符串都是3的倍数，也就是能够被3整除。
b) Does the grammar generate all binary strings with values divisible by 3?
3的7倍为21=16+4+1，二进制表达方式为10101,无法用上面的文法产生
S → S S + | S S * | a
a) Show how the string aa+a* can be generated by this grammar
- a是S，因为S→ a
- aa+是S，因为 S → S S +，而a 是S
- aa+a*是S，因为 S → S S *,而且aa+是S , a是S
b) Construct a parse tree for the string
c) What language is generated by this grammar? Justify your answer.
应该是任意数目a和+＊相互交叉，但是+*的数目之和永远比a少1，另外+*不可能出现在字符串的最开始，但可以出现在最后。
最简单的情况a，+*比a少一，不管采用哪一种产生式，永远是多了2个a,再多了一个+或者*，因此还是a比+*多一个。
2.2 What language is generated by the following grammars? In each case justify your answer.
a) S → 0 S 1 | 0 1
任意个0后跟相同数目的1，S -> 0 1 ，如果用它去替换 S → 0 S 1中右边的S，得到 0 0 1 1 ，继续替换，每次前面增加一个0，后面同时增加一个1
b) S → + S S | - S S | a
类似于第一题，但是+-只能出现字符串最开始，而不能出现在最后
c) S → S ( S ) S | ε
任意括号组合
1. S可以是一个括号，因为S可以取ε，则S → S ( S ) S 得到 S → S ( S ) ，第一个S可以取ε，S → ( S ), S可以取ε，S → ()
2. S可以是两个括号，因为S可以取ε，则S → S ( S ) S 得到 S → S ( S )，S → S( ),此时如果S取一个括号，则得到两个括号
3.同理,S可以取任意多个的括号连接
4.S → ( S )可以取得一层嵌套，又根据S → ( S )，依次可以知道可以任意增加嵌套，每一层内部根据3可以得到任意数目的嵌套
5.因此，任意嵌套、任意数目的括号可以得到
该文法具有二义性，例如，对token字符串()()，可以有两棵解析树：
d) S → a S b S | b S a S | ε
相同的数目的a b任意组合，因为字符串可以为空，或者是ab,ba，这个时候ab的数目还是一样。不管选择S → a S b S还是b S a S，总是在原先的S上插入a和 b，因此ab字符的数目永远一样，由于可以选择，a或者b在前，所以可以任意组合，只要字符数目一样
e) S → a | S + S | S S | S * | ( S )
任意数目的连续的a中间(可以用括号括起）穿插+或者*，其中+和*不连续。可以看作一个+或者*的表达式，其中+和*的操作数可以是任意数目的a或者是()括起的子表达式。但是*可以出现在结尾。这个文法显然是具有二义性的，例如字符串aaaaa就可以有很多解析树。同样aa+aaa+aaaaa这样的字符串也可以有很多解析树。
2.3 which of the grammar in Exercise 2.2 are ambiguous?
如上
2.4 Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct.
a) Arithmetic expressions in postfix notation.
expr → expr expr + | expr expr - | expr expr * | expr expr /| (expr) | digit
对后缀表达式来说，不可能产生结合性的问题，也没有优先级的问题，对四则运算总是两个操作数加上一个操作符，例如12+3+，3肯定属于它后面一个加号所要应用的操作数，不可能属于前面一个加号，优先级问题也一样。
b) Left-associative lists of identifiers separated by commas.
list → list , id | id
c) right-associative lists of identifiers separated by commas.
list → id , list | id
d) Arithmetic expressions of integers and identifiers with the four binary operators +,-,*,/
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → integer | id | (expr)
e) Add unary plus and minus to the arithmetic operators of (d).
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → + integer | - integer | integer | id | (expr)
*2.5 a) Show that all binary string generated by the following grammar hava values divisible by 3. Hint. Use induction on the number of nodes in a parse tree.
num → 11 | 1001 | num 0 | num num
写出计算数字值的语意动作
num → 11 {num.value = 3;} （1）
| 1001 {num.value = 9;} （2）
| num 0 {num2.value = num1.value*2;} （3）
| num num {num3.value = num1.value*2n + num2.value;} （4）
<1>
我们可以看到，如果一个字符串是通过（1）产生的，那么则为3，所以num为3的倍数，如果一个字符串是通过（2）产生的，即为9，所以也是3的倍数
<2>
现在假设现有的任何num字符串全部都是3的倍数，那么还有两种方法可以产生新的字符串
产生式(3) :由于现有所有的num都是3的倍数，因此num1.value是3的倍数，num1.value*2也是3的倍数，也就是说用产生式（3）产生的所有新的字符串都是3的倍数
产生式(4):由于现有所有的num都是3的倍数，因此num1.value和num2.value都是3的倍数，因此num1.value*2n也是3的倍数（n代表num2的长度），num1.value*2n + num2.value也是3的倍数，也就是说用产生式（4）产生的所有新的字符串都是3的倍数
<3>
从<1>得知，（1）和（2）产生的字符串都是3的倍数，从<2>得知，任何在3倍数的字符串基础上产生的新字符串都是3的倍数，所以所有该文法产生的字符串都是3的倍数，也就是能够被3整除。
b) Does the grammar generate all binary strings with values divisible by 3?
3的7倍为21=16+4+1，二进制表达方式为10101,无法用上面的文法产生
星期四, 十月 12, 2006
2.9 PUTTING THE TECHNIQUES TOGETHER
本章中，我们展现了一些用来构造一个编译器前端的语法导向技术。为了总结这些技术，我们把它们组合起来成为一个C程序，实现中缀到后缀表达式的翻译，语言由一系列用分号结束的表达式组成。表达式可以包含数字、标识符和操作符+,-,*,/,div和mod。翻译器的输出是每一个表达式的后缀表现形式。翻译器是在section 2.5-2.7开发的程序的一个扩展。完整的C程序在本节末尾。
Description of the Translator
这里设计的翻译器使用Fig. 2.35的translation scheme。
token id代表一个非空的字母和数字序列，以字母开始。num是一系列数字，而eof是文件结束字符。Token用空格、tab和新行分割（叫做空白)。id的属性lexeme是形成该token的字符串，而num的属性value是num代表的整数值。
翻译器的代码安排为7个模块，每一个在各自的文件中。执行从模块main.c开始，调用init进行初始化，接着调用parse()进行翻译。剩下的6个模块如Fig. 2.36所示。还有一个全局头文件global.h包含通用的定义，为多个模块所用；每一个模块的开始语句都是
#include "global.h"
.在显示翻译器的代码之前，我们大致描述一下每个模块。
The Lexical Analysis Module lexer.c
词法分析器是一个叫做lexan()的例程，解析器调用它寻找token。从Fig. 2.30的伪代码实现，例程每次从输入读入一个字符，把它找到的token返回给解析器。和该token相关的属性赋给一个全局变量tokenval.
解析器预期能够得到下面的token之一：
+ - * / DIV MOD ( ) ID NUM DONE
这里ID代表一个标识符，NUM代表一个数字，DONE代表文件结束字符。空白被词法分析器默默去掉了。Fig. 2.37的table显示对于每种源语言lexeme,词法分析器生成的token和属性值。
Fig 2.37 Description of tokens.
词法分析器使用符号表例程lookup来决定一个标识符lexeme是否已经碰到过，例程insert保存一个新的lexeme到符号表。它也增加一个全局lineno每次它看到一个新行字符。
The Parser Module parser.c
解析器使用Section 2.5的技术构造。我们首先从Fig. 2.35的translation scheme中排除左递归，这样下面的文法就能够用一个递归下降的解析器解析。转换后的文法如Fig. 2.38所示。
我们于是为非终结符expr,term,factor构造函数，就如我们在Fig. 2.24中所做的一样。函数parse()实现文法的start符号；它在需要一个新token的时候调用lexan。解析器使用函数emit生成输出，用函数error报告一个语法错误。
The Emitter Module emitter.c
emitter模块只包含一个函数emit(t,tval)为具有属性tval的token生成输出。
The Symbol-Table Modules symbol.c and init.c
符号表模块symbol.c 实现了section 2.7中Fig 2.29的数据结构。数组symtable中的条目由一个对组成，一个指向lexemes数组的指针和一个保存在此处的token整数。 操作insert(s,t)返回lexeme s形成的token t的符号表索引。函数lookup(s)返回symtable中条目的索引，对于lexeme s，如果不存在，则返回0。
模块init.c用来预加载symtable中的关键字。所有关键字的lexeme和token代表保存在数组keywords中，它 具有和symtable数组相同的类型。函数init()从keyword数组开始，是用函数insert在符号表中放入关键字。这种安排允许我们用一种方便的办法改变关键字token的表现形式。
The Error Module error.c
错误模块管理错误报告，非常原始。
在碰到一个语法错误时，编译器打印一个消息说一个错误已经发生在当前输入行并退出。一个更好的错误恢复技术可能是跳过下一个分号，并继续进行解析；我们鼓励读者对翻译器进行这样的修改。更加成熟的错误恢复技术在第4章讨论。
Creating the Compiler
模块代码出现在7个文件中：lexer.c, parser.c, emitter.c, symbol.c, init.c, error.c和main.c。文件main.c包含C程序的主例程，它调用init()，然后是parse()，exit(0)成功退出。
在UNIX操作系统下，编译器可以用下面的命令创建：
cc lexer.c parser.c emitter.c symbol.c init.c error.c main.c
或者单独编译文件，用
cc -c filename.c
然后连接起来
cc lexer.o parser.o emitter.o symbol.o init.o error.o main.o
cc命令创建一个文件a.out包含翻译器。翻译器可以通过输入a.out后跟要被翻译的表达式，例如：
2+3*5
12 div 5 mod 2;
Description of the Translator
这里设计的翻译器使用Fig. 2.35的translation scheme。
start → list eof
list → expr; list
| ε
expr → expr + term {print('+') }
| expr - term {print('-')}
| term
term → term * factor {print('*')}
| term / factor {print('/')}
| term div factor {print('DIV')}
| term mod factor {print('MOD')}
| factor
factor → ( expr )
| id { print(id.lexeme) }
| num { print(num.value) }
Fig. 2.35 Specification for infix-to-postfix translator
token id代表一个非空的字母和数字序列，以字母开始。num是一系列数字，而eof是文件结束字符。Token用空格、tab和新行分割（叫做空白)。id的属性lexeme是形成该token的字符串，而num的属性value是num代表的整数值。
翻译器的代码安排为7个模块，每一个在各自的文件中。执行从模块main.c开始，调用init进行初始化，接着调用parse()进行翻译。剩下的6个模块如Fig. 2.36所示。还有一个全局头文件global.h包含通用的定义，为多个模块所用；每一个模块的开始语句都是
#include "global.h"
.在显示翻译器的代码之前，我们大致描述一下每个模块。
The Lexical Analysis Module lexer.c
词法分析器是一个叫做lexan()的例程，解析器调用它寻找token。从Fig. 2.30的伪代码实现，例程每次从输入读入一个字符，把它找到的token返回给解析器。和该token相关的属性赋给一个全局变量tokenval.
解析器预期能够得到下面的token之一：
+ - * / DIV MOD ( ) ID NUM DONE
这里ID代表一个标识符，NUM代表一个数字，DONE代表文件结束字符。空白被词法分析器默默去掉了。Fig. 2.37的table显示对于每种源语言lexeme,词法分析器生成的token和属性值。
| LEXEME | TOKEN | ATTRIBUTE VALUE |
|---|---|---|
| 空白................................ | ||
| 数字序列........................ | NUM | 序列的数字值 |
| div.................................. | DIV | |
| mod............................... | MOD | |
| 其它一个字母后跟字母 和数字........................... | ID | symtable中的索引 |
| 文件结束字符............... | DONE | |
| 任何其他字符............... | 该字符 | NONE |
Fig 2.37 Description of tokens.
词法分析器使用符号表例程lookup来决定一个标识符lexeme是否已经碰到过，例程insert保存一个新的lexeme到符号表。它也增加一个全局lineno每次它看到一个新行字符。
The Parser Module parser.c
解析器使用Section 2.5的技术构造。我们首先从Fig. 2.35的translation scheme中排除左递归，这样下面的文法就能够用一个递归下降的解析器解析。转换后的文法如Fig. 2.38所示。
start → list eof
list → expr; list
| ε
expr → term moreterms
moreterms → + term {print('+') } moreterms
| - term {print('-') } moreterms
| ε
term → factor morefactors
morefactors → * factor {print('*')} morefactors
| / factor {print('/')} morefactors
| div factor {print('DIV')} morefactors
| mod factor {print('MOD')} morefactors
| ε
factor → (expr)
| id { print(id.lexeme) }
| num { print(num.value) }
Fig. 2.38 Syntax-directed translation scheme after eliminating left-recursive
我们于是为非终结符expr,term,factor构造函数，就如我们在Fig. 2.24中所做的一样。函数parse()实现文法的start符号；它在需要一个新token的时候调用lexan。解析器使用函数emit生成输出，用函数error报告一个语法错误。
The Emitter Module emitter.c
emitter模块只包含一个函数emit(t,tval)为具有属性tval的token生成输出。
The Symbol-Table Modules symbol.c and init.c
符号表模块symbol.c 实现了section 2.7中Fig 2.29的数据结构。数组symtable中的条目由一个对组成，一个指向lexemes数组的指针和一个保存在此处的token整数。 操作insert(s,t)返回lexeme s形成的token t的符号表索引。函数lookup(s)返回symtable中条目的索引，对于lexeme s，如果不存在，则返回0。
模块init.c用来预加载symtable中的关键字。所有关键字的lexeme和token代表保存在数组keywords中，它 具有和symtable数组相同的类型。函数init()从keyword数组开始，是用函数insert在符号表中放入关键字。这种安排允许我们用一种方便的办法改变关键字token的表现形式。
The Error Module error.c
错误模块管理错误报告，非常原始。
在碰到一个语法错误时，编译器打印一个消息说一个错误已经发生在当前输入行并退出。一个更好的错误恢复技术可能是跳过下一个分号，并继续进行解析；我们鼓励读者对翻译器进行这样的修改。更加成熟的错误恢复技术在第4章讨论。
Creating the Compiler
模块代码出现在7个文件中：lexer.c, parser.c, emitter.c, symbol.c, init.c, error.c和main.c。文件main.c包含C程序的主例程，它调用init()，然后是parse()，exit(0)成功退出。
在UNIX操作系统下，编译器可以用下面的命令创建：
cc lexer.c parser.c emitter.c symbol.c init.c error.c main.c
或者单独编译文件，用
cc -c filename.c
然后连接起来
cc lexer.o parser.o emitter.o symbol.o init.o error.o main.o
cc命令创建一个文件a.out包含翻译器。翻译器可以通过输入a.out后跟要被翻译的表达式，例如：
2+3*5
12 div 5 mod 2;
星期二, 十月 10, 2006
2.8 ABSTRACT STACK MACHINE
一个编译器的前端构造源程序的中间表现形式，后端从它来生成目标程序。一个比较流行的中间代表是一种抽象栈机器的代码。如同第1章所说，把一个编译器分为前端和后端，让编译器在新机器上运行的时候修改更加简单。
本节中，我们将展现一种抽象栈机器，并显示如何为它生成代码。该机器有独立的指令和数据内存，所有的算术运算都对栈上的值进行。指令非常有限，分为3类：整数运算，栈操纵和控制流。Fig 2.31演示该机器。pc指针标示我们即将执行的指令。指令的含义后面马上讨论。
pc指针是我们将要执行的指令。指令的含义很快将在后面讨论。
Arithmetic Instructions
抽象机器必须实现中间语言的每一个操作符。一个基本的操作符，例如加或者减，被抽象机器直接支持。但是，更加复杂的操作符，可能需要被实现为一个抽象机器指令的序列。我们简化机器的描述，通过假设每一个算术操作符都有对应的抽象机器指令。
一个算术表达式的抽象机器代码用一个栈模拟了该表达式后缀表现形式的计算。计算过程从左到右处理后缀表达形式，碰到操作数就把它压入栈中。在碰到一个k-ary的操作符时，它最左边的参数是栈顶下面k-1位置，而最右边的参数是栈顶。计算把操作符应用到栈顶的k个值，弹出操作数，然后把结果压回栈。例如，在计算后缀表达式1 3 + 5 *，执行下面的动作：
最后留在栈顶的值（这里的20）就是整个表达式的值。
在中间语言中，所有的值都是整数，其中0对应false，而非零对应true。boolean操作符and 和or需要他们的参数都被计算。
L-values and R-values
赋值左边和右边的标识符具有不同的含义。在每一个赋值中：
i := 5;
i := i + 1;
右边指定一个整数值，而左边指定值将被存储的地方。类似的，如果p和q是指向字符的指针，而且
p↑ := q↑;
右边q↑指定一个字符，而p↑指定字符将要被保存的地方。术语l-value左值和r-value右值，分别指一个赋值的左边和右边的值。也就是，我们通常把r-value考虑为值，而把l-value考虑为位置。
Stack Manipulation
除了把一个整数常量压到栈上以及从栈顶弹出一个值这些明显的指令之外，还有一些指令用来存取数据内存：
push v 把v压入栈
rvalue l 压入数据位置l的内容
lvalue l 压入数据位置l的地址
pop 丢掉栈顶值
:= 栈顶的rvalue放入它下面的lvalue中，两者都被弹出
copy 压入一个栈顶值的拷贝
Translation of Expressions
在一个栈机器计算一个表达式的代码和该表达式的后缀记法紧密相关。按照定义，表达式E + F的后缀形式是E的后缀形式，F的后缀形式，以及+的连接。类似的，计算E+F的栈机器代码，是计算E的代码，计算F的代码，以及增加他们值的指令的连接。把表达式翻译为栈机器代码，因此可以通过修改Section 2.6和2.7的翻译器完成。
这里我们为表达式生成栈代码，其中的数据位置用符号地址（标识符的数据位置分配在第7章讨论）。表达式a+b翻译为：
把赋值翻译为栈机器代码的过程如下：
分配给标识符的l-value被压入栈，表达式被计算，它的右值被分配给标识符。例如，赋值
翻译为Fig. 2.32的代码
形式化的表达如下。每一个非终结符具有一个属性t给出他的翻译。id的属性lexeme给出这个标识符的字符串表现形式
stmt → id := expr
{ stmt.t := 'lvalue' || id.lexeme || expr.t || ':='}
Control Flow
栈机器按照数字序列执行指令，除非用一个条件或无条件跳转指令告诉它其它事情。可以用几种方法指定跳转的目标：
我们为抽象机器选择第3种选择，因为容易生成这样的跳转。另外，如果我们之后为抽象机器生成代码，不需要对符号地址进行改变，我们在代码中进行一定的改进，导致指令的插入和删除。
栈机器的控制流指令是：
label l 掉转到l的目标，没有其它影响
goto l 下一条指令取自具有label l 的语句
gofalse l 弹出栈顶值，为0则跳转
gotrue l 弹出栈顶值，非0则跳转
halt 停止执行
Translation of Statements
Fig. 2.33的布局勾勒了条件语句和while语句的抽象机器代码。下面的讨论集中在如何创建label标签。
考虑Fig. 2.33中if语句的代码布局。在一个源程序的翻译中，只能有一条label out指令，不然的话goto out语句就不知道跳转到哪个out去了。因此，我们需要某中机制，每次一个if语句被翻译的时候，生成一个唯一的标签。
假设newlabel是一个每次被调用就返回一个新标签的过程。在下面的语义动作中，对newlabel调用返回的新标签用一个局部变量out纪录下来：
Emitting a Translation
Section 2.5中表达式翻译器使用print语句增量地生成一个表达式的翻译。类似的print语句可以用来生成语句的翻译。取代print语句，我们用一个过程emit来隐藏打印的细节。例如，emit能够关心是否每一条抽象机器指令需要在单独的一行。使用过程emit，我们可以把(2.18)写成。
当语义动作出现在一个产生式中间时，我们用从左到右的顺序考虑产生式的右边。对上面的产生式，动作的顺序如下：在expr解析动作完成后，out被设置为newlabel返回的标签，gofalse指令被输出，stmt1解析动作完成后，最后label指令被输出。假设expr和stmt1输出这些非终结符的代码，那么上面的产生式实现Fig. 2.33的代码布局。
Fig 2.34. Pseudo-code for translating statements.
翻译赋值语句和条件语句的伪代码如Fig 2.34所示。因为变量是过程stmt的局部变量，它的值不受对expr和stmt过程的调用。标签的生成需要一些考虑。假设翻译中的标签是L1, L2,.....。操纵这样标签的伪代码使用L后跟整数。因此，out被定义为一个整数，newlabel返回一个整数变成out的值，emit用这个整数输出标签。
while语句的代码布局也可以用类似的方法产生。对一系列语句的翻译就是简单地把序列的语句串起来。
绝大多数单入口，但出口的构造都可以类似while语句一样翻译。我们通过考虑表达式中的控制流来演示这一点。
Example 2.10 Section 2.7的词法分析器包含一个条件，以下形式：
if t == blank or t == tab then
如果t是一个空格，那么显然没有必要检查t是否一个tab，因为第一个等号已经隐含条件为真。表达式
epr1 or expr2
因此可以实现为
if expr1 the true else expr2
读者可以检查下面的操作实现or操作符：
code for expr1
copy
gotrue out
pop
code for expr2
lable out
回忆一下，为了简化条件和while语句的代码生成，gotrue和gofalse指令弹出栈顶值。通过copy expr1的值，我们确保栈顶的值为true，如果gotrue指令导致一个跳转的话。
本节中，我们将展现一种抽象栈机器，并显示如何为它生成代码。该机器有独立的指令和数据内存，所有的算术运算都对栈上的值进行。指令非常有限，分为3类：整数运算，栈操纵和控制流。Fig 2.31演示该机器。pc指针标示我们即将执行的指令。指令的含义后面马上讨论。
pc指针是我们将要执行的指令。指令的含义很快将在后面讨论。
Arithmetic Instructions
抽象机器必须实现中间语言的每一个操作符。一个基本的操作符，例如加或者减，被抽象机器直接支持。但是，更加复杂的操作符，可能需要被实现为一个抽象机器指令的序列。我们简化机器的描述，通过假设每一个算术操作符都有对应的抽象机器指令。
一个算术表达式的抽象机器代码用一个栈模拟了该表达式后缀表现形式的计算。计算过程从左到右处理后缀表达形式，碰到操作数就把它压入栈中。在碰到一个k-ary的操作符时，它最左边的参数是栈顶下面k-1位置，而最右边的参数是栈顶。计算把操作符应用到栈顶的k个值，弹出操作数，然后把结果压回栈。例如，在计算后缀表达式1 3 + 5 *，执行下面的动作：
- Stack 1
- Stack 3
- 把最顶上的两个成员相加，弹出它们，把结果4压回栈
- Stack 5
- 把最顶上的两个成员相乘，弹出它们，把结果20压回栈
最后留在栈顶的值（这里的20）就是整个表达式的值。
在中间语言中，所有的值都是整数，其中0对应false，而非零对应true。boolean操作符and 和or需要他们的参数都被计算。
L-values and R-values
赋值左边和右边的标识符具有不同的含义。在每一个赋值中：
i := 5;
i := i + 1;
右边指定一个整数值，而左边指定值将被存储的地方。类似的，如果p和q是指向字符的指针，而且
p↑ := q↑;
右边q↑指定一个字符，而p↑指定字符将要被保存的地方。术语l-value左值和r-value右值，分别指一个赋值的左边和右边的值。也就是，我们通常把r-value考虑为值，而把l-value考虑为位置。
Stack Manipulation
除了把一个整数常量压到栈上以及从栈顶弹出一个值这些明显的指令之外，还有一些指令用来存取数据内存：
push v 把v压入栈
rvalue l 压入数据位置l的内容
lvalue l 压入数据位置l的地址
pop 丢掉栈顶值
:= 栈顶的rvalue放入它下面的lvalue中，两者都被弹出
copy 压入一个栈顶值的拷贝
Translation of Expressions
在一个栈机器计算一个表达式的代码和该表达式的后缀记法紧密相关。按照定义，表达式E + F的后缀形式是E的后缀形式，F的后缀形式，以及+的连接。类似的，计算E+F的栈机器代码，是计算E的代码，计算F的代码，以及增加他们值的指令的连接。把表达式翻译为栈机器代码，因此可以通过修改Section 2.6和2.7的翻译器完成。
这里我们为表达式生成栈代码，其中的数据位置用符号地址（标识符的数据位置分配在第7章讨论）。表达式a+b翻译为：
rvalue a
rvalue b
+
把赋值翻译为栈机器代码的过程如下：
分配给标识符的l-value被压入栈，表达式被计算，它的右值被分配给标识符。例如，赋值
day := (1461*y) div 4 + (153*m + 2) div 5 + d (2.17)
翻译为Fig. 2.32的代码
lvalue day
push 1461
rvalue y
*
push 4
div
push 153
rvalue m
*
push 2
+
push 5
div
+
rvalue d
+
:=
Fig. 2.32 Translation of day := (1461*y) div 4 + (153*m + 2) div 5 + d
形式化的表达如下。每一个非终结符具有一个属性t给出他的翻译。id的属性lexeme给出这个标识符的字符串表现形式
stmt → id := expr
{ stmt.t := 'lvalue' || id.lexeme || expr.t || ':='}
Control Flow
栈机器按照数字序列执行指令，除非用一个条件或无条件跳转指令告诉它其它事情。可以用几种方法指定跳转的目标：
- 指令操作数给出目标位置
- 指令操作数指定跳转的相对位置，正的或负的
- 用符号指定目标，也就是是说，机器支持标签
我们为抽象机器选择第3种选择，因为容易生成这样的跳转。另外，如果我们之后为抽象机器生成代码，不需要对符号地址进行改变，我们在代码中进行一定的改进，导致指令的插入和删除。
栈机器的控制流指令是：
label l 掉转到l的目标，没有其它影响
goto l 下一条指令取自具有label l 的语句
gofalse l 弹出栈顶值，为0则跳转
gotrue l 弹出栈顶值，非0则跳转
halt 停止执行
Translation of Statements
Fig. 2.33的布局勾勒了条件语句和while语句的抽象机器代码。下面的讨论集中在如何创建label标签。
考虑Fig. 2.33中if语句的代码布局。在一个源程序的翻译中，只能有一条label out指令，不然的话goto out语句就不知道跳转到哪个out去了。因此，我们需要某中机制，每次一个if语句被翻译的时候，生成一个唯一的标签。
假设newlabel是一个每次被调用就返回一个新标签的过程。在下面的语义动作中，对newlabel调用返回的新标签用一个局部变量out纪录下来：
stmt → if expr then stmt1 { out := newlabel;
stmt.t := expr.t ||
'gofalse' out || (2.18)
stmt1.t ||
'label' out}
Emitting a Translation
Section 2.5中表达式翻译器使用print语句增量地生成一个表达式的翻译。类似的print语句可以用来生成语句的翻译。取代print语句，我们用一个过程emit来隐藏打印的细节。例如，emit能够关心是否每一条抽象机器指令需要在单独的一行。使用过程emit，我们可以把(2.18)写成。
stmt → if
expr { out := newlabel; emit('gofalse', out); }
then
stmt1 {emit('label', out); }
当语义动作出现在一个产生式中间时，我们用从左到右的顺序考虑产生式的右边。对上面的产生式，动作的顺序如下：在expr解析动作完成后，out被设置为newlabel返回的标签，gofalse指令被输出，stmt1解析动作完成后，最后label指令被输出。假设expr和stmt1输出这些非终结符的代码，那么上面的产生式实现Fig. 2.33的代码布局。
procedure stmt;
var out:integer;
begin
if lookahead = id then begin
emit('lvalue', tokenval);match(id);match(':=');expr
end
else if lookahead='if' then begin
match('if');
expr;
out := newlabel;
emit('goflase', out);
match('then');
stmt;
emit('label', out);
end
/* code for remaining statements goes here */
else error;
end
Fig 2.34. Pseudo-code for translating statements.
翻译赋值语句和条件语句的伪代码如Fig 2.34所示。因为变量是过程stmt的局部变量，它的值不受对expr和stmt过程的调用。标签的生成需要一些考虑。假设翻译中的标签是L1, L2,.....。操纵这样标签的伪代码使用L后跟整数。因此，out被定义为一个整数，newlabel返回一个整数变成out的值，emit用这个整数输出标签。
while语句的代码布局也可以用类似的方法产生。对一系列语句的翻译就是简单地把序列的语句串起来。
绝大多数单入口，但出口的构造都可以类似while语句一样翻译。我们通过考虑表达式中的控制流来演示这一点。
Example 2.10 Section 2.7的词法分析器包含一个条件，以下形式：
if t == blank or t == tab then
如果t是一个空格，那么显然没有必要检查t是否一个tab，因为第一个等号已经隐含条件为真。表达式
epr1 or expr2
因此可以实现为
if expr1 the true else expr2
读者可以检查下面的操作实现or操作符：
code for expr1
copy
gotrue out
pop
code for expr2
lable out
回忆一下，为了简化条件和while语句的代码生成，gotrue和gofalse指令弹出栈顶值。通过copy expr1的值，我们确保栈顶的值为true，如果gotrue指令导致一个跳转的话。
2.7 INCORPORATING A SYMBOL TABLE
一个叫做符号表的数据结构通常用来保存各种语言构造的信息。信息被编译器的分析阶段收集，并且被合成阶段用来生成目标代码。例如，在词法分析阶段，字符串，或者lexeme，形成的标识符被保存为符号表的一个条目。编译器的后面阶段可能向这个条目增加信息，例如标识符的类型，他的用法（例如，procedure，variable或者label),以及它在存储中的位置。代码生成阶段将使用这些信息生成合适的代码来保存和存取这个变量。在7.6中，我们将详细讨论符号表的实现和使用。在本节中，显示词法分析器如何和一个符号表交互。
The Symbol-Table Interface
符号表例程主要和保存和获取lexeme相关。当一个lexeme被保存的时候，我们也保存和lexeme相关的token。下面的操作将在符号表上被执行。
insert(s,t): 返回字符串s相关的新条目的索引，token t
lookup(s): 返回字符串s的条目的索引，返回0如果没有找到。
词法分析器使用lookup操作判断符号表中是否存在一个lexeme的对应条目。如果不存在，那么它使用insert操作去创建一个。我们应该讨论一个实现，其中词法分析器和解析器都知道符号表条目的格式。
Handling Reserved Keywords
上面的符号表例程能够处理任意的保留关键字集合。例如，考虑div和mod这两个token分别具有lexme div和mod。我们可以使用下面的调用初始化符号表
insert("div", div);
insert("mod", mod);
任何后面对lookup("div")的调用都将返回token div，因此div不能用作一个标识符。
任何保留关键字的集合都可以这样处理，通过适当地初始化符号表。
A Symbol-Table Implementation
一个特定符号表的一个特定实现的数据结构勾勒在Fig. 2.29中。
我们不希望设置一个固定的空间来保存lexemes形成的标识符，固定数量的空间可能不够大以容纳一个非常长的标识符，而对比较短的标识符可能太浪费了，例如i。在Fig. 2.29中，一个单独的数组lexemes用来保存形成一个标识符的那些字符串。字符串以字符结束字符结束，即EOS，不会出现在任何标识符中。符号表数组symtable中的每一个条目是一个包含两个字段的记录，lexptr，指向一个lexeme的开始，以及token。额外的字段可以容纳属性值，虽然我们这里不需要这样做。
在Fig. 2.29中，第0个条目保留为空，因为lookup返回0表示没有一个字符串对应的条目。第1和第2条目分别对应关键字div和mod。而第3和第4条分别对应标识符count和i.
处理标识符的一个词法分析器的伪代码如Fig. 2.30所示；一个C实现在Section 2.9中。空白和整数常量被词法分析器用上一节Fig. 2.28一样的方式处理。
当我们的词法分析器读到一个字母时，它开始在一个缓冲区lexbuf中保存字母和数字。在lexbuf中搜集好的字符串在符号表中进行lookup。因为符号表中已经初始化了关键字div和mod，因此如果lexbuf中是div或者mod，那么就会返回相应的条目。如果找补到，那么lexbuf包含一个新标识符的新lexme。使用insert插入一个新条目，p是这个新条目在符号表中的索引。该索引通过设置tokenval=p和解析器通讯，该条目的token字段被返回。
缺省的动作是返回字符的整数编码。既然单个字符的token在这里没有属性，tokenval设置为NONE。
The Symbol-Table Interface
符号表例程主要和保存和获取lexeme相关。当一个lexeme被保存的时候，我们也保存和lexeme相关的token。下面的操作将在符号表上被执行。
insert(s,t): 返回字符串s相关的新条目的索引，token t
lookup(s): 返回字符串s的条目的索引，返回0如果没有找到。
词法分析器使用lookup操作判断符号表中是否存在一个lexeme的对应条目。如果不存在，那么它使用insert操作去创建一个。我们应该讨论一个实现，其中词法分析器和解析器都知道符号表条目的格式。
Handling Reserved Keywords
上面的符号表例程能够处理任意的保留关键字集合。例如，考虑div和mod这两个token分别具有lexme div和mod。我们可以使用下面的调用初始化符号表
insert("div", div);
insert("mod", mod);
任何后面对lookup("div")的调用都将返回token div，因此div不能用作一个标识符。
任何保留关键字的集合都可以这样处理，通过适当地初始化符号表。
A Symbol-Table Implementation
一个特定符号表的一个特定实现的数据结构勾勒在Fig. 2.29中。
我们不希望设置一个固定的空间来保存lexemes形成的标识符，固定数量的空间可能不够大以容纳一个非常长的标识符，而对比较短的标识符可能太浪费了，例如i。在Fig. 2.29中，一个单独的数组lexemes用来保存形成一个标识符的那些字符串。字符串以字符结束字符结束，即EOS，不会出现在任何标识符中。符号表数组symtable中的每一个条目是一个包含两个字段的记录，lexptr，指向一个lexeme的开始，以及token。额外的字段可以容纳属性值，虽然我们这里不需要这样做。
在Fig. 2.29中，第0个条目保留为空，因为lookup返回0表示没有一个字符串对应的条目。第1和第2条目分别对应关键字div和mod。而第3和第4条分别对应标识符count和i.
处理标识符的一个词法分析器的伪代码如Fig. 2.30所示；一个C实现在Section 2.9中。空白和整数常量被词法分析器用上一节Fig. 2.28一样的方式处理。
function lexan:integer;
var lexbuf: array[0..100] of char;
c: char;
begin
read a character into c;
if c is a blank or a tab then
do nothing
else if c is a newline then
lineno := lineno + 1
else if c is a digit then begin
set tokenval to the value of this and following digits;
return NUM
end
else if c is a letter then begin
place c and successive letters and digits into lexbuf;
p := lookup(lexbuf);
if p = 0 then
p := insert(lexbuf, ID);
tokenval := p;
return the token field of table entry p
end
else begin /* token is a single character */
set tokenval to NONE;
return integer encoding of character c
end
end
当我们的词法分析器读到一个字母时，它开始在一个缓冲区lexbuf中保存字母和数字。在lexbuf中搜集好的字符串在符号表中进行lookup。因为符号表中已经初始化了关键字div和mod，因此如果lexbuf中是div或者mod，那么就会返回相应的条目。如果找补到，那么lexbuf包含一个新标识符的新lexme。使用insert插入一个新条目，p是这个新条目在符号表中的索引。该索引通过设置tokenval=p和解析器通讯，该条目的token字段被返回。
缺省的动作是返回字符的整数编码。既然单个字符的token在这里没有属性，tokenval设置为NONE。
星期五, 十月 06, 2006
2.6 LEXICAL ANALYSIS
我们现在应该在翻译器中加入一个词法分析器，读取并把输入转换成token流。回忆Section 2.2中的一个文法定义，一种语言的语句由token字符串组成。组成一个单独的token的一个输入字符序列叫做一个Lexeme。一个词法分析器可以把一个解析器和token的lexeme表现形式隔离开来。我们开始列出某些函数，词法分析器需要执行的。
Removal of White Space and Comments
上一节中的表达式翻译器看到输入的每一个字符，所以额外的字符，例如空白，将导致失败。许多语言，允许“空白”(空格、tab和新行)出现在token之间。注释也通常被解析器和翻译器忽略，所以他们也可以被对待为空白。
如果空白被词法分析器排除，那么解析器将不需要考虑它们。不然就需要修改文法，加入对空白的处理，但非常难以实现。
Constants
任何时候当一个数字出现在表达式中时，看起来在这个出现的位置允许一个任意数目的整数常量是应该的。因为一个整数常量是一个数字序列，整数常量可以被允许要么向表达式文法中加入过程，要么为这样的常量创建一个token。通常，收集数字为整数的任务是词法分析器的，因为数字可以被对待为一个单一的单元，在翻译过程中。
让num是代表整数的token。当一个数字序列出现在输入流中，词法分析器将把num传递给parser.整数的值作为num token的一个属性一起传送过去。逻辑上，词法分析器可以同时把token和属性传输过去。如果，我们写一个token和他的属性为一个tuple，用<>，那么输入
31 + 28 + 59
将被翻译为tuples:
<num, 31> <+, > <num, 28> <+, > <num, 59>
+ 这个token没有任何属性。tuple的第二个元素，属性，在解析的过程中不承担任何角色，但是在翻译时需要
Recognizing Identifiers and Keywords
语言使用标识符作为变量、数组和函数的名字。一种语言的文法通常把一个标识符对待为一个token。基于这样一个文法的解析器想看到相同的文法，例如id，每次在输入中看到一个标识符的时候。例如，输入：
count = count + increment; (2.15)
会被词法分析器转换为token流：
id = id + id ; (2.16)
这个token流用作解析。
当谈论输入行(2.15)的词法分析时，有必要区分token id和 与这个token实例相关的lexeme－ count 和increment之间的区别。翻译器需要知道(2.16)中，前两个id实例的lexeme 是count，第三个id实例是lexeme increment.
当一个lexeme形成一个标识符在输入中被看到的时候，某些机制被需要去决定这个lexeme是否在以前被看倒过。第一章介绍过的符号表就是这样的一种机制。lexeme保存在符号表中，指向这个符号表项的一个指针变成这个token id的一个属性。
许多语言使用固定的字符串例如begin, end ,if等等，作为标点符号，或者指定一定的构造。这个字符串，称为关键字keywords，一般满足形成标识符的规则，因此需要有一种机制决定一个lexeme是一个关键字还是一个标识符。如果关键字是保留的，reserved，那么比较容易解决，也就是说，它们不能被用作为标识符。那么一个字符串只有不是关键字的时候才能作为一个标识符使用。
隔离token的问题也会发生，如果出现在lexeme中的相同的字符可以出现在多个token中，例如Pascal的< , <=和<>。高效识别这些token的技术将在Chapter3中讨论。
Interface to the Lexical Analyzer
当一个词法分析器被插入到解析器和输入流之间的时候，他可以象图2.25一样和两个交互。
它从输入读取字符，把它们分组为lexeme，然后把lexemes形成的token和他们的属性传递给编译器的后面阶段。在这样的情况下，词法分析器必须在决定返回给解析器什么token之前，预先读取某些字符。例如，一个Pascal的词法分析器必须预先读取，在它看到字符>之后。如果下一个字符是=，那么字符序列>=是形成"大于等于"操作符的lexeme。如果不是的情况下，它必须把这个字符放回到输入，因为它应该是下一个lexeme的开始字符。
词法分析器和解析器形成一个生产者－消费者对。procedure-consumer pair.词法分析器生产token，解析器消费它们。被生成的token可以放在一个token缓冲区中，直到它们被消费。两者之间的交互只受缓冲区大小的约束，因为词法分析器不能前进，当缓冲区满的时候，解析器也不能前进，如果buffer是空的。通常，buffer只包含一个token。此时，交互可以通过让词法分析器成为被解析器调用的过程简单地实现，按需返回token。
读取和退回字符通常用一个输入缓冲区来实现。每次，一个字符块被读入到缓冲区中，一个指针跟踪输入中已经被分析的部分。回退一个字符只需要指针向后移动即可。输入字符也可能用于错误报告而进行保存，因为需要给出错误出现的输入文本位置。单单出于效率考虑，对输入字符进行缓存也是有意义的。获取一块
A Lexical Analyzer
我们现在为2.5节的表达式翻译器构造一个初级的词法分析器。词法分析器的目的是为了允许空白和数字出现在表达式中。下一节中，我们会扩展词法分析器允许使用标识符。
Fig. 2,26 建议词法分析器如何来实现Fig2.25中的交互，写作C语言的函数lexan。例程getchar()和ungetc来自包含文件<stdio.h>小心处理输入缓冲；lexan通过调用getchar和ungetc实现相应的读取和退回输入字符。如果c声明为一个字符，下面的语句
c = getchar(); ungetc(c, stdin);
等于让输入没有任何变化。
如果实现的语言不允许从函数返回数据结构，那么token和他们的属性必须单独传输。lexan函数返回token的一个整数编码。一个字符的token可以是该字符的证书编码。一个token，例如num，因此可以编码为任何大于字符编码的整数，例如256。为了允许编码容易改变，我们用一个符号常量NUM来引用num的整数编码。在Pascal中，NUM和编码之间的关系可以用const声明，在C中，NUM可以用一个define语句。
#define NUM 256
函数lexan返回NUM当一个数字序列在输入中被看到时。一个全局变量tokenval的值被设置为数字序列的值。因此，如果7后面是一个6，那么tokenval的值就是整数值76,
允许数字出现在表达式中需要对Fig 2.19的文法做一个改变。我们可以用非终结符factor替换单个数字，并且介入下面的产生式和语义动作：
factor → （expr)
| num {print(num.val)}
Fig2.27 中factor的C代码是上面产生式的直接实现。
factor() {
if (lookahead = '(') {
match('(');expr();match(')');
} else if (lookahead == NUM) {
printf(" %d ", tokenval);match(NUM);
}
else error();
}
Fig. 2.27 C code for factor when operands can be numbers.
当lookahead等于NUM的时候，属性值num.val已经给了全局变量tokenval.打印这个值的动作是通过标准函数printf实现的。
lexan()函数的实现如图2.28所示。每次第8－18行的while语句被执行，一个字符就被第9行读入。如果字符是一个空格或者tab，那么没有token返回到解析器，我们只是继续进行循环。如果字符是一个新行，全局变量lineno被增加，跟踪输入中的行数，但是也不会返回token。错误信息提供行号可以帮助找到错误。
读取一系列数字的代码是14-23行。，isdigit(t)判断一个进入的字符是否一个数字。如果是的话，那么它的整数值被给于t-'0'对ASCII码和EBCDIC而言。对于其它字符集，转换的方式可能会有所不同。在2.9节中，我们把这个词法分析器合并到我们的表达式翻译器中。
Removal of White Space and Comments
上一节中的表达式翻译器看到输入的每一个字符，所以额外的字符，例如空白，将导致失败。许多语言，允许“空白”(空格、tab和新行)出现在token之间。注释也通常被解析器和翻译器忽略，所以他们也可以被对待为空白。
如果空白被词法分析器排除，那么解析器将不需要考虑它们。不然就需要修改文法，加入对空白的处理，但非常难以实现。
Constants
任何时候当一个数字出现在表达式中时，看起来在这个出现的位置允许一个任意数目的整数常量是应该的。因为一个整数常量是一个数字序列，整数常量可以被允许要么向表达式文法中加入过程，要么为这样的常量创建一个token。通常，收集数字为整数的任务是词法分析器的，因为数字可以被对待为一个单一的单元，在翻译过程中。
让num是代表整数的token。当一个数字序列出现在输入流中，词法分析器将把num传递给parser.整数的值作为num token的一个属性一起传送过去。逻辑上，词法分析器可以同时把token和属性传输过去。如果，我们写一个token和他的属性为一个tuple，用<>，那么输入
31 + 28 + 59
将被翻译为tuples:
<num, 31> <+, > <num, 28> <+, > <num, 59>
+ 这个token没有任何属性。tuple的第二个元素，属性，在解析的过程中不承担任何角色，但是在翻译时需要
Recognizing Identifiers and Keywords
语言使用标识符作为变量、数组和函数的名字。一种语言的文法通常把一个标识符对待为一个token。基于这样一个文法的解析器想看到相同的文法，例如id，每次在输入中看到一个标识符的时候。例如，输入：
count = count + increment; (2.15)
会被词法分析器转换为token流：
id = id + id ; (2.16)
这个token流用作解析。
当谈论输入行(2.15)的词法分析时，有必要区分token id和 与这个token实例相关的lexeme－ count 和increment之间的区别。翻译器需要知道(2.16)中，前两个id实例的lexeme 是count，第三个id实例是lexeme increment.
当一个lexeme形成一个标识符在输入中被看到的时候，某些机制被需要去决定这个lexeme是否在以前被看倒过。第一章介绍过的符号表就是这样的一种机制。lexeme保存在符号表中，指向这个符号表项的一个指针变成这个token id的一个属性。
许多语言使用固定的字符串例如begin, end ,if等等，作为标点符号，或者指定一定的构造。这个字符串，称为关键字keywords，一般满足形成标识符的规则，因此需要有一种机制决定一个lexeme是一个关键字还是一个标识符。如果关键字是保留的，reserved，那么比较容易解决，也就是说，它们不能被用作为标识符。那么一个字符串只有不是关键字的时候才能作为一个标识符使用。
隔离token的问题也会发生，如果出现在lexeme中的相同的字符可以出现在多个token中，例如Pascal的< , <=和<>。高效识别这些token的技术将在Chapter3中讨论。
Interface to the Lexical Analyzer
当一个词法分析器被插入到解析器和输入流之间的时候，他可以象图2.25一样和两个交互。
它从输入读取字符，把它们分组为lexeme，然后把lexemes形成的token和他们的属性传递给编译器的后面阶段。在这样的情况下，词法分析器必须在决定返回给解析器什么token之前，预先读取某些字符。例如，一个Pascal的词法分析器必须预先读取，在它看到字符>之后。如果下一个字符是=，那么字符序列>=是形成"大于等于"操作符的lexeme。如果不是的情况下，它必须把这个字符放回到输入，因为它应该是下一个lexeme的开始字符。
词法分析器和解析器形成一个生产者－消费者对。procedure-consumer pair.词法分析器生产token，解析器消费它们。被生成的token可以放在一个token缓冲区中，直到它们被消费。两者之间的交互只受缓冲区大小的约束，因为词法分析器不能前进，当缓冲区满的时候，解析器也不能前进，如果buffer是空的。通常，buffer只包含一个token。此时，交互可以通过让词法分析器成为被解析器调用的过程简单地实现，按需返回token。
读取和退回字符通常用一个输入缓冲区来实现。每次，一个字符块被读入到缓冲区中，一个指针跟踪输入中已经被分析的部分。回退一个字符只需要指针向后移动即可。输入字符也可能用于错误报告而进行保存，因为需要给出错误出现的输入文本位置。单单出于效率考虑，对输入字符进行缓存也是有意义的。获取一块
A Lexical Analyzer
我们现在为2.5节的表达式翻译器构造一个初级的词法分析器。词法分析器的目的是为了允许空白和数字出现在表达式中。下一节中，我们会扩展词法分析器允许使用标识符。
Fig. 2,26 建议词法分析器如何来实现Fig2.25中的交互，写作C语言的函数lexan。例程getchar()和ungetc来自包含文件<stdio.h>小心处理输入缓冲；lexan通过调用getchar和ungetc实现相应的读取和退回输入字符。如果c声明为一个字符，下面的语句
c = getchar(); ungetc(c, stdin);
等于让输入没有任何变化。
如果实现的语言不允许从函数返回数据结构，那么token和他们的属性必须单独传输。lexan函数返回token的一个整数编码。一个字符的token可以是该字符的证书编码。一个token，例如num，因此可以编码为任何大于字符编码的整数，例如256。为了允许编码容易改变，我们用一个符号常量NUM来引用num的整数编码。在Pascal中，NUM和编码之间的关系可以用const声明，在C中，NUM可以用一个define语句。
#define NUM 256
函数lexan返回NUM当一个数字序列在输入中被看到时。一个全局变量tokenval的值被设置为数字序列的值。因此，如果7后面是一个6，那么tokenval的值就是整数值76,
允许数字出现在表达式中需要对Fig 2.19的文法做一个改变。我们可以用非终结符factor替换单个数字，并且介入下面的产生式和语义动作：
factor → （expr)
| num {print(num.val)}
Fig2.27 中factor的C代码是上面产生式的直接实现。
factor() {
if (lookahead = '(') {
match('(');expr();match(')');
} else if (lookahead == NUM) {
printf(" %d ", tokenval);match(NUM);
}
else error();
}
Fig. 2.27 C code for factor when operands can be numbers.
当lookahead等于NUM的时候，属性值num.val已经给了全局变量tokenval.打印这个值的动作是通过标准函数printf实现的。
#include <stdio.h>
#include <ctype.h>
int lineno = 1;
int tokenval = NONE;
int lexan() {
int t;
while(1) {
t = getchar();
if(t == ' ' || t == '\t')
;
else if(t == '\n')
lineno = lineno + 1;
else if(isdigit(t))
{
tokenval = t - '0';
t = getchar();
while(isdigit(t)) {
tokenval = tokenval*10+ t - '0';
t = getchar();
}
ungetc(t, stdin);
return NUM;
} else {
tokenval = NONE;
return t;
}
}
}
Fig. 2.28
lexan()函数的实现如图2.28所示。每次第8－18行的while语句被执行，一个字符就被第9行读入。如果字符是一个空格或者tab，那么没有token返回到解析器，我们只是继续进行循环。如果字符是一个新行，全局变量lineno被增加，跟踪输入中的行数，但是也不会返回token。错误信息提供行号可以帮助找到错误。
读取一系列数字的代码是14-23行。，isdigit(t)判断一个进入的字符是否一个数字。如果是的话，那么它的整数值被给于t-'0'对ASCII码和EBCDIC而言。对于其它字符集，转换的方式可能会有所不同。在2.9节中，我们把这个词法分析器合并到我们的表达式翻译器中。
星期日, 十月 01, 2006
2.5 A TRANSLATOR FOR SIMPLE EXPRESSIONS
使用上面三节中的技术，我们可以构造一个语法导向的翻译器，以一个可工作C程序的形式，把算术表达式翻译成后缀形式。为了让开始的程序更小，我们开始的表达式只包含用加减号分开的数字。语言将在后面两节得到扩展，以包含数字，标识符和其他操作符。因为表达式在很多语言中出现，因此值得详细研究他们的翻译。
expr → expr + term {print('+')}
expr → expr - term {print('-')}
expr → term
term → 0 {print('0')}
term → 1 {print('1')}
term → 2 {print('2')}
.....
term → 9 {print('9')}
Fig. 2.19 Initial specification of infix-to-postfix translator
一个语法导向的translation scheme 通常能够作为一个翻译器的规格。我们使用Fig 2.19中的scheme(重复自Fig. 2.13)将被执行的翻译的定义。作为一种通常情况，一个给定scheme的下部文法必须被修改，在它能够作为一个predictive parser解析之前。特别，Fig 2.19中scheme之下的文法是左递归的，我们已经知道，一个predictive parser不能处理一个左递归文法。通过排除左递归，我们能够获得一个文法，适合在predictive 递归下降的翻译器中使用。
Abstract and Concrete Syntax
一种有用的考虑一个输入字符串的翻译的起点是一棵abstract syntax tree抽象语法树，其中每一个节点代表一个操作符，节点的子节点代表操作数。相反，一个解析树叫做concrete syntax tree具体语言树，下部的文法称为语言的concrete syntax具体语法。抽象语法树，或者简单地叫做语法树，和解析树不同，因为形式的表面不同，对于翻译并不重要，不会出现在语法树中。
例如，9-5+2的语法树如Fig. 2.20所示。因为+和-具有相同的优先级别，而相同优先级别的操作符从左到右计算，因此9-5组成一个子表达式。把Fig. 2.20和对应的解析树Fig. 2.2比较，我们注意到语法树把一个操作符和一个内部节点关联，而不是操作符变成子节点之一。
对一个translation scheme而言，它所基于的文法的解析树和语言树越接近越好。用Fig. 2.19 的文法对子表达式的分组类似于他们在语法树中的分组。不幸的是，Fig 2.19中的文法是左递归的，因此不适合predictive解析。看起来有点冲突，另一方面，我们需要一个文法能够方便解析，而另一方面要容易解析需要一个很大不同的文法。最明显的解决方案是排除左递归。但是，就象下面的例子一样，这种排除需要非常小心才能完成。
Example 2.9 下面的文法不适合用来把表达式翻译成后缀形式，即使它确实生成了Fig 2.19文法的相同语言，并且可以用来进行递归下降解析。
expr → term rest
rest → + expr | - expr | ε
term → 0 | 1 | ... | 9
该文法的问题是rest → + expr 和rest - expr 生成的操作符的操作数不明显。选择下面的任意一个，从expr.t翻译rest.t方法都是不可接受的。
rest → - expr {rest.t := '-' || expr.t} (2.12)
rest → - expr {rest.t := expr.t || '-' } (2.13)
(我们只显示了减法操作符的产生式和语义动作)。从9-5的翻译应该是95-。但是，如果我们使用(2.12)的动作，那么减法符号将在expr.t之前出现，因此9-5错误地在翻译后依旧保持9-5。
另一方面，如果我们使用(2.13)，那么操作符将一致地移到右端，那么9-5+2将错误地翻译成为952+-(正确的翻译应该是95-2+)。
Adapting the Translation Scheme
Fig. 2.18画出的左递归排除也可以运用到包含语义动作的产生式。我们扩展5.5中的转换，把合成属性考虑在内。该技术把产生式A → Aα | Aβ | ϒ 转换成
Α → ϒR
R → αR | βR | ε
当语义动作嵌入在产生式中时,我们可以在转换的过程中执行它们。这里，如果我们让A = expr , α =+ term {prnt('+')}, β = - term {print('-')}, ϒ = term, 那么上述的转换将产生translation scheme (2.14)。
expr → term rest
rest → + term { print('+') } rest | - term {print('-')} rest | ε
term → 0 {print('0') } (2.14)
term → 1 {print('1') }
................
term → 9 {print('9') }
Fig. 2-21展示了翻译过程：
Procedures for the Nonterminals expr, term and rest
我们现在用语法导向的translation scheme(2.14) 实现一个C编写的翻译器。翻译器的核心是Fig. 2.22 的C代码，包括expr,term和rest函数。这些函数实现(2.14)中对应的非终结符。
Fig. 2.22. Functions for the nonterminals expr, rest and term
函数match，将在后面给出。
非终结符的函数模拟产生式的右边。例如，expr→ term rest通过在函数expr()中调用term()和rest()实现。
另外一个例子，函数rest()使用rest的第一个产生式(2.14)，如果lookahead符号是一个加号，而如果是一个减号，则利用第二个产生式，缺省情况使用产生式rest → ε.第一个产生式对应rest()函数的第一个if条件，第2个产生式对应第2个条件，因为第3个产生式右边是ε，所以rest()的最后一个else什么也不做。
term的10个产生式生成10个数字。在Fig, 2.22 中，isdigit例程测试lookahead符号是否为数字。数字被打印，然后match。不然则发生错误（由于match以后会发生lookahead的改变，因此match在putchar之后）。
Optimizing the Translator
某些递归调用可以用循环代替。当一个过程体中的最后一个语句是对相同过程的一个递归调用时，这个调用叫做尾递归tail recursive。例如,rest()的第4行和第7行是tail recursive。
我们可以用循环替换tail recursive来加速一个程序。对一个没有参数的过程，一个tail-recursive 调用可以用一个jump到过程开始替换。rest的代码可以重写如下：
rest() {
L: if (lookahead == '+' ) {
match('+'); term(); putchar('+'); goto L;
}
else if (lookahead == '-') {
match('-');term();putchar('-');goto L;
}
else ;
}
只要lookahead符号是一个加号或者减号，过程rest匹配符号。掉用term去匹配一个数字，然后重复这一过程。注意因为match每次调用的时候都移去符号，循环只发生在改变符号的数字的序列。如果改变发生在Fig. 2.22，唯一需要留下的对rest的调用就是expr的第3行。因此两个函数可以继承为一个，如Fig 2.23所示。在C中，一个语句stmt可以重复执行通过：
while(1) stmt
因为1永远为真。我们可以用break语句跳出一个循环。
#include
#include
int lookahead;
void expr(void);
void term(void);
void match(int c);
void error(void);
void expr(void){
term();
while(1) {
if (lookahead == '+') {
match('+'); term(); putchar('+');
} else if (lookahead == '-') {
match('-'); term(); putchar('-');
} else
break;
}
}
void term(void){
if(isdigit(lookahead))
{
putchar(lookahead); match(lookahead);
} else
error();
}
void match(int c) {
if (lookahead == c)
lookahead = getchar();
else
error();
}
void error(void) {
fprintf(stderr, "syntax error\n");
exit(1);
}
int main (int argc, char const* argv[])
{
lookahead = getchar();
expr();
putchar('\n');
return 0;
}
expr → expr + term {print('+')}
expr → expr - term {print('-')}
expr → term
term → 0 {print('0')}
term → 1 {print('1')}
term → 2 {print('2')}
.....
term → 9 {print('9')}
Fig. 2.19 Initial specification of infix-to-postfix translator
一个语法导向的translation scheme 通常能够作为一个翻译器的规格。我们使用Fig 2.19中的scheme(重复自Fig. 2.13)将被执行的翻译的定义。作为一种通常情况，一个给定scheme的下部文法必须被修改，在它能够作为一个predictive parser解析之前。特别，Fig 2.19中scheme之下的文法是左递归的，我们已经知道，一个predictive parser不能处理一个左递归文法。通过排除左递归，我们能够获得一个文法，适合在predictive 递归下降的翻译器中使用。
Abstract and Concrete Syntax
一种有用的考虑一个输入字符串的翻译的起点是一棵abstract syntax tree抽象语法树，其中每一个节点代表一个操作符，节点的子节点代表操作数。相反，一个解析树叫做concrete syntax tree具体语言树，下部的文法称为语言的concrete syntax具体语法。抽象语法树，或者简单地叫做语法树，和解析树不同，因为形式的表面不同，对于翻译并不重要，不会出现在语法树中。
例如，9-5+2的语法树如Fig. 2.20所示。因为+和-具有相同的优先级别，而相同优先级别的操作符从左到右计算，因此9-5组成一个子表达式。把Fig. 2.20和对应的解析树Fig. 2.2比较，我们注意到语法树把一个操作符和一个内部节点关联，而不是操作符变成子节点之一。
对一个translation scheme而言，它所基于的文法的解析树和语言树越接近越好。用Fig. 2.19 的文法对子表达式的分组类似于他们在语法树中的分组。不幸的是，Fig 2.19中的文法是左递归的，因此不适合predictive解析。看起来有点冲突，另一方面，我们需要一个文法能够方便解析，而另一方面要容易解析需要一个很大不同的文法。最明显的解决方案是排除左递归。但是，就象下面的例子一样，这种排除需要非常小心才能完成。
Example 2.9 下面的文法不适合用来把表达式翻译成后缀形式，即使它确实生成了Fig 2.19文法的相同语言，并且可以用来进行递归下降解析。
expr → term rest
rest → + expr | - expr | ε
term → 0 | 1 | ... | 9
该文法的问题是rest → + expr 和rest - expr 生成的操作符的操作数不明显。选择下面的任意一个，从expr.t翻译rest.t方法都是不可接受的。
rest → - expr {rest.t := '-' || expr.t} (2.12)
rest → - expr {rest.t := expr.t || '-' } (2.13)
(我们只显示了减法操作符的产生式和语义动作)。从9-5的翻译应该是95-。但是，如果我们使用(2.12)的动作，那么减法符号将在expr.t之前出现，因此9-5错误地在翻译后依旧保持9-5。
另一方面，如果我们使用(2.13)，那么操作符将一致地移到右端，那么9-5+2将错误地翻译成为952+-(正确的翻译应该是95-2+)。
Adapting the Translation Scheme
Fig. 2.18画出的左递归排除也可以运用到包含语义动作的产生式。我们扩展5.5中的转换，把合成属性考虑在内。该技术把产生式A → Aα | Aβ | ϒ 转换成
Α → ϒR
R → αR | βR | ε
当语义动作嵌入在产生式中时,我们可以在转换的过程中执行它们。这里，如果我们让A = expr , α =+ term {prnt('+')}, β = - term {print('-')}, ϒ = term, 那么上述的转换将产生translation scheme (2.14)。
expr → term rest
rest → + term { print('+') } rest | - term {print('-')} rest | ε
term → 0 {print('0') } (2.14)
term → 1 {print('1') }
................
term → 9 {print('9') }
Fig. 2-21展示了翻译过程：
Procedures for the Nonterminals expr, term and rest
我们现在用语法导向的translation scheme(2.14) 实现一个C编写的翻译器。翻译器的核心是Fig. 2.22 的C代码，包括expr,term和rest函数。这些函数实现(2.14)中对应的非终结符。
expr() {
term(); rest();
}
rest() {
if (lookahead == '+') {
match('+'); term(); putchar('+');rest();
} else if (lookahead == '-') {
match('-'); term(); putchar('-'); rest();
} else
;
}
term() {
if(isdigit(lookahead))
{
putchar(lookahead); match(lookahead);
} else
error();
}
Fig. 2.22. Functions for the nonterminals expr, rest and term
函数match，将在后面给出。
非终结符的函数模拟产生式的右边。例如，expr→ term rest通过在函数expr()中调用term()和rest()实现。
另外一个例子，函数rest()使用rest的第一个产生式(2.14)，如果lookahead符号是一个加号，而如果是一个减号，则利用第二个产生式，缺省情况使用产生式rest → ε.第一个产生式对应rest()函数的第一个if条件，第2个产生式对应第2个条件，因为第3个产生式右边是ε，所以rest()的最后一个else什么也不做。
term的10个产生式生成10个数字。在Fig, 2.22 中，isdigit例程测试lookahead符号是否为数字。数字被打印，然后match。不然则发生错误（由于match以后会发生lookahead的改变，因此match在putchar之后）。
Optimizing the Translator
某些递归调用可以用循环代替。当一个过程体中的最后一个语句是对相同过程的一个递归调用时，这个调用叫做尾递归tail recursive。例如,rest()的第4行和第7行是tail recursive。
我们可以用循环替换tail recursive来加速一个程序。对一个没有参数的过程，一个tail-recursive 调用可以用一个jump到过程开始替换。rest的代码可以重写如下：
rest() {
L: if (lookahead == '+' ) {
match('+'); term(); putchar('+'); goto L;
}
else if (lookahead == '-') {
match('-');term();putchar('-');goto L;
}
else ;
}
只要lookahead符号是一个加号或者减号，过程rest匹配符号。掉用term去匹配一个数字，然后重复这一过程。注意因为match每次调用的时候都移去符号，循环只发生在改变符号的数字的序列。如果改变发生在Fig. 2.22，唯一需要留下的对rest的调用就是expr的第3行。因此两个函数可以继承为一个，如Fig 2.23所示。在C中，一个语句stmt可以重复执行通过：
while(1) stmt
因为1永远为真。我们可以用break语句跳出一个循环。
#include
#include
int lookahead;
void expr(void);
void term(void);
void match(int c);
void error(void);
void expr(void){
term();
while(1) {
if (lookahead == '+') {
match('+'); term(); putchar('+');
} else if (lookahead == '-') {
match('-'); term(); putchar('-');
} else
break;
}
}
void term(void){
if(isdigit(lookahead))
{
putchar(lookahead); match(lookahead);
} else
error();
}
void match(int c) {
if (lookahead == c)
lookahead = getchar();
else
error();
}
void error(void) {
fprintf(stderr, "syntax error\n");
exit(1);
}
int main (int argc, char const* argv[])
{
lookahead = getchar();
expr();
putchar('\n');
return 0;
}
星期四, 九月 28, 2006
2.4 PARSING
解析是判断一个token字符串是否能够被一个文法生成的过程。在讨论这个问题的时候，考虑将被构造的一棵解析树是很有帮助的，即使一个编译器不一定构造这样一棵数。但是，一个解析器必须能够构造树，不然的话，翻译不能保证一定是正确的。
本节介绍一种解析方法，可以应用来构造语法导向翻译器。一个完整的C程序，实现Fig 2.13的translation scheme，出现在下一节中。一种可选的方式是使用一种软件工具直接从一个translation scheme产生一个翻译器。参见4.9描述这样一种工具。他可以不加修改实现Fig 2.13的translation scheme.
可以为任何文法构造一棵解析树。但是实际中使用的文法，有一种特殊的形式。对任何上下文无关的文法，有一个解析器取最多O(n^3)时间来解析一个n个token的字符串。但是3次方的时间太昂贵了。给定一个编程语言，我们一般能够构造一个快速解析的文法。实际中，线性算法基本上足以解析所有的语言。编程语言解析器基本上总是在输入上进行一次从左到右的扫描，每次只看一个token.
最大多数解析方法属于两种类别之一，叫做top-down自顶向下和bottom-up自底至上.这些术语指解析树的节点被构造的顺序。前者，构造从根节点开始，朝着叶节点进发，而后者，构造开始于叶节点，朝着根前进。top-down解析器的流行归功于采用top-down方法能够用手工比较简单地构造高校的解析器。但是Bottom-up解析，能够处理更多类别的文法和translation schemes，因此直接用来从文法产生解析器的软件工具趋向于采用bottom-up方法。
Top-Down Parsing
我们用适合这种方法的一种文法介绍top-down解析。本节后面，我们讨论一般性的top-down解析器构造。下面的文法生成Pascal的一个子集。我们使用dotdot代表".."，重点突出字符序列当作一个单元。
type → simple
| ↑id
| array [simple] of type
simple →integer
| char
| num dotdot num
一棵解析树的top-down构造，从root开始，标以开始非终结符，然后重复下面的两步(Fig 2.15为例).
对某些文法而言，上面各步可以在对输入字符串进行一次从左到右的扫描即可实现。输入中当前被扫描的token经常被引用为lookahead符号。开始，lookahead 符号是第一个，也就是最左边，输入字符串的token。Figure 2.16演示了解析下面字符串的过程：
array [ num dotdot num] of integer
最初，array这个token是lookahead symbol, 解析树的已知部分由root组成，标签是Fig. 1.16(a)的开始非终结符type。目标是构造解析树的剩余部分，以便让这个解析树生成的字符串和输入字符串匹配。
当一个匹配发生的时候，Fig. 2.16(a)的非终结符type必须派生一个字符串，从lookahead symbol array开始。在文法(2.8)中，只有一个type的产生式可以派生这样的字符串，我们选择它，用它右边构造root的子节点。
Fig2.16三个快照的每一个都有一个箭头标记输入字符串中的lookahead symbol，以及当前被考虑的解析树中的节点。当某一个节点的子节点被构造时，我们接下去考虑最左边的子。在Fig2.16(b)中，root的子刚刚被构造出来，最左边的子array正被考虑。
当解析树中被考虑的节点是一个终结符，并且终结符匹配lookahead symbol的时候，我们同时前进解析树和输入。输入中的下一个token变成新的lookahead symbol，解析树的下一个子节点被考虑。在Fig. 2.16(c)中，解析树的箭头前进到root的下一个子节点，输入中的箭头也前进到下一个token [。在下一次前进以后，解析树中的箭头将指向非终结符simple这个子节点。当一个非终结符的节点被考虑时，我们将重复为非终结符选择一个产生式的过程。
一般来说，非终结符产生式的选择可能回引起trail-and-error;也就是，我们可能必须尝试一个产生式，如果发现不合适的时候回退并尝试另外一个产生式。如果使用了一个产生式，我们不能完成匹配输入字符串的一棵树，那么这个产生式是不合适的。但是，这里有一种重要的特殊情况，叫做predictive parsing，不会发生回退。
Predictive Parsing
Recursive-descent parsing递归下降解析是一种top-down的语法分析方法，其中我们执行一系列递归过程去处理输入。一个过程和文法的每一个非终结符关联。这里我们考虑递归下降解析的一种特殊情况，叫做predictive parsing，其中lookahead symbol无二义性地确定了每一个非终结符选择的过程。处理输入时过程的被调用序列隐式地定义了输入的一棵解析树。
Fig. 2.17. Pseudo-code for a predictive parser
Fig. 2.17的predictive解析器由文法(2.8)中的非终结符type和simple对应的过程组成，另外还有一个附加的过程match.我们使用match来简化type和simple的代码。它前进到下一个输入token，如果它的参数t匹配lookahead symbol。于是match改变变量lookahead，它是当前被扫描的输入token.
解析从我们文法中的开始非终结符type对应的过程开始。和Fig. 2.16一样的输入，lookahead开始是第一个token array。过程type 执行代码
对应产生式的右边
type → array [simple] of type
注意右边的每一个终结符被lookahead symbol匹配，而每一个非终结符导致对它相应过程的调用。
使用Fig. 2.16的输入，在array后面，[被匹配之后，lookahead符号是num。在这一点过程simple被调用，执行代码：
match(num);match(dotdot);match(num);
lookahead符号引导对产生式的选择。如果产生式的右边开始于一个token，那么在lookahead symbol匹配这个token的时候，这个产生式就能够使用。现在考虑一个右边开始于一个非终结符，例如：
type → simple (2.10)
这个产生式在lookahead symbol 能够从simple生成出来的时候使用。例如，在执行代码片断(2.9)的过程中，假设lookahead symbol是integer，当控制到达过程调用type的时候。没有任何type的产生式开始于token integer。但是，simple的一个产生式确实开始于integer，因此产生式(2.10)被使用，在lookahead是integer的时候，type调用simple过程。
Predictive parsing依赖于一个信息，就是一个产生式的右边能够产生什么样的第一个symbol。更加精确地说，让α非终结符A的右边。我们定义FIRST(α)为由α生成的字符串中，可能出现为第一个symbol的token集合。如果α是ε，或者能够生成ε,那么ε也在FIRST(α)之内。例如：
FIRST(simple) = {integer, char, num}
FIRST(↑id) = {↑}
FIRST(array [ simple ] of type) = {array}
实践中，很多产生式右边以token开始，从而简化了FIRST集合的构造。计算FIRST的一个算法在4.4中。
如果有两个产生式A →α和A →β,那么必须考虑FIRST集合。没有回退的递归下降解析需要FIRST(α)和FIRST(β)是分离的。这样lookahead符号能够用来决定使用哪一个产生式。如果lookahead符号在FIRST(α)中，那么采用α。不然，如果lookahead 符号在FIRST(β)中，那么使用β。
When to Use ε-Productions
右边带有 ε的产生式需要特别的对待。递归下降解析器将使用ε-Production作为缺省，如果没有其他的产生式可用。例如，考虑
stmt → begin opt_stmts end
opt_stmts → stmt_list | ε
在解析opt_stmts的时候，如果lookahead符号不在FIRST(stmt_list)中，那么将使用ε-Production。这个选择非常正确,如果lookahead符号是end.任何不是end的lookahead符号将导致错误，在解析stmt的过程中。
Designing a Predictive Parser
一个predictive parser 是一个程序，其中每一个非终结符都有一个过程。每一个过程做两件事情：
我们将在下一节构造这样一个翻译器。
Left Recursion
一个递归下降解析器可能无穷循环。例如
expr → expr + term
其中右边最左边的符号和产生式左边的非终结符一样。假设expr的过程决定应用此产生式。右边以expr开始，因此对expr将被递归调用。于是解析器就陷入了无穷循环。注意,lookahead符号仅在右边的一个终结符被匹配的时候才会发生变化。因此产生式以非终结符expr开始，那么就不会对输入发生任何改变，导致无穷循环。
一个左递归产生式可以通过重写产生式排除。考虑一个非终结符A具有两个产生式：
A → Aα | β
其中α和β是不以A开始的终结符和非终结符。例如，表达式：
expr → expr + term | term
中，A = expr, α = + term, β = term.
非终结符A是left recursive左递归的，因为产生式A → Aα的右边还是以A开始。重复此产生式在A的右边构造起一序列的α，例如图2.18(a)。当A最终被β替换的时候，我们有一个β后面跟着一系列的0或者多个α.
相同的效果，可以通过Fig 2.18(1)实现，通过用下面的方式重写A的产生式：
A → βR
R → αR | ε (2.11)
这里R是一个新的非终结符。
产生式R → αR 是右递归的，因为R的产生式右边，R是最后一个符号。右递归的产生式导致树朝右下方增长，如Fig. 2.18(b)所示。朝右下方增长的数使得它难以翻译包含左结合操作符的表达式，例如减。但是，在下一节中，我们可以看到表达式正确翻译成后缀记法，如果在一个右递归文法上仔细定义translation scheme。
在第4章中，我们会讨论左递归更加通用的形式，显示可以从一种文法中排除所有的左递归。
本节介绍一种解析方法，可以应用来构造语法导向翻译器。一个完整的C程序，实现Fig 2.13的translation scheme，出现在下一节中。一种可选的方式是使用一种软件工具直接从一个translation scheme产生一个翻译器。参见4.9描述这样一种工具。他可以不加修改实现Fig 2.13的translation scheme.
可以为任何文法构造一棵解析树。但是实际中使用的文法，有一种特殊的形式。对任何上下文无关的文法，有一个解析器取最多O(n^3)时间来解析一个n个token的字符串。但是3次方的时间太昂贵了。给定一个编程语言，我们一般能够构造一个快速解析的文法。实际中，线性算法基本上足以解析所有的语言。编程语言解析器基本上总是在输入上进行一次从左到右的扫描，每次只看一个token.
最大多数解析方法属于两种类别之一，叫做top-down自顶向下和bottom-up自底至上.这些术语指解析树的节点被构造的顺序。前者，构造从根节点开始，朝着叶节点进发，而后者，构造开始于叶节点，朝着根前进。top-down解析器的流行归功于采用top-down方法能够用手工比较简单地构造高校的解析器。但是Bottom-up解析，能够处理更多类别的文法和translation schemes，因此直接用来从文法产生解析器的软件工具趋向于采用bottom-up方法。
Top-Down Parsing
我们用适合这种方法的一种文法介绍top-down解析。本节后面，我们讨论一般性的top-down解析器构造。下面的文法生成Pascal的一个子集。我们使用dotdot代表".."，重点突出字符序列当作一个单元。
type → simple
| ↑id
| array [simple] of type
simple →integer
| char
| num dotdot num
一棵解析树的top-down构造，从root开始，标以开始非终结符，然后重复下面的两步(Fig 2.15为例).
- 在节点n，标以非终结符A，选择A的其中一个产生式，用产生式右边的符号构造n的子节点
- 寻找将被构造子树的下一个节点
对某些文法而言，上面各步可以在对输入字符串进行一次从左到右的扫描即可实现。输入中当前被扫描的token经常被引用为lookahead符号。开始，lookahead 符号是第一个，也就是最左边，输入字符串的token。Figure 2.16演示了解析下面字符串的过程：
array [ num dotdot num] of integer
最初，array这个token是lookahead symbol, 解析树的已知部分由root组成，标签是Fig. 1.16(a)的开始非终结符type。目标是构造解析树的剩余部分，以便让这个解析树生成的字符串和输入字符串匹配。
当一个匹配发生的时候，Fig. 2.16(a)的非终结符type必须派生一个字符串，从lookahead symbol array开始。在文法(2.8)中，只有一个type的产生式可以派生这样的字符串，我们选择它，用它右边构造root的子节点。
Fig2.16三个快照的每一个都有一个箭头标记输入字符串中的lookahead symbol，以及当前被考虑的解析树中的节点。当某一个节点的子节点被构造时，我们接下去考虑最左边的子。在Fig2.16(b)中，root的子刚刚被构造出来，最左边的子array正被考虑。
当解析树中被考虑的节点是一个终结符，并且终结符匹配lookahead symbol的时候，我们同时前进解析树和输入。输入中的下一个token变成新的lookahead symbol，解析树的下一个子节点被考虑。在Fig. 2.16(c)中，解析树的箭头前进到root的下一个子节点，输入中的箭头也前进到下一个token [。在下一次前进以后，解析树中的箭头将指向非终结符simple这个子节点。当一个非终结符的节点被考虑时，我们将重复为非终结符选择一个产生式的过程。
一般来说，非终结符产生式的选择可能回引起trail-and-error;也就是，我们可能必须尝试一个产生式，如果发现不合适的时候回退并尝试另外一个产生式。如果使用了一个产生式，我们不能完成匹配输入字符串的一棵树，那么这个产生式是不合适的。但是，这里有一种重要的特殊情况，叫做predictive parsing，不会发生回退。
Predictive Parsing
Recursive-descent parsing递归下降解析是一种top-down的语法分析方法，其中我们执行一系列递归过程去处理输入。一个过程和文法的每一个非终结符关联。这里我们考虑递归下降解析的一种特殊情况，叫做predictive parsing，其中lookahead symbol无二义性地确定了每一个非终结符选择的过程。处理输入时过程的被调用序列隐式地定义了输入的一棵解析树。
procedure match(t:token);
begin
if lookahead = t then
lookahead := nexttoken
else error
end;
procedure type
begin
if lookahead is in {integer, char, num} then
simple
else if lookahead = '↑' then begin
match('↑');match(id)
end
else if lookahead = array then begin
match(array);match('[');simple;match(']');match(of);type
end
else error
end;
procedure simple
begin
if lookahead = integer then
match(integer)
else if lookahead = char then
match(char)
else if lookahead = num then begin
match(num);match(dotdot);match(num);
end
else error
end;
Fig. 2.17. Pseudo-code for a predictive parser
Fig. 2.17的predictive解析器由文法(2.8)中的非终结符type和simple对应的过程组成，另外还有一个附加的过程match.我们使用match来简化type和simple的代码。它前进到下一个输入token，如果它的参数t匹配lookahead symbol。于是match改变变量lookahead，它是当前被扫描的输入token.
解析从我们文法中的开始非终结符type对应的过程开始。和Fig. 2.16一样的输入，lookahead开始是第一个token array。过程type 执行代码
match(array);match('[');simple;match(']');match(of);type对应产生式的右边
type → array [simple] of type
注意右边的每一个终结符被lookahead symbol匹配，而每一个非终结符导致对它相应过程的调用。
使用Fig. 2.16的输入，在array后面，[被匹配之后，lookahead符号是num。在这一点过程simple被调用，执行代码：
match(num);match(dotdot);match(num);
lookahead符号引导对产生式的选择。如果产生式的右边开始于一个token，那么在lookahead symbol匹配这个token的时候，这个产生式就能够使用。现在考虑一个右边开始于一个非终结符，例如：
type → simple (2.10)
这个产生式在lookahead symbol 能够从simple生成出来的时候使用。例如，在执行代码片断(2.9)的过程中，假设lookahead symbol是integer，当控制到达过程调用type的时候。没有任何type的产生式开始于token integer。但是，simple的一个产生式确实开始于integer，因此产生式(2.10)被使用，在lookahead是integer的时候，type调用simple过程。
Predictive parsing依赖于一个信息，就是一个产生式的右边能够产生什么样的第一个symbol。更加精确地说，让α非终结符A的右边。我们定义FIRST(α)为由α生成的字符串中，可能出现为第一个symbol的token集合。如果α是ε，或者能够生成ε,那么ε也在FIRST(α)之内。例如：
FIRST(simple) = {integer, char, num}
FIRST(↑id) = {↑}
FIRST(array [ simple ] of type) = {array}
实践中，很多产生式右边以token开始，从而简化了FIRST集合的构造。计算FIRST的一个算法在4.4中。
如果有两个产生式A →α和A →β,那么必须考虑FIRST集合。没有回退的递归下降解析需要FIRST(α)和FIRST(β)是分离的。这样lookahead符号能够用来决定使用哪一个产生式。如果lookahead符号在FIRST(α)中，那么采用α。不然，如果lookahead 符号在FIRST(β)中，那么使用β。
When to Use ε-Productions
右边带有 ε的产生式需要特别的对待。递归下降解析器将使用ε-Production作为缺省，如果没有其他的产生式可用。例如，考虑
stmt → begin opt_stmts end
opt_stmts → stmt_list | ε
在解析opt_stmts的时候，如果lookahead符号不在FIRST(stmt_list)中，那么将使用ε-Production。这个选择非常正确,如果lookahead符号是end.任何不是end的lookahead符号将导致错误，在解析stmt的过程中。
Designing a Predictive Parser
一个predictive parser 是一个程序，其中每一个非终结符都有一个过程。每一个过程做两件事情：
- 它通过察看lookahead符号决定采用哪个产生式。如果产生式的右边为α，lookahead符号在FIRST(α)，那么将采用这个产生式。如果对任何lookahead 符号，两个右边存在着一个冲突，那么我们就不能在这种文法上使用这种解析方法。一个右边具有ε的产生式将被使用，如果lookahead符号不再任何其它右边的FIRST集合中。
- 过程通过模拟右边使用一个产生式。一个非终结符导致对应过程的调用，一个匹配lookahead符号的token导致下一个token被读入。如果在某些点，产生式中的token和lookahead符号不匹配，那么就会报告错误。Fig 2.17是把这些规则应用到文法2.8的结果。
- 构造一个predictive parser, 忽略产生式中的动作。
- 把translation scheme中的动作复制到解析器。如果动作出现在产生式p中的文法符号X之后，那么他就被复制到实现X的代码之后。如果它出现在产生式的开始，那么他就被复制到实现该产生式的代码之前。
我们将在下一节构造这样一个翻译器。
Left Recursion
一个递归下降解析器可能无穷循环。例如
expr → expr + term
其中右边最左边的符号和产生式左边的非终结符一样。假设expr的过程决定应用此产生式。右边以expr开始，因此对expr将被递归调用。于是解析器就陷入了无穷循环。注意,lookahead符号仅在右边的一个终结符被匹配的时候才会发生变化。因此产生式以非终结符expr开始，那么就不会对输入发生任何改变，导致无穷循环。
一个左递归产生式可以通过重写产生式排除。考虑一个非终结符A具有两个产生式：
A → Aα | β
其中α和β是不以A开始的终结符和非终结符。例如，表达式：
expr → expr + term | term
中，A = expr, α = + term, β = term.
非终结符A是left recursive左递归的，因为产生式A → Aα的右边还是以A开始。重复此产生式在A的右边构造起一序列的α，例如图2.18(a)。当A最终被β替换的时候，我们有一个β后面跟着一系列的0或者多个α.
相同的效果，可以通过Fig 2.18(1)实现，通过用下面的方式重写A的产生式：
A → βR
R → αR | ε (2.11)
这里R是一个新的非终结符。
产生式R → αR 是右递归的，因为R的产生式右边，R是最后一个符号。右递归的产生式导致树朝右下方增长，如Fig. 2.18(b)所示。朝右下方增长的数使得它难以翻译包含左结合操作符的表达式，例如减。但是，在下一节中，我们可以看到表达式正确翻译成后缀记法，如果在一个右递归文法上仔细定义translation scheme。
在第4章中，我们会讨论左递归更加通用的形式，显示可以从一种文法中排除所有的左递归。
星期一, 九月 25, 2006
2.3 SYNTAX-DIRECTED TRANSLATION
为了翻译一个编程语言构造，除了为该构造生成的代码外，一个编译器需要跟踪许多量.例如，编译器需要知道该构造的类型，或者目标代码中第一条指令的位置，或者是生成的指令数目。我们因此谈论和该构造相关的属性attributes。一个属性可以代表任何量，例如类型、一个字符串、一个内存地址，等等。
在本节中，我们给出一种形式叫做语法导向的定义，用来指定对编程语言构造的翻译。一个语法导向的定义一种构造的翻译，用它语法成员的属性来定义。在后面的各章，语法导向的定义用来指定许多翻译，发生在一个编译器的前端。
我们也将介绍一种更加过程型的记法，叫做translation scheme，用来指定翻译。本章，我们使用translation scheme把中缀表达式翻译为后缀记法。更加的细节和它们的实现在第5章。
Postfix Notation
一个表达式E的postfix notation 后缀记法可以归纳定义如下：
后缀记法中不需要括号，因为操作符的位置和arity(参数的数目）只允许一种后缀表达式编码方式。例如(9-5)+2的后缀记法是95-2+而9-(5+2)的后缀记法是952+-。
Syntax-Directed Definitions
一个syntax-directed definition 使用一个上下文无关文法来指定输入的语法结构。对每一个文法符号，它关联一系列属性，以及对于每一个产生式，都有一套语义规则semantic rules来计算出现在该产生式中的符号的属性值。文法和语义规则集合组成语法导向定义。
一次翻译就是一次输入输出映射。每一个输入x的输出用下列方式指定。
首先，构造x的一棵解析树。假设解析树中一个节点n用文法符号X作为标签。我们写成X.a来表示该节点上X属性a的值。在n上X.a值的计算是通过在节点n使用的X-产生式相关的属性a的语义规则得到的。一棵解析树，每一个节点都显示属性值，我们称之为annotated parse tree.
Synthesized Attributes
如果一个节点的某一属性值是由该节点的子节点的属性值决定的，我们称之为synthesized合成的。合成属性具有一个很好的特性，就是它们能够通过一次自底向上的解析树遍历计算得到。本章只使用合成属性；“继承”属性在chap 5介绍。
Example 2.6 翻译一个由数字组成并由加减号分隔的表达式的后缀表达式的一个语法导向的定义如Fig. 2.5 所示。和每个非终结符相关是一个字符值属性t，它代表在一棵解析树中该非终结符生成的表达式的后缀记法。
Fig 2.5 syntax-directed definition for infix to postfix translation
一个数字的后缀表达式是它自己，例如，和产生式term→ 9相关的语义规则定义term.t 是9，无论何时这个产生式用在一个解析树中的节点。当产生式expr → term被应用的时候，term.t的值变成expr.t的值。
产生式expr → expr1 + term 派生一个表达式包含一个加号操作符(expr1中的下标区分右边和左边两个不同的expr实例).加法操作符左边的操作数由expr1和右边的操作数term给出。和这个产生式相关连的语义规则：
expr.t := expr1.t || term.t || '+'
连接epr1.t和term.t的后缀形式，再加上加号，这样定义了属性expr.t的值。语义规则中的||操作符代表字符串连接。
Fig 2.6包含了一个annoted解释树对应Fig 2.2的树。
Example 2.7 假设一个机器人可能被指令从它的当前位置向东、南、西、北移动一步。这样的一系列指令可以用下面的文法产生：
seq → seq instr | begin
instr → east | morth | west | south
输入序列
begin west south east east east north north
发生的机器人位置改变如Fig 2.7
在图中，一个位置是通过一对(x,y)标记的，其中x和y 代表从开始位置往东和北的步数
让我们构造一个语法导向的定义把指令序列翻译为一个机器人的位置。我们应该使用两个属性seq.x和seq.y，跟踪由非终结符seq生成的指令序列得到的结果位置。最初seq生成begin,seq.x和seq.y都是0，如所示在begin west south解析树最左边的内部节点。
位置的改变是由于从instr派生的单个指令找成的，我们给它们instr.dx和instr.dy属性。例如，如果instr派生west，那么instr.dx = -1，instr.dy = 0。假设一个序列是由一个序列seq加上一个新的指令instr组成的。那么robot的新位置是由下列规则给出的：
seq.x = seq1.x + instr.dx
seq.y = seq1.y + instr.dy
把指令序列翻译成机器人位置的语法导向的定义如Fig 2.9所示。
Depth-First Traversals
一个语法导向的定义并不对一棵解析树上属性的计算强加任何顺序；任何计算的顺序，只要它在计算a的属性前，计算好所有a依赖的属性，那么都是允许的。通常，在遍历解析树的时候，我们有时侯在某一个节点首次到达的时候必须计算某些属性，其它的则在它所有的子被访问以后，或者在访问节点的子节点之间的某个点。合适的计算顺序以后讨论。
本章的翻译都可以用固定的顺序、根据语义规则计算解析树的属性。一个树的遍历traversal从根节点开始，以某些顺序访问树中的每个节点。语义规则将通过Fig 2.10 定义的深度优先算法进行计算。
procedure visit(n:node)
begin
for each child m of n. from left to right do
visit(m);
evaluate semantic rules at node n
end
Fig 2.10 树的深度优先遍历
Fig2.11 演示这一过程，从root开始，按照从左到右的次序递归访问每一个节点的子
给定节点的语义规则在所有它的后代节点被访问才进行计算。之所以叫做深度优先是因为它尽可能首先访问一个节点的未被访问的子节点，因此它尝试访问可能的离根节点最远的节点。
Translation Schemes
本章剩下部分，我们使用一个过程型的规格定义一种翻译。一个translation scheme是一个上下文无关文法，其中叫做semantic action的程序片断嵌入到产生式的右边。一个translation scheme 就象一个语法导向定义，除了语义规则的计算顺序是显式展现出来的。
动作执行的点通过{}号表示，并且写在产生式右边的中间，例如：
rest → + term {print('+')} rest1
一个translation scheme 为每一个语句x生成输出，由底下的文法通过执行动作生成的，次序是它们在x解析树中的深度优先遍历顺序。例如，考虑一个解析树节点标为rest代表这个产生式。那么动作{print('+')}将在term子树被遍历但在rest1子树被访问前执行。
在为一个translation scheme画出一棵解析树时，我们把动作作为一个额外的子节点，通过一条虚线和它产生式的节点相连。例如，上述产生式的解析树部分和动作显示在Fig 2.12。一个语义动作节点没有子节点，所以访问到该节点的时候动作将被执行。
Emitting a Translation
本章中，translations schemes的语义动作将把一个翻译的输出写到一个文件中，每次一个字符或字符串。例如，我们把9-5+2翻译为95-2+,其中每个字符被打印一次，不使用任何存储用于子表达式的翻译。当输出用这种方式增量创建时，字符被打印的次序非常重要。
注意，到现在为止提到的语法导向的定义有下列重要的属性：代表每个生成式左边的非终结符的翻译的字符串是把所有右边非终结符翻译连接起来的结果，按照产生式中的相同顺序，在中间加入附加的字符串（可能没有）。具有这个属性的语法导向定义有一个术语叫做simple。例如，考虑下面的第一个产生式和语义规则，取自Fig2.5的语法导向定义：
PRODUCTION SEMANTIC RULE
expr → expr1 + term expr.t := expr.t || term.t || '+' (2.6)
这里expr.t的翻译是把expr1的翻译和term的翻译连接起来，跟上符号＋.注意产生式的右边expr1出现在term的前面。
在term.t和rest1.t中间出现附加的字符串：
PRODUCTION SEMANTIC RULE
rest → + term rest1 rest.t := term.t || '+' || rest1.t (2.7)
但是，再次，非终结符term在右边出现在rest1的前面。
简单的语法导向定义可以用translation scheme来实现，其中action打印附加的字符串，以他们在定义中出现的顺序。下面产生式中的动作分别打印(2.6)和(2.7)中的附加字符串：
expr → expr1 + term {print('+')}
rest → + term {print('+')} rest1
Example 2.8. Figure 2.5包含一个简单的定义，把表达式翻译成后缀形式。Fig. 2.13 给出一个从该定义派生的translation scheme，以及一棵有动作的解析树9-5+2 在2.14:
expr → expr + term {print('+')}
expr → expr -term {print('-')}
expr → term
term → 0 {print('0')}
term → 1 {print('1')}
...
term → 9 {print('9')}
Fig. 2.13 Actions translating expressions into postfix notation.
注意虽然Fig 2.6 和2.14代表相同的输入输出映射，但是两种情况下翻译用不同的方式构造出来。
Fig 2.6把输出附加到解析树的根，而Fig 2.14增量的打印输出。
Fig 2.14的根代表Fig 2,13的第一个产生式。在一个深度优先遍历中，我们首先执行左边操作符expr子树的所有动作，当我们遍历根的最左子树。我们接着访问叶子+，没有动作。我们接着执行右边的操作数term的子树，最后，语义动作{print('+')}这个额外节点被执行。
因为term的产生式右边只有一个数字，该数字被打印。对产生式expr → term而言不需要任何输出，前两个产生式也只有操作符需要被打印。在执行解析树的深度优先遍历时，Fig. 2.14的动作打印95-2+.
作为一个通用规则，绝大多数解析方法以一种“贪婪”的方式处理它们的输入，从左到右，也就是说，它们尽可能多地构造一棵解析树的部分，在阅读下一个输入token前。在一个简单translation scheme(从一个简单语法导向定义派生而来)中，动作也是按照从左到右的次序完成的。因此，为了实现一个简单的translation scheme，我们可以在解析的同时执行语义动作，根本没有必要去构造解析树。
在本节中，我们给出一种形式叫做语法导向的定义，用来指定对编程语言构造的翻译。一个语法导向的定义一种构造的翻译，用它语法成员的属性来定义。在后面的各章，语法导向的定义用来指定许多翻译，发生在一个编译器的前端。
我们也将介绍一种更加过程型的记法，叫做translation scheme，用来指定翻译。本章，我们使用translation scheme把中缀表达式翻译为后缀记法。更加的细节和它们的实现在第5章。
Postfix Notation
一个表达式E的postfix notation 后缀记法可以归纳定义如下：
- 如果E是一个变量或常量，那么E的后缀记法就是E自己
- 如果E是一个具有E1 op E2 形式的表达式，op是任何二元操作符，那么E的后缀记法是E1' E2' op，其中E1'和E2'分别是E1和E2的后缀记法
- 如果E是一个具有(E1)形式的表达式，那么E1的后缀记法就是E的后缀记法
后缀记法中不需要括号，因为操作符的位置和arity(参数的数目）只允许一种后缀表达式编码方式。例如(9-5)+2的后缀记法是95-2+而9-(5+2)的后缀记法是952+-。
Syntax-Directed Definitions
一个syntax-directed definition 使用一个上下文无关文法来指定输入的语法结构。对每一个文法符号，它关联一系列属性，以及对于每一个产生式，都有一套语义规则semantic rules来计算出现在该产生式中的符号的属性值。文法和语义规则集合组成语法导向定义。
一次翻译就是一次输入输出映射。每一个输入x的输出用下列方式指定。
首先，构造x的一棵解析树。假设解析树中一个节点n用文法符号X作为标签。我们写成X.a来表示该节点上X属性a的值。在n上X.a值的计算是通过在节点n使用的X-产生式相关的属性a的语义规则得到的。一棵解析树，每一个节点都显示属性值，我们称之为annotated parse tree.
Synthesized Attributes
如果一个节点的某一属性值是由该节点的子节点的属性值决定的，我们称之为synthesized合成的。合成属性具有一个很好的特性，就是它们能够通过一次自底向上的解析树遍历计算得到。本章只使用合成属性；“继承”属性在chap 5介绍。
Example 2.6 翻译一个由数字组成并由加减号分隔的表达式的后缀表达式的一个语法导向的定义如Fig. 2.5 所示。和每个非终结符相关是一个字符值属性t，它代表在一棵解析树中该非终结符生成的表达式的后缀记法。
| PRODUCTION | SEMANTIC RULE | |
|---|---|---|
| expr → expr1 + term | expr.t := expr1.t || term.t || '+' | |
| expr → expr1 - term | expr.t := expr1.t || term.t || '-' | |
| expr → term | expr.t = term.t | |
| term → 0 | term.t := '0' | |
| term → 1 | term.t := '1' | |
| .... | ... | |
| term → 9 | term.t = '9' |
Fig 2.5 syntax-directed definition for infix to postfix translation
一个数字的后缀表达式是它自己，例如，和产生式term→ 9相关的语义规则定义term.t 是9，无论何时这个产生式用在一个解析树中的节点。当产生式expr → term被应用的时候，term.t的值变成expr.t的值。
产生式expr → expr1 + term 派生一个表达式包含一个加号操作符(expr1中的下标区分右边和左边两个不同的expr实例).加法操作符左边的操作数由expr1和右边的操作数term给出。和这个产生式相关连的语义规则：
expr.t := expr1.t || term.t || '+'
连接epr1.t和term.t的后缀形式，再加上加号，这样定义了属性expr.t的值。语义规则中的||操作符代表字符串连接。
Fig 2.6包含了一个annoted解释树对应Fig 2.2的树。
Example 2.7 假设一个机器人可能被指令从它的当前位置向东、南、西、北移动一步。这样的一系列指令可以用下面的文法产生：
seq → seq instr | begin
instr → east | morth | west | south
输入序列
begin west south east east east north north
发生的机器人位置改变如Fig 2.7
在图中，一个位置是通过一对(x,y)标记的，其中x和y 代表从开始位置往东和北的步数
让我们构造一个语法导向的定义把指令序列翻译为一个机器人的位置。我们应该使用两个属性seq.x和seq.y，跟踪由非终结符seq生成的指令序列得到的结果位置。最初seq生成begin,seq.x和seq.y都是0，如所示在begin west south解析树最左边的内部节点。
位置的改变是由于从instr派生的单个指令找成的，我们给它们instr.dx和instr.dy属性。例如，如果instr派生west，那么instr.dx = -1，instr.dy = 0。假设一个序列是由一个序列seq加上一个新的指令instr组成的。那么robot的新位置是由下列规则给出的：
seq.x = seq1.x + instr.dx
seq.y = seq1.y + instr.dy
把指令序列翻译成机器人位置的语法导向的定义如Fig 2.9所示。
Depth-First Traversals
一个语法导向的定义并不对一棵解析树上属性的计算强加任何顺序；任何计算的顺序，只要它在计算a的属性前，计算好所有a依赖的属性，那么都是允许的。通常，在遍历解析树的时候，我们有时侯在某一个节点首次到达的时候必须计算某些属性，其它的则在它所有的子被访问以后，或者在访问节点的子节点之间的某个点。合适的计算顺序以后讨论。
本章的翻译都可以用固定的顺序、根据语义规则计算解析树的属性。一个树的遍历traversal从根节点开始，以某些顺序访问树中的每个节点。语义规则将通过Fig 2.10 定义的深度优先算法进行计算。
procedure visit(n:node)
begin
for each child m of n. from left to right do
visit(m);
evaluate semantic rules at node n
end
Fig 2.10 树的深度优先遍历
Fig2.11 演示这一过程，从root开始，按照从左到右的次序递归访问每一个节点的子
给定节点的语义规则在所有它的后代节点被访问才进行计算。之所以叫做深度优先是因为它尽可能首先访问一个节点的未被访问的子节点，因此它尝试访问可能的离根节点最远的节点。
Translation Schemes
本章剩下部分，我们使用一个过程型的规格定义一种翻译。一个translation scheme是一个上下文无关文法，其中叫做semantic action的程序片断嵌入到产生式的右边。一个translation scheme 就象一个语法导向定义，除了语义规则的计算顺序是显式展现出来的。
动作执行的点通过{}号表示，并且写在产生式右边的中间，例如：
rest → + term {print('+')} rest1
一个translation scheme 为每一个语句x生成输出，由底下的文法通过执行动作生成的，次序是它们在x解析树中的深度优先遍历顺序。例如，考虑一个解析树节点标为rest代表这个产生式。那么动作{print('+')}将在term子树被遍历但在rest1子树被访问前执行。
在为一个translation scheme画出一棵解析树时，我们把动作作为一个额外的子节点，通过一条虚线和它产生式的节点相连。例如，上述产生式的解析树部分和动作显示在Fig 2.12。一个语义动作节点没有子节点，所以访问到该节点的时候动作将被执行。
Emitting a Translation
本章中，translations schemes的语义动作将把一个翻译的输出写到一个文件中，每次一个字符或字符串。例如，我们把9-5+2翻译为95-2+,其中每个字符被打印一次，不使用任何存储用于子表达式的翻译。当输出用这种方式增量创建时，字符被打印的次序非常重要。
注意，到现在为止提到的语法导向的定义有下列重要的属性：代表每个生成式左边的非终结符的翻译的字符串是把所有右边非终结符翻译连接起来的结果，按照产生式中的相同顺序，在中间加入附加的字符串（可能没有）。具有这个属性的语法导向定义有一个术语叫做simple。例如，考虑下面的第一个产生式和语义规则，取自Fig2.5的语法导向定义：
PRODUCTION SEMANTIC RULE
expr → expr1 + term expr.t := expr.t || term.t || '+' (2.6)
这里expr.t的翻译是把expr1的翻译和term的翻译连接起来，跟上符号＋.注意产生式的右边expr1出现在term的前面。
在term.t和rest1.t中间出现附加的字符串：
PRODUCTION SEMANTIC RULE
rest → + term rest1 rest.t := term.t || '+' || rest1.t (2.7)
但是，再次，非终结符term在右边出现在rest1的前面。
简单的语法导向定义可以用translation scheme来实现，其中action打印附加的字符串，以他们在定义中出现的顺序。下面产生式中的动作分别打印(2.6)和(2.7)中的附加字符串：
expr → expr1 + term {print('+')}
rest → + term {print('+')} rest1
Example 2.8. Figure 2.5包含一个简单的定义，把表达式翻译成后缀形式。Fig. 2.13 给出一个从该定义派生的translation scheme，以及一棵有动作的解析树9-5+2 在2.14:
expr → expr + term {print('+')}
expr → expr -term {print('-')}
expr → term
term → 0 {print('0')}
term → 1 {print('1')}
...
term → 9 {print('9')}
Fig. 2.13 Actions translating expressions into postfix notation.
注意虽然Fig 2.6 和2.14代表相同的输入输出映射，但是两种情况下翻译用不同的方式构造出来。
Fig 2.6把输出附加到解析树的根，而Fig 2.14增量的打印输出。
Fig 2.14的根代表Fig 2,13的第一个产生式。在一个深度优先遍历中，我们首先执行左边操作符expr子树的所有动作，当我们遍历根的最左子树。我们接着访问叶子+，没有动作。我们接着执行右边的操作数term的子树，最后，语义动作{print('+')}这个额外节点被执行。
因为term的产生式右边只有一个数字，该数字被打印。对产生式expr → term而言不需要任何输出，前两个产生式也只有操作符需要被打印。在执行解析树的深度优先遍历时，Fig. 2.14的动作打印95-2+.
作为一个通用规则，绝大多数解析方法以一种“贪婪”的方式处理它们的输入，从左到右，也就是说，它们尽可能多地构造一棵解析树的部分，在阅读下一个输入token前。在一个简单translation scheme(从一个简单语法导向定义派生而来)中，动作也是按照从左到右的次序完成的。因此，为了实现一个简单的translation scheme，我们可以在解析的同时执行语义动作，根本没有必要去构造解析树。
星期六, 九月 23, 2006
2.2 SNYTAX DEFINITION
我们介绍上下文无关文法context-free grammar这种记法
一种文法自然地描述许多编程语言构造的层次型结构。例如C的if-else语句
使用变量expre代表一个表达式，变量stmt代表一个语句，上面的规则可以表达为：
一个context-free grammer 具有四个组成部分：
传统上，文法是通过列出它们的产生式来指定的，
Example 2.1 本章的几个例子使用数字、加减号组成的表达式，例如9-5+2,3-1和7等等。因为一个加号或者减号必须出现在两个数字之间，我们把这样的表达式称为"由加减号分隔的数字列表"。下面的文法描述这些表达式的语法，这些产生式为：
按照我们的约定，文法的token是
+ - 0 1 2 3 4 5 6 7 8 9
而非终结符是斜体的list和digit，其中list是开始非终结符，因为它的产生式出现在第一条
我们说一个产生式是针对for一个非终结符的，如果这个非终结符出现在产生式的左边。一个token字符串是0个或多个token组成的一个序列。包含0个token的字符串，写作ε，叫做空字符串empty string.
一个文法派生字符串，从start符号symbol开始，用一个非终结符产生式的右边重复替换该非终结符。能够从start symbol派生出来的token字符串形成该文法定义的语言language。
Example 2.2 由文法Example2.1 定义的语言由用加减号分隔的数字列表组成。
非终结符digit的10个产生式允许它代表任何一个token 0,1,.....,9。根据产生式(2.4)，一个数字本身是一个列表。产生式(2.2)和(2.3)表示，我们可以取任意列表，后面加上一个加号或减号，再后跟一个数字，我们就可以得到一个新的列表。
因此，产生式(2.2)到(2.5)可以让我们定义感兴趣的语言。例如，我们可以推断9-5+2是一个list,按照：
Example 2.3 有点不同类型的列表是Pascal begin-end 块中的用分号隔开的语句序列。这些列表可能是一个空的语句列表在begin和end之间。我们可能开始一个文法如下：
block → begin opt_stmts end
opt_stmt → stmt_list | ε
stmt_list → stmt_list; stmt | stmt
注意opt_stmts第2个可能的右边是ε,代表空字符串。也就是说，opt_stmts可以被一个空字符串替换，因此一个block可由两个token字符串begin end组成。注意stmt_list的产生式和Example 2.1中的list相似。只不过分号代替了算术操作符，而stmt代替了digit。我们没有展示stmt的产生式。我们马上就会讨论各种不同语句的产生式，例如if语句、赋值语句等等。
Parse Tree
一棵解析树能够非常形象化地显示文法的开始符号是如何派生语言的字符串的。如果非终结符A有一个产生式A → XYZ，那么解析树就具有一个内部节点A和三个子节点X,Y,Z，从左到右
正式讲，给定一个上下文无关文法，一棵解析树parse tree是具有下列属性的一棵树：
Example 2.4 在Fig2.2中，root标签是list，Example 2.1的开始节点。根节点的子从左到右分别标以list,+和digit，注意
list → list + digit
是Example 2.1文法的一个产生式。
一个解析树的叶子从左到右阅读形成tree的yield，它是一个从解析树的根节点的非终结符生成或派生的字符串。在Fig2.2，生成的字符串是9-5+2。在那个图中所有的叶子都显示在底层。以后，我们没有必要再这样排列叶子。任何树的叶子都分出一个自然的从左到右的顺序，因为如果a和b是同一个节点的两个子节点，并且a在b的左边，那么所有a的后代肯定在b后代的左边。
一种文法生成的语言的另一个定义是能够用某些解析树声称的字符串集合。根据一个给定的token字符串寻找一个解析树的过程叫做parsing解析这个字符串。
Ambiguity
我们必须小心谈论一个字符串的结构按照一个文法。虽然，每一棵解析树可以确定它派生的字符串，但是一种文法可以有多个解析树生成一个给定的token字符串。这样的文法成为ambiguous.为了显示一种文法是ambiguous的，我们只需要找出一个token字符串具有多棵解析树。这样的一个字符串通常具有多种含义，为了编译应用程序，我们必须设计无二义性的文法，或者用特殊的规则来解决文法中的二义性。
Example 2.5 假设我们不区分Example 2.1中的数字和列表，我们可以写作：
string → string + string | string - string | 0 | 1 | 2 | 3| 4| 5|6|7 |8 | 9
把digit和list合并成为非终结符string看起来是可行的，因为一个digit是list的一种特殊情况。
但是， Fig. 2.3显示象9-5+2这样的表达式现在有多棵解析树。9-5+2的两棵解析树对应表达式的两种括号形式(9-5)+2和9-(5+2)。而Example 2.1的文法不允许后面一种解释。
Associativity of Operators
按照习惯，9+5+2和(9+5)+2是等价的，而9-5-2和(9-5)-2是等价的。当一个操作数例如5左边和右边有操作符的时候，需要有约定来决定哪个操作符使用该操作数。
我们说操作符+ 结合到左边 associates to the left，因为如果一个操作符的左右两边都有加号的话，那么取左边那个操作符。在绝大多数编程语言中，四个算术操作符，加减乘除是左结合的。
某些常用的操作符例如指数是有右结合的。另外一个例子，C里面的赋值操作符=也是右结合的，在C里面表达式a=b=c和a-(b=c)是等价的。
象a=b=c这样具有右结合操作符是由下列文法生成的。
right → letter = right | letter
letter → a | b | ... | z
一个象-一样的左结合操作符和一个象=这样的右结合操作符的解析树之间的对比如图2.4:
注意9-5-2的解析树朝左下方增长，而a=b=c的解析树朝右下方增长
Precedence of Operators
考虑表达式9+5*2.有两种可能的解释方式：(9+5)*2和9+(5*2)。+和*的结合性不能解决这种模糊性。因此我们必须知道操作符的相对优先级（如果同时出现两个操作副的时候）
我们说*比+优先级更高,如果先取*后取+。在普通算术中，乘法和除法比加法和减法的优先级高。因此，5被*所取，不管是9+5*2还是9*5+2，也就是说，分别等价于9+(5*2)和((*5)+2
Syntax of expression 表达式语法。算术表达式的文法可以用一张表构造，其中显示操作符的结合性和优先级。我们从4个常见的算术操作符和一个优先级表开始，按递增的优先级显示，相同的优先级写在同一行
左结合: + -
左结合: * /
我们创建两个非终结符expr和term，分别对应这两个层次的优先级，以及一个额外的非终结符factor用来生成表达式的基本单位。表达式的基本单位是数字和括号的表达式：
factor → digit | (expr)
现在考虑二元操作符，*和/，具有最高优先级。因为这些操作符是左结合的，因此类似于那些左结合的列表
term → term * factor
| term / factor
| factor
类似的，expr生成加减
expr → expr + term
| expr - term
| term
结果文法依次为：
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → digit | (expr)
该文法把表达式看作+ 或 - 分隔的item ,而一个term则是* 或/分割的factor。注意任何括号的表达式也是一个factor，因此用括号我们可以开发具有任意深度的嵌套（也就是任意深度的树).
Syntax of statements 语句的语法 关键字允许我们识别绝大多数语言中的语句。任何Pascal语句开始一个关键字，除了赋值和过程调用。某些Pascal语句可以用下面的文法（具有两义性）来定义，其中token id代表一个标识符。
stmt → id := expr
| if expr then stmt
| if expr then stmt else stmt
| while expr do stmt
| begin opt_stmts end
非终结符opt_stmts在Example 2.3中定义。
一种文法自然地描述许多编程语言构造的层次型结构。例如C的if-else语句
if (expression) statement else statement
使用变量expre代表一个表达式，变量stmt代表一个语句，上面的规则可以表达为：
stmt → if (expr) stmt else stmt (2.1)
其中箭头可以读为"具有形式"。这样一条规则叫做一个production产生式。在一个产生式中，词法元素例如关键字if和括号叫做tokens。expr和stmt等代表token序列的变量叫做nonterminals。非终结符一个context-free grammer 具有四个组成部分：
- 一系列token，叫做终结符号terminal symbols
- 一系列非终结符
- 一系列产生式，其中每一个产生式由一个非终结符，叫做产生式的left side左边，一个箭头，以及一系列token和/或非终结符，叫做产生式的right side右边组成
- 指定的某一个非终结符叫做start symbol开始符号
传统上，文法是通过列出它们的产生式来指定的，
- start symbol列在第一个。
- 我们假定数字、象<=这样的符号，以及粗体字符串如while是终结符。
- 一个斜体的名字是一个非终结符
- 任何非斜体的名字和符号可以假设为token。
Example 2.1 本章的几个例子使用数字、加减号组成的表达式，例如9-5+2,3-1和7等等。因为一个加号或者减号必须出现在两个数字之间，我们把这样的表达式称为"由加减号分隔的数字列表"。下面的文法描述这些表达式的语法，这些产生式为：
list → list + digit (2.2)
list → list - digit (2.3)
list → digit (2.4)
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (2.5)
按照我们的约定，文法的token是
+ - 0 1 2 3 4 5 6 7 8 9
而非终结符是斜体的list和digit，其中list是开始非终结符，因为它的产生式出现在第一条
我们说一个产生式是针对for一个非终结符的，如果这个非终结符出现在产生式的左边。一个token字符串是0个或多个token组成的一个序列。包含0个token的字符串，写作ε，叫做空字符串empty string.
一个文法派生字符串，从start符号symbol开始，用一个非终结符产生式的右边重复替换该非终结符。能够从start symbol派生出来的token字符串形成该文法定义的语言language。
Example 2.2 由文法Example2.1 定义的语言由用加减号分隔的数字列表组成。
非终结符digit的10个产生式允许它代表任何一个token 0,1,.....,9。根据产生式(2.4)，一个数字本身是一个列表。产生式(2.2)和(2.3)表示，我们可以取任意列表，后面加上一个加号或减号，再后跟一个数字，我们就可以得到一个新的列表。
因此，产生式(2.2)到(2.5)可以让我们定义感兴趣的语言。例如，我们可以推断9-5+2是一个list,按照：
- a) 9是一个list(2.4)，因为9是一个digit
- b) 9-5是一个list(2.3)，因为9是一个list，而5是一个digit
- c)9-5+2是一个list(2.2)，因为9-5是一个list,而2是一个digit
Example 2.3 有点不同类型的列表是Pascal begin-end 块中的用分号隔开的语句序列。这些列表可能是一个空的语句列表在begin和end之间。我们可能开始一个文法如下：
block → begin opt_stmts end
opt_stmt → stmt_list | ε
stmt_list → stmt_list; stmt | stmt
注意opt_stmts第2个可能的右边是ε,代表空字符串。也就是说，opt_stmts可以被一个空字符串替换，因此一个block可由两个token字符串begin end组成。注意stmt_list的产生式和Example 2.1中的list相似。只不过分号代替了算术操作符，而stmt代替了digit。我们没有展示stmt的产生式。我们马上就会讨论各种不同语句的产生式，例如if语句、赋值语句等等。
Parse Tree
一棵解析树能够非常形象化地显示文法的开始符号是如何派生语言的字符串的。如果非终结符A有一个产生式A → XYZ，那么解析树就具有一个内部节点A和三个子节点X,Y,Z，从左到右
正式讲，给定一个上下文无关文法，一棵解析树parse tree是具有下列属性的一棵树：
- 根标以开始符号
- 每一个叶节点标以一个token或者ε
- 每一个内部节点都标以非终结符
- 如果A是一个标以非终结符的内部节点，而且X1,X2,....Xn是节点所有子节点的标签（从左到右）,那么A → X1X2...Xn是一个产生式。这里，X1,X2...Xn可以是一个终结符或者非终结符。特殊情况下，如果A → ε,那么标签为A的节点可能只有一个子标签为ε。
Example 2.4 在Fig2.2中，root标签是list，Example 2.1的开始节点。根节点的子从左到右分别标以list,+和digit，注意
list → list + digit
是Example 2.1文法的一个产生式。
一个解析树的叶子从左到右阅读形成tree的yield，它是一个从解析树的根节点的非终结符生成或派生的字符串。在Fig2.2，生成的字符串是9-5+2。在那个图中所有的叶子都显示在底层。以后，我们没有必要再这样排列叶子。任何树的叶子都分出一个自然的从左到右的顺序，因为如果a和b是同一个节点的两个子节点，并且a在b的左边，那么所有a的后代肯定在b后代的左边。
一种文法生成的语言的另一个定义是能够用某些解析树声称的字符串集合。根据一个给定的token字符串寻找一个解析树的过程叫做parsing解析这个字符串。
Ambiguity
我们必须小心谈论一个字符串的结构按照一个文法。虽然，每一棵解析树可以确定它派生的字符串，但是一种文法可以有多个解析树生成一个给定的token字符串。这样的文法成为ambiguous.为了显示一种文法是ambiguous的，我们只需要找出一个token字符串具有多棵解析树。这样的一个字符串通常具有多种含义，为了编译应用程序，我们必须设计无二义性的文法，或者用特殊的规则来解决文法中的二义性。
Example 2.5 假设我们不区分Example 2.1中的数字和列表，我们可以写作：
string → string + string | string - string | 0 | 1 | 2 | 3| 4| 5|6|7 |8 | 9
把digit和list合并成为非终结符string看起来是可行的，因为一个digit是list的一种特殊情况。
但是， Fig. 2.3显示象9-5+2这样的表达式现在有多棵解析树。9-5+2的两棵解析树对应表达式的两种括号形式(9-5)+2和9-(5+2)。而Example 2.1的文法不允许后面一种解释。
Associativity of Operators
按照习惯，9+5+2和(9+5)+2是等价的，而9-5-2和(9-5)-2是等价的。当一个操作数例如5左边和右边有操作符的时候，需要有约定来决定哪个操作符使用该操作数。
我们说操作符+ 结合到左边 associates to the left，因为如果一个操作符的左右两边都有加号的话，那么取左边那个操作符。在绝大多数编程语言中，四个算术操作符，加减乘除是左结合的。
某些常用的操作符例如指数是有右结合的。另外一个例子，C里面的赋值操作符=也是右结合的，在C里面表达式a=b=c和a-(b=c)是等价的。
象a=b=c这样具有右结合操作符是由下列文法生成的。
right → letter = right | letter
letter → a | b | ... | z
一个象-一样的左结合操作符和一个象=这样的右结合操作符的解析树之间的对比如图2.4:
注意9-5-2的解析树朝左下方增长，而a=b=c的解析树朝右下方增长
Precedence of Operators
考虑表达式9+5*2.有两种可能的解释方式：(9+5)*2和9+(5*2)。+和*的结合性不能解决这种模糊性。因此我们必须知道操作符的相对优先级（如果同时出现两个操作副的时候）
我们说*比+优先级更高,如果先取*后取+。在普通算术中，乘法和除法比加法和减法的优先级高。因此，5被*所取，不管是9+5*2还是9*5+2，也就是说，分别等价于9+(5*2)和((*5)+2
Syntax of expression 表达式语法。算术表达式的文法可以用一张表构造，其中显示操作符的结合性和优先级。我们从4个常见的算术操作符和一个优先级表开始，按递增的优先级显示，相同的优先级写在同一行
左结合: + -
左结合: * /
我们创建两个非终结符expr和term，分别对应这两个层次的优先级，以及一个额外的非终结符factor用来生成表达式的基本单位。表达式的基本单位是数字和括号的表达式：
factor → digit | (expr)
现在考虑二元操作符，*和/，具有最高优先级。因为这些操作符是左结合的，因此类似于那些左结合的列表
term → term * factor
| term / factor
| factor
类似的，expr生成加减
expr → expr + term
| expr - term
| term
结果文法依次为：
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → digit | (expr)
该文法把表达式看作+ 或 - 分隔的item ,而一个term则是* 或/分割的factor。注意任何括号的表达式也是一个factor，因此用括号我们可以开发具有任意深度的嵌套（也就是任意深度的树).
Syntax of statements 语句的语法 关键字允许我们识别绝大多数语言中的语句。任何Pascal语句开始一个关键字，除了赋值和过程调用。某些Pascal语句可以用下面的文法（具有两义性）来定义，其中token id代表一个标识符。
stmt → id := expr
| if expr then stmt
| if expr then stmt else stmt
| while expr do stmt
| begin opt_stmts end
非终结符opt_stmts在Example 2.3中定义。
星期五, 九月 22, 2006
2.1 OVERVIEW
描述一种语言看起来象什么(语言的语法)和它的程序意味着什么(语言的语义)可以定义一种编程语言.
除了指定语言的语法，一个上下文无关文法可以用来帮助指导程序的翻译。一种面向文法的编译技术，叫做语法导向的翻译syntax-directed translation，对组织一个编译器前端是非常有帮助的，并且在本章中大量使用。
在讨论语法导向翻译的过程中，我们应该构造一个编译器，把中缀表达式转换为后缀形式，一种记法－其中操作符出现在操作数的后面。例如，中缀表达式9-5+2的后缀表达形式是95-2+。后缀表达式可以直接翻译成一种计算机的代码，这种计算机使用一个stack执行它的所有计算。
我们从构造一个简单的程序开始，把数字组成、加减号分开的表达式转换成后缀形式。基本的想法清楚以后，我们扩展程序处理更加通用的编程语言构造。我们的每个翻译器都通过扩展前一个得到。
在我们的编译器中，词法分析器把输入的字符流变成token流，然后变成下一阶段的输入，如Fig.2.1 所示
图中，syntax-directed translator 是一个语法分析器和一个中间代码生成器的组合。
从数字组成的表达式开始的原因是，词法分析可以很简单。每一个输入字符形成一个token.
后面我们会扩展语言包含词法构造例如数字、标识符和关键字。我们会为之构造一个词法分析器，收集连续的输入字符成为合适的token。
- 为了指定语法的语法，我们给出一种广泛使用的记法，叫做上下文无关文法或者BNF(Backus-Naur Form)。
- 有了这种记法，描述一种语言的语义要比语法难得多了。为了指定一种语言的语义，我们应该使用非形式化的描述和建议的范例
除了指定语言的语法，一个上下文无关文法可以用来帮助指导程序的翻译。一种面向文法的编译技术，叫做语法导向的翻译syntax-directed translation，对组织一个编译器前端是非常有帮助的，并且在本章中大量使用。
在讨论语法导向翻译的过程中，我们应该构造一个编译器，把中缀表达式转换为后缀形式，一种记法－其中操作符出现在操作数的后面。例如，中缀表达式9-5+2的后缀表达形式是95-2+。后缀表达式可以直接翻译成一种计算机的代码，这种计算机使用一个stack执行它的所有计算。
我们从构造一个简单的程序开始，把数字组成、加减号分开的表达式转换成后缀形式。基本的想法清楚以后，我们扩展程序处理更加通用的编程语言构造。我们的每个翻译器都通过扩展前一个得到。
在我们的编译器中，词法分析器把输入的字符流变成token流，然后变成下一阶段的输入，如Fig.2.1 所示
图中，syntax-directed translator 是一个语法分析器和一个中间代码生成器的组合。
从数字组成的表达式开始的原因是，词法分析可以很简单。每一个输入字符形成一个token.
后面我们会扩展语言包含词法构造例如数字、标识符和关键字。我们会为之构造一个词法分析器，收集连续的输入字符成为合适的token。
Chapter 2 A Simple One-Pass Compiler
本章是对3－8章中材料的一个介绍。
展现一系列基本的编译技术，开发一个可以工作的C程序，把中缀表达式翻译为后缀形式
重点是编译器的前端－词法分析、解析和中间代码生成。
展现一系列基本的编译技术，开发一个可以工作的C程序，把中缀表达式翻译为后缀形式
重点是编译器的前端－词法分析、解析和中间代码生成。
1.6 COMPILER-CONSTRUCTION TOOLS
两类工具：
就在第一个编译器完成后不久，帮助编写编译器的系统就出现了。这些系统通常称为编译器编译器compiler-compilers，编译器生成器compiler-generators或者翻译器编写系统 translator-writing systems。很大程度上，他们面向一种特定的语言模型，它们最适合生成和该模型类似的语言的编译器。
例如，或许假设所有语言的词法分析器基本上是相同的，除了特定的关键字和符号。
某些通用的工具用于特定编译器部件的自动化设计。这些工具使用专用语言指定并实现部件，很多使用非常复杂的算法。最成功的是那些隐藏了算法细节，同时产生可能轻易集成到编译器其它组成部分的那些工具。下面是一些有用的编译器构造工具：
- 通用：编译器的编写者和任何程序员一样，当然可以从各种软件工具获益，例如debugger,version manager, profiles等等。
- 专用：除了这些通用的软件开发工具之外，还有一些专用的工具，帮助实现一个编译器的不同阶段
就在第一个编译器完成后不久，帮助编写编译器的系统就出现了。这些系统通常称为编译器编译器compiler-compilers，编译器生成器compiler-generators或者翻译器编写系统 translator-writing systems。很大程度上，他们面向一种特定的语言模型，它们最适合生成和该模型类似的语言的编译器。
例如，或许假设所有语言的词法分析器基本上是相同的，除了特定的关键字和符号。
- 许多编译器编译器实际上产生固定的词法分析例程，用于生成的编译器。
- 这些例程只在识别的关键字列表上有所不同，而这个列表由用户提供。
- 这种方法是有效的，但是如果需要识别非标准的token时就可能无法工作，例如某些标识符包含字母和数字之外的字符。
某些通用的工具用于特定编译器部件的自动化设计。这些工具使用专用语言指定并实现部件，很多使用非常复杂的算法。最成功的是那些隐藏了算法细节，同时产生可能轻易集成到编译器其它组成部分的那些工具。下面是一些有用的编译器构造工具：
- Parser generator 解析器生成器，这些产生语法分析器，通常从输入基于一个上下文无关文法。在早期的编译器中，被消费的语法分析不但一个编译器运行时间的大部分，而且是编写一个编译器所需智力活动的大部分。现在这个阶段被认为是最容易实现的阶段之一。许多解析器生成器利用了强大的解析算法，手工实现的话就太过复杂了。
- Scanner generators 扫描器生成器 自动生成词法分析器，通常来自一个规格，基于正则表达式。结果的词法分析器的基本组织是一个有穷自动机。
- Syntax-directed translation engines 语法导向翻译引擎 产生遍历解析树（如图1.4）的一套例程,生成中间代码。基本的思想是一个或多个“翻译”是和解析树的每一个节点相关的，而每一个翻译用它在树中相邻节点的翻译得以定义。
- Automatic code generate 自动代码生成器取一套规则，定义把中间语言的每个操作翻译成目标机器机器语言的方法。这些规则必须包含足够的细节，以便我们能够处理数据的不同存取方法，例如，变量可能在寄存器中，在一个内存的固定（静态）位置，可能在一个栈上分配的一个位置。
基本的技术是“模版匹配”"template matching"。中间代码语句被代表机器指令序列的“模版”替换。因为通常有在哪里替换变量（例如在寄存器之1或者在内存中）有很多选项，因此有很多可能的方式把中间代码“铺”到一个给顶的模版集合，有必要选择一种好的铺法，而不会产生编译器运行时间的组合爆发。 - Data-flow engine 数据流引擎。许多代码优化都需要首先进行数据流分析，收集关于值是如何从一个程序的一部分传送到另一部分的信息。这种性质的不同任务可以被基本相同的例程执行，用户提供中间代码语句和被收集信息之间的关系。
1.5 THE GROUPING OF PHASES
1.3的讨论是丛一个编译器的逻辑方面来得。实现的时候，几个阶段的活动通常分组在一起。
Front and Back Ends
通常，阶段分为一个前端front end和一个后端back end。
分开的好处
Passes
编译的不同阶段通常实现为一个pass遍，一遍从输入文件读取代码并且写出到输出文件中。
而实践中，编译器的各个阶段如何被组织成遍有很大的差异，因此我们从阶段而不是遍的角度来讨论更加好一点。
12章会讨论一些代表性的编译器，以及它们如何把阶段组织成遍。
通常把几个阶段组织成一遍，而这些阶段的活动在遍中相互交叉。例如，词法分析、语法分析、语义分析和中间代码生成可能组织成一遍。如果这样做得话，词法分析后的token流可能被直接翻译成中间代码：
遍数的两难：
特别是，中间代码和目标代码生成通常能够被合并成一遍，使用一种叫做"backpatching"的技术。
虽然在第8章中间代码生成之前，我们不能解释所有的细节，但是我们还是能够用汇编器演示backpathcing的过程。
回忆一下，我们将过两遍汇编器，第一遍发现所有代表内存位置的标识符并且推断它们的地址。第2遍用地址替换标识符。
我们可以组合各遍的动作如下：在碰到一个是向前引用的汇编语句时：
GOTO target
我们生成一个骨架指令，GOTO的机器操作码，但是地址为空白。所有地址为空白target的指令都保存在一个列表中，和符号表中的target的条目关联。当我们最后遇到一个下面这样的指令：
target: MOV foobar, R1
的时候，可以确定target的值：就是当前指令的地址，并且可以把空白填上了。
于是我们进行"backpatch"，通过遍历target对应的列表，所有的指令都需要它的地址，把地址中空白的位替换为当前的地址。这种方法比较容易实现，如果指令保存在内存中直至所有的目标地址都计算完毕。
这种方法对那些能够把所有的输出保存在内存中的汇编器还是不错的。因为对汇编器而言，代码的中间和最终表现形式大致相同，因此具有近似的长度，baclpatching 整个汇编程序的长度并不是不可行的。
但是，在一个编译器中，中间代码需要消耗大量的空间，我们可能需要小心backpatching发生的距离。
Front and Back Ends
通常，阶段分为一个前端front end和一个后端back end。
- 前端包括哪些阶段或者阶段的部分，主要依赖于源程序，而和目标机器尽量无关。通常包括词法和语法分析，符号表的创建，语义分析以及中间代码的生成。一定数量的代码优化也可以在前端完成。前端当然也包括这些阶段相应的错误处理。
- 后端包括编译器中那些依赖于目标机器的部分，一般来说，这些部分不依赖于源程序，而只依赖于中间语言。包括代码优化阶段，代码生成阶段以及相应的错误处理和符号表操作。如果后端被小心设计，那么可能不必要对后端做太多的重新设计。
分开的好处
- 可以直接取一个编译器的前端，然后重做相关的后端，那么编译器就可以把同一种源语言编译到不同的机器。
- 也有可能编译不同的语言到相同的中间语言，为不同的前端使用一个通用的后端，从而在同一台机器上获得不同的编译器。
Passes
编译的不同阶段通常实现为一个pass遍，一遍从输入文件读取代码并且写出到输出文件中。
而实践中，编译器的各个阶段如何被组织成遍有很大的差异，因此我们从阶段而不是遍的角度来讨论更加好一点。
12章会讨论一些代表性的编译器，以及它们如何把阶段组织成遍。
通常把几个阶段组织成一遍，而这些阶段的活动在遍中相互交叉。例如，词法分析、语法分析、语义分析和中间代码生成可能组织成一遍。如果这样做得话，词法分析后的token流可能被直接翻译成中间代码：
- 更细一点，我们可以把语法分析器考虑为正被"in charge"。
- 它试图发现所看到的token的文法结构，在需要的时候获取token，
- 通过调用词法分析器来寻找下一个token.
- 当它发现文法结构的时候，解析器调用中间代码生成器执行语义分析、并生成这部分代码。
遍数的两难：
- 我们希望遍数相对较少，因为读取和写出中间文件需要时间。
- 另一方面，我们把几个阶段组织成一遍，我们可能被强制要求在内存中保留整个程序，因为一个阶段需要的信息和前一个阶段直接产生的信息可能具有不同顺序。
- 程序的中间形式可能会比整个源程序和目标程序大得多，因此空间不是一件简单的事情。
- 对某些阶段而言，把它们组织成一遍不会有太多问题。例如，词法分析器和语法分析器之间的接口通常只限于一个token。
- 另一方面,如果中间表现形式还没有完全生成，那么就很难进行代码生成。
- 例如，某些语言如PL/1和Algol 68允许在变量声明前使用它们。我们不能生成该构造的目标代码，如果我们不知道产生这个构造的相关变量类型。
- 类似，绝大多数语言允许用goto在代码中向前跳跃。我们不能决定一个跳跃的目标地址，如果还没有看到介于中间的源代码和为它生成的中间代码
特别是，中间代码和目标代码生成通常能够被合并成一遍，使用一种叫做"backpatching"的技术。
虽然在第8章中间代码生成之前，我们不能解释所有的细节，但是我们还是能够用汇编器演示backpathcing的过程。
回忆一下，我们将过两遍汇编器，第一遍发现所有代表内存位置的标识符并且推断它们的地址。第2遍用地址替换标识符。
我们可以组合各遍的动作如下：在碰到一个是向前引用的汇编语句时：
GOTO target
我们生成一个骨架指令，GOTO的机器操作码，但是地址为空白。所有地址为空白target的指令都保存在一个列表中，和符号表中的target的条目关联。当我们最后遇到一个下面这样的指令：
target: MOV foobar, R1
的时候，可以确定target的值：就是当前指令的地址，并且可以把空白填上了。
于是我们进行"backpatch"，通过遍历target对应的列表，所有的指令都需要它的地址，把地址中空白的位替换为当前的地址。这种方法比较容易实现，如果指令保存在内存中直至所有的目标地址都计算完毕。
这种方法对那些能够把所有的输出保存在内存中的汇编器还是不错的。因为对汇编器而言，代码的中间和最终表现形式大致相同，因此具有近似的长度，baclpatching 整个汇编程序的长度并不是不可行的。
但是，在一个编译器中，中间代码需要消耗大量的空间，我们可能需要小心backpatching发生的距离。
星期四, 九月 21, 2006
1.4 COUSINS OF THE COMPILER
我们在Fig. 1.3看到过，输入到一个编译器之前可能先要经过预处理器，而编译器的输出可能进一步处理才能变成真正可以运行的机器码。
Preprocessors
预处理器为编译器产生输入。可能执行：
Example 1.2 TEX字处理系统包含一个通用的宏设施。宏定义的格式如下：
\define <macro name> <template> {<body>}
宏的名字是任何字母字符串前面加反斜杠。template模版是任何字符串，其中#1,#2,....#9被看作形式参数。这些符号也出现在body中，可以任意次数。例如，下面的宏定义对Journal of the ACM的一个引用：
\define\JACM #1;#2;#3.
{{\sl J. ACM} {\bf #1}:#2, pp. #3.}
宏的名字是\JACM，模版是"#1;#2;#3." ;把参数分开，最后的参数后面跟一个句号。
使用这个宏取template的形式，除了用任意字符串替换形式参数。因此，我们可以写：
\JACM 17;4;715-728.
那么就能看到：
J.ACM 17:4 pp. 715-728
body中{\s1 J. ACM}部分表示要对J.ACM进行斜体。表达式{\bf #1}说第一个参数应该粗体，这个参数用作volumn号。
TEX允许在\JACM的定义中使用任何标点符号或文本字符串分隔volumn, issue和page number。我们甚至可以根本不用标点符号。此时TEXT会取每一个实际参数为一个字符或者一个{}括起来的字符串。
Assembles
汇编代码和机器代码的关系：
Assembly code 汇编代码是机器码的助记缩写版本，其中用名字代替操作的二进制代码，内存的地址也用名字代替。一个典型的汇编指令序列可能是：
MOV a, R1
ADD #2, R1
MOV R1, b (1.6)
这份代码把地址a的值移入寄存器1，然后对它加上常量2，把寄存器1的内容作为一个定点数字，最后把结果保存到b命名的位置。因此，它计算b := a + 2.
Two-Pass Assembly
最简单的汇编器在输入上进行两遍，其中一pass遍对输入文件读取一次。
Loaders and Link-Editors
通常一个程序loader执行loading和link-editing两个功能。
可重定位的机器代码文件必须为每一个被外部引用的数据位置或指令标签保留符号表中的信息。如果我们事先不知道什么可能被引用，那么我们必须包含整个汇编器符号表，作为机器代码的一部分。
例如，代码(1.7)可能产生
a 0
b 4
如果一个和(1.7)一起加载的文件引用(1.7)b，那么引用将被4代替，加上文件(1.7)被重定位时的数据位置偏移。
Preprocessors
预处理器为编译器产生输入。可能执行：
- Macro processing。允许为长的构造定义短的宏
- File inclusion .把头文件包含到程序文本
- "Rational " precessors 。
- Language extensions.这些处理器试图向语言加入新的能力。例如Qquel是数据库查询语言嵌入到C。##开始的语句由预处理器处理，翻译为执行数据库存取的例程。
- 宏定义－一般有某些唯一的字符或关键字指定，例如define或者macro，通常包含
- 被定义的宏的名字
- 一个body
- 通常，宏预处理器允许在它们的定义中使用形式参数formal parameters，也就是将被值替换的符号（值在这个上下文中，是一个字符串)
- 宏使用提供宏的名字和实际参数actual parameters，也就是形式参数的值。
- 宏处理器用实际参数替换body中的形式参数
- 转换后的body代替了宏本身
Example 1.2 TEX字处理系统包含一个通用的宏设施。宏定义的格式如下：
\define <macro name> <template> {<body>}
宏的名字是任何字母字符串前面加反斜杠。template模版是任何字符串，其中#1,#2,....#9被看作形式参数。这些符号也出现在body中，可以任意次数。例如，下面的宏定义对Journal of the ACM的一个引用：
\define\JACM #1;#2;#3.
{{\sl J. ACM} {\bf #1}:#2, pp. #3.}
宏的名字是\JACM，模版是"#1;#2;#3." ;把参数分开，最后的参数后面跟一个句号。
使用这个宏取template的形式，除了用任意字符串替换形式参数。因此，我们可以写：
\JACM 17;4;715-728.
那么就能看到：
J.ACM 17:4 pp. 715-728
body中{\s1 J. ACM}部分表示要对J.ACM进行斜体。表达式{\bf #1}说第一个参数应该粗体，这个参数用作volumn号。
TEX允许在\JACM的定义中使用任何标点符号或文本字符串分隔volumn, issue和page number。我们甚至可以根本不用标点符号。此时TEXT会取每一个实际参数为一个字符或者一个{}括起来的字符串。
Assembles
某些编译器产生汇编代码，如(1.5)，然后把它传给一个汇编器进一步处理。 其他编译器执行汇编器的工作，产生可重定位的机器代码，可以直接传输给loader/link-editor。
汇编代码和机器代码的关系：
Assembly code 汇编代码是机器码的助记缩写版本，其中用名字代替操作的二进制代码，内存的地址也用名字代替。一个典型的汇编指令序列可能是：
MOV a, R1
ADD #2, R1
MOV R1, b (1.6)
这份代码把地址a的值移入寄存器1，然后对它加上常量2，把寄存器1的内容作为一个定点数字，最后把结果保存到b命名的位置。因此，它计算b := a + 2.
Two-Pass Assembly
最简单的汇编器在输入上进行两遍，其中一pass遍对输入文件读取一次。
第一遍，所有指定存储位置的标识符被发现，并且保存到符号表（和编译器无关）。第一次碰到标识符时，为它们分配存储位置，因此例如在读取(1.6)以后，符号表可能包含如Fig. 1.12这些条目。 
此图中，我们假设一个WORD，包含4个字节，为每一个标识符分配，地址从0开始分配- 第2遍，汇编器再次检查输入。这一次，它把每一个操作代码翻译为该操作在机器语言中的bit序列,同时把每一个代表一个位置的标识符翻译为符号表中登记的该标识符的地址。
- 第2遍的输出通常是relocatable可重定位的机器代码，意味着它可以从任何位置L开始加载：也就是说，L被加到代码中的所有地址，那么所有的引用都能够正确了。因此，汇编器的输出必须区分指令中引用到地址的部分
- Example 1.3 下面是1.6翻译后假想的机器代码
0001 01 00 00000000 ＊
0011 01 10 00000010
0010 01 00 00000100 ＊ （1.7)
我们预想一个很小的指令字：- 其中前面4位是指令代码，0001,0010和0011各自代表load,store和add。load和store意味着从内存移到寄存器或相反；
- 接下去的两位指定一个寄存器，01指三条指令中的寄存器1.
- 这之后的两位代表一个'tag'
- 其中00代表普通地址模式，后8位指向内存地址。
- tag 10代表"立即"immediate模式，最后8为取作操作数的字面意义。该模式出现在(1.7)的第2条指令中。
- (1.7)的第1行和第3行有1个*，*代表可重定位的位relocation bit，和可重定位机器代码的每一个操作数相关。假设包含数据的地址空间被加载到起始位置L。那么*的存在表示L必须加到指令的地址上。因此，如果L = 00001111，也就是15，那么a和b分别在位置15和19。(1.7)的指令变为：
0001 01 00 00001111
0011 01 10 00000010
0010 01 00 00010011 （1.8)
这是绝对的，或者不可重定位的机器代码。注意(1.7)的第2条指令没有*，因此L也不会加到它的地址上，这当然是正确的，因为这些bit代表的是常量2，而不是位置2。
Loaders and Link-Editors
通常一个程序loader执行loading和link-editing两个功能。
- 加载的过程包括取可重定位的机器代码，按照前面讨论的方法改变可重定位的地址，替换内存中适当位置被改变的指令和数据。
- 连接编辑器允许我们用多个可重定位机器代码文件组成一个程序。这些文件可能是不同编译的结果，以及系统提供例程的一个或多个库文件。
- 这种引用可能是在一个文件中定义的数据位置，在另外一个文件中使用
- 或者可能是一个过程的入口点出现在一个文件的代码中，在另一个文件中对它进行调用
可重定位的机器代码文件必须为每一个被外部引用的数据位置或指令标签保留符号表中的信息。如果我们事先不知道什么可能被引用，那么我们必须包含整个汇编器符号表，作为机器代码的一部分。
例如，代码(1.7)可能产生
a 0
b 4
如果一个和(1.7)一起加载的文件引用(1.7)b，那么引用将被4代替，加上文件(1.7)被重定位时的数据位置偏移。
1.3 THE PHASES OF A COMPILER
概念上，一个编译器操作于阶段phases，每一个阶段把源程序从一种表现形式转换为另一种。一个编译器的典型分解如图Fig 1.9所示。实践中，某些阶段可能组合在一起，如1.5所提到的，分组的阶段之间的中间表现形式不需要明确构造出来。
开始3个阶段，形成一个编译器的分析部分，在上一节中已经介绍。另外两个活动，符号表管理和错误处理，显示出和6个阶段之间的交互－词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成。口头上，我们把symbol-table manager和错误处理也叫做"阶段".
Symbol-Table Management
一个编译器的基本功能之一是记录源程序中使用的标识符，收集和每个标识符相关的各种属性信息。这些属性可能提供一个标识符的存储分配信息、它的类型、范围(在程序的哪些地方有效)，以及，标识符是过程名字的情况下，象参数的数目和名字，每个参数传递的方法(例如通过引用)和返回的类型等等。
一个符号表symbol table 是记录每个标识符以及相应属性字段的数据结构。该数据结构允许我们快速寻找每一个标识符的记录，快速存储和获取该该记录中的数据。符号表在第2章和第7章讨论。
当一个源程序中的标识符被词法分析器检测到的时候，该标识符进入符号表。但是，标识符的属性通常无法在词法分析时决定。例如，一个Pascal 声明：
var position , initial , rate :real;
词法阶段看到position,initial和rate的时候，real类型还不知道。
剩下的阶段在符号表中加入标识符相关的信息，并且以各种方式使用这些信息。例如，在语义分析和中间代码生成阶段，我们需要知道标识符的类型，所以我们检查源程序有效使用他们的方式，从而我们能够生成相关的正确操作。代码生成器通常输入并使用标识符存储分配相关的详细信息。
Error Detection and Reporting
每一个阶段都可能碰到错误。
通常语法和语义分析阶段处理编译器能够检测到的大部分错误。词法阶段可以检测到错误其中输入中剩余的字符不能形成语言的任何token。那些token流违反语言的结构规则（语法）的错误由语法分析阶段判断。而在语义分析阶段，编译器试图检测具有正确的语法结构但是没有任何意义的操作，例如，如果我们试图把两个标识符相加，其中一个是数组的名字，而另外一个是过程的名字。
The Analysis Phases
随着翻译的进展，编译器对于源程序的内部表现形式也随之发生变化。我们通过考虑下面语句的翻译来演示这些表现形式：
position := initial + rate * 60 (1.1)
Figure 1.10 显示了该语句在每一阶段之后的表现形式：
词法阶段读取源程序中的字符，把它们分组为token流，每个token代表一个逻辑内聚的字符序列，例如一个标识符，一个关键字(if, while等等)，一个标点字符，或者一个多字符操作符如:=。字符序列形成一个token成为token的lexeme.
某些token具有"词法值"。例如，发现rate这个标识符时，词法分析器不但需要生成一个toke，id，还需要把lexeme rate进入到符号表，如果还没有被加入的话。和这一次id出现相关的值指向符号表的rate条目。
这一节中，我们使用id1,id2,id3分别代表postion, initial和rate，重点突出一个标识符的内部表现形式和形成标识符的字符序列是不同的。因此，(1.1)词法分析以后的表现形式是：
id1 := id2 + id3 * 60 (1.2)
当然:=和60也应该有token，但目前先放一放
第2和第3阶段，语法和语义分析，已经介绍过。语法分析在token流之上构造一个层次结构，我们可以用Fig 1.11(a)描述。Fig 1.11(b)显示了实现这种树的一个常用的数据结构，
Intermediate Code Generation
语法和语义分析以后，某些编译器生成源程序的显式中间表现形式。我们可以把这种中间表达形式看作一个抽象机器的程序。这种中间表达形式应该具有两个重要属性：
可能具有各种形式，第8章有一种中间形式叫做"三地址代码" three-address code，类似于一种机器的汇编语言，其中每一个内存地址都可以当作一个寄存器。
三地址代码由一个指令序列组成，每一条最多可以有三个操作数。(1.1)源程序的三地址形式可能如下：
temp1 := inttoreal(60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3 (1.3)
这种中间形式可以有几个属性。
代码优化阶段试图增强中间代码，以便快速运行将被产生的机器代码。
某些优化很简单，例如一个自然的算法产生中间代码(1.3)，语义分析后树表达形式中每一个操作符都需要使用一条指令，即使有更好的方法执行相同的计算。
使用两条指令
temp1 := id3 * 60.0
id1 = id2 + temp1 (1.4)
上面这种简单算法并没有问题，因为代码优化阶段能够修正。
不同的编译器在执行代码优化的数量上有很大的差异。
Code Generation
编译器的最后阶段是目标代码的生成，一般由可重定位的机器代码或汇编代码组成。程序使用的每一个变量都会选择好内存地址。然后，中间指令每一条被翻译成执行相同任务的一系列机器指令。一个关键的方面是把变量和寄存器之间的赋值。
例如，使用寄存器1和2，代码(1.4)的翻译可能如下：
MOVF id3, R2
MULF #60.0 R2
MOVF id2, R!
ADDF R2, R1
MOVF R1, id1 (1.5)
每一条指令的第一个和第二个操作数指令相应的源和目标。每条指令中的F告诉我们指令处理浮点数字。
开始3个阶段，形成一个编译器的分析部分，在上一节中已经介绍。另外两个活动，符号表管理和错误处理，显示出和6个阶段之间的交互－词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成。口头上，我们把symbol-table manager和错误处理也叫做"阶段".
Symbol-Table Management
一个编译器的基本功能之一是记录源程序中使用的标识符，收集和每个标识符相关的各种属性信息。这些属性可能提供一个标识符的存储分配信息、它的类型、范围(在程序的哪些地方有效)，以及，标识符是过程名字的情况下，象参数的数目和名字，每个参数传递的方法(例如通过引用)和返回的类型等等。
一个符号表symbol table 是记录每个标识符以及相应属性字段的数据结构。该数据结构允许我们快速寻找每一个标识符的记录，快速存储和获取该该记录中的数据。符号表在第2章和第7章讨论。
当一个源程序中的标识符被词法分析器检测到的时候，该标识符进入符号表。但是，标识符的属性通常无法在词法分析时决定。例如，一个Pascal 声明：
var position , initial , rate :real;
词法阶段看到position,initial和rate的时候，real类型还不知道。
剩下的阶段在符号表中加入标识符相关的信息，并且以各种方式使用这些信息。例如，在语义分析和中间代码生成阶段，我们需要知道标识符的类型，所以我们检查源程序有效使用他们的方式，从而我们能够生成相关的正确操作。代码生成器通常输入并使用标识符存储分配相关的详细信息。
Error Detection and Reporting
每一个阶段都可能碰到错误。
- 但是，检测到一个错误以后，一个阶段必须处理错误，以便编译能够进行下去，允许检测到源程序中更多的错误。
- 一碰到错误就停止的编译器没有能够提供它应该可以提供的帮助。
通常语法和语义分析阶段处理编译器能够检测到的大部分错误。词法阶段可以检测到错误其中输入中剩余的字符不能形成语言的任何token。那些token流违反语言的结构规则（语法）的错误由语法分析阶段判断。而在语义分析阶段，编译器试图检测具有正确的语法结构但是没有任何意义的操作，例如，如果我们试图把两个标识符相加，其中一个是数组的名字，而另外一个是过程的名字。
The Analysis Phases
随着翻译的进展，编译器对于源程序的内部表现形式也随之发生变化。我们通过考虑下面语句的翻译来演示这些表现形式：
position := initial + rate * 60 (1.1)
Figure 1.10 显示了该语句在每一阶段之后的表现形式：
词法阶段读取源程序中的字符，把它们分组为token流，每个token代表一个逻辑内聚的字符序列，例如一个标识符，一个关键字(if, while等等)，一个标点字符，或者一个多字符操作符如:=。字符序列形成一个token成为token的lexeme.
某些token具有"词法值"。例如，发现rate这个标识符时，词法分析器不但需要生成一个toke，id，还需要把lexeme rate进入到符号表，如果还没有被加入的话。和这一次id出现相关的值指向符号表的rate条目。
这一节中，我们使用id1,id2,id3分别代表postion, initial和rate，重点突出一个标识符的内部表现形式和形成标识符的字符序列是不同的。因此，(1.1)词法分析以后的表现形式是：
id1 := id2 + id3 * 60 (1.2)
当然:=和60也应该有token，但目前先放一放
第2和第3阶段，语法和语义分析，已经介绍过。语法分析在token流之上构造一个层次结构，我们可以用Fig 1.11(a)描述。Fig 1.11(b)显示了实现这种树的一个常用的数据结构，
- 其中一个内部节点是一个纪录，具有一个操作符相关的字段，以及两个指针字段指向左和右子节点。
- 一个叶节点具有两个或多个字段，一个确定在叶子上的token，其它的记录该token的相关信息。
Intermediate Code Generation
语法和语义分析以后，某些编译器生成源程序的显式中间表现形式。我们可以把这种中间表达形式看作一个抽象机器的程序。这种中间表达形式应该具有两个重要属性：
- 容易产生
- 容易翻译为目标程序
可能具有各种形式，第8章有一种中间形式叫做"三地址代码" three-address code，类似于一种机器的汇编语言，其中每一个内存地址都可以当作一个寄存器。
三地址代码由一个指令序列组成，每一条最多可以有三个操作数。(1.1)源程序的三地址形式可能如下：
temp1 := inttoreal(60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3 (1.3)
这种中间形式可以有几个属性。
- 首先，每条三地址指令除了赋值外最多有一个操作符，因此，在生成这些指令的时候，编译器必须决定操作的顺序，源程序(1.1)中，乘法比加法优先
- 其次，编译器必须生成临时的名字保存每一条指令计算得到的值。
- 第三，某些“三地址”指令可能少于三个操作数，例如(1.3)的第一条和最后一条指令
代码优化阶段试图增强中间代码，以便快速运行将被产生的机器代码。
某些优化很简单，例如一个自然的算法产生中间代码(1.3)，语义分析后树表达形式中每一个操作符都需要使用一条指令，即使有更好的方法执行相同的计算。
使用两条指令
temp1 := id3 * 60.0
id1 = id2 + temp1 (1.4)
上面这种简单算法并没有问题，因为代码优化阶段能够修正。
- 也就是说，编译器能够推断把60从整数转换为实数表现形式可以一次完全，并且可以在编译时刻完成，所以inttoreal操作可以消除。
- 另外，temp3只使用一次，目的是把值传输给id1，因此用id1替换temp3是安全的，因此(1.3)最后一条语句是不需要的，结果产生1.4代码。
不同的编译器在执行代码优化的数量上有很大的差异。
- 做得最多的那种，叫做“优化编译器”"optimizing compilers"，编译的大部分时间都花在这个阶段。
- 但是，某些简单的优化可以大大改善目标程序的运行时间而不会太降低编译的速度。
Code Generation
编译器的最后阶段是目标代码的生成，一般由可重定位的机器代码或汇编代码组成。程序使用的每一个变量都会选择好内存地址。然后，中间指令每一条被翻译成执行相同任务的一系列机器指令。一个关键的方面是把变量和寄存器之间的赋值。
例如，使用寄存器1和2，代码(1.4)的翻译可能如下：
MOVF id3, R2
MULF #60.0 R2
MOVF id2, R!
ADDF R2, R1
MOVF R1, id1 (1.5)
每一条指令的第一个和第二个操作数指令相应的源和目标。每条指令中的F告诉我们指令处理浮点数字。
- 代码把地址id3的内容移到寄存器2，
- 然后把它和实数常量60相乘。#表示60.0是一个常量。
- 第3条指令把id2移到寄存器1，
- 然后把它和前面计算后放在寄存器2中的值相加。
- 最后，寄存器1的值移到id1的地址,因此代码实现Fig. 1.10中的赋值。
星期三, 九月 20, 2006
1.2 ANALYSIS OF THE SOURCE PROGRAM
本节介绍分析、展示在某些文本格式化语言中的应用。
在编译中，分析包括3个阶段：
在一个编译器中，线性分析叫做lexical analysis 或者 scanning。例如，在词法分析中，赋值语句中的字符
position := initial + rate * 60
会分组为下列token
用来分隔这些token的字符通常在词法分析阶段就被排除了
Syntax Analysis
层次型的分析叫做parsing或者syntax analysis。把源程序的token分组为文法词组，编译器可以用来合成输出。通常源程序的文法词组用一棵解析树代表，如下图Fig 1.4
在表达式 initial + rate * 60中，词组rate * 60是一个逻辑单元，因为通常的算术表达式习惯告诉我们乘法应该在加法前计算。因为表达式initial+rate后跟一个* ，所以它们不能组成一个词组。
程序的层次型结构通常用递归规则来表达。例如，我们可以用下面的规则来定义上面的表达式
类似地，许多语言用规则递归定义语句如下：
第2章和第5章详细讨论，syntax-directed translation语法导向翻译，其中编译器使用输入的层次型结构帮助生成输出
Semantic Analysis
语义分析阶段检查源程序是否有语义错误，并且为后继代码生成阶段收集类型信息。它使用语法分析阶段得到的层次型结构确定表达式和语句操作符和操作数
语义分析的一个重要组成部分是类型检查。这里编译器检查每一个操作符，看看它们的操作数类型是否为源语言规格所允许。例如，许多编程语言定义需要一个编译器每次发现把一个real作为数组下标的时候报告错误。但是语言的规格可能允许某些操作数转换，例如，当一个二元算术操作符对一个整数和一个实数操作的时候。此时，编译器可能需要把integer转换成real。
例1在一种机器内，表达一个整数的位模式bit pattern一般来说和表达一个实数的位模式是不同的，就算整数和实数的值一样也是如此。现在假设，所有Fig1.5中的标识符都声明为real，而60自己是一个integer。Fig1.5(a)的类型检查发现*应用于一个实数rate，和一个整数60。一般的做法是把integer转换成real.Fig1.5(b)插入了一个额外的节点，操作符为inttoreal，显式地把整数转换为一个实数。也可以选择两外一种做法，因为inttoreal的操作数是一个常量，编译器可以直接把整数常量替换成相等的实数常量。
Analysis in Text Formatters
可以把一个文本格式化器的输入看作指定boxes的一个层次，box都是矩形区域，被某些位模式所填充，代表浅色和深色像素，然后由输出设备打印。
例如Tex系统用这种方法显示它的输入。每一个不是命令组成部分的字符代表一个包含该字符bit pattern的box，辅以适当的字体和大小。不被“空白”分开的字符组成单词，由一系列横向放置的box组成，Fig1.6图解这一结构。组成单词（或者命令）的字符是文本格式化器分析的线性或者词法方面。
TEX中的Box可能是通过任意横向和纵向组合更小的box生成的。例如：
\hbox{
这些操作符可以递归应用，例如EQN文本
a sub {i sup 2}
产生
。把操作符sub和sup分组为token是EQN文本的词法分析部分，但是文本的语法结构需要判断box的大小和放置。
在编译中，分析包括3个阶段：
- Linear analysis: 组成源程序的字符流从左到右读进来，分组为tokens，具有联合意义的字符串序列
- Hierarchical analysis 字符或者token被层次型组织为具有联合意义的嵌套集合
- Semantic analysis 执行一定的检查，确保程序的组成部分能够有意义地配合在一起
在一个编译器中，线性分析叫做lexical analysis 或者 scanning。例如，在词法分析中，赋值语句中的字符
position := initial + rate * 60
会分组为下列token
- 标识符position
- 赋值符号 :=
- 标识符intial
- 加号+
- 标识符rate
- 乘号*
- 数字60
用来分隔这些token的字符通常在词法分析阶段就被排除了
Syntax Analysis
层次型的分析叫做parsing或者syntax analysis。把源程序的token分组为文法词组，编译器可以用来合成输出。通常源程序的文法词组用一棵解析树代表，如下图Fig 1.4
在表达式 initial + rate * 60中，词组rate * 60是一个逻辑单元，因为通常的算术表达式习惯告诉我们乘法应该在加法前计算。因为表达式initial+rate后跟一个* ，所以它们不能组成一个词组。
程序的层次型结构通常用递归规则来表达。例如，我们可以用下面的规则来定义上面的表达式
- 任何identifier都是一个expression
- 任何number都是一个expression
- 如果expression1和expression2都是表达式，那么下面都是表达式
- expression1 + expression2
- expression1 * expression2
- ( expression1 )
类似地，许多语言用规则递归定义语句如下：
- 如果identifier1是一个标识符，而expression2是一个表达式，那么
identifier1 := expression2
是一个语句 - 如果expression1是一个表达式，而statement2是一个语句，那么
while ( expression1 ) do statement2
if ( expression1 ) then statement2
都是语句
- 例如，识别标识符不需要递归，通常它们是字符串，以一个字母开始，后跟字母和数字。我们通过对输入流的简单扫描就能够识别标识符。一直等到一个既不是字母也不是数字的字符，然后把到这一点位置所有已经发现的字母和数字组合起来成为一个token。组合起来的字符记录在一个表格中，叫做symbol table，从输入中移去，然后开始处理下一个token。
- 另一方面，这种线性扫描在分析表达式或语句的时候不够强大。例如，如果我们不把输入放到某中层次型或嵌套结构中，那么我们就不能正确匹配表达式中的括号，或者匹配语句中的begin和end。
第2章和第5章详细讨论，syntax-directed translation语法导向翻译，其中编译器使用输入的层次型结构帮助生成输出
Semantic Analysis
语义分析阶段检查源程序是否有语义错误，并且为后继代码生成阶段收集类型信息。它使用语法分析阶段得到的层次型结构确定表达式和语句操作符和操作数
语义分析的一个重要组成部分是类型检查。这里编译器检查每一个操作符，看看它们的操作数类型是否为源语言规格所允许。例如，许多编程语言定义需要一个编译器每次发现把一个real作为数组下标的时候报告错误。但是语言的规格可能允许某些操作数转换，例如，当一个二元算术操作符对一个整数和一个实数操作的时候。此时，编译器可能需要把integer转换成real。
例1在一种机器内，表达一个整数的位模式bit pattern一般来说和表达一个实数的位模式是不同的，就算整数和实数的值一样也是如此。现在假设，所有Fig1.5中的标识符都声明为real，而60自己是一个integer。Fig1.5(a)的类型检查发现*应用于一个实数rate，和一个整数60。一般的做法是把integer转换成real.Fig1.5(b)插入了一个额外的节点，操作符为inttoreal，显式地把整数转换为一个实数。也可以选择两外一种做法，因为inttoreal的操作数是一个常量，编译器可以直接把整数常量替换成相等的实数常量。
Analysis in Text Formatters
可以把一个文本格式化器的输入看作指定boxes的一个层次，box都是矩形区域，被某些位模式所填充，代表浅色和深色像素，然后由输出设备打印。
例如Tex系统用这种方法显示它的输入。每一个不是命令组成部分的字符代表一个包含该字符bit pattern的box，辅以适当的字体和大小。不被“空白”分开的字符组成单词，由一系列横向放置的box组成，Fig1.6图解这一结构。组成单词（或者命令）的字符是文本格式化器分析的线性或者词法方面。
\hbox{
- }
通过横向并列把一个box列表组合起来，而\vbox则实现类似的纵向组合。因此，如果我们在TEX中说：
\hbox{\vbox{ ! 1} \vbox{@ 2}}
那么我们就得到Fig1.7中的box排列。
- 决定输入所隐含的box的层次安排是TEX中的语法分析部分。
另外一个例子，用于数学的EQN预处理器，或者TEX中的数学处理器，从类似sub下标和sup上标这样的操作符来构造数学表达式。如果EQN碰到下面这种形式的输入文本
BOX sub box
那么它缩小box的大小，把它放到一个BOX的右下角，如Fig 1.8所示。sup类似，只不过是放在右上角。
a sub {i sup 2}
产生
。把操作符sub和sup分组为token是EQN文本的词法分析部分，但是文本的语法结构需要判断box的大小和放置。
1.1 Compilers
编译器是一个程序，把一个用一种语言（source language)编写的程序翻译成等价的另一种语言的程序(target language)(figure 1.1)。
重要部分之一：向用户报告源代码中的错误
一眼看，编译器的种类太多了
分类：
single-pass,multi-pass,load-and-go,debugging,optimizing等等
虽然看起来很复杂，但是任何编译器执行的基本任务几乎是一样的。理解了这些任务，我们就可以用相同的基本技术构造适用于各种源语言和目标机器的编译器
1950以来，关于组织和编写编译器的知识大大提高了。
The Analysis-Synthesis Model of Compilation
编译有两部分：
分析和合成
此两者中，合成需要更多的专用技术
分析阶段，源程序隐含的操作被判断并纪录在一个层次型的结构－tree中。一种特定类型的树，语法树.syntax tree－每一个节点代表一个操作，节点的子代表操作的参数，例如下面是一个赋值语句的语法树
重要部分之一：向用户报告源代码中的错误
- 源语言，从传统的Fortran,pascal到几乎每个领域的专用语言
- 目标语言－可能是另外一种编程语言，也可能是机器语言，从microprocessor到supercomputer
分类：
single-pass,multi-pass,load-and-go,debugging,optimizing等等
虽然看起来很复杂，但是任何编译器执行的基本任务几乎是一样的。理解了这些任务，我们就可以用相同的基本技术构造适用于各种源语言和目标机器的编译器
1950以来，关于组织和编写编译器的知识大大提高了。
The Analysis-Synthesis Model of Compilation
编译有两部分：
分析和合成
- 分析部分把源代码打碎成为连续的片段，创建了源程序的一个中间表现形式
- 合成部分从中间表现形式构造出需要的目标程序
此两者中，合成需要更多的专用技术
分析阶段，源程序隐含的操作被判断并纪录在一个层次型的结构－tree中。一种特定类型的树，语法树.syntax tree－每一个节点代表一个操作，节点的子代表操作的参数，例如下面是一个赋值语句的语法树
许多操纵源程序的软件工具首先执行某种类型的分析，例子包括：
The Context of a Compiler
除了编译器外，可能还需要其它程序才能产生一个可执行的目标程序。源程序可能分成不同模块存放在不同的文件中。
收集源程序的任何可能交给单独的程序，叫做preprocessor。预处理器可能扩展缩写、宏到源程序语句中。
Figure 3.1是一个典型的“编译”。编译器创建的目标程序在运行前需要更多处理。图中的编译器创建汇编代码，被一个汇编器翻译为机器代码，和其它的库进程连接成为可以实际在机器上run的代码。
- structure editor: 取一个命令输入流，构造一个源程序。结构编辑器不但执行文本创建、修改一个普通文本编辑器的功能，同时它也分析程序文本，在源程序上加入一个适当的层次型结构。因此，结构编辑器能够执行对程序准备有用的额外任务。例如，它可以检查输入是否被正确格式化，可以自动提供关键字（例如，当用户输入while的时候，编辑器提供匹配的do，并且提醒用户他们之间必须有一个条件），可以从一个begin或左括号跳到匹配的end或者右括号。另外，这样一种编辑器的输出通常和一个编译器的分析阶段输出很象
- Pretty printers。分析程序，打印它，使得程序的结构清晰可见。
- Static checkers。读取一个程序，分析它，试图在不运行的情况下发现潜在的bug。分析部分往往和优化编译器采用的技术很相近。例如，一个静态检查器可以检测源代码中永远不会被执行的部分，或者某个变量可能在定义前被使用。另外，通过采用类型检查技术，它可以捕获诸如把一个real变量当作一个指针使用这样的逻辑错误。
- Interpreter。不产生目标程序，执行源程序隐含的操作。例如对一个赋值语句，一个解释器可能构造类似figure 1.2这样的一棵树，然后通过遍历这棵树执行该操作：
- 在树的root，它发现需要执行一个赋值
- 因此调用一个进程去计算右边的表达式
- 然后把结果值放到一个可以和position这个标识符关联的地方
- 在root的右子，进程会发现需要计算两个表达式的和
- 它递归调用自己计算表达式rate+60的值
- 然后把这个值和变量initial的值相加
- Text formatter: 一个文本格式器取一个字符流作为输入,大部分是文字，但某些是命令，指定段落、图表或者数学公式
- Silicon compiler 语言的变量代表的并非内存位置，而是电路板上的逻辑信号或信号
- Query interpreter，SQL
The Context of a Compiler
除了编译器外，可能还需要其它程序才能产生一个可执行的目标程序。源程序可能分成不同模块存放在不同的文件中。
收集源程序的任何可能交给单独的程序，叫做preprocessor。预处理器可能扩展缩写、宏到源程序语句中。
Figure 3.1是一个典型的“编译”。编译器创建的目标程序在运行前需要更多处理。图中的编译器创建汇编代码，被一个汇编器翻译为机器代码，和其它的库进程连接成为可以实际在机器上run的代码。
Chapter 1 Introduction to Compiling
编译器编写的原则和技术非常普遍，所以在很多时候多要用到。编译器编写横跨程序语言、机器体系结构、语言理论、算法和软件工程。
幸运的是，一些基本的技术可以适用很大的范围
本章的作用是
幸运的是，一些基本的技术可以适用很大的范围
本章的作用是
- 描述编译器的组成部件
- 编译器工作的环境
- 方便构造编译器的一些工具
订阅：
评论 (Atom)