图3 递归下降法分析算术表达式的框图
(a) ZC过程 (b) E过程 (c) T过程 (d) F过程 (e) ADVANCE过程
2、示例二：基于预测分析法的语法分析程序。
参考教材P121例4.3，首先编写无二义性的简单算术表达式的文法(4.1)，并通过消除左递归对其进行改写得到文法(4.1)’。然后求出如表4-1所示的各个FIRST集和FOLLOW集。再检查是不是LL(1)文法，并按照LL(1)文法构造如表4-2所示的预测分析表。最后根据预测分析器的工作流程，实现预测分析器的控制程序。
3、示例三：用C语言编制算符优先分析法的语法分析程序如程序三所示。其中使用了分析栈stack，用来在分析过程中存放当前句型的某一前缀，一旦句型的最左素短语在栈顶形成，便立即进行归约。
程序三 算符优先分析算法
#define RIGHT 1 #define ERROR 0
#define MAXINPUT 300 #define MAXSTACK 100 #define STARTSYMBOL ′S′
int stack[MAXSTACK]，a[MAXINPUT]; /* a[ ] is input line */ int IsHigherThan (int, int); /* priority detection */ int IsLowerThan (int, int); /* priority detection */ int IsEqualTo (int, int); /* priority detection */ int Reduce (int begin, int end, int len);
int IsVt (int); /* determine if stack symbol is in Vt */ int parser (void) {
int i, k, r, NewVn; /* NewVn holds left side of a production */ i=0; k=0; /* i, k is index of a[ ] and stack[ ] separately */ stack[0]= ′#′; do {
int j; r=a[i++];
if (IsVt(stack[k])) j=k; else j=k-1; while (IsHigherThan(stack[j],r)) {
int q; do {
q=stack[j];
if (IsVt(stack[j-1])) j--; else j-=2; } while(!IsLowerThan(stack[j],q); NewVn=Reduce(stack[j+1],stack[k],k-j);
k=j+1; /* reduce the leftmost prime phrase */ stack[k]=NewVn; /* it is stack[j+1] stack[j+2] … stack[k] */ } /*end of while*/
if (IsLowerThan(stack[j],r)) || IsEqualTo(stack[j],r)) stack[++k]=r; else return ERROR; } while (r!=′#′); return RIGHT; }
程序三给出的仅是采用算符优先分析方法的示意性识别算法，还有许多工作要做。如：首先要确定一种合适的数据结构，以便构造所给文法G2[<算术表达式>]的机内表示。然后，构造该文法的算符优先关系矩阵，在此可以根据算术表达式中各算符的优先级和结合性，直接手工构造算符优先关系。最后，编写程序三中所用到的各个函数，完成整个算符优先语法分析器的开发。
4、示例四：SLR(1)分析器的开发。
首先，对于分析对象，即算术表达式的文法G2[E]，引入一个新的开始符号E’，得到G2[E]的拓广文法G2’[E’]：
0. E’→E 1. E→E+T 2. E→E-T 3. E→T 4. T→T*F 5. T→T/F 6. T→F 7. F→(E) 8. F→i
求出文法中各个非终结符号的FOLLOW集如下：
Follow(E)={#，)，+，-} Follow(T)={#，)，+，-，*，/} Follow(F)={#，)，+，-，*，/}
然后，根据文法G2’[E’]构造识别其全部活前缀的DFA，以便据此构造SLR(1)分析表，参见表III。
表III G2’[E’]的SLR(1)分析表
状态 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 （ S4 S4 S4 S4 S4 S4 ） R3 R6 R8 S15 R1 R2 R4 R5 R7 + S6 R3 R6 R8 S6 R1 R2 R4 R5 R7 ACTION - * S7 R3 R6 R8 S7 R1 R2 R4 R5 R7 S8 R6 R8 S8 S8 R4 R5 R7 / S9 R6 R8 S9 S9 R4 R5 R7 i S5 S5 S5 S5 S5 S5 # Acc R3 R6 R8 R1 R2 R4 R5 R7 GOTO E T F 1 10 2 2 11 12 3 3 3 3 13 14 最后，编程实现SLR(1)分析表的驱动程序，即开发LR分析器的总控程序，完成对算术表达式的识别。
实验三 语义分析程序实现
一、实验目的与要求
在实现词法、语法分析程序的基础上，编写相应的语义子程序，进行语义处理，加深对语法制导翻译原理的理解，进一步掌握将语法分析所识别的语法范畴变换为某种中间代码（四元式）的语义分析方法，并完成相关语义分析器的代码开发。
二、一般实现方法
语法制导翻译模式是在语法分析的基础上，增加语义操作来实现的，实际上是对前后文无关文法的一种扩展。一般而言，首先需要根据进行的语义分析工作，完成对给定文法的必要拆分和语义动作的编写，从而为每一个产生式都配备相应的语义子程序，以便在进行语法分析的同时进行语义解释。即在语法分析过程中，每当用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要调用相应的语义子程序，以便完成生成中间代码、查填有关表格、检查并报告源程序中的语义错误等工作。每个语义子程序需指明相应产生式中各个符号的具体含义，并规定使用该产生式进行分析时所应采取的语义动作。这样，语法制导翻译程序在对源程序从左到右进行的一遍扫描中，既完成语法分析任务，又完成语义分析和中间代码生成方面的工作。本实验要求从编译器的整体设计出发，重点通过对实验二中语法分析程序的扩展，完成一个编译器前端程序的编写、调试和测试工作，形成一个将源程序翻译为中间代码序列的编译系统。
三、实验内容
基本实验题目：对文法G2[<算术表达式>]中的产生式添加语义处理子程序，完成无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。
输入：包含测试用例（如由无符号数和+、?、*、/、(、)构成的算术表达式）的源程序文件。
输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。若源程序中有错误，应指出错误信息。
扩展实验：在所给文法G2的基础上，增加语义分析的范围，如运算对象不再只局限于常量（和简单变量），还可以是函数调用、数组元素等。另外，可进一步选择赋
值语句、流程控制语句等其它语法结构类型进行语义分析。
四、要求
1、上机前的准备：完成语法制导翻译系统的程序流图设计，并编写语义动作。 2、调试：结合实验一和实验二中的相关内容，完成编译器前端程序的调试工作。 3、测试：对完成的编译系统要进行全面测试，供测试的例子应包括符合语义规则的语句，以及分析程序能够判别的若干错例，并给出执行结果。
4、结果输出：将所涉及到的分析过程中的信息，即词法、语法、语义分析的结果输出到文件中。对于有错误的输入字符串，应有较为明确的信息告诉外界。
五、参考实现方法
示例：对文法G2[<算术表达式>]在利用递归下降法进行语法分析的同时，生成四元式形式的中间代码序列。其语法制导翻译程序的核心部分（指表达式E、项T和因式F的处理）的算法思想，可用程序四所示的框架描述。
程序四 利用递归下降法生成简单算术表达式的四元式序列
E( ) /* 识别<算术表达式> */ {
E1_PLACE=T( ); /*调用T( )分析产生算术表达式计算的第一项E1*/ while (SYM=’+’ || SYM=’-’) {
ADVANCE; /*使输入串指针指向下一个输入符号，即调用扫描器读入下一个单词符号*/ E2_PLACE=T( ); /*调用T( )分析产生算术表达式计算的第二项*/ T1=NewTemp( ); /*分配一个新的临时变量，以便存储计算结果*/
GEN(±, E1_PLACE, E2_PLACE, T1); /*根据所给实参产生一个四元式，送入四元式表*/ E1_PLACE=T1; /*将计算结果作为下一次表达式计算的第一项*/ }
return E1_PLACE; }
T( ) /* 识别<项>*/ {
T1_PLACE=F( );
while (SYM=’*’ || SYM=’/’) {
ADVANCE;
T2_PLACE=F( ); T1=NewTemp( );
GEN(*/, T1_PLACE, T2_PLACE, T1); T1_PLACE=T1; }
return T1_PLACE; }