LL1语法分析程序实验报告40283.pdf
z LL1 实验报告 1.设计原理 所谓 LL1分析法，就是指从左到右扫描输入串源程序，同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应中选择的规则。实现 LL1分析的程序又称为 LL1分析程序或 LL11分析器。我们知道一个文法要能进展 LL1分析，则这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的 FIRST 和 FOLLOW 集合，然后根据 FIRST 和 FOLLOW 集合构造 LL1分析表，最后利用分析表，根据 LL(1)语法分析构造一个分析器。LL1的语法分析程序包含了三个局部，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进展语法分析，该程序是采用了 C+语言来编写，其逻辑构造图如下：LL1预测分析程序的总控程序在任何时候都是按 STACK 栈顶符号*和当前的输入符号 a 做哪种过程的。对于任何*，a，总控程序每次都执行下述三种可能的动作之一：假设*=a=*，则宣布分析成功，停顿分析过程。假设*=a*，则把*从 STACK 栈顶弹出，让 a 指向下一个输入符号。假设*是一个非终结符，则查看预测分析表 M。假设 MA，a中存放着关于*的一个产生式，则，首先把*弹出 STACK 栈顶，然后，把产生式的右部符号串按反序一一弹出 STACK栈假设右部符号为，则不推什么东西进 STACK 栈。假设 MA，a中存放着“出错标志，则调用出错诊断程序 ERROR。事实上，LL1的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在 LL1分析器中，实际上是以 LL1分析表代替相应方法来进展分析的。2.分析 LL(1)分析表是一个二维表，它的表列符号是当前符号，包括文法所有的终结和自定义。的句子完毕符号*，它的表行符号是可能在文法符号栈SYN 中出现的所有符号，包括所有的非终结符，所有出现在产生式右侧且不在首位置的终结符，自定义的句子完毕符号*表项。为当前栈符号与当前符号匹配后，所要求的栈操作和输入操作。表项说明了文法的终结符与非终结符是否可能相遇。其中，栈操作包括两种，一是弹栈;二是z 弹栈后，将符号串 ABc 反转后压栈;输 入 操作 包 括 两 种，一 是 读 入下一符号，是保持当前符号不变。具体的造算法为171。(1)设 A,B 为文法的非终结符，C 为文法的终结符和非终结符组成的字符串，a 为文法的终结符将所 有 产 生式分为四类:6)A-aB，则(A,a)项填写为(B 调向后压栈，读入下一个字符):(ii)A-a;A-a,则将A,a)项填写为(弹栈，读入下一个字符):(iii)A-BC，则将(A,select(A-BC)项全部填写为(将 BC 调向后压栈，保持当前字符不读入):(iv)A-N，则将(A,follow(A)项全部填写为(弹栈，保持当前字符不读)。(2)对表行和表列的所有字符进展循环；(3)如果当前表行的字符是非终结符，它必有产生式，依据此产生式的类型，填写表项。(4)如果当前表列的字符不在此产生式的选择集合中，该项填写为 Eror。(5)对(*，*)项填写为 OK；(6)对当前表行字符为终结符的，只有它与表列字符一样时，才填写为(弹栈，读入下一个字符)，否则填入 Eror。3.流程图 是 是 数据构造*includeiostream.h*include stdio.h*include malloc.h*include conio.h 开场 读入文法 有效.是 LL(1)文法.判断句型 报错 完毕 z struct Lchar char char_ch;struct Lchar*ne*t;Lchar,*p,*h,*temp,*top,*base;char curchar;char curtocmp;int right;int table58=1,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,0,0,0,1,1,0,1,1,1,0,0,1,0,0;int i,j;void push(char pchar)temp=(struct Lchar*)malloc(sizeof(Lchar);temp-char_ch=pchar;temp-ne*t=top;top=temp;void pop(void)curtocmp=top-char_ch;if(top-char_ch!=*)top=top-ne*t;void doforpush(int t)switch(t)case 0:push(A);push(T);break;case 5:push(A);push(T);break;case 11:push(A);push(T);push(+);break;case 20:push(B);push(F);break;case 23:push(B);push(F);break;case 32:push(B);push(F);push(*);break;case 40:push(i);break;case 43:push();push(E);push();void changchartoint()switch(curtocmp)z case A:i=1;break;case B:i=3;break;case E:i=0;break;case T:i=2;break;case F:i=4;switch(curchar)case i:j=0;break;case+:j=1;break;case*:j=2;break;case(:j=3;break;case):j=4;break;case*:j=5;void dosome(void)int t;for(;)pop();curchar=h-char_ch;printf(n%ct%c,curchar,curtocmp);if(curtocmp=*&curchar=*)break;if(curtocmp=A|curtocmp=B|curtocmp=E|curtocmp=T|curtocmp=F)if(curtocmp!=*)changchartoint();if(tableij)t=10*i+j;doforpush(t);continue;else right=0;break;else z if(curtocmp!=curchar)right=0;break;else break;else if(curtocmp!=curchar)right=0;break;else h=h-ne*t;continue;void main(void)char ch;cout*文件名称:语法分析endl;cout endl;cout/*程序相关说明*/endl;cout-endl;cout-/*A=E B=T*/endl;cout-*目 的:对输入 LL(1)文法字符串，本程序能自动判断所给字符串是 -endl;cout-*否 为 所 给 文 法 的 句 子，并 能 给 出 分 析 过 程。-endl;cout-*-endl;cout表达式文法为：endl;coutE+T|Tendl;coutT*F|Fendl;cout(E)|iendl;cout请在下行输入要分析的串(*号完毕)：ne*t=NULL;base-char_ch=*;temp=(struct Lchar*)malloc(sizeof(Lchar);temp-ne*t=base;temp-char_ch=E;top=temp;h=(struct Lchar*)malloc(sizeof(Lchar);h-ne*t=NULL;p=h;do ch=getch();putch(ch);if(ch=i|ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=*)temp=(struct Lchar*)malloc(sizeof(Lchar);temp-ne*t=NULL;temp-char_ch=ch;h-ne*t=temp;h=h-ne*t;else temp=p-ne*t;printf(nInput a wrong char!Input again:n);for(;)if(temp!=NULL)printf(%c,temp-char_ch);else break;temp=temp-ne*t;while(ch!=*);p=p-ne*t;h=p;dosome();if(right)printf(n 成功!n);else printf(n 错误!n);getch();z 截图：
