编译原理 语法分析规约.docx
《编译原理 语法分析规约.docx》由会员分享,可在线阅读,更多相关《编译原理 语法分析规约.docx(13页珍藏版)》请在冰点文库上搜索。
编译原理语法分析规约
课程名称编译原理
设计题目语法分析——规约
一.问题描述.....................................
(2)
二.文法及属性文法的描述..........................
(2)
2.1文法描述.....................................
(2)
2.2while-do循环语句的文法.........................
(2)
2.3属性文法描述.................................
(2)
3语法分析方法及中间代码形式的描述...............(3)
3.1语法分析方法................................(3)
3.2中间代码形式描述............................(3)
4简要的分析与概要设计............................(4)
4.1词法分析....................................(4)
4.2递归下降翻译器的设计........................(4)
4.3语法制导翻译................................(5)
5详细的算法描述.................................(5)
5.1文法.......................................(6)
5.2查错.......................................(6)
三.测试方法和测试结果...........................(9)
3.1测试方法....................................(9)
3.2测试结果....................................(9)
四.设计心得....................................(10)
一、问题描述
1.1能够写出一个while-do语句,此语句符合LL
(1)的文法。
1.2构造词法分析程序对while-do语句进行词法分析。
1.3构造语法分析程序对while-do语句进行语法分析,判断语法正确性。
1.4运行程序,要求有正确的语义输出(4地址码)。
二、文法及属性文法的描述:
2.1文法描述:
基本概念:
文法是对语言结构的定义与描述。
即从形式上用于描述和规定语言
构的称为“文法”。
定义:
文法G=(VN,VT,P,Z)
VN:
非终结符号集
VT:
终结符号集
P:
产生式或规则的集合
Z:
开始符号(识别符号)Z∈VN
其中:
2.2while-do循环语句的文法
文法G(s)如下:
S-->WEDG(意思是whileEdoG)
G-->c=R
R-->dTe|d
T-->+|-|*|/
E-->aFb
F-->>|==|<(id1,id2代表标识符)
2.3属性文法的描述:
2.3.1属性文法的定义形式:
每个文法符号有一组属性,每个文法产生式A->α有一组产生式b:
=f(c1,c2,……,ck)的语义规则,其中f式函数,b和c1,c2,……,ck式该产生式文法符号的属性。
3.语法分析方法及中间代码形式的描述;
3.1语法分析方法:
3.1.1本次设计采用LL
(1)分析:
预测分析方法概述:
分析钜阵的元素M[A,a]中的下标A为非终结符,a为终结符或句子的结束标记“#”,钜阵元素M[A,a]的内容为一条关于A的产生式。
它表明当用非终结符A向下推而当输入符a时,所应该采用的后选式。
当钜阵元素为空时,则表示用A往下推导时遇到了不应该出现的符号,即A与a不能匹配,因此应该出错处理。
在构造预测分析表时,对每个终结符或“#”号用a表示,则若a∈SELECT(A->a)。
令M[A,a]=A->a(一般为了简化,取M[A,a]=a)把所有的无定义的M[A,a]标上ERROR(一般在表中用空白表示)。
3.1.2此程序预测分析方法:
此设计为非左递归while-do文法,应采用自上而下的预测分析方法。
在此设计中,产生式只到E->id1>id2|id1=id2|id1id1=id2(E->aFbF->>|==|<)对F只有一种产生式而在输入串中的终结符a,b……等在程序中用id代替了,正好做到了输入串和符号栈的匹配抵消,因此简化了预测分析表的构造,对于E来说有3个侯选式,在本程序中通过函数firstset()来判断应该选哪个产生式,但是firstset()是依赖Token2数组来判断的,没有完全摆脱掉数组的限制,因此也是本程序的不足之处。
3.2中间代码的描述:
3.2.1中间代码概述:
中间代码采用四元式输出,一个四元式是一个带有四个域的记录结构,这四个域分别称为op﹑arg1﹑arg2及result。
域op包含一个代表运算符的内部码。
语句whilea100(<,a,b,102)
101(j,_,_,105)
102(+,a,b,n)
103(=,n,_,a)
104(j,_,_,100)
3.2.1本次设计的中间代码:
本次程序的中间代码是根据一定的语义规则写出的:
T
whileAdoE
F
代码结构:
S.begin:
E.codetoE.ture
E.ture:
A.codetoE.false
gotoS.begin
toE.false:
……
4.简要分析与概要设计
4.1词法分析
词法分析程序的任务是:
从左至右逐个字符地对源程序进行扫描,产生一个个的单词符号,把作为字符串的源程序改造成为单词符号的中间程序。
词法分析检查的错误主要是挑出源程序中出现的非法符号。
所谓非法符号是指不是程序设计语言中允许出现的符号,就像自然语句中的错字。
4.2递归下降翻译器的设计
1.:
对每个非终结符F构造一个函数过程,对F的每个继承属性设置一个形式参数,函数的返回值为F的综合属性,F对应的函数过程中,为出现在F的产生式中的每一个文法符号的每一个属性都设置一个局部变量。
非终结符F对应的函数过程中,根据当前的输入符号决定使用哪个产生式候选。
2:
每个产生式对应的程序代码中,按照从左到右的次序,对于单词符号,非3:
终结符和语义动作分别做以下工作。
(1)对于带有综合属性x的终结符X,把x的值存入为X,x设置的变量中。
然后产生一个匹配X的调用,并继续读入一个输入符号。
(2)对于每个非终结符号R,产生一个右边带有函数调用的赋值语句c=R(r1,r2,…,rk)
(3)对于语义动作,把动作的代码抄进分析器中,用代表属性的变量来代替对应属性的每一次引用。
4.3语法制导翻译
在语法分析过程中,随着分析的步步进展,根据每个产生式所对应的语义子程序(或语义规则描述的语义动作)进行翻译。
属性文法的每个符号有属性,所以每个符号入栈时,必须连属性一起入栈,这样,栈符号就由文法符号及存放该符号属性的域所组成。
由于属性类型不同,属性域存放的内容就要根据属性的类型来定。
有的可能直接存放属性值,也有的存放的是指向属性值的指针。
对于综合属性,其属性域不存放其属性值,而是存放一个指针,指向存贮该属性值的单元。
对于继承属性,其属性域直接保存其属性值。
继承属性的属性域刚入栈时为空,但是在该栈符号变成栈顶符号之前的某一时刻,它们必须接受相应的属性值,即在成为栈顶时,继承属性的属性域必须有值。
5.详细算法描述
5.1文法
/*
文法G(s)
s-->WEDG
G-->c=R
R-->dTe|d
T->+|-|*|/|%E-->aFb
F-->>|==|<
*/
5.2查错:
按照递归下降法求Wa1)S()
voidS()
{
printf("%d\tS-->WEDG\n",total);total++;
W();
E();
}
2)W()
voidW()
{
if(ch!
='W')
{
printf("有非法字符%c请按回车返回!
!
",ch);
getchar();
getchar();
exit
(1);
}
}
3)E()
voidE()
{
ch=a[++i1];
if(ch!
='a')
{
printf("有非法字符%c%c请按回车返回!
!
",ch);
getchar();
getchar();
exit
(1);
}
printf("%d\tE-->aFb\n",total);total++;
F();
}
4)F()
voidF()
{
inti;
ch=a[++i1];
i=i1+1;
if(a[i]!
='b')
{
printf("有非法字符%c请按回车返回!
!
",a[i]);
getchar();
getchar();
exit
(1);
}
switch(ch)
{
case'>':
printf("%d\tF-->>\n",total);total++;
break;
case'==':
printf("%d\tF-->==\n",total);total++;
break;
default:
printf("%d\tF--><\n",total);total++;
break;
}
D();
G();
}
5)D()
voidD()
{
++i1;
ch=a[++i1];
if(ch!
='D')
{
printf("有非法字符%c请按回车返回!
!
",ch);
getchar();
getchar();
exit
(1);}
ch=a[++i1];
}
6)G()
voidG()
{
inti=i1+1;
if(ch!
='c'&&a[i]!
='=')
{
printf("有非法字符%c%c请按回车返回!
!
",ch,a[i]);
getchar();
getchar();
exit
(1);
}
printf("%d\tG-->c=R\n",total);total++;
R();
}
7)R()
voidR()
{
inti;
i=i1+1;
i1=i1+2;
ch=a[i1];
if(a[i]!
='='&&ch!
='d')
{
printf("有非法字符%c%c请按回车返回!
!
",a[i],ch);
getchar();
getchar();
exit
(1);
}
else
{
if((a[i1+1]=='+')||(a[i1+1]=='-')||(a[i1+1]=='*')||(a[i1+1]=='/'))
{
printf("%d\tR-->dTe\n",total);total++;
T();
}
else
{
printf("%d\tR-->d\n",total);total++;
W();
E();
}
}
}
8)T()
voidT()
{
ch=a[++i1];
switch(ch)
{
case'+':
printf("%d\tT-->+\n",total);total++;
break;
case'-':
printf("%d\tT-->-\n",total);total++;
break;
case'*':
printf("%d\tT-->*\n",total);total++;
break;
default:
printf("%d\tT-->/\n",total);total++;
break;
}
ch='#';
}
三、测试方法和测试结果
3.1测试方法
在C++环境下,设计几个有代表的用例,进行测试,例如:
输入语句W(while)a本次课程设计在运行时,按照while语句的语法要求输入符合条件的语法,最后语句应以#结束若得出的不是预期的结果,那么程序就出现问题。
如果有问题的话就进行单步调试找到程序中出现的逻辑问题。
词法部分:
因为本此输入的单词符号都是符合词法分析程序定义所以能够得到正确的词法分析结果。
语法部分:
因为次此的输入aaFbf-><)的正确的推导,并且R推导出的是一个赋值语句a=a+b(R->dFbG->c=R),符合本程序定义的while-do语法规则,所以语法正确。
语义输出:
在识别非终结符号的时候将与其相对应的产生式输出(相应的语义动作),实现了语法制导翻译,最后将其以4地址的形式输出。
3.2测试结果
测试结果如下:
四、设计心得
本次设计是采用递归下降的方法对输入的while--do循环语句进行语法,语义分析,并输出四元式。
因此程序中充分体现了递归下降的思想。
通过对语法分析的实践操作,对它在实践中的应用有了更深刻的理解,通过上机实践,提高了从错误中分析问题,解决问题的能力。
在实践的基础上,把所学的知识得到了实际应用,通过本次的编译原理课程设计,让我对用C++编程的大致思路又进行了一次回顾,设计一个可运行的程序代码的思路规范,声明变量,定义各大需要调用的函数及其调用。
此程序只能实现对Wa本次课程设计巩固了我所学习的关于递归下降法这一方面的知识,并且使我对WHILE—DO循环语句也有了更深刻的理解,提高了我的动手能力。