Dragon Book Reading: 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;

Dragon Book Reading

星期四, 十月 12, 2006

2.9 PUTTING THE TECHNIQUES TOGETHER

没有评论:

博客归档