下载文档原格式
编译原理语法分析器实验报告班级：学号：姓名：实验名称语法分析器一、实验目的1、根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。
2、本次实验的目的主要是加深对自上而下分析法的理解。
二、实验内容[问题描述]递归下降分析法：0.定义部分：定义常量、变量、数据结构。
1.初始化：从文件将输入符号串输入到字符缓冲区中。
2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。
LL（1）分析法：模块结构：1、定义部分：定义常量、变量、数据结构。
2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）；3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则；4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。
[基本要求]1. 对数据输入读取2. 格式化输出分析结果2．简单的程序实现词法分析public static void main(String args[]) {LL l = new LL();l.setP();String input = "";boolean flag = true;while (flag) {try {InputStreamReader isr = newInputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);System.out.println();System.out.print("请输入字符串(输入exit退出)：");input = br.readLine();} catch (Exception e) {e.printStackTrace();}if(input.equals("exit")){flag = false;}else{l.setInputString(input);l.setCount(1, 1, 0, 0);l.setFenxi();System.out.println();System.out.println("分析过程");System.out.println("----------------------------------------------------------------------");System.out.println(" 步骤| 分析栈| 剩余输入串| 所用产生式");System.out.println("----------------------------------------------------------------------");boolean b = l.judge();System.out.println("----------------------------------------------------------------------");if(b){System.out.println("您输入的字符串"+input+"是该文法的一个句子");}else{System.out.println("您输入的字符串"+input+"有词法错误！");}}}}//实现各函数并且加注释三、编程并上机调试运行运行结果如下图：四、实验小结通过这次实验，我对语法分析有了更深刻的了解，对它的形成有了更清楚得认识。
集美大学计算机工程学院实验报告课程名称：编译原理指导教师：付永钢实验成绩：实验编号：实验三实验名称：LL(1)语法分析器的构造班级：计算14姓名：学号上机实践日期：2017.6上机实践时间：6学时一、实验目的1、掌握LL(1)分析法的基本原理；2、掌握LL(1)分析表的构造方法；3、掌握LL(1)驱动程序的构造方法。
二、实验环境Ubuntu三、实验原理1、对文法要求LL(1)分析法属于自顶向下分析方法，因此需要预测匹配的产生式。
即在LL(1)分析法中，每当在符号栈的栈顶出现非终结符时，要预测用哪个产生式的右部去替换该非终结符。
LL(1)分析方法要求文法满足如下条件：对于任一非终结符A，其任意两个产生式A→α,A→β，都要满足下面条件：First(A→α)∩First(A→β)=∅2、分析表构造LL(1)分析表的作用是对当前非终结符和输入符号确定应该选择用哪个产生式进行推导。
它的行对应文法的非终结符，列对应终结符，表中的值有两种：一是产生式的编号，一是错误编号。
若用T表示LL(1)分析表，则T可表示如下：T: V N×V T→P∪{Error}T(A, t) = A→α，当t∈First(A→α)T(A, t) = Error，否则其中P表示所有产生式的集合。
显然，一个文法G是LL(1)文法，当且仅当T的元素包含唯一的一个产生式或Error。
3、驱动程序构造LL(1)分析主要包括以下四个动作，其中X为符号栈栈顶元素，a为输入流当前字符。
●替换：当X∈V N时选相应产生式的右部β去替换X。
●匹配：当X∈V T时它与a进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动一位，否则报错。
●成功：当格局为（空，空）时报告分析成功。
●报错：出错后，停止分析。
四、实验内容已知文法G[E]:E→E+T|TT→T*F|FF→(E)|i说明：终结符号i为用户定义的简单变量, 即标识符的定义。
实验3 ＬL(1）文法构造一、实验目的熟悉ＬL（１）文法的分析条件,了解LL(1)文法的构造方法。
二、实验内容1、编制一个能够将一个非LＬ(1)文法转换为ＬL（1）文法；２、消除左递归;3、消除回溯。
三、实验要求1、将一个可转换非ＬL(1）文法转换为LＬ（1）文法,要经过两个阶段，1）消除文法左递归，2）提取左因子，消除回溯。
2、提取文法左因子算法:１）对文法G的所有非终结符进行排序２)按上述顺序对每一个非终结符Pi依次执行:foｒ( j=1; j＜ i-１；j++）将Pj代入Pi的产生式(若可代入的话）;消除关于Pi的直接左递归:Pi －＞ Pｉα|β ,其中β不以Ｐi开头,则修改产生式为：Pi —> βPi′Pｉ′—＞αPi′｜ε3)化简上述所得文法。
3、提取左因子的算法:Ａ—＞δβ1｜δβ2|…|δβn|γ１｜γ2|…|γｍ(其中,每个γ不以δ开头) 那么,可以把这些产生式改写成A —＞δA′｜γ1| γ２…|γｍA′—>β１|β2|…|βn4、利用上述算法,实现构造一个LL（1）文法:1）从文本文件ｇ．ｔｘｔ中读入文法,利用实验1的结果，存入实验１设计的数据结构；2）设计函数remove_left_ｒeｃｕrｓioｎ(）和remoｖｅ_left＿gｅne()实现消除左递归和提取左因子算法，分别对文法进行操作,消除文法中的左递归和提出左因子；3）整理得到的新文法;4）在一个新的文本文件neｗg．txt输出文法，文法输出按照一个非终结符号一行,开始符号引出的产生式写在第一行,同一个非终结符号的候选式用“｜”分隔的方式输出。
四、实验环境ＰC微机DOS操作系统或Wiｎdoｗｓ操作系统Turbo Ｃ程序集成环境或ViｓuａｌC＋+ 程序集成环境五、实验步骤１、学习LＬ（1）文法的分析条件;２、学习构造LL(1）文法的算法;3、结合实验１给出的数据结构，编程实现构造ＬＬ（1）文法的算法;4、结合实验1编程和调试实现对一个具体文法运用上述算法,构造它的LＬ（１）文法形式;5、把实验结果写入一个新建立的文本文件。
目录引言 (1)第一章概述 (4)1.1设计内容 (4)1.2设计要求 (4)第二章设计的基本原理 (4)2.1预测分析表的构成原理 (4)2.2预测分析程序的生成 (5)第三章程序设计 (5)3.1总体方案设计 (6)3.2各模块设计 (6)第四章程序测试 (7)附录程序清单 (8)课 程 设 计L L (1)文法分析器2010 年 12 月设计题目学 号 专业班级 学生姓名指导教师合肥工业大学课程设计任务书第一章概述1.1 设计内容:1:预测分析表自动构造程序的实现2:预测分析程序的实现1.2 设计要求1:设计内容及要求：对于任意输入的一个LL(1)文法，构造其预测分析表。
要求：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再实现教材P.79给出的预测分析表构造算法。
程序显示输出预测分析表或输出到指定文件中。
2:设计内容及要求：对文法 G: E→E+T|T 按教材P.76表4.1构造出G的预测分析程序，T→T*F|F 程序显示输出如P.78那样的匹配过程。
F→（E）|i第二章设计的基本原理2.1预测分析表的构成原理对于任意给定的LL(1) 文法G,为了构造它的预测分析表M,我们就必须构造与文法G有关的集合First和fellow.首先我们对每一个X∈V T U Vn ,构造FIRST(X),办法是,连续使用下面的规则,直至每个集合FIRST不再增大为止.(1)若X∈V T,,则FIRST(X)={X}.(2)若X∈Vn ,且有产生式X->a……,则把a加入到FIRST(X)中,若X->ε,也是一条产生式,则把ε也加到FIRST(X)中.(3)若X->Y……是一个产生式且Y∈Vn,则把FIRST(Y)中所有非ε-元素都加到FIRST(X)中,若X->Y1Y2……Y K ,是一个连续的产生式, Y1Y2……Y i-1 都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Y j) 都含有ε(即Y1Y2……Y i-1=>ε),则把FIRST(Y i) 中的所有非ε-元素都加到FIRST(X)中,特别是,若所有的FIRST(Y j)均含有ε,j=1,2,……,k,则把ε加到FIRST(X)中.对于文法G中每个非终结符A构造FOLLOW(A)的办法是,连续使用下面的规则,直到每个FOLLOW不在增大为止.(1)对于文法的开始符号S,置#于FOLLOW(S)中;(2)若A->aBb是一个产生式,则把FIRST(b)\{ ε}加至FOLLOW(B)中;(3)若A->aB是一个产生式,或A->aBb是一个产生式而b=>ε(即ε∈FIRST( b))则把FOLLOW(A)加至FOLLOW(B)中构造分析表M的算法是:(1)对文法G的每个产生式A->a执行第二步和第三步;(2)对每个终结符a∈FIRST(a), 把A->a加至M[A,a]中;(3)若ε∈FIRST(a),则把任何b∈FOLLOW(A)把A->a加至M[A,b]中;(4)把所有无定义的M[A,a]标上出错标志.2.2 预测分析程序的生成预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号行事的,对于任何(X,a),总控程序每次都执行下述三种可能的动作之一;(1)若X=a=”#”,则宣布分析成功,停止分析过程.(2)若X=a≠”#”,则把X从STACK栈顶逐出,让a指向下一个输入符号.(3)若X是一个非终结符,则查看分析表M,若M[A,a]中存放着关于X的一个产生式,那么,首先把X逐出STACK栈顶,然后,把产生式的右部符号串按反序一一推进STACK栈(若右部符号为ε,则意味着不推什么东西进栈).在把产生式的右部符号推进栈的同时应做这个产生式相应得语义动作,若M[A,a]中存放着”出错标志”,则调用出错诊察程序ERROR.第三章程序设计3.1 总体方案设计在看到这个题目后,首先想到的就是要分模块进行设计.(1)第一模块:把文本文件中的LL(1)文法读入到程序中grammer类中的数组成员g中.(2)第二模块:通过对已输入到数组g中的文法,进行扫描,把相应的非终结符和终结符输入到非终结符数组VN中和终结符数组VT中.(3)第三模块:生成所有的非终结符的FIRST集合(4)第四模块:生成所有的非终结符的FOLLOW集合(5)第五模块:生成文法的预测分析表(6)第六模块:生成文法的预测分析程序通过这六模块的设计,最后可连接成一个预测分析程序.3.2 各模块程序设计首先要建立两个类,分别是grammer类和SeqStack类Grammer类中有保存从文本文件读入的LL(1)文法,用一个二维字符数组g保存, 保存非终结符的字符数组VN,保存终结符的字符数组VT,文法开始符号字符变量begin ,元素对应first集合中的有空字符的非终结符数组emptychar,预测分析表为二维整形数组form.SeqStack类主要的作用为在预测分析时作为符号栈.(1)第一模块的设计:对于这个模块的设计,就是用输入流对文本文件中的文法进行读入当读到字符’|’或’/n’时意味着一个产生式已结束,那么相应数组中相应的下标变量+1;数组g[i][0]所存放着这个产生式对应的字符的数量.g[i][1]为这个产生式左边的非终结符.(2)第二模块的设计:在已把文法读入到数组g中后,那么相应的g[i][0]为每个产生式的非终结符,若此非终结符不在数组VN中,那么把此字符加入到VN中对终结符的读入,则是从每个g[i][2]开始扫描,若此字符不在非终结符数组VN中,也不在VT 中,那么就把此字符加入到VT中.(3)第三模块的设计:生成FIRST集合这个算法基本上按照书上的原理,如对每个产生式进行扫描,当扫描到非终结符时,把此字符加入到相应非终结符的FIRST集合中,若遇到非终结符时,需把此非终结符的FIRST集合中除了空字符外全加入到对应的非终结符的first集合中,这就涉及到算法的一个递归算法,我是利用在函数的参数表中设置俩个参数,一个是FIRST数组,另外一个是非终结符,在用到递归时,我是利用把FIRST数组设为本产生式第一个非终结符的FIRST数组,而非终结符参数则设置为在扫描产生式右部过程中所遇到的非终结符.然后通过循环对这个文法中的所有非终结符进行函数的调用,这样来求到所有非终结符的FIRST集合.(4)第四模块的设计:生成FOLLOW集合这个算法,关键就是求某非终结符A的FOLLOW集合,那么就是扫描到A后面的字符,若为终结符,则把此终结符加入到A的FOLLOW集合,那么若为非终结符,则把此非终结符的FIRST集合加入到A的FOLLOW集合中,若A为某个产生式最后一个字符,则把这个产生式的第一个字符的FOLLOW集合加入到A的FOLLOW集合中,在这个算法的过程中叶涉及到运用递归,此递归的方法同样与上述求FIRST集合中运用的递归方法类似(5)第五模块的设计:求预测分析表的过程同样是对每个产生式进行扫描,对每个产生式的FIRST集合中的元素,都把相应的产生式的编号写入到对应的预测分析表中对应的位置(6)第六模块的设计:生成预测分析程序,就是把’#’和文法开始符号进入到栈中,然后把相应的分析语句中当前的输入符号对应,在每一步过程中按照书上讲到的原理,在预测分析表中找到相应的产生式.第四章程序测试附录程序清单class SeqStack;//声明栈类class grammer//定义grammer类,此类的作用把文本文件中的文法保存,并且产生这个文法的非终结符集合,终结符集合,first集合,fellow集合,预测分析表等{public:grammer();~grammer();void openfile(char *);void prepareform();void buildform();void buildProcess(SeqStack& ss);private:char begin;char *vt;char **g;char *vn;char **first;//这时所有非终结符的first集合char **fellow;//这是所有非终结符的fellow集合char *emptychar;//这个集合中的元素为对应first集合中的有空字符的非终结符int **form;//这是对应文法的预测分析表int count;void buildVn();void buildVt();void buildemptychar();void buildfirst();void buildfellow();void fellowzh(char *,char);void firstzh(char *,char);int search(char *,char);void printform();void outputblank(int);};const int stackIncreament=20;class SeqStack//定义SeqStack类,这个类的主要作用是在对语句的预测分析过程中作符号栈{public:friend grammer;SeqStack(int sz=50);~SeqStack();void Push(char x);bool Pop(char& x);bool getTop(char& x);bool IsEmpty();bool IsFull();int getSize();void MakeEmpty();void showPlay();private:char *elements;int top;int maxSize;void overflowProcess();};#include<fstream>#include<iostream>#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<windows.h>#include "编译.h"using namespace std;grammer::grammer(){count=0;}grammer::~grammer(){int i;for(i=0;i<count;i++)delete g[i];delete g;delete vt;delete vn;}void grammer::openfile(char *file)//这个函数的主要功能在于对文本文件中的文法进行读入,并保存在对应的数组中,一并产生对应文法的终结符集合和非终结符集合{char ch;int i,j;ifstream infile(file,ios::in);//定义文件流if(!infile){cout<<"open error!"<<endl;exit(1);}while((ch=infile.get())!=EOF){if(ch=='-'){if((ch=infile.get())=='>'){count++;}else{infile.seekg(-1,ios::cur);}}else if(ch=='|'){count++;}else{}}g=new char *[count];for(i=0;i<count;i++){g[i]=new char [15];g[i][0]=0;}infile.clear();//能重新激活文件流infile.seekg(0,ios::beg);//定位i=0;j=1;while((ch=infile.get())!=EOF){if(ch=='-'){if(infile.get()!='>'){g[i][j]=ch;g[i][0]++;j++;if(ch==EOF)break;elseinfile.seekg(-1,ios::cur);}}else if(ch=='|'){i++;g[i][1]=g[i-1][1];g[i][0]=1;j=2;}else if(ch=='\n'){infile.seekg(-3,ios::cur);ch=infile.get();if(ch!='\n'){i++;j=1;}infile.seekg(2,ios::cur);}else{g[i][j]=ch;g[i][0]++;j++;}}cout<<count<<endl;for(i=0;i<count;i++){for(j=1;j<=g[i][0];j++){cout<<g[i][j]<<" ";}cout<<endl;}buildVn();//建立非终结符集合buildVt();//建立终结符集合}void grammer::buildVn()int i=1,j=0;vn=new char[count+1];vn[i]=g[j++][1];for(;j<count;j++)if(g[j][1]!=g[j-1][1]){i++;vn[i]=g[j][1];}vn[0]=i;begin=vn[1];cout<<"本文法开始符为:"<<begin<<endl;cout<<"本文法非终结符为:"<<" ";for(i=1;i<=vn[0];i++)cout<<vn[i]<<" ";cout<<endl;}void grammer::buildVt(){int i=1,j=0,t;char ch;vt=new char[100];vt[0]=0;for(;j<count;j++){t=2;for(;t<=g[j][0];t++){ch=g[j][t];if(!search(vt,ch)&&!search(vn,ch)){vt[i++]=g[j][t];vt[0]++;}}}cout<<"本文法终结符为:"<<" ";for(i=1;i<=vt[0];i++)cout<<vt[i]<<" ";cout<<endl;}int grammer::search(char *a,char ch)//搜索函数,用于在指定数组中对指定字符进行搜寻,若存在输出对应的序号,若不在则输出0for(int i=1;i<=a[0];i++){if(ch==a[i])return i;}return 0;}void grammer::buildemptychar()//建立对应first集合中含有空字符的的非终结符集合{int i=0,j=2,t=1;bool flag=true,flag1;emptychar=new char[vn[0]+1];emptychar[0]=0;for(;i<count;i++){if(g[i][2]=='@'&&!search(emptychar,g[i][1])){emptychar[t++]=g[i][1];emptychar[0]++;}}while(flag){flag=false;for(i=0;i<count;i++){for(j=2;j<=g[i][0];j++){if(search(emptychar,g[i][j])){flag1=true;}else{flag1=false;break;}}if(flag1==true&&!search(emptychar,g[i][1])){emptychar[t++]=g[i][1];emptychar[0]++;flag=true;}}cout<<"First集中含有空字符的有: ";for(i=1;i<=emptychar[0];i++){cout<<emptychar[i]<<" ";}cout<<endl;}void grammer::buildfirst(){int i;first=new char* [vn[0]];for(i=0;i<vn[0];i++){first[i]=new char[vt[0]+1];}for(i=0;i<vn[0];i++)first[i][0]=0;for(i=1;i<=vn[0];i++){firstzh(first[i-1],vn[i]);}}void grammer::buildfellow(){int i,j;fellow=new char* [vn[0]];for(i=0;i<vn[0];i++){fellow[i]=new char[vt[0]+1];}for(i=0;i<vn[0];i++)fellow[i][0]=0;for(i=1;i<=vn[0];i++){fellowzh(fellow[i-1],vn[i]);}for(i=0;i<vn[0];i++){cout<<vn[i+1]<<"的fellow集合为: ";for(j=1;j<=fellow[i][0];j++){cout<<fellow[i][j]<<" ";cout<<endl;}}void grammer::firstzh(char *a,char ch)//对指定非终结符建立对应的first集合{int i,j,t=1;for(i=0;i<count;i++){for(j=2;j<=g[i][0];j++){if(g[i][1]==ch){if(!search(vn,g[i][j])&&g[i][j]!='@')//找到对应产生式中的终结符时{if(!search(a,g[i][j])){a[t++]=g[i][j];a[0]++;}break;}else if(g[i][j]!='@')//找到对应的产生式中的非终结符时{firstzh(a,g[i][j]);//用递归的方法算出此非终结符的first集合if(!search(emptychar,g[i][j]))//当此非终结符的first集合中无空字符时,对此产生式扫描完毕break;}else{}}elsebreak;}}}void grammer::fellowzh(char *a,char ch)//对指定非终结符建立fellow集合{int i,j,k,m,n,t=a[0];if(ch==begin)//把#字符放入开始符的fellow集合{if(!search(a,'#'))a[++t]='#';a[0]++;}}for(i=0;i<count;i++){for(j=2;j<=g[i][0];j++){if(g[i][j]==ch){for(m=j;m<=g[i][0];m++){if(m==g[i][0]){if(g[i][1]!=ch)fellowzh(a,g[i][1]);//发现要求的非终结符在此产生式的末尾时elsebreak;}else{if(!search(vn,g[i][m+1]))//当此非终结符后面的字符为终结字符时,放入对应的fellow集合{if(!search(a,g[i][m+1])){a[++t]=g[i][m+1];a[0]++;}break;}else{k=search(vn,g[i][m+1]);//把此非终结符后面的非终结符的first集合中的元素放入对应的fellow集合for(n=1;n<=first[k-1][0];n++){if(!search(a,first[k-1][n])){a[++t]=first[k-1][n];a[0]++;}}if(!search(emptychar,g[i][m+1]))break;}}}}}}void grammer::prepareform(){int i,j;buildemptychar();buildfirst();buildfellow();for(i=0;i<vn[0];i++){if(search(emptychar,vn[i+1])){j=first[i][0];first[i][++j]='@';first[i][0]++;}}for(i=0;i<vn[0];i++){cout<<vn[i+1]<<"的first集合为: ";for(j=1;j<=first[i][0];j++){cout<<first[i][j]<<" ";}cout<<endl;}}void grammer::buildform(){int i,j,k,t,m,n;bool flag;form=new int*[vn[0]];for(i=0;i<vn[0];i++)form[i]=new int[vt[0]];for(i=0;i<vn[0];i++){for(j=0;j<vt[0];j++){form[i][j]=-1;}for(i=0;i<count;i++){t=search(vn,g[i][1]);flag=true;for(j=2;j<=g[i][0];j++){k=search(vt,g[i][j]);//若发现这个产生式的first集合中的对应的终结符时if(k){if(g[i][j]!='@'){if(form[t-1][k-1]!=-1){cout<<"本终结符错误!"<<endl;exit(1);}form[t-1][k-1]=i;flag=false;break;}else//若发现对应产生式中的first集合中含有空字符时{for(m=1;m<=fellow[t-1][0];m++){if(fellow[t-1][m]!='#')//可把对应的非终结符的fellow集合中的元素对应的表项中填入该产生式的标号{n=search(vt,fellow[t-1][m]);if(form[t-1][n-1]!=-1){cout<<"有终结符@本fellow集合中非#错误!"<<endl;exit(1);}form[t-1][n-1]=i;}else{if(form[t-1][k-1]!=-1){cout<<"有终结符@本fellow集合中#错误!"<<endl;exit(1);}form[t-1][k-1]=i;}flag=false;break;}}else//找到该产生式中的非终结符时{k=search(vn,g[i][j]);for(m=1;m<=first[k-1][0];m++){if(first[k-1][m]!='@'){n=search(vt,first[k-1][m]);if(form[t-1][n-1]!=-1){cout<<"本first集合中非@!"<<endl;exit(1);}form[t-1][n-1]=i;}else{}}if(!search(first[k-1],'@'))//若在此终结符对应的first集合中无空字符时{flag=false;break;}}}if(flag==true)//说明该产生式对应的first集合中含有空字符{for(m=1;m<=fellow[t-1][0];m++){if(fellow[t-1][m]!='#'){n=search(vt,fellow[t-1][m]);if(form[t-1][n-1]!=-1){cout<<"本fellow集合中非#错误!"<<endl;exit(1);}form[t-1][n-1]=i;}{n=search(vt,'@');if(form[t-1][n-1]!=-1){cout<<"本fellow集合中#错误!"<<endl;exit(1);}form[t-1][n-1]=i;}}}}printform();}void grammer::outputblank(int i){int j;for(j=0;j<i;j++)cout<<" ";}void grammer::printform(){int i,j,k,t,m;cout<<"-----------------------------预测分析表如下所示------------------------------"<<endl;outputblank(6);for(i=1;i<=vt[0];i++){if(vt[i]=='@'){cout<<"#";outputblank(10);}else{cout<<vt[i];outputblank(10);}}cout<<endl;for(i=0;i<vn[0];i++){cout<<" "<<vn[i+1];outputblank(4);{k=form[i][j];if(k==-1){Sleep(500);cout<<"error";outputblank(6);}else{Sleep(1000);t=9-g[k][0];cout<<g[k][1]<<"->";for(m=2;m<=g[k][0];m++){cout<<g[k][m];}outputblank(t);}}cout<<endl;}}void grammer::buildProcess(SeqStack& ss) {char *dia,ch;int i,j,inlen,m,n,index=0,proc=0;bool flag=true,flag1=false;dia=new char[20];cout<<"请输入待分析的字符串"<<endl;cin>>dia;for(i=0,inlen=0;i<20;i++){if(dia[i]!='\0')inlen++;elsebreak;}cout<<"步骤";outputblank(8);cout<<"符号栈";outputblank(15);cout<<"输入串";outputblank(15);cout<<"所用产生式"<<endl;dia[inlen++]='#';ss.Push('#');ss.Push(begin);while(flag){Sleep(1500);cout<<proc;if(proc>=10)outputblank(11);elseoutputblank(12);++proc;ss.showPlay();outputblank(21-ss.getSize());for(j=index;j<inlen;j++)cout<<dia[j];outputblank(21-inlen+index);if(flag1==true){cout<<g[form[m-1][n-1]][1]<<"->";for(j=2;j<=g[form[m-1][n-1]][0];j++)cout<<g[form[m-1][n-1]][j];cout<<endl;}elsecout<<endl;ss.getTop(ch);m=search(vn,ch);if(dia[index]!='#')n=search(vt,dia[index]);elsen=search(vt,'@');if(search(vt,ch))//当栈顶是终结符{if(ch==dia[index])//且此终结符与输入串此时检测的终结符符号相同{index++;ss.Pop(ch);flag1=false;}else{cout<<"该字符串不能由该文法推出"<<endl;exit(1);}}else if(ch=='#'){if(ch==dia[index]){cout<<endl;cout<<"---------------------------------分析完成------------------------------"<<endl;flag=false;}else{cout<<"该字符串不能由该文法推出"<<endl;exit(1);}}else if(form[m-1][n-1]!=-1)//当栈顶的非终结符与输入串对应的终结符在预测分析表中相应的项存在时{if(g[form[m-1][n-1]][2]!='@'){ss.Pop(ch);for(i=g[form[m-1][n-1]][0];i>=2;i--){ss.Push(g[form[m-1][n-1]][i]);}}elsess.Pop(ch);flag1=true;}else{cout<<"该字符串不能由该文法推出"<<endl;exit(1);}}}void SeqStack::overflowProcess(){char *newArray=new char[maxSize+stackIncreament];if(newArray==NULL){cerr<<"存储分配失败!"<<endl;exit(1);}for(int i=0;i<=top;i++)newArray[i]=elements[i];maxSize=maxSize+stackIncreament;delete []elements;elements=newArray;}void SeqStack::Push(char x){if(IsFull()==true)overflowProcess();elements[++top]=x;}bool SeqStack::Pop(char &x){if(IsEmpty()==true)return false;x= elements[top--];return true;}bool SeqStack::getTop(char &x){if(IsEmpty()==true)return false;x=elements[top];return true;}void SeqStack::showPlay(){for(int i=0;i<=top;i++)cout<<elements[i];}SeqStack::SeqStack(int sz):top(-1),maxSize(sz) {elements=new char[maxSize];assert(elements!=NULL);}SeqStack::~SeqStack(){delete []elements;}bool SeqStack::IsEmpty(){return(top==-1)?true:false;}bool SeqStack::IsFull(){return (top==maxSize-1)?true:false;}int SeqStack::getSize(){return top+1;}void SeqStack::MakeEmpty(){top=-1;}#include<iostream>#include"编译.h"using namespace std;void main(){//char ch;grammer ga;SeqStack ss;char filename[20];cout<<"欢迎来到本LL(1)文法预测分析表自动生成程序"<<endl;cout<<endl;cout<<endl;cout<<"请输入文法所在的文件名"<<endl;cin>>filename;ga.openfile(filename);ga.prepareform();ga.buildform();ga.buildProcess(ss);}。
LL（1）⽂法分析表的构造和分析过程⽰例在考完编译原理之后才弄懂，悲哀啊。
不过懂了就好，知识吗，不能局限于考试。
⽂法：E→TE'E'→+TE'|εT→FT 'T'→*FT'|εF→id| (E)⼀、⾸先判断是不是 LL(1)⽂法--------------------------------------------------------------------------------------------------------⽂法G的任意两个具有相同左部的产⽣式 A --> α|β满⾜下列条件：1、如果α和β不能同时推导出ε，则 FIRST（α）∩FIRST(β) = 空2、α和β⾄多有⼀个能推导出ε3、如果β --*--> ε ,则 FIRST（α)∩ FOLLOW（A）＝空--------------------------------------------------------------------------------------------------------对于 E'→+TE'|ε，显然ε --> ε， First(+TE') = {+} ，Follow(E') = {{),#} 显然⼆者交集为空满⾜。
对于 F→id|(E) ，First(id) = {id} First((E)) = {(} 显然⼆者交集为空满⾜。
所以该⽂法是LL(1)⽂法。
⼆、计算出First集和Follow集参考：三、构建LL(1)分析表输⼊：⽂法G输出：分析表M步骤：1、对G中任意⼀个产⽣式 A --> α执⾏第2步和第3步2、for 任意a ∈ First(α)，将 A --> α填⼊M[A,a]3、if ε∈ First(α) then 任意a ∈ Follow(A)，将 A --> α填⼊M[A,a]if ε∈ First(α) & # ∈Follow(A)， then 将 A --> α填⼊M[A,#] （觉得这步没⽤）4、将所有没有定义的M[A,b] 标上出错标志（留空也可以）--------------------------------------------------------------------------------------------------------过程就不赘述了，结果：四、分析过程步骤：1、如果 X = a = # 则分析成功并停机2、如果 X = a != # 则弹出栈顶符号X, 并将输⼊指针移到下⼀个符号上3、如果 X != a，查询分析表M[X,a] , 如果 M[X,a] = {X --> UVW}，则⽤UVW (U在栈顶) 替换栈顶符号 X。
《编译原理》构造LL（1）分析表的步骤-例题解析《编译原理》构造 LL(1) 分析表的步骤 - 例题解析易错点及扩展：1、求每个产⽣式的 SELECT 集2、注意区分是对谁 FIRST 集 FOLLOW 集3、开始符号的 FOLLOW 集包含 #4、各集合对对应的对象以及含义集对象含义FIRST 集是对产⽣式右部右部内部的所有终结符集，可能为εFOLLOW 集是对产⽣式左部（⾮终结符）⾮终结符后⾯紧跟的终结符，可能为 #，和该⾮终结符推导出的右部⽆关（因为LL(1)⽂法不包含递归，所以右部不会再有该⾮终结符，所以不能通过该右部判断该⾮终结符后跟集合）SELECT集是对产⽣式需要考虑产⽣式右部的不同情况，进⼀步确定是根据 FIRST 集还是 FOLLOW 集5、SELECT 集的定义注：注意区分 FIRST 集 FOLLOW 时是对α还是 A给定⽂法 G，对于产⽣式 A→α，α∈ V*，则可选集 SELECT(A→α) 有：（1）若α ≠ ε，且α ≠+> ε，则 SELECT(A→α) = FIRST(α)（2）若α ≠ ε，但α =+> ε，则 SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)（3）若α = ε，则 SELECT(A→α) = FOLLOW(A)描述：第 1 条是，当α ≠ ε，且通过1次或多次推不出ε，SELECT(A→α) = FIRST(α)第 2 条是，当α ≠ ε，但α经有限步可推出ε，SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)（注意是⼀个α，⼀个 A）第 3 条是，当α = ε，SELECT 集就等于左部 A 的 FOLLOW 集解题时，先判断是否为ε，是则⽤第（3）条，否则再判断能否通过1次或多次推出ε，是则⽤第（2）条，否则⽤第（1）条求 FIRST，FOLLOW，SELECT 集详细例题可参考：6、LL(1) 分析表的结构分析表是⼀个⼆维数组 M[A，a]，其中 A 表⽰⾏，是⾮终结符，a 表式列是终结符或 #。
