《编译原理》实验指导书
图1 识别表I所列语言中的部分单词的DFA及相关的语义过程
图1及程序一中所出现的语义变量及语义函数的含义和功能说明如下。 函数GETCHAR：每调用一次，就把扫描指示器当前所指示的源程序字符送入字符变量ch，然后把扫描指示器前推一个字符位置。
字符数组TOKEN：用来依次存放一个单词词文中的各个字符。
函数CAT：每调用一次，就把当前ch中的字符拼接于TOKEN中所存字符串的右边。
函数LOOKUP：每调用一次，就以TOKEN中的字符串查保留字表，若查到，就将相应关键字的类别码赋给整型变量c；否则将c置为零。
函数RETRACT：每调用一次，就把扫描指示器回退一个字符位置（即退回多读的那个字符）。
函数OUT：一般仅在进入终态时调用此函数，调用的形式为OUT(c，VAL)。其中，实参c为相应单词的类别码或其助记符；当所识别的单词为标识符和整数
《编译原理》课程组 5 of 37
《编译原理》实验指导书
时，实参VAL为TOKEN（即词文分别为字母数字串和数字串），对于其余种类的单词，VAL均为空串。函数OUT的功能是，在送出一个单词的内部表示之后，返回到调用该词法分析程序的那个程序。
程序一 根据图1编写的扫描器
# include
# include
extern int lookup (char*); extern void out (int, char*); extern report_error (void);
void scanner_example (FILE *fp) {
char ch; int i, c; ch=fgetc (fp);
if (isalpha (ch)) /*it must be a identifer!*/ {
TOKEN[0]=ch; ch=fgetc (fp); i=1; while (isalnum (ch)) {
TOKEN[i]=ch; i++； ch=fgetc (fp); }
TOKEN[i]= ′＼0′
fseek(fp,-1,1); /* retract*/ c=lookup (TOKEN);
if (c==0) out (ID,TOKEN); else out (c,\； } else
if(isdigit(ch)) {
TOKEN[0]=ch; ch=fgetc(fp); i=1; while(isdigit(ch)) {
TOKEN[i]=ch; i++; ch=fgetc(fp); }
TOKEN[i]= ′＼0′； fseek(fp,-1,1); out(INT,TOKEN); } else
switch(ch) {
case ′＜′: ch=fgetc(fp);
if(ch==′=′)out(LE,\
else if(ch==′＞′) out (NE,\
else {
fseek (fp,-1,1); out (LT,\} break;
case ′=′: out(EQ, \
《编译原理》课程组 6 of 37
《编译原理》实验指导书
case ′＞′: ch=fgetc(fp);
if(ch==′=′)out(GE,\ else {
fseek(fp,-1,1); out(GT,\}
break;
default: report_error( ); break; } return; }
提示：扫描器所用的若干函数以及主程序有待于具体编写，并需事先建立好保留字表，以备查询。另外，在扫描源程序字符串时，一旦识别出关键字、标识符、整常数以及运算符中之一，即以二元式形式（类别编码，值）输出单词。每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形成相应的单词串形式的源程序。
6、 输出结果：以文件形式输入的例子至少应包含两行以上的源代码，并以对
照的形式将扫描器的分析结果输出，必要时给出正误信息。 例：以下例题说明运行时的输入输出效果： 输入：
const a=10; var b,c; begin read(b); c:=a+b; write(c) end. 输出：
(constsym ,const ) (ident , a) (eql , =) (number, 10) (semicolon , ;) (varsym , var ) (ident, b) (comma, , ) (ident, c )
(semicolon , ;) (begins ym,begin) (readsym, read ) (lparen , ( ) (ident, b) (rparen , ) ) (semicolon , ;)
《编译原理》课程组 7 of 37
《编译原理》实验指导书
(ident, c )
(becomes , := ) (ident, a ) (plus , + ) (ident, b )
(semicolon , ;) (writesym ,write ) (lparen , ( ) (ident, c ) (rparen , ) ) (endsym , end )
实验二. 自顶向下语法分析 1. 实验目的
（1）通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。
（2）选择最有代表性的语法分析方法递归子程序法；选择对各种常见程序语言都具备的语法结构，如赋值语句，特别是表达式，作为分析对象。
2. 实验准备
微机CPU P4以上，256M以上内存，安装好C语言，或C++，或Visual C++.
3. 实验时间
4学时
4. 实验内容
? 构造递归下降LL(1)语法分析器。完成P87，例4.12
5. 实验要求
? 语法分析器的编写方法采用递归子程序法。扩充完整例4.12的程序
部分。
《编译原理》课程组 8 of 37
《编译原理》实验指导书
? 输入文法的句子，作为表达式语法分析器的输入，进行语法解析，
对于语法正确的表达式，报告“语法正确”；
? 对于语法错误的表达式，报告“语法错误”， 指出错误原因。 ? 把语法分析器设计成一个独立一遍的过程。
6. 输入输出
输入：
至少找到2个句子，其中一个是文法的句子，另一个不是，分别
输入。
输出：
对于语法正确的表达式，报告“语法正确”；
对于语法错误的表达式，报告“语法错误”， 指出错误原因。
《编译原理》课程组 9 of 37