非递归预测分析器1

预测分析法

1．实验目的与任务

设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。

2．实验要求

建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。

3．实验内容

（1）文法描述及其LL(1)分析表 表达式语言（XL）的语法规则如下：

1． 程序 → 表达式；

2． |表达式；程序 3． 表达式→ 表达式 + 项 4． |项 5． 项 → 项 * 因式 6． |因式 7． 因式 → num_or_id 8． |(表达式)

将该语言的文法转换为如下的LL(1)文法：

1 prgm → expr;prgm’ 8 term → factor term’ 2 prgm’ → prgm 9 term’ → *factor term’ 3 prgm’ →ε 10 term’ →ε

4 expr → term expr’ 11 factor → (expr) 5 expr →ε 12 factor → num 6 expr’ → +term expr’ 13 system_goal → prgm 7 expr’ →ε

该LL(1)文法的LL(1)分析表如下：

T N prgm prgm’ expr expr’ term term’ factor system_goal 12 13 8 Num 1 2 4 + 6 10 * 9 ( 1 2 4 8 11 13 ) 5 7 10 ; 1 2 5 7 10 13 # 3

对文法中每个文法符号指定一个常数值，符号编码表如下：

文法符号 常数值 备注 （ Num + ) ; * # Expr expr’ term term’ factor prgm prgm’ system_goal 4 6 2 5 1 3 0 258 260 259 262 261 256 257 263 终结符 （#为输入结束标志） 非终结符 （2）文法及其LL(1)分析表的数据结构

文法的产生式可用数组Yy_pushtab[]存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于该表达式语言XL的LL(1)分析表，可用数组Yy_d[]存放。第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：0（表示接受），1（表示产生式号），-1（表示语法错）。

数组Yy_d[]的具体内容及表示如下：

0 1 2 3 4 5 6 # ； + * （ ） Num

prgm 256 -1 0 -1 -1 0 -1 0 prgm’ 257 2 1 -1 -1 1 -1 1 expr 258 -1 4 -1 -1 3 4 3 term 259 -1 -1 -1 -1 7 -1 7 expr’ 260 -1 6 5 -1 -1 6 -1 factor 261 -1 -1 -1 -1 10 -1 11 term’ 262 -1 9 9 8 -1 9 -1 system_goal 263 -1 12 -1 -1 12 -1 12

数组Yy_pushtab[]的具体内容及表示如下： 0 257,1,258,0 Yyp00 prgm’ ; expr 1 256,0 Yyp01 prgm

（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；进行分析。综合分析过程可用下表表示。 栈（符号） 栈（数值） 输入串 1+2；# 1+2；# 1+2；# 1+2；# 1+2；# 1+2；# +2；# +2；# +2；# 2；# 2；# 2；# ；# ；# ；# # What_to_do 12 0 3 7 11 9 5 7 11 9 6 2 system_goal 263 prgm 256 prgm’ ; expr 257 1 258 prgm’ ; expr’ term 257 1 260 259 prgm’ ; expr’ term’ 257 1 260 262 261 factor 257 1 260 262 6 prgm’ ; expr’ term’ 257 1 260 262 Num 257 1 260 prgm’ ; expr’ term’ 257 1 260 259 2 prgm’ ; expr’ 257 1 260 259 prgm’ ; expr’ term + 257 1 260 262 261 prgm’ ; expr’ term 257 1 260 262 6 prgm’ ; expr’ term’ 257 1 260 262 factor 257 1 260 prgm’ ; expr’ term’ 257 1 260 262 Num 257 prgm’ ; expr’ term’ prgm’ ; expr’ prgm’ ; prgm’

（5）请考虑如何设计并实现LL(1)分析表的自动生成程序。 源程序：预测分析法源程序： #include #include #include #include using namespace std; #define stacksize 10 #define stringsize 20

typedef struct sqst //定义分析栈 { int data[stacksize]; int top; //栈顶指针 }sqstack;

string word1[]={\string word2[ ]={\

int main() { void out(sqstack st,string str,int sp,int k); //输出函数 void init(int Yy_pushtab[13][4],int Yy_d[264][7]); //初始化分析栈Yy_d[]与Yy_pushtab[] void str_to_st1(string str,int st1[]); //对输入字符串的转换

void Foreparser(sqstack st,int Yy_pushtab[13][4],int Yy_d[264][7], int st1[],string str); //预测分析法 int Yy_pushtab[13][4],Yy_d[264][7]; int st1[stringsize]; string str; sqstack st; st.top=-1; //分析栈的初始化 st.top++;

st.data[st.top]=263; //分析栈初始化\

cout<<\请输入字符串:\ cin>>str; cout<<\栈(符号) \ 栈(数值)\ 输入串 \

str_to_st1(str,st1);

init(Yy_pushtab,Yy_d); Foreparser(st,Yy_pushtab,Yy_d,st1,str);

return 0; }

void out(sqstack st,string str,int sp,int k)//输出函数 { int n,m=0; for(int i=0;i<=sp;i++)//输出栈(符号) { if(st.data[i]<7) { cout<

m=n+m; }

for(i=m;i<30;i++) cout<<\

for(i=0;i<=sp;i++) //输出栈(数字) cout<

void init(int Yy_pushtab[13][4],int Yy_d[264][7]) //初始化分析栈Yy_d[]与Yy_pushtab[] { int i,j;

ifstream infile1(\ ifstream infile2(\ for(i=0;i<13;i++) { for(j=0;j<4;j++) {

infile1>>Yy_pushtab[i][j]; // cout<

//cout<

for(i=256;i<264;i++) { for(j=0;j<7;j++) { infile2>>Yy_d[i][j]; // cout<

// cout<

if(str[i]>='0'&&str[i]<='9') st1[i]=6; } }

void Foreparser(sqstack st,int Yy_pushtab[13][4],int Yy_d[264][7], int st1[],string str) 分析法 { int i,k=0,what_to_do;

while(st.top!=-1)

//预测 {

out(st,str,st.top,k); if(st.data[st.top]>=0&&st.data[st.top]<=6)//栈顶元素为终结符 if(st.data[st.top]!=st1[k]) { cout<<\未能分析成功\ break; } else { st.top--; k++; cout<

if(Yy_pushtab[what_to_do][i]!=-1&&Yy_pushtab[what_to_do][i]!=0) { st.top++; st.data[st.top]=Yy_pushtab[what_to_do][i]; } } } if(st.top==-1&&st1[k]==0) cout<

初始化文件需要放在代码文件夹 1、初始化Yy_pushtab[] 文件：

2、初始化Yy_d[] 文件：

程序运行截图：

1、对文法句子 1+2;# 进行分析：

1+2;# 是本文法句子，与手工分析一致。

2、对文法句子 2-1;# 进行分析：

2-1;#不是本文法句子，与手工分析一致。

本文来源：https://www.bwwdw.com/article/fyu6.html