LL(1)预测分析法实验报告

编 译 原 理 实 验 报 告

一、 实验目的及要求

1. 通过本次实验，加深对LL(1)预测分析法原理的认识和理解。 2. 构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子。

3. 了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。 二、 运行环境： 硬件：windows xp 软件：visual c++6.0 三、 实验内容

1、分析使用LR(1)的优点：

(1)LR分析器能够构造来识别所有能用上下文无关文法写的程序设计语言的结构。

(2)LR分析方法是已知的最一般的无回溯移进-归约方法，它能够和其他移进-归约方法一样有效地实现。

(3)LR方法能分析的文法类是预测分析法能分析的文法类的真超集。

(4)LR分析器能及时察觉语法错误,快到自左向右扫描输入的最大可能。

为了使一个文法是LR的，只要保证当句柄出现在栈顶时，自左向右扫描的移进-归约分析器能够及时识别它便足够了。当句柄出现在栈顶时，LR分析器必须要扫描整个栈就可以知道

这一点，栈顶的状态符号包含了所需要的一切信息。如果仅知道栈内的文法符号就能确定栈顶是什么句柄。LR分析表的转移函数本质上就是这样的有限自动机。不过，这个有限自动机不需要根据每步动作读栈，因为，如果这个识别句柄的有限自动机自底向上读栈中的文法符号的话，它达到的状态正是这时栈顶的状态符号所表示的状态，所以，LR分析器可以从栈顶的状态确定它需要从栈中了解的一切。 2、LR分析器由三个部分组成：

(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。

(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。

(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。

分析器的动作就是由栈顶状态和当前输入符号所决定。

四、 程序源代码：

//edge.h

#ifndef HEAD_EDGE #define HEAD_EDGE

#include

using namespace std;

extern int SUM;

extern string NODE,ENODE;

class edge {

public: edge();

string getlf(); string getrg(); string getfirst(); string getfollow(); string getselect(); string getro(); int getrlen();

void newfirst(string w); void newfollow(string w); void newselect(string w); void delfirst(); private:

string left,right,first,follow,select; int rlen; };

#endif

/////////////////////////////////////////////////////////////////////////////

//edge.cpp

#include #include %using namespace std;

edge::edge() {

cin>>left>>right; rlen=right.length();

if(NODE.find(left)>NODE.length()) NODE+=left; }

string edge::getlf() {

return left; }

string edge::getrg() {

return right; }

string edge::getfirst() {

return first; }

string edge::getfollow() {

return follow; }

string edge::getselect() {

return select; }

string edge::getro() {

string str; str+=right[0]; return str; }

int edge::getrlen() {

return right.length(); }

void edge::newfirst(string w) { int i;

for(i=0;i

if(first.find(w[i])>first.length()) first+=w[i]; }

void edge::newfollow(string w) { int i;

for(i=0;i

if(follow.find(w[i])>follow.length()&&w[i]!='*') follow+=w[i]; }

void edge::newselect(string w) { int i;

for(i=0;i

if(select.find(w[i])>select.length()&&w[i]!='*') select+=w[i]; }

void edge::delfirst() {

int i=first.find('*'); first.erase(i,1); }

//LL1.cpp

#include #include #include %using namespace std;

int SUM;

string NODE,ENODE;

//计算first

void first(edge ni,edge *n,int x) { int i,j;

for(j=0;j

if(ni.getlf()==n[j].getlf()) {

if(NODE.find(n[j].getro())

for(i=0;i

if(n[i].getlf()==n[j].getro()) first(n[i],n,x); } else

n[x].newfirst(n[j].getro()); } } }

//计算follow

void follow(edge ni,edge *n,int x) {

int i,j,k,s; string str;

for(i=0;i

s=NODE.find(ni.getrg()[i]);

if(s-1) //是非终结符 if(i

if(n[j].getlf().find(ni.getrg()[i])==0) {

if(NODE.find(ni.getrg()[i+1])

for(k=0;k

if(n[k].getlf().find(ni.getrg()[i+1])==0) {

n[j].newfollow(n[k].getfirst());

if(n[k].getfirst().find(\ n[j].newfollow(ni.getfollow()); } } else {

str.erase();

str+=ni.getrg()[i+1]; n[j].newfollow(str); } } } }

//计算select

void select(edge &ni,edge *n) { int i,j;

if(ENODE.find(ni.getro())

ni.newselect(ni.getro()); if(ni.getro()==\

ni.newselect(ni.getfollow()); } else

for(i=0;i

if(ni.getrg()[i]==n[j].getlf()[0]) {

ni.newselect(n[j].getfirst());

if(n[j].getfirst().find('*')>n[j].getfirst().length()) return; } }

//输出集合

void out(string p) { int i;

if(p.length()==0) return; cout<<\

for(i=0;i

cout<

cout<

//连续输出符号

void outfu(int a,string c) { int i;

for(i=0;i

//输出预测分析表

void outgraph(edge *n,string (*yc)[50]) {

int i,j,k; bool flag;

for(i=0;i

if(ENODE[i]!='*') {

outfu(10,\

cout<

outfu(10,\cout<<\int x;

for(i=0;i

outfu(4,\ cout<

for(k=0;k

flag=1;

for(j=0;j

if(NODE[i]==n[j].getlf()[0]) {

x=n[j].getselect().find(ENODE[k]); if(x-1) {

cout<<\ yc[i][k]=n[j].getrg();

outfu(9-n[j].getrlen(),\ flag=0; }

x=n[j].getselect().find('#');

if(k==ENODE.length()-1&&x-1) {

cout<<\ yc[i][j]=n[j].getrg(); }

} }

if(flag&&ENODE[k]!='*') outfu(11,\ }

cout<

//分析符号串

int pipei(string &chuan,string &fenxi,string (*yc)[50],int &b) {

char ch,a; int x,i,j,k; b++;

cout<9)

outfu(8,\else

outfu(9,\cout<

outfu(26-chuan.length()-fenxi.length(),\cout<

ch=fenxi[fenxi.length()-1]; x=ENODE.find(ch);

if(x-1) {

if(ch==a) {

fenxi.erase(fenxi.length()-1,1); chuan.erase(0,1);

cout<<\匹配\ if(pipei(chuan,fenxi,yc,b)) return 1; else

return 0; } else

return 0; } else {

if(ch=='#') {

if(ch==a) {

cout<<\分析成功\ return 1; } else

return 0; } else

if(ch=='*') {

fenxi.erase(fenxi.length()-1,1); if(pipei(chuan,fenxi,yc,b)) return 1; else

return 0; } else {

i=NODE.find(ch); if(a=='#') {

x=ENODE.find('*');

if(x-1) j=ENODE.length()-1; else

j=ENODE.length(); } else

j=ENODE.find(a); if(yc[i][j].length()) {

cout<-1;k--) if(yc[i][j][k]!='*') fenxi+=yc[i][j][k];

if(pipei(chuan,fenxi,yc,b)) return 1; else

return 0; } else

return 0;

} } }

void main() {

edge *n;

string str,(*yc)[50]; int i,j,k; bool flag=0;

cout<<\请输入上下文无关文法的总规则数：\cin>>SUM;

cout<<\请输入具体规则（格式：左部 右部，*为空）：\n=new edge[SUM]; for(i=0;i

for(j=0;j

str=n[i].getrg();

if(NODE.find(str[j])>NODE.length()&&ENODE.find(str[j])>ENODE.length()) ENODE+=str[j]; }

//计算first集合 for(i=0;i

first(n[i],n,i); /*

cout<<\ out(n[i].getfirst()); cout<

//outfu(10,\for(i=0;i

if(n[i].getfirst().find(\ {

if(NODE.find(n[i].getro())

for(k=1;k

if(NODE.find(n[i].getrg()[k])

for(j=0;j

if(n[i].getrg()[k]==n[j].getlf()[0]) {

n[i].newfirst(n[j].getfirst()); break; } }

if(n[j].getfirst().find(\ {

n[i].delfirst(); break; } } } } } /*

for(i=0;i

cout<<\ out(n[i].getfirst()); cout<

outfu(10,\*/

//计算follow集合 for(k=0;k

for(i=0;i

if(n[i].getlf()==n[0].getlf()) n[i].newfollow(\ follow(n[i],n,i); }

for(i=0;i

for(j=0;j

if(n[j].getrg().find(n[i].getlf())==n[j].getrlen()-1) n[i].newfollow(n[j].getfollow()); /*

cout<<\ out(n[i].getfollow()); cout<

}

//outfu(10,\//计算select集合 for(i=0;i

select(n[i],n); /*

cout<<\ out(n[i].getselect()); cout<

for(i=0;i

str.erase();

for(j=0;j

if(n[j].getlf()[0]==NODE[i]) {

if(!str.length())

str=n[j].getselect(); else {

for(k=0;k

flag=1; break; } } } } /*

for(i=0;i

cout<<\ out(n[i].getselect()); cout<

cout<

cout<<\outfu(5+SUM,\cout<

for(i=0;i

for(j=0;j

if(NODE[i]==n[j].getlf()[0]) {

outfu(3,\ cout<

outfu(SUM+4-2*n[j].getfirst().length(),\ out(n[j].getfollow()); cout<

outfu(5+SUM,\

cout<

cout<<\该文法不是LL(1)文法!\ return; } else {

cout<<\该文法是LL(1)文法!\ }

//输出预测分析表

cout<

for(i=0;i

for(j=0;j

cout<

string chuan,fenxi,fchuan;

cout<>chuan; fchuan=chuan; fenxi=\

fenxi+=NODE[0];

//cout<<\//分析符号串 i=0;

cout<

cout<<\分析栈\outfu(10,\

cout<<\剩余输入串\outfu(10,\cout<<\动作\

if(pipei(chuan,fenxi,yc,i))

cout<

cout<

五、 解析结果：

测试数据一： S→a︳^︳(T) T→SF F→,SF F→ε 实验截图

输入（a，（a））#后测试结果为

测试数据二：

S →AB S→ bC A →* A →b

B →* B →aD C →AD C →b D →aS D →c

实验结果截图

六、 实验总结分析

通过本次上机实验，我加深了对预测分析LL（1）分析法的理解，同时体验到了编译原理中一些算法的巧妙。由于LL（1）分析法程序是一个相当复杂的程序，它需要利用到大量的编译原理，编程技巧和数据结构。由于先前掌握的知识不够牢固深刻使之在实验过程中出现了大量的问题。由于课前的充分准备，加上同学和老师的帮助，最后顺利完成了实验。

编译原理的在整个计算机体系课程中有着重要的地位，我现在才刚刚入门，所以，我会在以后的课程和实验中继续努力，学好编译原理课程，为以后的学习打下基础。

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