非递归预测分析器

预测分析法1实验目的与任务设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。2实验要求建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。3实验内容（1）文法描述及其LL(1)分析表表达式语言（XL）的语法规则如下：1 程序 表达式；2 |表达式；程序3 表达式 表达式 + 项4 |项5 项 项 * 因式6 |因式7 因式 num_or_id8 |(表达式)将该语言的文法转换为如下的LL(1)文法：1 prgm expr;prgm 8 term factor term2 prgm prgm 9 term *factor term 3 prgm 10 term 4 expr term expr 11 factor (expr) 5 expr 12 factor num6 expr +term expr 13 system_goal prgm7 expr 该LL(1)文法的LL(1)分析表如下： TNNum+*();#prgm111prgm2223expr4455expr677term88term1091010factor1211system_goal131313对文法中每个文法符号指定一个常数值，符号编码表如下：文法符号常数值备注（Num+);*#4625130终结符（#为输入结束标志）Exprexprtermtermfactorprgmprgmsystem_goal258260259262261256257263非终结符（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-10-1-10-1021-1-11-11-14-1-1343-1-1-1-17-17-165-1-16-1-1-1-1-110-111-1998-19-1-112-1-112-112prgm 256 prgm 257 expr 258 term 259 expr 260factor 261term 262system_goal 263数组Yy_pushtab的具体内容及表示如下：257,1,258,0prgm ; expr256,0prgm0260,259,0expr term0260,259,2,0expr term +0262,261,0term factor262,261,2,0term factor *5,258,4,0) expr (06,0Num256,0prgm0123456789101112Yyp00Yyp01Yyp02Yyp03Yyp04Yyp05Yyp06Yyp07Yyp08Yyp09Yyp10Yyp11Yyp12（3）预测分析器总控程序结构预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈（元素类型为int），其结构如下：初始化；/* 把开始符号的常数值压入分析站，输入指向第一个输入符号 */while(分析栈非空) if(栈顶常数表示一个终结符)if(该常数与输入符号的常数不等)报语法错；else 把一个数从栈顶弹出；advance读下一输入符号；else /* 栈顶的常数表示一个非终结符 */what_to_do=Yy_d栈顶常数当前输入符号的常数；if(what_to_do= -1)报语法错；else 把栈顶元素弹出栈；把Yy_pushtabwhat_to_do中列出的全部常数压入分析栈；请实现该程序。在程序中添加输出栈内容的功能，以便和手工模拟分析过程作比较。（4）用预测分析器和手工模拟两种方式对文法的句子1+2；进行分析。综合分析过程可用下表表示。栈（符号）栈（数值）输入串What_to_dosystem_goalprgmprgm ; exprprgm ; expr termprgm ; expr term factorprgm ; expr term Numprgm ; expr termprgm ; expr prgm ; expr term +prgm ; expr termprgm ; expr term factorprgm ; expr term Numprgm ; expr term prgm ; expr prgm ; prgm 263256257 1 258257 1 260 259257 1 260 262 261257 1 260 262 6257 1 260 262 257 1 260 257 1 260 259 2257 1 260 259 257 1 260 262 261257 1 260 262 6257 1 260 262257 1 260 257 1 260 262257 1+2；#1+2；#1+2；#1+2；#1+2；#1+2；#+2；#+2；#+2；#2；#2；#2；#；#；#；#120371195711962（5）请考虑如何设计并实现LL(1)分析表的自动生成程序。源程序：预测分析法源程序：#include#include#include#includeusing namespace std;#define stacksize 10#define stringsize 20typedef struct sqst /定义分析栈int datastacksize;int top; /栈顶指针sqstack;string word1=prgm,prgm,expr,term,expr,factor,term,system_goal;string word2 =#,;,+,*,(,),NUM;int main()void out(sqstack st,string str,int sp,int k); /输出函数void init(int Yy_pushtab134,int Yy_d2647); /初始化分析栈Yy_d与Yy_pushtabvoid str_to_st1(string str,int st1); /对输入字符串的转换 void Foreparser(sqstack st,int Yy_pushtab134,int Yy_d2647, int st1,string str); /预测分析法int Yy_pushtab134,Yy_d2647; int st1stringsize;string str;sqstack st;st.top=-1; /分析栈的初始化 st.top+; st.datast.top=263; /分析栈初始化# coutstr;cout栈(符号) 栈(数值) 输入串 What_to_doendl; 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.datai7)coutword2st.datai ;n=word2st.datai.length()+1;else coutword1st.datai-256 ;n=word1st.datai-256.length()+1; m=n+m; for(i=m;i30;i+) cout ; for(i=0;i=sp;i+) /输出栈(数字)coutsetiosflags(ios:left)setw(3)st.datai ; for(int h=sp+1;h6;h+)cout ; for(int j=k;jstrlen(str.c_str();j+) /输出输入串 coutstrj; for(int g=strlen(str.c_str()-k;g10;g+) cout ; cout ; void init(int Yy_pushtab134,int Yy_d2647) /初始化分析栈Yy_d与Yy_pushtabint i,j; ifstream infile1(1.txt,ios:in); ifstream infile2(2.txt,ios:in);for(i=0;i13;i+)for(j=0;jYy_pushtabij;/coutYy_pushtabij ; /coutendl; for(i=256;i264;i+)for(j=0;jYy_dij;/coutYy_dij ; / coutendl;infile1.close();infile2.close();void str_to_st1(string str,int st1) /对输入字符串的转化for(int i=0;i=0&stri=0&st.datast.top=6)/栈顶元素为终结符if(st.datast.top!=st1k)cout未能分析成功endl; break;else st.top-;k+;coutendl;else /栈顶元素为非终结符what_to_do=Yy_dst.datast.topst1k; coutwhat_to_doendl; /输出what_to_doif(what_to_do=-1)coutstr不是本文法句子。endl;break;else st.top-;for(i=0;i4;i+) /把Yy_pushtabwhat_to_do中列出的全部常数压入分析栈 if(Yy_pushtabwhat_to_doi!=-1&Yy_pushtabwhat_to_doi!=0) s