编译原理实验报告语法分析程序的设计.docx
《编译原理实验报告语法分析程序的设计.docx》由会员分享，可在线阅读，更多相关《编译原理实验报告语法分析程序的设计.docx（12页珍藏版）》请在冰点文库上搜索。
编译原理实验报告语法分析程序的设计
RUSERredactedonthenightofDecember17,2020
编译原理实验报告语法分析程序的设计
实验5语法分析程序的设计
（2）
一、实验目的
通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。
二、实验内容
设计一个文法的算法优先分析程序，判断特定表达式的正确性。
三、实验要求
1、给出文法如下：
G[E]
E->T|E+T;
T->F|T*F;
F->i|（E）;
可以构造算符优先表如下：
+
*
（
）
i
+
*
（
）
i
2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式；
1、给出算符优先分析算法如下：
k:
=1;S[k]:
=‘#’;
REPEAT
把下一个输入符号读进a中；
IFS[k]∈VTTHENj:
=kELSEj:
=k-1;
WHILES[j]aDO
BEGIN
REPEAT
Q:
=S[j];
IFS[j-1]∈VTTHENj:
=j-1ELSEj:
=j-2
UNTILS[j]Q
把S[j+1]…S[k]归约为某个N；
k:
=j+1;
S[k]:
=N;
ENDOFWHILE;
IFS[j]aORS[j]aTHEN
BEGIN
k:
=k+1;S[k]:
=a
END
ELSEERROR
UNTILa=‘#’
1、根据给出算法，利用适当的数据结构实现算符优先分析程序；
2、利用算符优先分析程序完成下列功能：
1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束；
2）读入文本文件中的表达式；
3）调用实验2中的词法分析程序搜索单词；
4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息；
5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。
四、实验环境
PC微机
DOS操作系统或Windows操作系统
TurboC程序集成环境或VisualC++程序集成环境
五、实验步骤
1、分析文法中终结符号的优先关系；
2、存放优先关系或构造优先函数；
3、利用算符优先分析的算法编写分析程序；
4、写测试程序，包括表达式的读入和结果的输出；
5、程序运行效果，测试数据可以参考下列给出的数据。
六、测试数据
输入数据：
编辑一个文本文文件，在文件中输入如下内容：
10;
1+2;
（1+2）*3+（5+6*7）;
（（1+2）*3+4;
1+2+3+（*4+5）;
（a+b）*（c+d）;
（（ab3+de4）**5）+1;
正确结果：
（1）10;
输出：
正确
（2）1+2;
输出：
正确
（3）（1+2）*3+（5+6*7）;
输出：
正确
（4）（（1+2）*3+4
输出：
错误
（5）1+2+3+（*4+5）
输出：
错误
（6）（a+b）*（c+d）
输出：
正确
（7）（（ab3+de4）**5）+1
输出：
错误
七、实验报告要求
实验报告应包括以下几个部分：
1、给定文法优先关系和存放方式；
+
*
（
）
i
#
+
*
（
e1
）
e2
e2
i
e2
e2
#
e3
e4
引入“#”，将句型包含起来并填入出错标记。
使用二维数组将其存放。
2、算符优先分析程序的算法和结构；
程序从文本文件中逐行读取表达式，每行以“；”做标记。
调用词法分析程序将这行数据分析出由一个个的单词组成的表达式，再逐个分析单词。
另外，由于文法中没写入关于标识符和常数的产生式，所以在对单词符号进行语法分析时，会将标识符和常数自动规约为“i”。
数据结构：
优先关系表R：
二维数组，存储了终结符+、*、（、）、i、#的优先关系。
符号W：
结构体，有四个成员，包括：
ch：
char类型，非终结符与终结符的字符标记；
po：
int类型，只对终结符有效，与在R中的位置有关，有词法分析器提供；对于非终结符，其po无效；
val：
string类型，综合属性；对终结符i，其值由词法分析器提供；对非终结符，其值由规约时对应的产生式的规则计算得到；对界符或运算符，val无效；
type：
int类型，标记属性值类型，0为标识符，不可计算；1为可计算的数值；由词法分析器提供；
注意：
程序内部数值的计算和标记一律使用十进制，文本中的表达式必须为十进制整数，即如果在文本中使用八进制或十六进制，词法分析器分析后不会添加至缓冲区，在表达式语法正确且其中不含标志符时，计算得到的结果一律使用十进制。
例：
对于文本中十进制数字10，其对应的初始结构体成员的值ch=’i’，po=5，val=”10”，type=1。
符号栈S：
符号结构体的一维数组。
算法：
说明：
G[E]
E->T|E+T;
T->F|T*F;
F->i|（E）;
算符优先文法并未对非终结符定义优先关系，无法对单非产生式进行规约，所以实际上在规约时，上面的E->T，T->F基本没有使用，而且规约时并不严格按照产生式的右部规约，只要待规约项符合句型#N1a1N2a2…NnanNn+1#（每个ai都是终结符，Ni是可有可无的非终结符），
并且相对产生式，在相同位置有相同的非终结符即可规约，这样算符优先文法规约很快，但有些语法错误将无法识别，在本实验中，只要在要规约的地方准确的判断可规约的项，即符合句型，在不严格要求非终结符相同而终结符位置符号相同时，存在可匹配文法的产生式，即可规约，例如：
F*F可以匹配T*F继而规约为T。
定义用W[ch]表示字符名为ch的符号；实际程序中关于终结符优先关系的比较是利用R获取优先关系标志的，算法中为了可读性，直接将结构体进行比较了。
从文本文件读入一行数据，反复调用scanP（）得到符号集合，用符号结构体数组E存储；
k=1;i=0;S[k]=W[#];
Do{
A=E[i++];
if（S[k]是终结符）
j=k;
else
j=k–1;
while（S[j]>A）{
Do{
Q=S[j];
If（S[j-1]是终结符）
j=j–1;
else
j=j–2;
}while（S[j]N=Statute（S,j+1,k）;
k=j+1；
S[k]=N；
}
If（S[j]k++;
S[k]=A;
}
elseerror（S[j].po,;
}while（A==W[#]）;
程序功能说明：
程序从文本文件读入表达式，判断语法是否正确，正确则输出结果，其中有标识符的话，结果还是含有标识符的原表达式，语法错误的话，则输出错误信息。
源程序：
程序中文本文件在桌面文件名为
#include
#include
#include<>
usingnamespacestd;
#defineNULL0
#defineMAXSIZE30h=='i'&&s==e）{
='F';
=S[s].val;
=S[s].type;
}
elseif（S[s].ch=='（'&&!
（checkVt（S[s+1].ch））&&S[e].ch=='）'）{
if（S[s+1].type==1）{
='F';
=S[s+1].val;
=S[s+1].type;
}
else{
='F';
='（'+S[s+1].val+'）';
=S[s+1].type;
}
}
elseif（!
（checkVt（S[s].ch））&&S[s+1].ch=='+'&&!
（checkVt（S[e].ch）））{
='E';
if（S[s].type==1&&S[e].type==1）{
=1;
intv=atoi（S[s].（））+atoi（S[e].（））;
charl[30];
sprintf_s（l,30,"%d",v）;
=l;
}
else{
=0;
=S[s].val+S[s+1].ch+S[e].val;
}
}
elseif（（s!
=e）&&!
（checkVt（S[s].ch））&&S[s+1].ch=='*'&&!
（checkVt（S[e].ch）））{
='T';
if（S[s].type==1&&S[e].type==1）{
=1;
intv=atoi（S[s].（））*atoi（S[e].（））;
charl[30];
sprintf_s（l,30,"%d",v）;
=l;
}
else{
=0;
=S[s].val+S[s+1].ch+S[e].val;
}
}
elseif（S[s].ch=='T'&&s==e）{
='E';
=S[s].val;
=S[s].type;
}
else{
='#';
}
=4;
returnN;
}
voiderror（charerrnum）{h））o][]=='>'）{
do{
Q=S[j];
if（checkVt（S[j-1].ch））
j=j-1;
else
j=j-2;
}while（pre[S[j].po][]!
='<'）;
WN=Statute（S,j+1,k）;
if=='#'）{
error（'4'）;
return0;
}
k=j+1;
S[k]=N;
}
if（pre[S[j].po][]=='<'||pre[S[j].po][]=='='）{
k++;
S[k]=A;
}
else{
error（pre[S[j].po][]）;
return0;
}
}while!
='#'）;
if=='#'）{
printf（"正确，结果为：
%s\n\n",S[k-1].（））;
return0;
}
}
intmain（）{
FILE*fp;
errno_terr;
if（（err=fopen_s（&fp,"C:
\\Users\\Administrator\\Desktop\\","r"））!
=NULL）{//以只读方式打开文件，失败则退出程序
printf（"filecannotopen!
"）;
exit（0）;
}
intn=0;
printf（"语法分析结果如下：
\n\n"）;
while（!
feof（fp））{//若不是文件尾则执行循环
intnum=0;
WE[MAXSIZE];//存储一行表达式
GetBC（fp）;
if（!
feof（fp））{
n++;
fseek（fp,-1L,1）;
printf（"（%d）",n）;
}
else{
break;
}
while
（1）{//只读一行，行末标志为“；”
intflag=scan（fp,E,num）;
if（flag==0）break;
num++;
}
printf（"\n输出：
"）;
syntax（E,num）;
}
fclose（fp）;//关闭文件
fp=NULL;//避免指向非法内存
}
3、程序运行流程；
4、程序的测试结果和问题；
实验报告源数据：
其它数据：
问题：
实验时是根据实验报告提供的算法编程的，但是原算法使用了类似Pascal的语言，而我用的是C，算法实现时具体的语法不同，例如Pascal的repeat…until与C语言的do…while并一样，实验时不注意会使程序出错，二者的循环条件是相反的。
编程时，误将终结符数组的左右括号输入成了中文的括号，导致在判断是否为终结符时，英文的左右括号无法与中文的括号匹配，程序出现了错误，虽然调试时很容易就发现了，但这样的细节问题不应该费时间要调试才解决，这提醒我编程时更应该认真仔细，效率才能得到保证。
另外，语法错误时，这一行表达式的分析就可以直接终止但此时程序是在两层循环里面，只有跳出这两层循环才会终止，而break则只能跳出一层，若在最后一层使用标志，再跳出一层，这就导致之后的每一行都会多做一次判断，而我又不想使用goto，所以最后我决定使用子函数，将语法分析的主要程序段放在子函数中，有语法错误，直接return就可以了。
5、实验总结。
本次实验有之前的词法分析程序和已经提供的算法作基础，编写起来并不难，就是要注意算符优先文法本身的优缺点，它忽略右部只有一个非终结符的产生式，而且规约的时候主要还是匹配终结符，由于这个原因，规约很快，但有些语法错误的表达式会误认为句子，所以在在原本算法的第十一步，规约的具体步骤要按具体的文法来完成，其中要包括没有匹配时对应的错误处理。
实验的最主要部分的算法很容易实现，主要是如何正确的完成规约，并将正确的句子的结果计算出来，此处是借助于结构体，在每个规约步骤中，加上对应的计算规则，即可完成。
通过这个，再次让我明白，编程时，设计好算法和数据结构事半功倍。
升级会员 