编译方法 实 验 报 告
实验名称：简单的语法分析程序设计
实验要求
1. 功能：对简单的赋值语句进行语法分析
随机输入赋值语句，输出所输入的赋值语句与相应的四元式
2. 采用递归下降分析程序完成（自上而下的分析）
3. 确定各个子程序的功能并画出流程图
4. 文法如下：
5. 编码、调试通过
采用标准输入输出方式。输入输出的样例如下：
【样例输入】
x:=a+b*c/d-(e+f)
【样例输出】(说明，语句和四元式之间用5个空格隔开)
T1:=b*c (*,b,c,T1)
T2:=T1/d (/,T1,d,T2)
T3:=a+T2 (+,a,T2,T3)
T4:=e+f (+,e,f,T4)
T5:=T3-T4 (-,T3,T4,T5)
x:=T5 (:=,T5,-,x)
【样例说明】程序除能够正确输出四元式外，当输入的表达式错误时，还应能检测出语法错误，给出相应错误提示。
6. 设计3-5个赋值语句测试实例，检验程序能否输出正确的四元式；当输入错误的句子时，检验程序能够给出语法错误的相应提示信息。
7. 报告内容包括：
递归程序的调用过程，各子程序的流程图和总控流程图，详细设计，3-5个测试用例的程序运行截图及相关说明，有详细注释的程序代码清单等。
目录
1.语法分析递归下降分析算法 ................................................................................................................................................... 4
1.1背景知识 ........................................................................................................................................................................ 4 1.2消除左递归 .................................................................................................................................................................... 6 2.详细设计及流程图 ................................................................................................................................................................... 7
2.1 函数void V( ) // V -> a|b|c|d|e...|z .............................................................................................................................. 7 2.2 函数void A( ) // A -> V:=E ..................................................................................................................................... 8 2.3 函数void E() //E -> TE' ....................................................................................................................................... 9 2.4函数void T( ) // T -> FT' ........................................................................................................................................ 10 2.5函数void E1( ) //E'-> +TE'|-TE'|null ........................................................................................................................ 10 2.6函数void T1() // T'-> *FT'|/FT'|null ...................................................................................................................... 11 3.测试用例及截图 ..................................................................................................................................................................... 12
3.1测试用例1及截图 ...................................................................................................................................................... 12 3.2测试用例2及截图 ...................................................................................................................................................... 13 3.3测试用例3及截图 ...................................................................................................................................................... 14 代码清单.................................................................................................................................................................................... 15
1.语法分析递归下降分析算法
1.1背景知识
无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。
无左递归：既没有直接左递归，也没有间接左递归。
无回溯：对于任一非终结符号U的产生式右部x1|x2|…|xn，其对应的字的首终结符号两两不相交。
如果一个文法不含回路，也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。
文法的左递归消除算法：
1、将文法G的所有非终结符排序为U1 ,U2 ,… ,Un;
2、For(i=1；i++；i≥n)
{
for j→1 to i-1
把产生式Ui→Ujα替换成Ui→β1α| β2α|…|βmα；
其中：Uj→ β1| β2 |… |βm 消除Ui产生式中的直接左递归；
}
3.化简改写之后的文法，删除多余产生式。
文法的直接左递归消除公式：
直接左递归形式：
U→Ux|y；
其中：x，y∈（VN∪VT）* ，y不以U打头。
直接左递归的消除：
U→yU‟
U‟→xU‟|ε
直接左递归的一般形式：
U→Ux1|Ux2|…|Uxm|y1|y2|…|yn；
其中：xi≠ε ,yi都不以U打头。
一般形式直接左递归的消除:
U→y1U‟| y2U‟ |…| ynU‟
U‟→x1U‟| x2U‟| …| xmU‟|ε
回溯的消除的前提是文法不得含有左递归，可提左因子来消除回溯。
1.2消除左递归
根据实验中给出的文法，进行消除左递归及回溯，得到下列的式子
A -> V:=E
E -> TE'
E'-> +TE'|-TE'|null
T -> FT'
T'-> *FT'|/FT'|null
F -> V|(E)
V -> a|b|c|d|e...|z
2.详细设计及流程图
根据消除左递归后的文法，可以编写相应的函数。
2.1 函数void V( ) // V -> a|b|c|d|e...|z
void V() // V -> a|b|c|d|e...|z函数设计主要用来识别小写字母的，如果是小写字母的话，放入字符表，不是的话，输出语法错误。函数比较简单，代码如下：
if(islower(s[sym]))
{
Table[list_n][0] = s[sym]; //把读取的小写字母存入符号表，便于分析
是生成中间代码
Table[list_n][1] = '\\0';
list_n++;
sym++;
}
else
{
printf(\"Operand Errors!\\n\"); //运算对象错误
SIGN=1;
exit(0);
}
2.2 函数void A( ) // A -> V:=E
void A() // A -> V:=E 函数主要用来实现赋值的操作，流程图如图1所示。
开始V( )s[sym]==':'&&s[sym+1]=='='Ysym+=2;E( );输出表达式N输出错误结束
图1 A( ) 函数流程图
2.3 函数void E() //E -> TE'
函数E（）里面主要递归调用函数T( )和E'( )。当没有出现语法错误时就可正常的运行。函数比较简单，代码如下：
{
if(SIGN==0)
{
T();
E1();
}
}
2.4函数void T( ) // T -> FT'
函数T( )里面主要递归调用函数F ( )和T''( )。当没有出现语法错误时就可正常的运行。函数比较简单，代码如下：
if(SIGN==0)
{
F();
T1();
}
2.5函数void E1( ) //E'-> +TE'|-TE'|null
函数void E1() //E'-> +TE'|-TE'|null，主要用来实现加减法的语义分析。流程图如图2所示。
开始SIGN==0s[sym] == '+'||s[sym]=='-'Yp=sym; sym++T()N 输出三地址式和四元表达式NE1()结束
图2 E1 ( ) 函数流程图
2.6函数void T1() // T'-> *FT'|/FT'|null
函数void T1() // T'-> *FT'|/FT'|null，主要用来实现乘除法的语义分析。流程图如图3所示。
开始SIGN==0s[sym] == '*'||s[sym]=='/'Yp=sym; sym++F()N 输出三地址式和四元表达式NT1()结束
图3 T1 ( ) 函数流程图
3.测试用例及截图
3.1测试用例1及截图
用例1为实验要求上的的用例。测试结果图4所示。
图4 测试用例1及结果截图
3.2测试用例2及截图
用例2为出现大写字母，出现报错。测试结果图5所示。
图5 测试用例2及结果截图
3.3测试用例3及截图
用例3为随意编写用例。测试结果图6所示。
图6 测试用例3及结果截图
代码清单
#include #include #include #include void A(); // A -> V:=E void E(); // E -> TE' void T(); // T -> FT' void E1(); // E'-> +TE'|-TE'|null void T1(); // T'-> *FT'|/FT'|null void F(); // F -> V|(E) void V(); // V -> a|b|c|d|e...|z char s[50],n='1'; //s[50]用于存放输入的赋值表达式 char Table[50][3]; //产生中间代码所需的符号表 int SIGN,sym; //sym为s[50]中当前读入符号的下标 int list_n=0; //符号表的下标 /*消除左递归及回溯 A -> V:=E E -> TE' E'-> +TE'|-TE'|null T -> FT' T'-> *FT'|/FT'|null F -> V|(E) V -> a|b|c|d|e...|z */ int main() { SIGN = 0; //SIGN用于指示赋值表达式是否出现错误 sym=0; scanf(\"%s\ if( s[0] == '\\0') //没有输入的情况直接退出 return 0; A(); if(s[sym]!='\\0'&&SIGN==0) { printf(\"ERROR!\\n\"); exit(0); } return 0; } void A() // A -> V:=E { V(); if(s[sym]==':'&&s[sym+1]=='=') //判断赋值号是否有拼写错误 { sym+=2; E(); printf(\"%s:=%s\ printf(\" (:=,%s,-,%s)\\n\ } else { printf(\"The assignment Symbol spelling mistakes!\\n\"); //赋值号拼写错误 SIGN=1; exit(0); } } void V() // V -> a|b|c|d|e...|z { if(islower(s[sym])) { Table[list_n][0] = s[sym]; //把读取的小写字母存入符号表，便于分析是生成中间代码 Table[list_n][1] = '\\0'; list_n++; sym++; } else { printf(\"Operand Errors!\\n\"); SIGN=1; exit(0); } //运算对象错误 } void E() //E -> TE' { if(SIGN==0) { T(); E1(); } } void T() // T -> FT' { if(SIGN==0) { F(); T1(); } } void E1() //E'-> +TE'|-TE'|null { int p; if(SIGN==0) { if(s[sym] == '+'||s[sym]=='-') { p=sym; //用p记录出现'+'或'-'时sym的值 sym++; T(); char ch[3]; ch[0] = 'T'; ch[1] = n; ch[2] = '\\0'; if(s[p] == '+') { printf(\"%s:=%s+%s\able[list_n-2],Table[list_n-1]); //输出三地址代码 printf(\" (+,%s,%s,%s)\\n\Table[list_n-2],Table[list_n-1],ch); 输出四元式 } else { // printf(\"%s:=%s-%s\ //输出三地址代码 printf(\" (-,%s,%s,%s)\\n\Table[list_n-2],Table[list_n-1],ch); //输出四元式 } strcpy(Table[list_n-2],ch); list_n--; n++; E1(); } } } void T1() // T'-> *FT'|/FT'|null { //将当前结果归结式放在符号表中 int p; if(SIGN==0) { if(s[sym] == '*'||s[sym]=='/') { p=sym; sym++; F(); char ch[3]; ch[0] = 'T'; ch[1] = n; ch[2] = '\\0'; if(s[p] == '*') { printf(\"%s:=%s*%s\ //输出三地址代码 printf(\" (*,%s,%s,%s)\\n\输出四元式 } else { printf(\"%s:=%s/%s\ //输出三地址代码 printf(\" (/,%s,%s,%s)\\n\输出四元式 } strcpy(Table[list_n-2],ch); //将当前结果归结式放在符号表中 list_n--; n++; T1(); } } } void F() //F -> V|(E) { if(SIGN==0) { if(s[sym]=='(') { sym++; E(); if(s[sym]==')') sym++; else { printf(\"ERROR!\\n\"); SIGN=1; exit(0); } } else if(islower(s[sym])) V(); else { printf(\"ERROR!\\n\"); SIGN=1; //判断s[sym]是否是小写字母 exit(0); } } } 因篇幅问题不能全部显示，请点此查看更多更全内容