预测分析程序实验报告

题目：预测分析法一、实验目的1、通过实验要学会用消除左递归和消除回溯的方法来使文法满足进行确定自顶向下分析的条件；2、学会用C/C++高级程序设计语言编写一个LL（1）分析法程序二、实验内容及要求LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X=a=‘#’，则宣布分析成功，停止分析过程。（２）若X=a‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。1、给定文法S->a|b|(T) T->SH|d H->,SH|ε2、该文法对应的预测分析表Ab(),#SS->aS->bS->(T)TT->SHT->SHT->SHHH->εH->,SH3、编写预测分析程序对句子进行分析三、试验程序设计说明1、相关函数说明分析栈可以采取许多的存储方法来设计，在这里采用的顺序栈。根据预测分析原理，LL(1)分析程序的实现关键在于分析栈和分析表是采用何种数据结构来实现。分析表是一个矩阵，当我们要调用分析表来分析时，就根据栈顶的非终结符和当前输入的终结符来决定执行哪种过程。具体设计思想如下：printStack（）输出分析栈内内容；printinputString（）输出用户输入的字符串；Pop（）弹出栈顶元素；Push（）向栈内添加一个元素；Search（）查找非终结符集合VT中是否存在输入的非终结符；yuCeFenXi（）进行输入串的预测分析的主功能函数；M(charA,chara)查看预测分析表M[A,a]中是否存在相应产生式。2、程序流程图把符号把符号’#’和文法符号依次推进stack栈FLAG置为TRUEFLAG=TRUE？把栈顶符号上托出去并存放在X中把第一个符号读进aX为终结符？X=a？错误处理把下一输入符号读进aX=‘#’？X=aFLAG=FALSE错误处理利用分析表分析TFFFFFTTYESTT开始结束四、实验结果语法分析的任务就是识别词法分析程序输出的单词序列是否为给定方法的正确句子。现在我们若从键盘上输入的是有正确的句子，例如：(a,a)#,显示“success”。运行结果如下：五、实验小结本次实验完成了语法分析-预测分析法的实现过程，通过本次实验巩固了以前所学过的知识，对语法分析有了更深入的了解，掌握了预测分析法的原理及其实现过程。附：#include"stdio.h"#include"string.h"charinputString[10];charstack[10];intbase=0,top=1;charVT[6]={'a','b','(',')',',','d'};/*用来存放6个终结符*/charchanShengShi[10];/*用来存放预测分析表M[A,a]中的一条产生式*/intfirstCharIntex=0;/*firstCharIntex用来存放用户输入串的第一个元素的下标*/intM(charA,chara);voidinit(){ inti; for(i=0;i<10;i++) { inputString[i]=NULL;/*初始化数组*/ stack[i]=NULL;/*初始化栈*/ chanShengShi[i]=NULL;/*初始化数组*/ } printf("\t\t1>文法G[S]:");/*输出文法做为提示*/ printf("\n\t\t\tS->a|b|(T)\n"); printf("\t\t\tT->SH|d\n"); printf("\t\t\tH->,SH|ε\n"); printf("\t\t2>该文法对应的预测分析表:\n"); printf("\t\t|a|b|(|)|,|#|\n"); printf("\t\tS|S->a|S->b|S->(T)||||\n"); printf("\t\tT|T->SH|T->SH|T->SH||||\n"); printf("\t\tH||||H->ε|H->,SH||\n");}voidprintStack()/*输出栈内内容*/{ for(inti=1;i<top;i++) printf("%c",stack[i]);} voidprintinputString()/*输出用户输入的字符串*/{ inttemp=firstCharIntex; printf("\t\t");/*该句控制输出格式*/ do{ printf("%c",inputString[temp]); temp++; }while(inputString[temp-1]!='#'); printf("\n");}charPop()/*弹出栈顶元素，用topChar返回*/{ chartopChar; topChar=stack[--top]; return topChar;}voidPush(charch){ if(top>9) printf("error:stackoverflow\n"); else { stack[top]=ch;/*给栈顶空间赋值*/ top++; }}intsearch(chartemp){ inti,flag=0; for(i=0;i<6;i++) { if(temp==VT[i])/*终结符集合中存在temp*/ { flag=1; break; } } if(flag==1) return1;/*flag==1说明已找到等于temp的元素*/ else return0; }intyuCeFenXi() { charX;/*X变量存储每次弹出的栈顶元素*/ chara;/*a变量存储用户输入串的第一个元素*/ inti; intcounter=1;/*该变量记录语法分析的步骤数*/ init();/*初始化数组*/ printf("\t\t请输入待分析字符串以#结束:"); scanf("%s",inputString); printf("\t\t3>对输入串(a,a)#的分析过程\n"); Push('#'); Push('S'); printf("\t\t步骤\t\t分析栈\t\t输入串\n");/*输出结果提示语句*/ while(1)/*while循环为语法分析主功能语句块*/ { printf("\t\t%4d",counter);/*输出分析步骤数*/ printf("\t\t");/*输出格式控制语句*/ printStack(); X=Pop(); printinputString(); if(search(X)==0) { if(X=='#') { printf("\t\t\tsuccess...\n"); return1; } else { a=inputString[firstCharIntex]; if(M(X,a)==1) { for(i=0;i<10;i++) { if(chanShengShi[i]=='$') break; } i--; while(i>=0) { Push(chanShengShi[i]); i--; } } else { printf("\t\t\terror(1)!!\n"); return0; } } } else/*说明X为终结符*/ {if(X==inputString[firstCharIntex]) firstCharIntex++; else { printf("\t\t\terror(2)!!\n"); return0; } } counter++; }}intM(charA,chara){ if(A=='S'&&a=='a') { strcpy(&chanShengShi[0],"a$"); return1; } if(A=='S'&&a=='b') { strcpy(&chanShengShi[0],"b$"); return1; } if(A=='S'&&a=='(') { strcpy(&chanShengShi[0],"(T)$"); return1; } if(A=='T'&&a=='a') { strcpy(&chanShengShi[0],"SH$"); return1; } if(A=='T'&&a=='b') { strcpy(&chanShengShi[0],"SH$"); return1; } if(A=='('&&a=='b') { strcpy(&chanShengSh