编译原理实验报告5-语法分析程序的设计（2）
- 格式：pdf
- 大小：216.24 KB
- 文档页数：11
编译原理实验报告5-语法分析程序的设计（2）
实验5 语法分析程序的设计（2）
⼀、实验⽬的
通过设计、编制、调试⼀个典型的语法分析程序，实现对词法分析程序所提供的单词序列进⾏语法检查和结构分析，进⼀步掌握常⽤的语法分析中算法优先分析⽅法。
⼆、实验内容
设计⼀个⽂法的算法优先分析程序，判断特定表达式的正确性。
三、实验要求1、给出⽂法如下：
G[E]
E->T|E+T;
T->F|T*F;
F->i|(E);
可以构造算符优先表如下：+ * ( ) i
+
*
(
)
i
2、计算机中表⽰上述优先关系，优先关系的机内存放⽅式有两种1）直接存放，2）为优先关系建⽴优先函数，这⾥由学⽣⾃⼰选择⼀种⽅式；
给出算符优先分析算法如下：k:=1; S[k]:=‘#’;
REPEAT
把下⼀个输⼊符号读进a中；IF S[k]∈V T THEN j:=k ELSE j:=k-1;
WHILE S[j] a DO
BEGIN
REPEAT
Q:=S[j];
IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2
UNTIL S[j] Q
把S[j+1]…S[k]归约为某个N；k:=j+1;
S[k]:=N;END OF WHILE;
IF S[j] a OR S[j] a THEN
BEGIN
k:=k+1;S[k]:=a
END
ELSE ERROR
UNTIL a=‘#’
根据给出算法，利⽤适当的数据结构实现算符优先分析程序；
利⽤算符优先分析程序完成下列功能：
⼿⼯将测试的表达式写⼊⽂本⽂件，每个表达式写⼀⾏，⽤“；”表⽰结束；
读⼊⽂本⽂件中的表达式；
调⽤实验2中的词法分析程序搜索单词；
把单词送⼊算法优先分析程序，判断表达式是否正确（是否是给出⽂法的语⾔），若错误，应给出错误信息；
完成上述功能，有余⼒的同学可以对正确的表达式计算出结果。
四、实验环境PC微机
DOS操作系统或Windows 操作系统
Turbo C 程序集成环境或Visual C++ 程序集成环境
五、实验步骤
分析⽂法中终结符号的优先关系；
存放优先关系或构造优先函数；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
输出：错误
七、实验报告要求
实验报告应包括以下⼏个部分：
给定⽂法优先关系和存放⽅式；+ * ( ) i #
+
*
( e1
) e2 e2
i e2 e2
e4
# e3
引⼊“#”，将句型包含起来并填⼊出错标记。使⽤⼆维数组将其存放。
算符优先分析程序的算法和结构；
程序从⽂本⽂件中逐⾏读取表达式，每⾏以“；”做标记。调⽤词法分析程序将这⾏数据分析出由⼀个个的单词组成的表达式，再逐个分析单词。另外，由于⽂法中没写⼊关于标识符和常数的产⽣式，所以在对单词符号进⾏语法分析时，会将标识符和常数⾃动规约为“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] < Q);
N = Statute(S,j + 1,k);
k = j + 1；
S[k] = N；
}If(S[j] < A || S[j] == A) {
k++;
S[k] = A;
}
else error(S[j].po,;
}while(A == W[#]);
程序功能说明：
程序从⽂本⽂件读⼊表达式，判断语法是否正确，正确则输出结果，其中有标识符的话，结果还是含有标识符的原表达式，语法错误的话，则输出错误信息。
源程序：
程序中⽂本⽂件在桌⾯⽂件名为#include
#include
#include<>
using namespace std;
#define NULL 0
#define MAXSIZE 30 h == 'i' && s == e) {
= 'F';
= S[s].val;
= S[s].type;
}
else if (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;
}
}
else if (!(checkVt(S[s].ch)) && S[s + 1].ch == '+' && !(checkVt(S[e].ch))) {
= 'E';
if (S[s].type == 1 && S[e].type == 1) {= 1;
int v = atoi(S[s].()) + atoi(S[e].());
char l[30];
sprintf_s(l,30,"%d", v);
= l;
}
else {
= 0;
= S[s].val + S[s + 1].ch + S[e].val;
}
}
else if ((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;
int v = atoi(S[s].()) * atoi(S[e].());
char l[30];
sprintf_s(l, 30,"%d", v);
= l;
}
else {
= 0;
= S[s].val + S[s + 1].ch + S[e].val;
}
}
else if(S[s].ch == 'T' && s == e){
= 'E';
= S[s].val;
= S[s].type;
}
else {
= '#';
}
= 4;
return N;
}
