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

1. a是S，因为S→ a
2. aa+是S，因为 S → S S +，而a 是S
3. 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,无法用上面的文法产生

2.9 PUTTING THE TECHNIQUES TOGETHER

本章中，我们展现了一些用来构造一个编译器前端的语法导向技术。为了总结这些技术，我们把它们组合起来成为一个C程序，实现中缀到后缀表达式的翻译，语言由一系列用分号结束的表达式组成。表达式可以包含数字、标识符和操作符+,-,*,/,div和mod。翻译器的输出是每一个表达式的后缀表现形式。翻译器是在section 2.5-2.7开发的程序的一个扩展。完整的C程序在本节末尾。

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;

2.8 ABSTRACT STACK MACHINE

一个编译器的前端构造源程序的中间表现形式，后端从它来生成目标程序。一个比较流行的中间代表是一种抽象栈机器的代码。如同第1章所说，把一个编译器分为前端和后端，让编译器在新机器上运行的时候修改更加简单。

本节中，我们将展现一种抽象栈机器，并显示如何为它生成代码。该机器有独立的指令和数据内存，所有的算术运算都对栈上的值进行。指令非常有限，分为3类：整数运算，栈操纵和控制流。Fig 2.31演示该机器。pc指针标示我们即将执行的指令。指令的含义后面马上讨论。



pc指针是我们将要执行的指令。指令的含义很快将在后面讨论。

Arithmetic Instructions

抽象机器必须实现中间语言的每一个操作符。一个基本的操作符，例如加或者减，被抽象机器直接支持。但是，更加复杂的操作符，可能需要被实现为一个抽象机器指令的序列。我们简化机器的描述，通过假设每一个算术操作符都有对应的抽象机器指令。

一个算术表达式的抽象机器代码用一个栈模拟了该表达式后缀表现形式的计算。计算过程从左到右处理后缀表达形式，碰到操作数就把它压入栈中。在碰到一个k-ary的操作符时，它最左边的参数是栈顶下面k-1位置，而最右边的参数是栈顶。计算把操作符应用到栈顶的k个值，弹出操作数，然后把结果压回栈。例如，在计算后缀表达式1 3 + 5 *，执行下面的动作：

1. Stack 1
2. Stack 3
3. 把最顶上的两个成员相加，弹出它们，把结果4压回栈
4. Stack 5
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

栈机器按照数字序列执行指令，除非用一个条件或无条件跳转指令告诉它其它事情。可以用几种方法指定跳转的目标：

1. 指令操作数给出目标位置
2. 指令操作数指定跳转的相对位置，正的或负的
3. 用符号指定目标，也就是是说，机器支持标签

前两种方法具有附加的可能性，从栈顶取操作数。

我们为抽象机器选择第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一样的方式处理。

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。

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实现的。

#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节中，我们把这个词法分析器合并到我们的表达式翻译器中。

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)中对应的非终结符。

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;
}