《编译原理》实验二.docx
《《编译原理》实验二.docx》由会员分享，可在线阅读，更多相关《《编译原理》实验二.docx（26页珍藏版）》请在冰点文库上搜索。
《编译原理》实验二
实验二预测分析法设计与实现
实验时间：
2013.5.7，5.21，6.4
实验目的
设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。
实验要求
建立文法及其LL
（1）分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。
实验内容
（1）文法描述及其LL
（1）分析表
表达式语言（XL）的语法规则如下：
1．程序→表达式；
2．|表达式；程序
prgm→expr;prgm’prgm’→prgmprgm’→ε
3．表达式→表达式+项
4．|项
expr→termexpr’expr’→+termexpr’expr’→ε
5．项→项*因式
6．|因式
term→factorterm’term’→*factorterm’term’→ε
7．因式→num_or_id
8．|（表达式）
factor→（expr）factor→num
将该语言的文法转换为如下的LL
（1）文法：
1prgm→expr;prgm’7term→factorterm’
2prgm’→prgm8term’→*factorterm’
3prgm’→ε9term’→ε
4expr→termexpr’10factor→（expr）
5expr’→+termexpr’11factor→num
6expr’→ε
first（prgm）={（,num}first（prgm’）={（,num,ε}
first（expr）={（,num}first（expr’）={+,ε}
first（term）={（,num}first（term’）={*,ε}
first（factor）={（,num}
follow（prgm）={#}follow（prgm’）={#}
follow（expr）={;,）}follow（expr’）={;,）}
follow（term）={+,;,）}follow（term’）={+,;,）}
follow（factor）={*,+,;}
select（prgm→expr;prgm’）={（,num}
select（prgm’→prgm）={（,num}
select（prgm’→ε）={#}
select（expr→termexpr’）={（,num}
select（expr’→+termexpr’）={+}
select（expr’→ε）={;,）}
select（term→factorterm’）={（,num}
select（term’→*factorterm’）={*}
select（term’→ε）={+,;,）}
select（factor→（expr））={（}
select（factor→num）={num}
该LL
（1）文法的LL
（1）分析表如下：
T
N
Num
+
*
（
）
;
#
prgm
1
1
prgm’
2
2
3
expr
4
4
expr’
5
6
6
term
7
7
term’
9
8
9
9
factor
11
10
对文法中每个文法符号指定一个常数值，符号编码表如下：
文法符号
常数值
备注
（
Num
+
）
;
*
#
4
6
2
5
1
3
0
终结符
（#为输入结束标志）
Expr
expr’
term
term’
factor
prgm
prgm’
258
260
259
262
261
256
257
非终结符
（2）文法及其LL
（1）分析表的数据结构
文法的产生式可用数组Yy_pushtab[]存放。
数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。
对于该表达式语言XL的LL
（1）分析表，可用数组Yy_d[]存放。
第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：
0（表示接受），1（表示产生式号），-1（表示语法错）。
数组Yy_pushtab[]的具体内容及表示如下：
0
1
2
3
4
5
6
7
8
9
10
Yyp00
257,1,258,0
prgm’;expr
Yyp01
256,0
prgm
Yyp02
0
Yyp03
260,259,0
expr’term
260,259,2,0
expr’term+
262,261,2,0
term’factor*
0
5,258,4,0
）expr（
6,0
Num
0
262,261,0
term’factor
Yyp04
Yyp05
Yyp06
Yyp07
Yyp08
Yyp09
Yyp10
数组Yy_d[]的具体内容及表示如下：
0123456
#；+*（）Num
-1
-1
-1
-1
0
-1
0
2
-1
-1
-1
1
-1
1
-1
-1
-1
-1
3
-1
3
-1
-1
-1
-1
6
-1
6
-1
5
4
-1
-1
5
-1
-1
-1
-1
-1
9
-1
10
-1
8
8
7
-1
8
-1
prgm256
prgm’257
expr258
term259
expr’260
factor261
term’262
（3）预测分析器总控程序结构
预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈（元素类型为int），其结构如下：
初始化；/*把开始符号的常数值压入分析站，输入指向第一个输入符号*/
while（分析栈非空）{
if（栈顶常数表示一个终结符）
if（该常数与输入符号的常数不等）
报语法错；
else{
把一个数从栈顶弹出；
advance读下一输入符号；
}
else{/*栈顶的常数表示一个非终结符*/
what_to_do=Yy_d[栈顶常数][当前输入符号的常数]；
if（what_to_do==-1）
报语法错；
else{
把栈顶元素弹出栈；
把Yy_pushtab[what_to_do]中列出的全部常数压入分析栈；
}
}
}
请实现该程序。
在程序中添加输出栈内容的功能，以便和手工模拟分析过程作比较。
（4）用预测分析器和手工模拟两种方式对文法的句子1+2；进行分析。
综合分析过程可用下表表示。
栈（符号）
栈（数值）
输入串
What_to_do
system_goal
prgm
prgm’;expr
prgm’;expr’term
prgm’;expr’term’factor
prgm’;expr’term’Num
prgm’;expr’term’
prgm’;expr’
prgm’;expr’term+
prgm’;expr’term
prgm’;expr’term’factor
prgm’;expr’term’Num
prgm’;expr’term’
prgm’;expr’
prgm’;
prgm’
263
256
2571258
2571260259
2571260262261
25712602626
2571260262
2571260
25712602592
2571260259
2571260262261
25712602626
2571260262
2571260
2571260262
257
1+2；#
1+2；#
1+2；#
1+2；#
1+2；#
1+2；#
+2；#
+2；#
+2；#
2；#
2；#
2；#
；#
；#
；#
#
12
0
3
7
11
9
5
7
11
9
6
2
（5）请考虑如何设计并实现LL
（1）分析表的自动生成程序。
下面是一个实例：
可作为参考
//LL
（1）语法分析
#include
#include
#include
#defineMAX50
usingnamespacestd;
structT_NT
{
intcode;
charstr[MAX];
};
T_NTT[7]={{0,"#"},{1,";"},{2,"+"},{3,"*"},{4,"（"},{5,"）"},{6,"Num"}};//终结符
T_NTNT[8]={{256,"prom"},{257,"prom'"},{258,"expr"},{259,"term"},//非终结符
{260,"expr'"},{261,"factor"},{262,"term'"},{263,"system_goal"}};
typedefstructsqst
{
intdata[MAX];
inttop;
}SqStack;
intYy_pushtab[13][4]=/*逆序存放产生式右部内容*/
{{257,1,258,0},
{256,0},
{0},
{260,259,0},
{0},
{260,259,2,0},
{0},
{262,261,0},
{262,261,2,0},
{0},
{5,258,4,0},
{6,0},
{256,0}
};
intYy_d[8][7]=//LL1分析表初始化
{
{-1,0,-1,-1,0,-1,0},
{2,1,-1,-1,1,-1,1},
{-1,4,-1,-1,3,4,3},
{-1,-1,-1,-1,7,-1,7},
{-1,6,5,-1,-1,6,-1},
{-1,-1,-1,-1,10,-1,11},
{-1,9,9,8,-1,9,-1},
{-1,12,-1,-1,12,-1,12},
};
intmain（）
{
SqStackst;
inti=0,j=0,l=0;
intq,k,m,n,a,what_to_do;
charc,t[MAX];
ints[MAX];
cout<<"请输入该文法的句型";
while（c!
='#'）
{
cin>>c;
t[l]=c;
l++;
if（c>='0'&&c<='9'）
s[i]=6;
else
{
switch（c）
{
case'（':
s[i]=4;break;
case'+':
s[i]=2;break;
case'）':
s[i]=5;break;
case';':
s[i]=1;break;
case'*':
s[i]=3;break;
case'#':
s[i]=0;break;
}
}
i++;
}
cout<<"LL1文法非递归预测分析表如下:
"<cout<<"栈符号"<<"│|"<<"栈数值"<<"│|"<<"输入串"<<"│|"<<"what_to_do"<st.top=-1;
st.top++;
st.data[st.top]=263;
while（st.top!
=-1）//栈非空
{
intp=0;
while（p<=st.top）
{
for（l=0;l<8;l++）
if（NT[l].code==st.data[p]）cout<for（i=0;i<7;i++）
if（T[i].code==st.data[p]）
cout<p++;
}
cout<p=0;
while（p<=st.top）
{
cout<<""<p++;
}
cout<<"│|";
for（a=j;a<5;a++）
cout<if（st.data[st.top]>=0&&st.data[st.top]<7）//栈顶为终结符
{
if（st.data[st.top]!
=s[j]）//栈顶常数与输入符号常数不等
cout<<"语法错误";
else
{
st.top--;//把一个数从栈顶弹出
j++;//读下一输入符号
}
}
else//栈顶常数为一个非终结符
{
m=st.data[st.top]-256;
n=s[j];
what_to_do=Yy_d[m][n];
cout<<"│|";
cout<<""<if（what_to_do==-1）
cout<<"语法错误";
else
{
st.top--;//把元素从栈顶弹出
k=0;
while（Yy_pushtab[what_to_do][k]!
=0）
{
st.top++;
st.data[st.top]=Yy_pushtab[what_to_do][k];
k++;
}
}
}
cout<}
return0;
}
//简单词法分析器
#include
#include
#include
#include
#include
#include
#defineNULL0
FILE*fp;
charcbuffer;
char*key[21]={"AND","BEGIN","CONST","DIV","DO","ELSE","END",
"FUNCTION","IF","INTEGER","NOT","OR","PROCEDURE",
"PROGRAM","READ","REAL","THEN","TYPE","VAR","WHILE",
"WRITE"};
char*border[8]={",",";",":
",".","（","）","[","]"};
char*arithmetic[4]={"+","-","*","/"};
char*relation[10]={"=","<",">","<>","<=",">=",":
=","{","}","#"};
char*consts[20];
char*label[20];
intconstnum=0,labelnum=0;
intsearch（charsearchchar[],intwordtype）
{
inti=0;
switch（wordtype）{
case1:
for（i=0;i<=20;i++）
{
if（strcmp（key[i],searchchar）==0）
return（i+1）;
};
case2:
{for（i=0;i<=7;i++）
{
if（strcmp（border[i],searchchar）==0）
return（i+24）;
};
return（0）;
}
case3:
{for（i=0;i<=3;i++）
{
if（strcmp（arithmetic[i],searchchar）==0）
{
return（i+35）;
};
};
return（0）;
};
case4:
{for（i=0;i<=9;i++）
{
if（strcmp（relation[i],searchchar）==0）
{
return（i+39）;
};
};
return（0）;
};
case5:
{for（i=0;i<=constnum;i++）
{
if（strcmp（consts[i],searchchar）==0）
{
return（23）;
};
}
consts[i-1]=（char*）malloc（sizeof（searchchar））;
strcpy（consts[i-1],searchchar）;
constnum++;
return（23）;
};
case6:
{for（i=0;i<=labelnum;i++）
{
if（strcmp（label[i],searchchar）==0）
{
return（22）;
};
}
label[i-1]=（char*）malloc（sizeof（searchchar））;
strcpy（label[i-1],searchchar）;
labelnum++;
return（22）;
};
}
}
charalphaprocess（charbuffer）
{
intatype;
inti=-1;
charalphatp[20];
while（（isalpha（buffer））||（isdigit（buffer）））
{
alphatp[++i]=buffer;
buffer=fgetc（fp）;
};
alphatp[i+1]='\0';
if（atype=search（alphatp,1））
printf（"%-10s,%-5d\n",alphatp,atype-1）;
else
{
atype=search（alphatp,6）;
printf（"%-10s,%-5d\n",alphatp,atype-1）;
};
return（buffer）;
}
chardigitprocess（charbuffer）
{
inti=-1;
chardigittp[20];
intdtype;
while（（isdigit（buffer）））
{
digittp[++i]=buffer;
buffer=fgetc（fp）;
}
digittp[i+1]='\0';
dtype=search（digittp,5）;
printf（"%-10s,%-5d\n",digittp,dtype-1）;
return（buffer）;
}
charotherprocess（charbuffer）
{
inti=-1;
charothertp[20];
intotype,otypetp;
othertp[0]=buffer;
othertp[1]='\0';
if（otype=search（othertp,3））
{
printf（"%-10s,%-5d\n",othertp,otype-1）;
buffer=fgetc（fp）;
gotoout;
};
if（otype=search（othertp,4））
{
buffer=fgetc（fp）;
othertp[1]=buffer;
othertp[2]='\0';
if（otypetp=search（othertp,4））
{
printf（"%-10s,%-5d\n",othertp,otypetp-1）;
gotoout;
}
else
othertp[1]='\0';
printf（"%-10s,%-5d\n",othertp,otypetp-1）;
gotoout;
};
if（buffer==':
'）
{
buffer=fgetc（fp）;
if（buffer=='='）
printf（":
=,44\n"）;
buffer=fgetc（fp）;
gotoout;
}
else
{
if（otype=search（othertp,2））
{
printf（"%-10s,%-5d\n",othertp,otype-1）;
buffer=fgetc（fp）;
gotoout;
}
};
if（（buffer!
='\n'）&&（buffer!
=''））
printf（"%cerror,notaword\n",buffer）;
buffer=fgetc（fp）;
out:
return（buffer）;
}
voidmain（）
{
inti;
clrscr（）;
printf（"TheResult:
\n"）;
for（i=0;i<=20;i++）
{
label[i]=NULL;
consts[i]=NULL;
};
if（（fp=fopen（"pas.PAS","r"））==NULL）
printf（"error"）;
else
{
cbuffer=fgetc（fp）;
while（cbuffer!
=EOF）
{
if（isalpha（cbuffer））
cbuffer=alphaprocess（cbuffer）;
elseif
升级会员 