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;
}
没有评论:
发表评论