语法分析程序

LL1实验报告1.设计原理所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。

实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。

我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。

当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW 集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。

LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C++语言来编写，其逻辑结构图如下：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。

事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。

2.分析LL ( 1) 分析表是一个二维表，它的表列符号是当前符号，包括文法所有的终结和自定义。

的句子结束符号#，它的表行符号是可能在文法符号栈SYN中出现的所有符号，包括所有的非终结符，所有出现在产生式右侧且不在首位置的终结符，自定义的句子结束符号#表项。

语法分析程序#include <stdio.h>#include <stdlib.h>#include <string.h>char prog[100],ch,token[8];int p=0,syn,n,i;char *keyword[6]={"begin","then","if","while","do","end"};void scaner();void Irparse();void statement();void expression_r();void term();void factor();void main(){int select=-1;p=0;printf("please input sentence, end of '#' !\n");do{ch=getchar();prog[p++]=ch;}while(ch!='#');p=0;printf("请输⼊1 或 2 \n 1.词法分析\n 2.语法分析\n");scanf("%d",&select);if(select==1){do{scaner();switch(syn){case -1:printf("词法分析出错\n");break;default :printf("<%d,%s>\n",syn,token);break;}}while(syn!=0);printf("词法分析成功\n");}else if(select==2){scaner();if(syn==1){Irparse();}//beginelse{printf("语法分析出错! 请检查begin关键字\n");return;}if(syn==6)//end{scaner();if(syn==0){printf("恭喜语法分析成功\n");}else{printf("语法分析出错! 请检查是否缺少'#'\n");}}else{printf("语法分析出错! 请检查是否缺少'end'\n");}}getchar();}void scaner(){for(n=0;n<8;n++){token[n]='\0';}n=0;ch=prog[p++];while(ch==''){ch=prog[p++];}if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){do{token[n++]=ch;ch=prog[p++];}while((ch>='a'&&ch<='z')||(ch>='a'&&ch<='z')||(ch>='0'&&ch<='9'));syn=10;for(n=0;n<6;n++){if(strcmp(token,keyword[n])==0){syn=n+1;}}p--;//return;}else if(ch>='0'&&ch<='9'){p--;do{token[n++]=prog[p++];ch=prog[p];}while(ch>='0'&&ch<='9');syn=11;return;}else{//ch=prog[p++];switch(ch){case'+':syn=13;token[0]=ch;break;case'-':syn=14;token[0]=ch;break;case'*':syn=15;token[0]=ch;break;case'/':syn=16;token[0]=ch;break;case':':syn=17;token[0]=ch;ch=prog[p++];if(ch=='='){token[1]=ch;syn++;}else p--;break;case'<':syn=20;token[0]=ch;ch=prog[p++];if(ch=='>'){token[1]=ch;syn++;}else if(ch=='='){token[1]=ch;syn=syn+2;}else p--;break;case'>':syn=23;token[0]=ch;ch=prog[p++];if(ch=='='){token[1]=ch;syn++;}else p--;break;case'=':syn=25;token[0]=ch;break;case';':syn=26;token[0]=ch;break;case'(':syn=27;token[0]=ch;break;case')':syn=28;token[0]=ch;break;case'#':syn=0;token[0]=ch;break;default: printf("词法分析出错! 请检查是否输⼊⾮法字符\n");syn=-1;break; }//return;}}void Irparse(){scaner();statement();while(syn==26)//;{scaner();statement();}}void statement(){if(syn==10){scaner();if(syn==18){scaner();expression_r();}else{printf("语法分析出错! 请检查表达式是否正确\n");return;}}else{printf("语法分析出错! 请检查语句是否正确\n");return;}}void expression_r(){term();while(syn==13||syn==14)//+ -{scaner();term();}}void term(){factor();while(syn==15||syn==16)//* /{scaner();factor();}}void factor(){if(syn==10||syn==11){scaner();}else if(syn==27){scaner();expression_r();if(syn==28){scaner();}else {printf("语法分析出错! 请检查是否缺少')'\n");return;}}else {printf("语法分析出错! 请检查是否输⼊⾮法字符\n");return;} }。

编译原理实验实验二语法分析器实验二：语法分析实验一、实验目的根据给出的文法编制LR（1）分析程序，以便对任意输入的符号串进行分析。

本次实验的目的主要是加深对LR（1）分析法的理解。

二、实验预习提示1、LR（1）分析法的功能LR（1）分析法的功能是利用LR（1）分析表，对输入符号串自下而上的分析过程。

2、LR（1）分析表的构造及分析过程。

三、实验内容对已给语言文法，构造LR(1)分析表，编制语法分析程序，要求将错误信息输出到语法错误文件中，并输出分析句子的过程（显示栈的内容）；实验报告必须包括设计的思路，以及测试报告（输入测试例子，输出结果）。

语法分析器一、功能描述：语法分析器，顾名思义是用来分析语法的。

程序对给定源代码先进行词法分析，再根据给定文法，判断正确性。

此次所写程序是以词法分析器为基础编写的，由于代码量的关系，我们只考虑以下输入为合法：数字自定义变量+ * （）$作为句尾结束符。

其它符号都判定为非法。

二、程序结构描述：词法分析器：class wordtree；类，内容为字典树的创建，插入和搜索。

char gettype(char ch)：类型处理代入字串首字母ch，分析字串类型后完整读入字串，输出分析结果。

因读取过程会多读入一个字母，所以函数返回该字母进行下一次分析。

bool isnumber(char str[])：判断是否数字代入完整“数字串”str,判断是否合法数字，若为真返回1，否则返回0。

bool isoperator(char str[])：判断是否关键字代入完整“关键字串”str,搜索字典树判断是否存在，若为存在返回1，否则返回0。

语法分析器：int action(int a,char b)：代入当前状态和待插入字符，查找转移状态或归约。

node2 go(int a)：代入当前状态，返回归约结果和长度。

void printstack()：打印栈。

int push(char b)：将符号b插入栈中，并进行归约。

编译原理实验词法分析程序实验一：词法分析程序1、实验目的从左至右逐个字符的对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成单词符号形式的中间程序。

2、实验内容表C语言子集的单词符号及内码值单词符号种别编码助记符内码值while 1 while --if 2 if --else 3 else --switch 4 switch --case 5 case --标识符 6 id id在符号表中的位置常数7 num num在常数表中的位置+ 8 + --- 9 - --* 10 * --<= 11 relop LE< 11 relop LT== 11 relop LQ= 12 = --; 13 ; --输入源程序如下if a==1 a=a+1;else a=a+2;输出对应的单词符号形式的中间程序3、实验过程实验上机程序如下：#include "stdio.h"#include "string.h"int i,j,k;char s ,a[20],token[20];int letter(){if((s>=97)&&(s<=122))return 1;else return 0;}int Digit(){if((s>=48)&&(s<=57))return 1;else return 0;}void get(){s=a[i];i=i+1;}void retract(){i=i-1;}int lookup(){if(strcmp(token, "while")==0)return 1;else if(strcmp(token, "if")==0)return 2;else if(strcmp(token,"else")==0)return 3;else if(strcmp(token,"switch")==0)return 4;else if(strcmp(token,"case")==0)return 5;else return 0;}void main(){printf("please input you source program,end('#'):\n");i=0;do{i=i+1;scanf("%c",&a[i]);}while(a[i]!='#');i=1;memset(token,0,sizeof(char)*10);j=0;get();while(s!='#'){if(s==' '||s==10||s==13)get();else{switch(s){case'a':case'b':case'c':case'd':case'e':case'f':case'g':case'h':case'i':case'j':case'k':case'l':case'm':case'n':case'o':case'p':case'q':case'r':case's':case't':case'u':case'v':case'w':case'x':case'y':case'z':while(Digit()||letter()){token[j]=s;j=j+1;get();}retract();k=lookup();if(k==0)printf("(6,%s)\n",token); elseprintf("(%d,null)\n",k); break;case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':while(Digit()){token[j]=s;j=j+1;get();}retract();printf("(%d,%s)\n",7,token); break;case'+':printf("(+,null)\n"); break;case'-':printf("(-,null)\n"); break;case'*':printf("(*,null)\n"); break;case'<':get();if(s=='=')printf("(relop,LE)\n"); else{retract();printf("(relop,LT)\n");}break;case'=':get();if(s=='=')printf("(relop,EQ)\n"); else{retract();printf("(=,null)\n");}break;case';':printf("(;,null)\n"); break;default:printf("(%c,error)\n",s);break;}memset(token,0,sizeof(char)*10);j=0;get();}}}4、实验结果实验结果分析：if是关键字，对应种别编码为2，输出（2，null）a是标识符，对应种别编码为6，值为a，输出（6，a）==的助记符是relop，内码值为LE，输出（relop，LE）1是常数，对应种别编码为7，值为1，输出（7，1）a是标识符，对应种别编码为6，值为a，输出（6，a）=是赋值符号，直接输出，（=，null）a是标识符，对应种别编码为6，值为a，输出（6，a）+是运算符，直接输出（=，null）1是常数，对应种别编码为7，值为1，输出（7，1）；是语句结束符号，直接输出（；，null）else是关键字，对应种别编码为3，输出（3，null）a是标识符，对应种别编码为6，值为a，输出（6，a）=是赋值符号，直接输出，（=，null）a是标识符，对应种别编码为6，值为a，输出（6，a）+是运算符，直接输出（=，null）2是常数，对应种别编码为7，值为2，输出（7，2）；是语句结束符号，直接输出（；，null）#是输入结束标志编译原理实验语法分析程序实验二：语法分析程序1、实验目的：将单词组成各类语法单位，讨论给类语法的形成规则，判断源程序是否符合语法规则3、实验内容：给定文法：G[E]:E→E+E|E-E|E*E|E/E|(E)E→0|1|2|3|4|5|6|7|8|9首先把G[E]构造为算符优先文法，即：G’[E]:E→E+T|TT→T-F|FF→F*G|GG→G/H|HH→(E)|i得到优先关系表如下：+ - * / i ( ) # + ·><·<·<·<·<··>·> - ·>·><·<·<·<··>·> * ·>·>·><·<·<··>·> / ·>·>·>·><·<··>·>i ·>·>·>·>·>·>( <·<·<·<·<·<·=) ·>·>·>·>·>·> # <·<·<·<·<·<·=构造出优先函数+ - * / i ( ) #f 6 8 10 12 12 2 12 2g 5 7 9 11 13 13 2 2要求输入算术表达式：（1+2）*3+2*（1+2）-4/2输出其对应的语法分析结果4、实验过程：上机程序如下：#include "stdio.h"#include "string.h"char a[20],optr[10],s,op;int i,j,k,opnd[10],x1,x2,x3;int operand(char s){if((s>=48)&&(s<=57))return 1;else return 0;}int f(char s){switch(s){case'+':return 6;case'-':return 8;case'*':return 10;case'/':return 12;case'(':return 2;case')':return 12;case'#':return 2;default:printf("error");}}int g(char s){switch(s){case'+':return 5;case'-':return 7;case'*':return 9;case'/':return 11;case'(':return 13;case')':return 2;case'#':return 2;default:printf("error");}}void get(){s=a[i];i=i+1;}void main(){printf("请输入算数表达式，并以‘#’结束:\n");i=0;do{scanf("%c",&a[i]);i++;}while(a[i-1]!='#');i=0;j=0;k=0;optr[j]='#';get();while((optr[j]!='#')||(s!='#')){if(operand(s)){opnd[k]=s-48;k=k+1;get();}else if(f(optr[j])<g(s)){j=j+1;optr[j]=s;get();}else if(f(optr[j])==g(s)){if(optr[j]=='('&&s==')'){j=j-1;get();}else if(optr[j]=='('&&s=='#'){printf("error\n");break;}else if(optr[j]=='#'&&s==')'){printf("error\n");break;}}else if(f(optr[j])>g(s)){op=optr[j];j=j-1;x2=opnd[k-1];x1=opnd[k-2];k=k-2;switch(op){case'+':x3=x1+x2;break;case'-':x3=x1-x2;break;case'*':x3=x1*x2;break;case'/':x3=x1/x2;break;}opnd[k]=x3;k=k+1;printf("(%c,%d,%d,%d)\n",op,x1,x2,x3);}else{printf("error\n");break;}}if(j!=0||k!=1)printf("error\n");}5、实验结果：实验结果分析：（1+2）*3+2*（1+2）-4/2#因为‘）’优先级大于‘*’，先计算1+2=3，并输出（+，1，2，3）原式变为：3*3+2*（1+2）-4/2#因为‘*’优先级大于‘+’，先计算3*3=9，并输出（*，3，3，9）原式变为：9+2*（1+2）-4/2#因为‘）’优先级大于‘-’，先计算1+2=3，并输出（+，1，2，3）原式变为：9+2*3-4/2#因为‘*’优先级大于‘-’，先计算2*3=6，并输出（*，2，3，6）原式变为：9+6-4/2#因为‘/’优先级大于‘#’，先计算4/2=2，并输出（/，4，2，2）原式变为：9+6-2#因为‘-’优先级大于‘#’，先计算6-2=4，并输出（-，6，2，4）原式变为：9+4#因为‘+’优先级大于‘#’，计算9+4=13，并输出（+，9，4，13）原式变为13#优先级等于#，跳出while循环，运算结束！。

内容：考虑以下的文法G[lexp]：lexp →NUMBER| ( op lexp-seq )op →+ | - | *lexp -seq →lexp-seq lexp|lexp注：该文法表达的是简单整型算术表达式，即在op符号后边应当有两个参数，但是该文法可以后跟1个或多个参数，此处我认为不是很合理，所以在处理的时候默认是以两个参数来分析的。

1.首先G[lexp]是间接递归的，所以应当将其转化为直接递归的文法结构：lexp →( op lexp lexp ) | NUMBERop →+ | - | *2.我在实现语法分析的时候，自己创建了一个类MyTree，其属性包含：opType ——用来表示该树的类型：+ 表示是加法运算- 表示是减法运算* 表示是乘法运算# 自己定义的类型，表示该树为叶子节点value ——用来记录该树的值：#型叶子节点直接给出来其余三种节点说明是复合结构，须有其左右节点算出来lv ——用来记录左操作数是否已经被叶子节点替换，true表示已经是叶子节点rv ——用来记录右操作数是否已经被叶子节点替换，true表示已经是叶子节点lexp1 ——用来连接左操作数的树lexp2 ——用来连接右操作数的树3.实现递归调用的思想：在试验中，我利用了一个容器vector来保存当前未处理完（“未处理完”指的是其value不能直接给出，即左右节点均没有用叶子节点替换）的树。

A．每当一个“（”读入后，根据文法可知其后必为一个复合的树来表达的操作数，那么在此时调用addNode函数来创建一个新的待处理的树；B．每当一个数字读入后，需将其联结至最近的那棵树的左或者右节点上去，而最近的那棵未处理完的树就是当前容器nodes中最后那棵树，使用it来指出其位置，添加一个#型的叶子节点；C．每当一个“）”读入后，根据文法可知，必然是最近的那棵树树已经可以求出其值，那么需要将其替换为一个#型的叶子节点并连接至其父亲节点，其父亲节点刚好是容器nodes倒数第二个节点。

词法分析一、实验目的二、设计、编制并调试一个词法分析程序, 加深对词法分析原理的理解。

三、实验要求2.1 待分析的简单的词法（1）关键字:begin if then while do end所有的关键字都是小写。

（2）运算符和界符: = + - * / < <= <> > >= = ; ( ) #（3）其他单词是标识符（ID）和整型常数（SUM）, 通过以下正规式定义：ID = letter (letter | digit)*NUM = digit digit*（4）空格有空白、制表符和换行符组成。

空格一般用来分隔ID.SUM、运算符、界符和关键字, 词法分析阶段通常被忽略。

2.2 各种单词符号对应的种别码:输入: 所给文法的源程序字符串。

输出: 二元组（syn,token或sum）构成的序列。

其中: syn为单词种别码；token为存放的单词自身字符串；sum为整型常数。

例如: 对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件, 经过词法分析后输出如下序列:(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)……三、词法分析程序的算法思想:算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号, 其基本思想是根据扫描到单词符号的第一个字符的种类, 拼出相应的单词符号。

3.1 主程序示意图:主程序示意图如图3-1所示。

其中初始包括以下两个方面:⑴关键字表的初值。

关键字作为特殊标识符处理, 把它们预先安排在一张表格中（称为关键字表）, 当扫描程序识别出标识符时, 查关键字表。

如能查到匹配的单词, 则该单词为关键字, 否则为一般标识符。

关键字表为一个字符串数组, 其描述如下:Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,};图3-1（2）程序中需要用到的主要变量为syn,token和sum3.2 扫描子程序的算法思想:首先设置3个变量: ①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn 用来存放单词符号的种别码。

编译程序的⼯作过程：词法分析、语法分析、语义分析、优化、
⽬标代码⽣成
词法分析：也就是从左到右⼀个⼀个地读⼊源程序，识别⼀个单词或符号，并进⾏归类。

语法分析：在词法分析的基础上，将单词序列分解成各类语法短语，如“程序”语句“表达式”等
语义分析：审查源程序是否有语义的错误，当不符合语⾔规范的时候，程序就会报错。

代码优化：这个阶段是对前阶段的中间代码进⾏变换或改造，⽬的是使⽣成的⽬标代码更为⾼效，即节省时间和空间。

⽬标代码⽣成：也就是吧优化后的中间代码变换成指令代码或汇编代码。

编写一个语法分析程序，对于给定的输入串，能够判断识别该串是否为给定文法的句型。

要求：1．从键盘读入输入串，并判断正误；2．若无误，由程序自动构造FIRST、FOLLOW集以及SELECT集合，判断是否为LL（1）文法；3．若符合LL（1）文法，由程序自动构造LL（1）分析表；4．由算法判断输入符号串是否为该文法的句型。

（可参考教材96页的例题1）#include "stdio.h"#include "stdlib.h"#define MaxRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 20#define MaxPLength 20#define MaxStLength 50struct pRNode{int rCursor;struct pRNode *next;};struct pNode{int lCursor;int rLength;struct pRNode *rHead;};char Vn[MaxVnNum + 1];int vnNum;char Vt[MaxVtNum + 1];int vtNum;struct pNode P[MaxRuleNum];int PNum;char buffer[MaxPLength + 1];char ch;char st[MaxStLength];struct collectNode{int nVt;struct collectNode *next;};struct collectNode* first[MaxVnNum + 1];struct collectNode* follow[MaxVnNum + 1];int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1];int analyseStack[MaxStackDepth + 1];int topAnalyse;int IndexCh(char ch);void InputVt();void InputVn();void ShowChArray(char* collect, int num); void InputP();bool CheckP(char * st);void First(int U);void AddFirst(int U, int nCh);bool HaveEmpty(int nVn);void Follow(int V);void AddFollow(int V, int nCh, int kind);void ShowCollect(struct collectNode **collect); void FirstFollow();void CreateAT();void ShowAT();void Identify(char *st);void InitStack();void ShowStack();void Pop();void Push(int r);void Init();int SE[10][10];int SEC[10][10];int select()//求解SELECT集并输出，{printf("\n");int i,j,b=0,c=20;for(i = 0; i < vnNum; i++){for(j = 0; j <= vtNum; j++){b=0;if(analyseTable[i][j]!=-1){while(SE[analyseTable[i][j]][b]!=20)b++;SE[(analyseTable[i][j])][b]=j;}}printf("所得select为:\n");for(i = 0; i < 10; i++){printf("R(%d) :", i);for(j = 0; j <= vtNum; j++){if(SE[i][0]==20&&c==20&&SE[i+1][0]!=20) {if(Vt[SE[i][j]]=='\0'){printf("%c ",Vt[SE[i+1][j]]);c=i;}}if(SE[i][j]!=20){printf("%c ",Vt[SE[i][j]]);}}printf("\n");if(SE[i+1][0]==20)break;}return c;}int check(int s)//判断是否是LL(1)文法{printf("\n");int a=1;printf("判断是否是LL(1)文法\n");if(s==20)printf("是LL(1)文法\n\n");else{printf("不是LL(1)文法：");printf("R(%d),R(%d)冲突\n\n",s,s+1);a=0;}return a;}int main(void)int i,j,k,m;for(i=0;i<10;i++)for(j=0;j<10;j++){SE[i][j]=20;SEC[i][j]=20;}char todo,ch;Init();InputVn();InputVt();InputP();getchar();FirstFollow();printf("\n所得first集为："); ShowCollect(first);printf("\n所得follow集为："); ShowCollect(follow);CreateAT();k=select();m=check(k);if(!m)return 0;ShowAT();todo = 'y';while('y' == todo){printf("\n是否继续进行句型分析？(y / n):"); todo = getchar();while('y' != todo && 'n' != todo){printf("\n(y / n)? ");todo = getchar();}if('y' == todo){int i;InitStack();printf("请输入符号串(以#结束) : ");ch = getchar();i = 0;while('#' != ch && i < MaxStLength){if(' ' != ch && '\n' != ch){st[i++] = ch;}ch = getchar();}if('#' == ch && i < MaxStLength) {st[i] = ch;Identify(st);}elseprintf("输入出错！\n");}}getchar();return 1;}void Init(){int i,j;vnNum = 0;vtNum = 0;PNum = 0;for(i = 0; i <= MaxVnNum; i++) Vn[i] = '\0';for(i = 0; i <= MaxVtNum; i++) Vt[i] = '\0';for(i = 0; i < MaxRuleNum; i++) {P[i].lCursor = NULL;P[i].rHead = NULL;P[i].rLength = 0;}PNum = 0;for(i = 0; i <= MaxPLength; i++) buffer[i] = '\0';for(i = 0; i < MaxVnNum; i++) {first[i] = NULL;follow[i] = NULL;}for(i = 0; i <= MaxVnNum; i++) {for(j = 0; j <= MaxVnNum + 1; j++)analyseTable[i][j] = -1;}}int IndexCh(char ch){int n;n = 0;while(ch != Vn[n] && '\0' != Vn[n])n++;if('\0' != Vn[n])return 100 + n;n = 0;while(ch != Vt[n] && '\0' != Vt[n])n++;if('\0' != Vt[n])return n;return -1;}void ShowChArray(char* collect){int k = 0;while('\0' != collect[k]){printf(" %c ", collect[k++]);}printf("\n");}void InputVn(){int inErr = 1;int n,k;char ch;while(inErr){printf("\n请输入所有的非终结符，注意："); printf("请将开始符放在第一位，并以#号结束:\n"); ch = ' ';n = 0;while(n < MaxVnNum)Vn[n++] = '\0';}n = 0;while(('#' != ch) && (n < MaxVnNum)){if(' ' != ch && '\n' != ch && -1 == IndexCh(ch)) {Vn[n++] = ch;vnNum++;}ch = getchar();}Vn[n] = '#';k = n;if('#' != ch){if( '#' != (ch = getchar())){while('#' != (ch = getchar()));printf("\n符号数目超过限制！\n");inErr = 1;continue;}}Vn[k] = '\0';ShowChArray(Vn);ch = ' ';while('y' != ch && 'n' != ch){if('\n' != ch){printf("输入正确确认?(y/n):");}scanf("%c", &ch);}if('n' == ch){printf("录入错误重新输入！\n");inErr = 1;}elseinErr = 0;}}}void InputVt(){int inErr = 1;int n,k;char ch;while(inErr){printf("\n请输入所有的终结符，注意："); printf("以#号结束:\n");ch = ' ';n = 0;while(n < MaxVtNum){Vt[n++] = '\0';}n = 0;while(('#' != ch) && (n < MaxVtNum)){if(' '!= ch && '\n' != ch && -1 == IndexCh(ch)) {Vt[n++] = ch;vtNum++;}ch = getchar();}Vt[n] = '#';k = n;if('#' != ch){if( '#' != (ch = getchar())){while('#' != (ch = getchar()))printf("\n符号数目超过限制！\n");inErr = 1;continue;}}Vt[k] = '\0';ShowChArray(Vt);ch =' ';while('y' != ch && 'n' != ch){if('\n' != ch){printf("输入正确确认?(y/n):");}scanf("%c", &ch);}if('n' == ch){printf("录入错误重新输入！\n");inErr = 1;}else{inErr = 0;}}}void InputP(){char ch;int i = 0, n,num;printf("请输入文法产生式的个数：");scanf("%d", &num);PNum = num;getchar();printf("\n请输入文法的%d个产生式,并以回车分隔每个产生式：", num); printf("\n");while(i < num){printf("第%d个：", i);for(n =0; n < MaxPLength; n++)buffer[n] = '\0';ch = ' ';n = 0;while('\n' != (ch = getchar()) && n < MaxPLength)if(' ' != ch)buffer[n++] = ch;}buffer[n] = '\0';if(CheckP(buffer)){pRNode *pt, *qt;P[i].lCursor = IndexCh(buffer[0]);pt = (pRNode*)malloc(sizeof(pRNode));pt->rCursor = IndexCh(buffer[3]);pt->next = NULL;P[i].rHead = pt;n = 4;while('\0' != buffer[n]){qt = (pRNode*)malloc(sizeof(pRNode));qt->rCursor = IndexCh(buffer[n]);qt->next = NULL;pt->next = qt;pt = qt;n++;}P[i].rLength = n - 3;i++;}elseprintf("输入符号含非法在成分，请重新输入！\n"); }}bool CheckP(char * st){int n;if(100 > IndexCh(st[0]))return false;if('-' != st[1])return false;if('>' != st[2])return false;for(n = 3; '\0' != st[n]; n ++){if(-1 == IndexCh(st[n]))return false;}return true;}void First(int U){int i,j;for(i = 0; i < PNum; i++){if(P[i].lCursor == U){struct pRNode* pt;pt = P[i].rHead;j = 0;while(j < P[i].rLength){if(100 > pt->rCursor){AddFirst(U, pt->rCursor); break;}else{if(NULL == first[pt->rCursor - 100]) {First(pt->rCursor);}AddFirst(U, pt->rCursor);if(!HaveEmpty(pt->rCursor)){break;}else{pt = pt->next;}}j++;}if(j >= P[i].rLength)AddFirst(U, -1);}}}void AddFirst(int U, int nCh){struct collectNode *pt, *qt;int ch;pt = NULL;qt = NULL;if(nCh < 100){pt = first[U - 100];while(NULL != pt){if(pt->nVt == nCh)break;else{qt = pt;pt = pt->next;}}if(NULL == pt){pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh;pt->next = NULL;if(NULL == first[U - 100]){first[U - 100] = pt;}else{qt->next = pt;}pt = pt->next;}}else{pt = first[nCh - 100];while(NULL != pt){ch = pt->nVt;if(-1 != ch){AddFirst(U, ch);}pt = pt->next;}}}bool HaveEmpty(int nVn){if(nVn < 100)return false;struct collectNode *pt;pt = first[nVn - 100];while(NULL != pt){if(-1 == pt->nVt)return true;pt = pt->next;}return false;}void Follow(int V){int i;struct pRNode *pt ;if(100 == V)AddFollow(V, -1, 0 );for(i = 0; i < PNum; i++){pt = P[i].rHead;while(NULL != pt && pt->rCursor != V)pt = pt->next;if(NULL != pt){pt = pt->next;if(NULL == pt){if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V)Follow(P[i].lCursor);}AddFollow(V, P[i].lCursor, 0);}else{while(NULL != pt && HaveEmpty(pt->rCursor)){AddFollow(V, pt->rCursor, 1);pt = pt->next;}if(NULL == pt){if(NULL == follow[P[i].lCursor - 100] && P[i].lCursor != V) {Follow(P[i].lCursor);}AddFollow(V, P[i].lCursor, 0);}else{AddFollow(V, pt->rCursor, 1);}}}}}void AddFollow(int V, int nCh, int kind){struct collectNode *pt, *qt;int ch;pt = NULL;qt = NULL;if(nCh < 100){pt = follow[V - 100];while(NULL != pt){if(pt->nVt == nCh)break;elseqt = pt;pt = pt->next;}}if(NULL == pt){pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh;pt->next = NULL;if(NULL == follow[V - 100]){follow[V - 100] = pt;}else{qt->next = pt;}pt = pt->next;}}else{if(0 == kind){pt = follow[nCh - 100];while(NULL != pt){ch = pt->nVt;AddFollow(V, ch, 0);pt = pt->next;}}else{pt = first[nCh - 100];while(NULL != pt){ch = pt->nVt;if(-1 != ch){AddFollow(V, ch, 1);}pt = pt->next;}}}void ShowCollect(struct collectNode **collect) {int i;struct collectNode *pt;i = 0;while(NULL != collect[i]){pt = collect[i];printf("\n%c:\t", Vn[i]);while(NULL != pt){if(-1 != pt->nVt){printf(" %c", Vt[pt->nVt]);}elseprintf(" #");pt = pt->next;}i++;}printf("\n");}void FirstFollow(){int i;i = 0;while('\0' != Vn[i]){if(NULL == first[i])First(100 + i);i++;}i = 0;while('\0' != Vn[i]){if(NULL == follow[i])Follow(100 + i);}}//构造预测分析表,例：U::xyz=============*/ void CreateAT(){int i;struct pRNode *pt;struct collectNode *ct;for(i = 0; i < PNum; i++){pt = P[i].rHead;while(NULL != pt && HaveEmpty(pt->rCursor)) {ct = first[pt->rCursor - 100];while(NULL != ct){if(-1 != ct->nVt)analyseTable[P[i].lCursor - 100][ct->nVt] = i;ct = ct->next;}pt = pt->next;}if(NULL == pt){ct = follow[P[i].lCursor - 100];while(NULL != ct){if(-1 != ct->nVt)analyseTable[P[i].lCursor - 100][ct->nVt] = i; elseanalyseTable[P[i].lCursor - 100][vtNum] = i;ct = ct->next;}}else{if(100 <= pt->rCursor){ct = first[pt->rCursor - 100];while(NULL != ct){analyseTable[P[i].lCursor - 100][ct->nVt] = i;ct = ct->next;}else{if(-1 == pt->rCursor){ct = follow[P[i].lCursor - 100];while(NULL != ct){if(-1 != ct->nVt)analyseTable[P[i].lCursor - 100][ct->nVt] = i; elseanalyseTable[P[i].lCursor - 100][vtNum] = i;ct = ct->next;}}else{analyseTable[P[i].lCursor - 100][pt->rCursor] = i; }}}}}void ShowAT(){int i,j;printf("构造预测分析表如下：\n");printf("\t|\t");for(i = 0; i < vtNum; i++){printf("%c\t", Vt[i]);}printf("#\t\n");printf("- - -\t|- - -\t");for(i = 0; i <= vtNum; i++)printf("- - -\t");printf("\n");for(i = 0; i < vnNum; i++){printf("%c\t|\t", Vn[i]);for(j = 0; j <= vtNum; j++){if(-1 != analyseTable[i][j])printf("R(%d)\t", analyseTable[i][j]);elseprintf("error\t");}printf("\n");}}void Identify(char *st){int current,step,r;printf("\n%s的分析过程：\n", st);printf("步骤\t分析符号栈\t当前指示字符\t使用产生式序号\n");step = 0;current = 0;printf("%d\t",step);ShowStack();printf("\t\t%c\t\t- -\n", st[current]);while('#' != st[current]){if(100 > analyseStack[topAnalyse]){if(analyseStack[topAnalyse] == IndexCh(st[current])){Pop();current++;step++;printf("%d\t", step);ShowStack();printf("\t\t%c\t\t出栈、后移\n", st[current]);}else{printf("%c-%c不匹配！", analyseStack[topAnalyse], st[current]); printf("此串不是此文法的句子！\n");return;}}else{r = analyseTable[analyseStack[topAnalyse] - 100][IndexCh(st[current])];if(-1 != r){Push(r);step++;printf("%d\t", step);ShowStack();printf("\t\t%c\t\t%d\n", st[current], r);}else{printf("无可用产生式，此串不是此文法的句子！\n"); return;}}}if('#' == st[current]){if(0 == topAnalyse && '#' == st[current]){step++;printf("%d\t", step);ShowStack();printf("\t\t%c\t\t分析成功！\n", st[current]);printf("%s是给定文法的句子！\n", st);}else{ while(topAnalyse > 0){ if(100 > analyseStack[topAnalyse]){ printf("无可用产生式，此串不是此文法的句子！\n"); return;}else{ r = analyseTable[analyseStack[topAnalyse] - 100][vtNum]; if(-1 != r){ Push(r);step++;printf("%d\t", step);ShowStack();if(0 == topAnalyse && '#' == st[current]){ printf("\t\t%c\t\t分析成功！\n", st[current]);printf("%s是给定文法的句子！\n", st);}elseprintf("\t\t%c\t\t%d\n", st[current], r); }else{ printf("无可用产生式，此串不是此文法的句子！\n"); return; }}}}}}void InitStack(){ int i;for(i = 0; i < MaxStLength; i++)st[i] = '\0';analyseStack[0] = -1;analyseStack[1] = 100;topAnalyse = 1;}void ShowStack(){ int i;for(i = 0; i <= topAnalyse; i++){ if(100 <= analyseStack[i])printf("%c", Vn[analyseStack[i] - 100]);else{ if(-1 != analyseStack[i])printf("%c", Vt[analyseStack[i]]);elseprintf("#");}}}void Pop(){ topAnalyse--;}void Push(int r){ int i;struct pRNode *pt;Pop();pt = P[r].rHead;if(-1 == pt->rCursor)return;topAnalyse += P[r].rLength;for(i = 0; i < P[r].rLength; i++){analyseStack[topAnalyse - i] = pt->rCursor; pt = pt->next;}}测试：LL(1)S H M A #ya b d e #y7S->aHH->aMdH->dM->AbM->A->aMA->e非LL(1)S #ya b #y3S->aSbS->aSS->。

实验二语法分析程序设计[实验目的]：1．了解语法分析的主要任务。

2．熟悉编译程序的编制。

[实验内容]：根据某文法，构造一基本递归下降语法分析程序。

给出分析过程中所用的产生式序列。

[实验要求]：1.选择一个文法，进行实验，可选的文法包括以下三个：P190 4.8P190 4.9P190 4.102.设计语法分析程序的输出形式（输出应为语法树或推导），一个可以参考的例子，可见图1。

3.编写递归下降语法分析程序（参考P148-149 Topdown parsing byrecursive-descent）,实现基本的递归下降分析器，能够分析任给的符号串是否为该文法所定义的合法句子。

实验报告中要说明分析使用的方法。

4.根据所作业题选项e所给出的input,生成并输出分析过程中所用的产生式序列(show the actions of parser)：1 产生式12 产生式2……5.自已设计一个不合法的句子，作为输出进行分析，给出结果。

[实验过程]本次实验选择的文法为P190 4.8lexp->atom|listatom->number|identifierlist->(lexp-seq)lexp-seq->lexp lexp-seq1.写出实现的算法，并画流程图。

本次实验采用递归下降算法，算法流程图如下图1-1：图1-1 算法流程图2.根据你选择的文法，分析左递归或左因子是否会影响本算法的结果。

会影响本算法的结果。

递归下降分析法要求的文法是LL(1)文法，需要消除左递归和左因子的影响。

如果存在左因子，对相同的字符跳转到不同的函数，无法实现递归。

3.列举实验设计过程中出现的问题及解决的方法（至少3条，选择实验中最困扰的问题）。

1).会多次输出accept/error结果解决方案：所有的递归函数返回类型为int，若accept返回1，error返回0，在main主函数中统一判断输出语句。

GCC语法分析483435351.doc第四部分:GCC语法与语义分析程序琚小明浙江大学信息与通信工程学系 2002年8月一、语法与语义分析程序的主要功能语法分析是编译过程的第二个阶段。

语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。

一般这种语法短语也称为语法单位，可表示成语法树。

(一)语法分析程序的主要功能语法分析所依据的是语言的语法规则，即描述程序结构的规则。

通过语法分析确定整个输入串是否构成一个语法上正确的程序。

在GCC中采用自底向上(bottom-up)最右规约的语法分析方法进行分析的，因为GCC的语法分析程序是由语法分析程序自动产生器(Yacc或bison)生成，LR方法是YACC设定的语法分析方法。

语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。

例如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。

词法分析和语法分析本质上都是对源程序的结构进行分析。

但词法分析的任务仅对源程序进行线性扫描即可完成，例如识别标识符，因为标识符的结构是字母打头的字母和数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母可数字组合在一起而构成单词标识符。

但这种线性扫描不能用于识别的递归定义的语法成分，比如不能用此办法去匹配表达式中的括号。

(二)语法分析程序自动产生器(YACC)简介由于GCC中的语法分析程序是由YACC产生的，故在此对YACC的工作原来作一简要的介绍。

YACC的工作示意图如图1:(有关YACC的详细资料见YACC的说明文档) YACC源程序YACC单词符号串语法分析的 (终结符)输入串输出词法分析程序语法分析程序yylex yyparse图1 YACC工作示意图。

YACC源程序是用户按要求对要处理语言的语法描述，经YACC产生语法分析程序yyparse。

杭州电子科技大学班级: 12052312 专业: 计算机科学与技术实验报告【实验名称】实验二语法分析一. 实验目的编写一个语法分析程序, 实现对词法分析程序所提供的单词序列的语法检查和结构分析。

二. 实验内容利用编程语言实现语法分析程序, 并对简单语言进行语法分析。

2.1 待分析的简单语言的语法用扩充的BNF表示如下:⑴<程序>: : =begin<语句串>end⑵<语句串>: : =<语句>{；<语句>}⑶<语句>: : =<赋值语句>⑷<赋值语句>: : =ID: =<表达式>⑸<表达式>: : =<项>{+<项> | -<项>}⑹<项>: : =<因子>{*<因子> | /<因子>⑺<因子>: : =ID | NUM | （<表达式>）2.2 实验要求说明输入单词串, 以“#”结束, 如果是文法正确的句子, 则输出成功信息, 打印“success”, 否则输出“error”。

例如:输入begin a:=9; x:=2*3; b:=a+x end #输出success！输入x:=a+b*c end #输出error测试以上输入的分析, 并完成实验报告。

2.3 语法分析程序的算法思想（1）主程序示意图如图2-1所示。

图2-1 语法分析主程序示意图（2）递归下降分析程序示意图如图2-2所示。

（3）语句串分析过程示意图如图2-3所示。

图2-3 语句串分析示意图图2-2 递归下降分析程序示意图（4）statement 语句分析程序流程如图2-4.2-5.2-6.2-7所示。

图2-4 statement 语句分析函数示意图 图2-5 expression 表达式分析函数示意图图2-7 factor 分析过程示意图三．个人心得一、 通过该实验, 主要有以下几方面收获: 二、 对实验原理有更深的理解。

1．实验目的构造文法的语法分析程序实验要求，2．实验要求采用预测分析法对输入的字符串进行语法分析。

3．实验环境V4．实验原理对文法G进行语法分析，文法G如下所示：*0. S→a */*1. S→^*2. S→(T)*3. T→SW **4. W→,SW*5. W→ε;5．软件设计与编程#include <stdio.h>#include <stdlib.h>#include <string.h>char str[100]; //存储待分析的句子const char T[ ] = "a^(),#"; //终结符，分析表的列符const char NT[ ] = "STW"; //非终结符，分析表的行符/*指向产生式右部符号串*/const char *p[] = {/*0. S→a */ "a",/*1. S→^ */ "^",/*2. S→(T) */ "(T)",/*3. T→SW */ "SW",/*4. W→,SW */ ",SW",/*5. W→ε; */ ""};//设M[i][j]=x，通过p[M[i][j]]=p[x]获取右部符号串。

const int M[][6] = {/* a ^ ( ) , # *//*S*/ { 0, 1, 2, -1, -1, -1 },/*T*/ { 3, 3, 3, -1, -1, -1 },/*W*/ { -1, -1,-1, 5, 4, -1 }};void init()//输入待分析的句子printf("请输入待分析的句子(以$结束)：\n");scanf("%s",str);}int lin(char c);//非终结符转换为行号int col(char c);//终结转换为列号bool isNT(char c);//isNT判断是否是非终结符bool isT(char c);//isT判断是否是终结符。

《编译原理》上机实验报告题目：LL(1)语法分析程序1.设计要求（1）对输入文法，它能判断是否为LL(1)文法，若是，则转（2）；否则报错并终止；（2）输入已知文法，由程序自动生成它的LL(1)分析表；（3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。

2.分析该程序可分为如下几步：（1）读入文法（2）判断正误（3）若无误，判断是否为LL(1)文法（4）若是，构造分析表；（5）由总控算法判断输入符号串是否为该文法的句型。

3.流程图4.源程序LL1语法分析程序#include<stdio.h>#include<string.h>int count=0; /*分解的产生式的个数*/int number; /*所有终结符和非终结符的总数*/char start; /*开始符号*/char termin[50]; /*终结符号*/char non_ter[50]; /*非终结符号*/char v[50]; /*所有符号*/char left[50]; /*左部*/char right[50][50]; /*右部*/char first[50][50],follow[50][50]; /*各产生式右部的FIRST和左部的FOLLOW集合*/ char first1[50][50]; /*所有单个符号的FIRST集合*/char select[50][50]; /*各单个产生式的SELECT集合*/char f[50],F[50]; /*记录各符号的FIRST和FOLLOW是否已求过*/char empty[20]; /*记录可直接推出^的符号*/char TEMP[50]; /*求FOLLOW时存放某一符号串的FIRST集合*/int validity=1; /*表示输入文法是否有效*/int ll=1; /*表示输入文法是否为LL(1)文法*/int M[20][20]; /*分析表*/char choose; /*用户输入时使用*/char empt[20]; /*求_emp()时使用*/char fo[20]; /*求FOLLOW集合时使用*//*******************************************判断一个字符是否在指定字符串中********************************************/int in(char c,char *p){//int i;size_t i;if(strlen(p)==0)return(0);for(i=0;;i++){if(p[i]==c)return(1); /*若在，返回1*/if(i==strlen(p))return(0); /*若不在，返回0*/}}/*******************************************得到一个不是非终结符的符号********************************************/char c(){char c='A';while(in(c,non_ter)==1)c++;return(c);}分解含有左递归的产生式********************************************/void recur(char *point){ /*完整的产生式在point[]中*/int j,m=0,n=3,k;char temp[20],ch;ch=c(); /*得到一个非终结符*/k=strlen(non_ter);non_ter[k]=ch;non_ter[k+1]='\0';for(j=0;size_t(j)<=strlen(point)-1;j++){if(point[n]==point[0]){ /*如果'|'后的首符号和左部相同*/ for(j=n+1;size_t(j)<=strlen(point)-1;j++){while(point[j]!='|'&&point[j]!='\0')temp[m++]=point[j++];left[count]=ch;memcpy(right[count],temp,m);right[count][m]=ch;right[count][m+1]='\0';m=0;count++;if(point[j]=='|'){n=j+1;break;}}}else{ /*如果'|'后的首符号和左部不同*/ left[count]=ch;right[count][0]='^';right[count][1]='\0';count++;for(j=n;size_t(j)<=strlen(point)-1;j++){if(point[j]!='|')temp[m++]=point[j];else{left[count]=point[0];memcpy(right[count],temp,m);right[count][m]=ch;right[count][m+1]='\0';m=0;count++;}}left[count]=point[0];memcpy(right[count],temp,m);right[count][m]=ch;right[count][m+1]='\0';count++;m=0;}}}/*******************************************分解不含有左递归的产生式********************************************/void non_re(char *point){int m=0,j;char temp[20];for(j=3;size_t(j)<=strlen(point)-1;j++){if(point[j]!='|')temp[m++]=point[j];else{left[count]=point[0];memcpy(right[count],temp,m);right[count][m]='\0';m=0;count++;}}left[count]=point[0];memcpy(right[count],temp,m);right[count][m]='\0';count++;m=0;}/*******************************************读入一个文法********************************************/char grammer(char *t,char *n,char *left,char right[50][50]) {char vn[50],vt[50];char s;char p[50][50];printf("\n请输入文法的非终结符号串：");scanf("%s",vn);getchar();i=strlen(vn);memcpy(n,vn,i);n[i]='\0';printf("请输入文法的终结符号串：");scanf("%s",vt);getchar();i=strlen(vt);memcpy(t,vt,i);t[i]='\0';printf("请输入文法的开始符号：");scanf("%c",&s);getchar();printf("请输入文法产生式的条数：");scanf("%d",&i);getchar();for(j=1;j<=i;j++){printf("请输入文法的第%d条（共%d条）产生式：",j,i);scanf("%s",p[j-1]);getchar();}for(j=0;j<=i-1;j++)if(p[j][1]!='-'||p[j][2]!='>'){ printf("\ninput error!");validity=0;return('\0');} /*检测输入错误*/for(k=0;k<=i-1;k++){ /*分解输入的各产生式*/if(p[k][3]==p[k][0])recur(p[k]);elsenon_re(p[k]);}return(s);}/*******************************************将单个符号或符号串并入另一符号串********************************************/void merge(char *d,char *s,int type){ /*d是目标符号串，s是源串，type＝1，源串中的' ^ '一并并入目串；type＝2，源串中的' ^ '不并入目串*/int i,j;for(i=0;size_t(i)<=strlen(s)-1;i++)if(type==2&&s[i]=='^');else{for(j=0;;j++){if(size_t(j)<strlen(d)&&s[i]==d[j])break;if(size_t(j)==strlen(d)){d[j]=s[i];d[j+1]='\0';break;}}}}}/*******************************************求所有能直接推出^的符号********************************************/void emp(char c){ /*即求所有由' ^ '推出的符号*/ char temp[10];int i;for(i=0;i<=count-1;i++){if(right[i][0]==c&&strlen(right[i])==1){temp[0]=left[i];temp[1]='\0';merge(empty,temp,1);emp(left[i]);}}}/*******************************************求某一符号能否推出' ^ '********************************************/int _emp(char c){ /*若能推出，返回1；否则，返回0*/ int i,j,k,result=1,mark=0;char temp[20];temp[0]=c;temp[1]='\0';merge(empt,temp,1);if(in(c,empty)==1)for(i=0;;i++){if(i==count)return(0);if(left[i]==c) /*找一个左部为c的产生式*/{j=strlen(right[i]); /*j为右部的长度*/if(j==1&&in(right[i][0],empty)==1)return(1);else if(j==1&&in(right[i][0],termin)==1)return(0);else{for(k=0;k<=j-1;k++)if(in(right[i][k],empt)==1)mark=1;if(mark==1)continue;else{for(k=0;k<=j-1;k++){result*=_emp(right[i][k]);temp[0]=right[i][k];temp[1]='\0';merge(empt,temp,1);}}}if(result==0&&i<count)continue;else if(result==1&&i<count)return(1);}}}/*******************************************判断读入的文法是否正确********************************************/int judge(){int i,j;for(i=0;i<=count-1;i++){if(in(left[i],non_ter)==0){ /*若左部不在非终结符中，报错*/ printf("\nerror1!");return(0);}for(j=0;size_t(j)<=strlen(right[i])-1;j++){if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!='^'){ /*若右部某一符号不在非终结符、终结符中且不为' ^ '，报错*/ printf("\nerror2!");validity=0;return(0);}}}return(1);}/*******************************************求单个符号的FIRST********************************************/void first2(int i){ /*i为符号在所有输入符号中的序号*/char c,temp[20];int j,k,m;c=v[i];char ch='^';emp(ch);if(in(c,termin)==1) /*若为终结符*/{first1[i][0]=c;first1[i][1]='\0';}else if(in(c,non_ter)==1) /*若为非终结符*/{for(j=0;j<=count-1;j++){if(left[j]==c){if(in(right[j][0],termin)==1||right[j][0]=='^'){temp[0]=right[j][0];temp[1]='\0';merge(first1[i],temp,1);}else if(in(right[j][0],non_ter)==1){if(right[j][0]==c)continue;for(k=0;;k++)if(v[k]==right[j][0])if(f[k]=='0'){first2(k);f[k]='1';}merge(first1[i],first1[k],2);for(k=0;size_t(k)<=strlen(right[j])-1;k++){empt[0]='\0';if(_emp(right[j][k])==1&&size_t(k)<strlen(right[j])-1){for(m=0;;m++)if(v[m]==right[j][k+1])break;if(f[m]=='0'){first2(m);f[m]='1';}merge(first1[i],first1[m],2);}else if(_emp(right[j][k])==1&&size_t(k)==strlen(right[j])-1){temp[0]='^';temp[1]='\0';merge(first1[i],temp,1);}elsebreak;}}}}}f[i]='1';}/*******************************************求各产生式右部的FIRST********************************************/void FIRST(int i,char *p){int length;int j,k,m;char temp[20];length=strlen(p);if(length==1) /*如果右部为单个符号*/{{if(i>=0){first[i][0]='^';first[i][1]='\0';}else{TEMP[0]='^';TEMP[1]='\0';}}else{for(j=0;;j++)if(v[j]==p[0])break;if(i>=0){memcpy(first[i],first1[j],strlen(first1[j]));first[i][strlen(first1[j])]='\0';}else{memcpy(TEMP,first1[j],strlen(first1[j]));TEMP[strlen(first1[j])]='\0';}}}else /*如果右部为符号串*/{for(j=0;;j++)if(v[j]==p[0])break;if(i>=0)merge(first[i],first1[j],2);elsemerge(TEMP,first1[j],2);for(k=0;k<=length-1;k++){empt[0]='\0';if(_emp(p[k])==1&&k<length-1){for(m=0;;m++)if(v[m]==right[i][k+1])break;if(i>=0)elsemerge(TEMP,first1[m],2);}else if(_emp(p[k])==1&&k==length-1){temp[0]='^';temp[1]='\0';if(i>=0)merge(first[i],temp,1);elsemerge(TEMP,temp,1);}else if(_emp(p[k])==0)break;}}}/*******************************************求各产生式左部的FOLLOW********************************************/void FOLLOW(int i){int j,k,m,n,result=1;char c,temp[20];c=non_ter[i]; /*c为待求的非终结符*/temp[0]=c;temp[1]='\0';merge(fo,temp,1);if(c==start){ /*若为开始符号*/temp[0]='#';temp[1]='\0';merge(follow[i],temp,1);}for(j=0;j<=count-1;j++){if(in(c,right[j])==1) /*找一个右部含有c的产生式*/{for(k=0;;k++)if(right[j][k]==c)break; /*k为c在该产生式右部的序号*/for(m=0;;m++)if(v[m]==left[j])break; /*m为产生式左部非终结符在所有符号中的序号*/ if(size_t(k)==strlen(right[j])-1){ /*如果c在产生式右部的最后*/if(in(v[m],fo)==1){merge(follow[i],follow[m],1);continue;}if(F[m]=='0'){FOLLOW(m);F[m]='1';}merge(follow[i],follow[m],1);}else{ /*如果c不在产生式右部的最后*/for(n=k+1;size_t(n)<=strlen(right[j])-1;n++){empt[0]='\0';result*=_emp(right[j][n]);}if(result==1){ /*如果右部c后面的符号串能推出^*/if(in(v[m],fo)==1){ /*避免循环递归*/merge(follow[i],follow[m],1);continue;}if(F[m]=='0'){FOLLOW(m);F[m]='1';}merge(follow[i],follow[m],1);}for(n=k+1;size_t(n)<=strlen(right[j])-1;n++)temp[n-k-1]=right[j][n];temp[strlen(right[j])-k-1]='\0';FIRST(-1,temp);merge(follow[i],TEMP,2);}}}F[i]='1';}/*******************************************判断读入文法是否为一个LL(1)文法********************************************/int ll1(){int i,j,length,result=1;char temp[50];for(j=0;j<=49;j++){ /*初始化*/first[j][0]='\0';follow[j][0]='\0';first1[j][0]='\0';select[j][0]='\0';TEMP[j]='\0';temp[j]='\0';f[j]='0';F[j]='0';}for(j=0;size_t(j)<=strlen(v)-1;j++)first2(j); /*求单个符号的FIRST集合*/ printf("\nfirst1:");for(j=0;size_t(j)<=strlen(v)-1;j++)printf("%c:%s ",v[j],first1[j]);printf("\nempty:%s",empty);printf("\n:::\n_emp:");for(j=0;size_t(j)<=strlen(v)-1;j++)printf("%d ",_emp(v[j]));for(i=0;i<=count-1;i++)FIRST(i,right[i]); /*求FIRST*/printf("\n");for(j=0;size_t(j)<=strlen(non_ter)-1;j++){ /*求FOLLOW*/if(fo[j]==0){fo[0]='\0';FOLLOW(j);}}printf("\nfirst:");for(i=0;i<=count-1;i++)printf("%s ",first[i]);printf("\nfollow:");for(i=0;size_t(i)<=strlen(non_ter)-1;i++)printf("%s ",follow[i]);for(i=0;i<=count-1;i++){ /*求每一产生式的SELECT集合*/ memcpy(select[i],first[i],strlen(first[i]));select[i][strlen(first[i])]='\0';for(j=0;size_t(j)<=strlen(right[i])-1;j++)result*=_emp(right[i][j]);if(strlen(right[i])==1&&right[i][0]=='^')result=1;if(result==1){for(j=0;;j++)if(v[j]==left[i])break;merge(select[i],follow[j],1);}}printf("\nselect:");for(i=0;i<=count-1;i++)printf("%s ",select[i]);memcpy(temp,select[0],strlen(select[0]));temp[strlen(select[0])]='\0';for(i=1;i<=count-1;i++){ /*判断输入文法是否为LL(1)文法*/length=strlen(temp);if(left[i]==left[i-1]){merge(temp,select[i],1);if(strlen(temp)<length+strlen(select[i]))return(0);}else{temp[0]='\0';memcpy(temp,select[i],strlen(select[i]));temp[strlen(select[i])]='\0';}}return(1);}/*******************************************构造分析表M********************************************/void MM(){int i,j,k,m;for(i=0;i<=19;i++)for(j=0;j<=19;j++)M[i][j]=-1;i=strlen(termin);termin[i]='#'; /*将#加入终结符数组*/termin[i+1]='\0';for(i=0;i<=count-1;i++){for(m=0;;m++)if(non_ter[m]==left[i])break; /*m为产生式左部非终结符的序号*/ for(j=0;size_t(j)<=strlen(select[i])-1;j++){if(in(select[i][j],termin)==1){for(k=0;;k++)if(termin[k]==select[i][j])break; /*k为产生式右部终结符的序号*/ M[m][k]=i;}}}}/*******************************************总控算法********************************************/void syntax(){int i,j,k,m,n,p,q;char ch;char S[50],str[50];printf("请输入该文法的句型：");scanf("%s",str);getchar();i=strlen(str);str[i]='#';str[i+1]='\0';S[0]='#';S[1]=start;S[2]='\0';j=0;ch=str[j];while(1){if(in(S[strlen(S)-1],termin)==1){if(S[strlen(S)-1]!=ch){printf("\n该符号串不是文法的句型！");return;}else if(S[strlen(S)-1]=='#'){printf("\n该符号串是文法的句型.");return;}else{S[strlen(S)-1]='\0';j++;ch=str[j];}}else{for(i=0;;i++)if(non_ter[i]==S[strlen(S)-1])break;for(k=0;;k++){if(termin[k]==ch)break;if(size_t(k)==strlen(termin)){printf("\n词法错误！");return;}}if(M[i][k]==-1){printf("\n语法错误！");return;}else{m=M[i][k];if(right[m][0]=='^')S[strlen(S)-1]='\0';else{p=strlen(S)-1;q=p;for(n=strlen(right[m])-1;n>=0;n--)S[p++]=right[m][n];S[q+strlen(right[m])]='\0';}}}printf("\nS:%s str:",S);for(p=j;size_t(p)<=strlen(str)-1;p++)printf("%c",str[p]);printf(" ");}}/*******************************************一个用户调用函数********************************************/void menu(){syntax();printf("\n是否继续？(y or n):");scanf("%c",&choose);getchar();while(choose=='y'){menu();}}/*******************************************主函数********************************************/void main(){int i,j;start=grammer(termin,non_ter,left,right); /*读入一个文法*/ printf("count=%d",count);printf("\nstart:%c",start);strcpy(v,non_ter);strcat(v,termin);printf("\nv:%s",v);printf("\nnon_ter:%s",non_ter);printf("\ntermin:%s",termin);printf("\nright:");for(i=0;i<=count-1;i++)printf("%s ",right[i]);printf("\nleft:");for(i=0;i<=count-1;i++)printf("%c ",left[i]);if(validity==1)validity=judge();printf("\nvalidity=%d",validity);if(validity==1){printf("\n文法有效");ll=ll1();printf("\nll=%d",ll);if(ll==0)printf("\n该文法不是一个LL1文法！");else{MM();printf("\n");for(i=0;i<=19;i++)for(j=0;j<=19;j++)if(M[i][j]>=0)printf("M[%d][%d]=%d ",i,j,M[i][j]);printf("\n");menu();}}}5.执行结果（1）输入一个文法（2）输入一个符号串（3）再次输入一个符号串，然后退出程序。