编译原理课程设计语法分析程序文档格式.docx
《编译原理课程设计语法分析程序文档格式.docx》由会员分享，可在线阅读，更多相关《编译原理课程设计语法分析程序文档格式.docx（40页珍藏版）》请在冰点文库上搜索。
这里我们用'
#'
作为输入串的结束符，或称为句子括号，如：
#输入串#。
定义3.给定上下文无关文法的产生式A→α,A∈VN,α∈V*,若α==>
ε,则SELECT（A→α）=FIRST（α）
如果α=*=>
ε，则SELECT（A→α）=FIRST（αε）∪FOLLOW（A）。
FIRST（αε）表示FIRST（α）的非{ε}元素。
更进一步可以看出能够使用自顶向下分析技术必须使文法满足如下条件，我们称满足条件的文法为LL
（1）文法，其定义为：
定义4.一个上下文无关文法是LL
（1）文法的充分必要条件是：
对每个非终结符A的两个不同产生式，A→α,A→β,满足SELECT（A→α）∩SELECT（A→β）=空,其中α，β不同时能ε.
定义5.LL
（1）文法也可定义为:
一个文法G是LL
（1）的，当且仅当对于G的每一个非终结符A的任何两个不同产生式A→α|β，下面的条件成立：
①FIRST（α）∩FIRST（β）=空,也就是α和β推导不出以某个相同的终结符a为首的符号串；
它们不应该都能推出空字ε．
②假若βε那么，FIRST（α）∩FOLLOW（A）＝空也就是，若βε则α所能推出的串的首符号不应在FOLLOW（A）中。
二、算法
该程序可分为如下几步：
（1）读入文法
（2）判断正误
（3）若无误，判断是否为LL
（1）文法
（4）若是，构造分析表；
（5）由总控算法判断输入符号串是否
为该文法的句型。
根据下面LL
（1）文法，对输入串w:
（i+i）*（i+i）+i*i进行LL
（1）分析,要求如下：
1、先手工建立LL
（1）分析表；
2、分析输入串，判断是否是语法上正确的句子，并输出整个分析过程。
LL
（1）文法G为：
E
→TE’
E’→+TE’|ε
T
→FT’
T’→*FT’|ε
F
→（E）|id
分析算法：
输入：
串w和文法G的分析表M。
输出：
如果W属于L（G），则输出W的最左推导，否则报告错误。
方法：
开始时，#S在分析栈中，其中S是文法的开始符号，在栈顶；
令指针ip指向W#的第一个符号；
repeat
让X等于栈顶符号，a为ip所指向的符号；
ifX是终结符号或#then
IfX=athen
把X从栈顶弹出并使ip指向下一个输入符号
elseerror（）
else
/*X是非终结符号*/
ifM[x,a]=Xà
y1y2…yk
thenbegin
从栈中弹出X；
把yk,yk-1,…,y1压入栈，y1在栈顶；
输出产生式Xà
y1y2…yk；
end
untilX=#
/*栈空*/
语法分析的流程算法
三、设计目的：
（1）理解和掌握LL
（1）语法分析方法的基本原理；
根据给出的LL
（1）文法，掌握LL
（1）分析表的构造及分析过程的实现。
（2）掌握预测分析程序如何使用分析表和栈联合控制实现LL
（1）分析。
四、实现环境和要求
选择实习环境为486以上CPU,4M内存,TURBOC2.0语言.实现程序见附录.
具体的实现要求：
（1）对输入文法，它能判断是否为LL
（1）文法，若是，则转
（2）；
否则报错并终止；
（2）输入已知文法，由程序自动生成它的LL
（1）分析表；
（3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。
五、总结
上机前应做好准备．即根据实习目的、要求和分析，选择相应的数据结构，使用Ｃ语言参照算法中的流程编写词法分析的程序．将编好的程序上机进行调试．注意调试的例子应有词法正确的，也应有词法错误的或是超出所选数据结构范围的．
实验完成达到实习目的之后，若尚有余力者，可以对所选子集适当扩大或是增加相应功能如：
扩充界符和保留字数目；
允许实型常数；
进行词法错误检查；
最大范围扩充以至PASCAL语言所有字符的集合．
通过这次程序设计，更加清楚透彻的明白了ＬＬ
（1）分析法的过程，从而也比较熟练掌握了自上而下语法分析的基本思想，此外，巩固了所学的数据结构的知识，自己所学的知识能够联系起来，使得知识自成系统。
在实现和调试时次采取模块化的思想，使得本次课程设计比较顺利，增强了自己的信心，提高了自己的编程能力和动手能力以及独立分析问题、解决问题的能力和综合运用所学知识的能力。
附录
/*****************************************************
预测分析程序（语法分析程序），分析对象为C语言源程序文件。
该分析程序有18部分组成：
《1》首先定义各种需要用到的常量和变量；
《2》判断一个字符是否在指定字符串中；
《3》得到一个不是非终结符的符号；
《4》分解含有左递归的产生式；
《5》分解不含有左递归的产生式；
《6》读入一个文法；
《7》将单个符号或符号串并入另一符号串；
《8》求所有能直接推出^的符号；
《9》求某一符号能否推出‘^’；
《10》判断读入的文法是否正确；
《11》求单个符号的FIRST；
《12》求各产生式右部的FIRST；
《13》求各产生式左部的FOLLOW；
《14》判断读入文法是否为一个LL
（1）文法；
《15》构造分析表M；
《16》总控算法；
《17》一个用户调用函数；
《18》主函数；
/*******************************************/
WORDANALYSEDEMOFORTURBOC2.0
Copyright（c）2005-6-30Author:
陈强
Allrightsreserved.
#include<
stdlib.h>
stdio.h>
string.h>
intcount=0;
/*分解的产生式的个数*/
intnumber;
/*所有终结符和非终结符的总数*/
charstart;
/*开始符号*/
chartermin[50];
/*终结符号*/
charnon_ter[50];
/*非终结符号*/
charv[50];
/*所有符号*/
charleft[50];
/*左部*/
charright[50][50];
/*右部*/
charfirst[50][50],follow[50][50];
/*各产生式右部的FIRST和左部的FOLLOW集合*/
charfirst1[50][50];
/*所有单个符号的FIRST集合*/
charselect[50][50];
/*各单个产生式的SELECT集合*/
charf[50],F[50];
/*记录各符号的FIRST和FOLLOW是否已求过*/
charempty[20];
/*记录可直接推出^的符号*/
charTEMP[50];
/*求FOLLOW时存放某一符号串的FIRST集合*/
intvalidity=1;
/*表示输入文法是否有效*/
intll=1;
/*表示输入文法是否为LL
（1）文法*/
intM[20][20];
/*分析表*/
charchoose;
/*用户输入时使用*/
charempt[20];
/*求_emp（）时使用*/
charfo[20];
/*求FOLLOW集合时使用*/
/*******************************************
判断一个字符是否在指定字符串中
********************************************/
intin（charc,char*p）
{
inti;
if（strlen（p）==0）
return（0）;
for（i=0;
;
i++）
{
if（p[i]==c）
return
（1）;
/*若在，返回1*/
if（i==strlen（p））
/*若不在，返回0*/
}
}
得到一个不是非终结符的符号
charc（）
charc='
A'
while（in（c,non_ter）==1）
c++;
return（c）;
分解含有左递归的产生式
voidrecur（char*point）
{/*完整的产生式在point[]中*/
intj,m=0,n=3,k;
chartemp[20],ch;
ch=c（）;
/*得到一个非终结符*/
k=strlen（non_ter）;
non_ter[k]=ch;
non_ter[k+1]='
\0'
for（j=0;
j<
=strlen（point）-1;
j++）
if（point[n]==point[0]）
{/*如果‘|’后的首符号和左部相同*/
for（j=n+1;
{
while（point[j]!
='
|'
&
point[j]!
）
temp[m++]=point[j++];
left[count]=ch;
memcpy（right[count],temp,m）;
right[count][m]=ch;
right[count][m+1]='
m=0;
count++;
if（point[j]=='
{
n=j+1;
break;
}
}
}
else
{/*如果‘|’后的首符号和左部不同*/
left[count]=ch;
right[count][0]='
^'
right[count][1]='
count++;
for（j=n;
if（point[j]!
temp[m++]=point[j];
else
left[count]=point[0];
printf（"
count=%d"
count）;
m=0;
left[count]=point[0];
memcpy（right[count],temp,m）;
right[count][m]=ch;
right[count][m+1]='
m=0;
分解不含有左递归的产生式
voidnon_re（char*point）
intm=0,j;
chartemp[20];
for（j=3;
{
if（point[j]!
temp[m++]=point[j];
{
left[count]=point[0];
right[count][m]='
m=0;
memcpy（right[count],temp,m）;
right[count][m]='
count++;
m=0;
读入一个文法
chargrammer（char*t,char*n,char*left,charright[50][50]）
charvn[50],vt[50];
chars;
charp[50][50];
inti,j,k;
printf（"
\n请输入文法的非终结符号串：
"
）;
scanf（"
%s"
vn）;
getchar（）;
i=strlen（vn）;
memcpy（n,vn,i）;
n[i]='
请输入文法的终结符号串：
vt）;
i=strlen（vt）;
memcpy（t,vt,i）;
t[i]='
请输入文法的开始符号：
%c"
&
s）;
请输入文法产生式的条数：
%d"
i）;
for（j=1;
=i;
printf（"
请输入文法的第%d条（共%d条）产生式：
j,i）;
scanf（"
p[j-1]）;
=i-1;
if（p[j][1]!
-'
||p[j][2]!
>
'
{printf（"
\ninputerror!
validity=0;
return（'
}/*检测输入错误*/
for（k=0;
k<
k++）
{/*分解输入的各产生式*/
if（p[k][3]==p[k][0]）
recur（p[k]）;
non_re（p[k]）;
return（s）;
将单个符号或符号串并入另一符号串
voidmerge（char*d,char*s,inttype）
{/*d是目标符号串，s是源串，type＝1，源串中的‘^’一并并入目串；
type＝2，源串中的‘^’不并入目串*/
inti,j;
i<
=strlen（s）-1;
if（type==2&
s[i]=='
;
for（j=0;
if（j<
strlen（d）&
s[i]==d[j]）
break;
if（j==strlen（d））
d[j]=s[i];
d[j+1]='
求所有能直接推出^的符号
voidemp（charc）
{/*即求所有由‘^’推出的符号*/
chartemp[10];
=count-1;
if（right[i][0]==c&
strlen（right[i]）==1）
temp[0]=left[i];
temp[1]='
merge（empty,temp,1）;
emp（left[i]）;
求某一符号能否推出‘^’
int_emp（charc）
{/*若能推出，返回1；
否则，返回0*/
inti,j,k,result=1,mark=0;
temp[0]=c;
temp[1]='
merge（empt,temp,1）;
if（in（c,empty）==1）
return
（1）;
if（i==count）
return（0）;
if（left[i]==c）/*找一个左部为c的产生式*/
j=strlen（right[i]）;
/*j为右部的长度*/
if（j==1&
in（right[i][0],empty）==1）
elseif（j==1&
in（right[i][0],termin）==1）
return（0）;
else
=j-1;
if（in（right[i][k],empt）==1）
mark=1;
if（mark==1）
continue;
else
for（k=0;
{
result*=_emp（right[i][k]）;
temp[0]=right[i][k];
temp[1]='
merge（empt,temp,1）;
}
if（result==0&
count）
continue;
elseif（result==1&
判断读入的文法是否正确
intjudge（）
if（in（left[i],non_ter）==0）
{/*若左部不在非终结符中，报错*/
printf（"
\nerror1!
validity=0;
return（0）;
for（j=0;
=strlen（right[i]）-1;
if（in（right[i][j],non_ter）==0&
in（right[i][j],termin）==0&
right[i][j]!
{/*若右部某一符号不在非终结符、终结符中且不为‘^’，报错*/
printf（"
\nerror2!
validity=0;
return
（1）;
求单个符号的FIRST
voidfirst2（inti）
{/*i为符号在所有输入符号中的序号*/
charc,temp[20];
intj,k,m;
c=v[i];
charch='
升级会员 