实验5 LL(1)语法分析程序的设计与实现(C语言)

实验5 语法分析程序的设计（2）一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。

二、实验内容设计一个文法的算法优先分析程序，判断特定表达式的正确性。

三、实验要求1、给出文法如下：G[E]E->T|E+T;T->F|T*F;F->i|(E);2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式；1、给出算符优先分析算法如下：k:=1; S[k]:=‘#’;REPEAT把下一个输入符号读进a中；IF S[k]∈V T THEN j:=k ELSE j:=k-1;WHILE S[j] a DOBEGINREPEATQ:=S[j];IF S[j-1]∈V T THEN j:=j-1 ELSE j:=j-2UNTIL S[j] Q把S[j+1]…S[k]归约为某个N；k:=j+1;S[k]:=N;END OF WHILE;IF S[j] a OR S[j] a THENBEGINk:=k+1;S[k]:=aENDELSE ERRORUNTIL a=‘#’1、根据给出算法，利用适当的数据结构实现算符优先分析程序；2、利用算符优先分析程序完成下列功能：1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束；2）读入文本文件中的表达式；3）调用实验2中的词法分析程序搜索单词；4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息；5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。

四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C++ 程序集成环境五、实验步骤1、分析文法中终结符号的优先关系；2、存放优先关系或构造优先函数；3、利用算符优先分析的算法编写分析程序；4、写测试程序，包括表达式的读入和结果的输出；5、程序运行效果，测试数据可以参考下列给出的数据。

实验五LL(1)文法识别程序设计之宇文皓月创作一、实验目的通过LL(1)文法识别程序的设计理解自顶向下的语法分析思想。

二、实验重难点FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。

三、实验内容与要求实验内容：1．阅读并理解实验案例中LL(1)文法判此外程序实现；2．参考实验案例，完成简单的LL(1)文法判别程序设计。

四、实验学时4课时五、实验设备与环境C语言编译环境六、实验案例1．实验要求参考教材93页预测分析方法，94页图5.11 预测分析程序框图，编写表达式文法的识别程序。

要求对输入的LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。

表达式文法为：E→E+T|TT→T*F|FF→i|(E)2．参考代码为了更好的理解代码，建议将图5.11做如下标注：/* 程序名称： LL(1)语法分析程序 *//* E->E+T|T *//* T->T*F|F *//* F->(E)|i *//*目的: 对输入LL(1)文法字符串，本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。

/********************************************//* 程序相关说明 *//* A=E' B=T' *//* 预测分析表中列号、行号 *//* 0=E 1=E' 2=T 3=T' 4=F *//* 0=i 1=+ 2=* 3=( 4=) 5=# *//************************************/#include"iostream"#include "stdio.h"#include "malloc.h"#include "conio.h"/*定义链表这种数据类型拜见：http://wenku.百度.com/link?url=_owQzf8PRZOt9H-5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKlNvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS###*/struct Lchar{char char_ch;struct Lchar *next;}Lchar,*p,*h,*temp,*top,*base;/*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/ char curchar; //存放当前待比较的字符:终结符char curtocmp; //存放当前栈顶的字符：非终结符int right;int table[5][6]={{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}};/*存放预测分析表，1暗示有发生式，0暗示无发生式。

实验5LL语法分析程序的设计与实现引言：LL语法分析器是一种自顶向下的语法分析方法，它从语法开始符号开始，通过向前看的一个或者多个输入符号预测产生式的选择，并且通过栈来保存未处理的非终结符。

本实验将设计并实现一个LL语法分析器，包括设计程序的数据结构，算法以及实现细节，并进行相应的测试。

设计概述：1. 实验环境：本实验采用Java编程语言进行实现。

2.数据结构：本实验的数据结构包括文法集合、FIRST集合和FOLLOW 集合、预测分析表等。

3.算法：a)根据给定的文法，构建文法集合和FIRST集合和FOLLOW集合。

b)根据构建的文法集合、FIRST集合和FOLLOW集合，构建预测分析表。

c)根据预测分析表，进行语法分析，实现LL语法分析器。

4.实现细节：本实验实现的LL语法分析器具备错误恢复和语法错误报告的功能。

具体设计与实现：1.构建文法集合：读取给定的文法文件，将每条文法规则分解成产生式的推导式，构建文法集合。

2.构建FIRST集合和FOLLOW集合：遍历文法集合，根据FIRST集合和FOLLOW集合的定义，递归计算每个非终结符的FIRST集合和FOLLOW集合。

3.构建预测分析表：根据构建的文法集合、FIRST集合和FOLLOW集合，生成预测分析表。

4.语法分析过程：根据预测分析表，进行语法分析。

具体过程如下：a)初始化分析栈和输入串，将开始符号和输入串的结束符号入栈；b)重复以下步骤：i)如果栈顶元素是终结符且与输入符号相同，则将栈顶元素出栈，输入串指针前移；ii) 如果栈顶元素是非终结符，则根据预测分析表，选择产生式进行推导，并将该产生式右侧的符号逆序入栈；iii) 如果栈顶元素是结束符号且输入指针也指向结束符号，分析成功；iv) 如果输入指针指向错误的终结符，进行错误恢复处理；v)如果预测分析表中没有对应的产生式，进行错误恢复处理。

5.错误恢复：错误恢复是语法分析器中一个重要的功能，它通过跳过错误符号，继续进行下一步分析来恢复错误。

LL(1)语法分析设计原理与实现技术实验报告变更说明一、实验目的：本实验的目的在于在教师的引导下以问题回朔与思维启发的方式，使学生在不断的探究过程中掌握编译程序设计和构造的基本原理和实现技术，启迪学生的抽象思维、激发学生的学习兴趣、培养学生的探究精神和专业素养，从而提高学生发现问题、分析问题和解决问题的能力。

二、实验内容：[实验项目]实现LL(1)分析中控制程序（表驱动程序）；完成以下描述算术表达式的LL(1)文法的LL(1)分析程序。

G[E]: E→TE′E′→ATE′|εT→FT′T′→MFT′|εF→ (E)|iA→+|-M→*|/[实验说明]终结符号i 为用户定义的简单变量,即标识符的定义。

[设计要求]（1）输入串应是词法分析的输出二元式序列，即某算术表达式“实验项目一”的输出结果。

输出为输入串是否为该文法定义的算术表达式的判断结果；（2）LL(1)分析过程应能发现输入串出错；（3）设计两个测试用例（尽可能完备，正确和出错），并给出测试结果。

三、实验环境：操作系统：Windows 7软件：VC++四、程序功能描述：提供了文件输入方式，且输入的内容为二元式序列；能够对输入的字符串做出正确的LL(1)分析判断，并给出判断结果，判断结果输出到文件，并显示在屏幕；能发现输入串中的错误，包含非法字符，输入不匹配等；能够处理一些可预见性的错误，如文件不存在，输入非法等。

五、数据结构设计：全局：局部（main()中）：六、程序结构描述：设计方法：本程序采用从文件读取的输入方式，输入的内容需为二元式序列，然后按照LL(1)分析的方法对输入的字符串进行分析判断，并输出判断结果，程序通过对输入串的检查能够发现输入串中的错误。

程序规定的单词符号及其种别码见下表：单词符号种别码单词符号种别码（1*5）2/6+3i7-4#8i+-*/()#E E→TG E→TGG G→ATG G→ATG G→εG→εT T→FH T→FHH H→εH→εH→MFH H→MFH H→εH→εF F→i F→(E)A A→+A→-M M→*M→/主要函数说明：check_VT(char ch)：bool型函数，检查ch是否为终结字符，是则返回true；create_analyseTable()：构建分析表函数，无返回值；error(FILE *fp)：输出错误，表示不是该文法的句子,参数fp用于退出前将打开的文件关闭；getnum_VN(char ch)：int型函数，查找ch在非终结字符中的位置并返回；getnum_VT(char ch)：int型函数，查找ch在终结字符中的位置并返回；justify()：bool型函数，判断文件读取内容是否合法，包括检查非法字符和不匹配现象，出错返回false，否则返回true；main()：主函数。

实验5---语法分析器（自下而上）：LR(1)分析法一、实验目的构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

二、实验内容程序输入/输出示例（以下仅供参考）：对下列文法，用LR（1）分析法对任意输入的符号串进行分析：（1）E->E+T（2）E->E—T（3）T->T*F（4）T->T/F（5）F-> (E)（6）F->i输出的格式如下：(1)LR（1）分析程序，编制人：姓名，学号，班级(2)输入一个以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串(3)输出过程如下：3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。

同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照。

三、实验方法1．实验采用C++程序语言进行设计，文法写入程序中，用户可以自定义输入语句；2．实验开发工具为DEV C++。

四、实验步骤1．定义LR(1)分析法实验设计思想及算法①若ACTION[sm , ai] = s则将s移进状态栈，并把输入符号加入符号栈，则三元式变成为：(s0s1…sm s , #X1X2…Xm ai , ai+1…an#)；②若ACTION[sm , ai] = rj则将第j个产生式A->β进行归约。

此时三元式变为(s0s1…sm-r s , #X1X2…Xm-rA , aiai+1…an#)；③若ACTION[sm , ai]为“接收”，则三元式不再变化，变化过程终止，宣布分析成功；④若ACTION[sm , ai]为“报错”，则三元式的变化过程终止，报告错误。

2．定义语法构造的代码，与主代码分离，写为头文件LR.h。

3．编写主程序利用上文描述算法实现本实验要求。

五、实验结果1. 实验文法为程序既定的文法，写在头文件LR.h中，运行程序，用户可以自由输入测试语句。

词法分析器实验报告实验名称：语法分析器实验内容：利用LL（1）或LR（1）分析语句语法，判断其是否符合可识别语法。

学会根据状态变化、first、follow或归约转移思想构造状态分析表，利用堆栈对当前内容进行有效判断实验设计：1.实现功能可对一段包含加减乘除括号的赋值语句进行语法分析，其必须以$为终结符，语句间以；隔离，判断其是否符合语法规则，依次输出判断过程中所用到的产生式，并输出最终结论，若有错误可以报错并提示错误所在行数及原因2.实验步骤3．算法与数据结构a)LLtable:left记录产生式左端字符；right记录产生式右端字符；ln记录产生式右端字符长度Status：记录token分析情况Token：category，类型；value，具体内容b)根据LL（1）算法，手工构造分析表，并将内容用数组存储，便于查找c)先将当前语句的各token按序存储，当前处理语句最后一个token以#标记，作为输入流与产生式比较，堆栈中初始放入#，x，a为处理输入流中当前读头内容✓若top=a=‘#‘表示识别成功，退出分析程序✓若top=a！=‘#‘表示匹配，弹出栈顶符号，读头前进一个✓若top为i或n，但top！=a，出错，输出当前语句所在行，出错具体字符✓若top不为i或n，查预测分析表，若其中存放关于top产生式，则弹出top，将产生式右部自右向左压入栈内，输出该产生式，若其中没有产生式，出错，输出当前语句所在行，出错具体字符d)以；作为语句终结，每次遇到分号则处理之前语句并清空后预备下语句处理，当遇到$表示该段程序结束，停止继续处理4．分析表构造过程a)x->i=ee->e+t|e-t|tt->t*f|t/f|ff->(e)|i|nnote: i表示变量，n表示数字,!表示空串b)提取左公因子x->i=ee->ea|ta->+t|-tt->tb|fb->*f|/ff->(e)|i|nc)消除左递归x->i=ee->tcc->ac|!a->+t|-tt->fdd->bd|!b->*e|/ff->(e)|i|n5．类class parser{public:LLtable table[100][100]; //LL(1)表void scanner(); //扫描输入流中内容并分析parser(istream& in); //初始化，得到输入文件地址int getLine() const; //得到当前行数private:int match(); //分析语法stack <char> proStack; //分析堆栈void constructTable(); //建立LL（1）表int getRow(char ch); //取字符所在表中行int getCol(char ch); //取字符所在表中列istream* pstream; //输入流void insertToken(token& t); //插入当前tokenstatus getToken(token& t); //找到tokenint getChar(); //得到当前字符int peekChar(); //下一个字符void putBackChar(char ch); //将字符放回void skipChar(); //跳过当前字符void initialization(); //初始化堆栈等int line; //当前行数token tokens[1000]; //字符表int counter; //记录当前字符表使用范围}6．主要代码void parser::constructTable() //建立LL（1）表{for (int i=0;i<8;i++){for (int j=0;j<9;j++){table[i][j].left=' ';for (int k=0;k<3;k++)table[i][j].right[k]=' ';}}table[0][6].left='x';table[0][6].ln=3;table[0][6].right[0]='i';table[0][6].right[1]='=';table[0][6].right[2]='e';table[1][4].left='e';table[1][4].ln=2;table[1][4].right[0]='t';table[1][4].right[1]='c';table[1][6].left='e';table[1][6].ln=2;table[1][6].right[0]='t';table[1][6].right[1]='c';table[1][7].left='e';table[1][7].ln=2;table[1][7].right[0]='t';table[1][7].right[1]='c';table[2][0].left='c';table[2][0].ln=2;table[2][0].right[0]='a';table[2][0].right[1]='c';table[2][1].left='c';table[2][1].ln=2;table[2][1].right[0]='a';table[2][1].right[1]='c';table[2][5].left='c';table[2][5].ln=0;table[2][5].right[0]='!';table[2][8].left='c';table[2][8].ln=0;table[2][8].right[0]='!';table[3][0].left='a';table[3][0].ln=2;table[3][0].right[0]='+'; table[3][0].right[1]='t'; table[3][1].left='a';table[3][1].ln=2;table[3][1].right[0]='-'; table[3][1].right[1]='t'; table[4][4].left='t';table[4][4].ln=2;table[4][4].right[0]='f'; table[4][4].right[1]='d'; table[4][6].left='t';table[4][6].ln=2;table[4][6].right[0]='f'; table[4][6].right[1]='d'; table[4][7].left='t';table[4][7].ln=2;table[4][7].right[0]='f'; table[4][7].right[1]='d'; table[5][0].left='d';table[5][0].ln=0;table[5][0].right[0]='!'; table[5][1].left='d';table[5][1].ln=0;table[5][1].right[0]='!'; table[5][2].left='d';table[5][2].ln=2;table[5][2].right[0]='b'; table[5][2].right[1]='d'; table[5][3].left='d';table[5][3].ln=2;table[5][3].right[0]='b'; table[5][3].right[1]='d'; table[5][5].left='d';table[5][5].ln=0;table[5][5].right[0]='!'; table[5][8].left='d';table[5][8].ln=0;table[5][8].right[0]='!'; table[6][2].left='b';table[6][2].ln=2;table[6][2].right[0]='*'; table[6][2].right[1]='f'; table[6][3].left='b';table[6][3].ln=2;table[6][3].right[0]='/'; table[6][3].right[1]='f'; table[7][4].left='f';table[7][4].ln=3;table[7][4].right[0]='(';table[7][4].right[1]='e';table[7][4].right[2]=')';table[7][6].left='f';table[7][6].ln=1;table[7][6].right[0]='i';table[7][7].left='f';table[7][7].ln=1;table[7][7].right[0]='n';}int parser::match() //分析语法{ofstream ofs("out.txt",ios::app);char a;int i=0;for (int p=0;p<counter;p++){cout<<tokens[p].value;ofs<<tokens[p].value;}cout<<endl;ofs<<endl<<"ANALYSIS:"<<endl;while(1){if(tokens[i].category=='n' || tokens[i].category=='i')a=tokens[i].category;elsea=(tokens[i].value)[0];if(a==proStack.top()){if(a=='#'){cout<<"This is valid!"<<endl<<endl;ofs<<"This is valid!"<<endl<<endl;return 0;}else{proStack.pop();i++;}}else{if(proStack.top() =='n'|| proStack.top() =='i'){if(a!='#'){cout<<"ERROR(LINE "<<getLine()<<" ): "<<a<<" cannot be matched"<<endl;ofs<<"ERROR(LINE "<<getLine()<<" ): "<<a<<" cannot be matched"<<endl;}else{cout<<"ERROR(LINE "<<getLine()<<" ): Unexpected ending"<<endl;ofs<<"ERROR(LINE "<<getLine()<<" ): Unexpected ending"<<endl;}cout<<"This is invalid!"<<endl<<endl;ofs<<"This is invalid!"<<endl<<endl;return 0;}else{if((table[getRow(proStack.top())][getCol(a)]).left!=' '){char pst=proStack.top();int n=table[getRow(pst)][getCol(a)].ln;int k=0;ofs<<table[getRow(pst)][getCol(a)].left<<"->"<<table[getRow(pst)][getCol(a)].right[0]<<table[getRow(pst)][g etCol(a)].right[1]<<table[getRow(pst)][getCol(a)].right[2]<<endl;proStack.pop();while (n>0){//cout<<n<<" "<<table[getRow(pst)][getCol(a)].right[n-1]<<endl;proStack.push(table[getRow(pst)][getCol(a)].right[n-1]);n--;}}else{if(a!='#'){cout<<"ERROR(LINE "<<getLine()<<" ): "<<a<<" cannot be matched"<<endl;ofs<<"ERROR(LINE "<<getLine()<<" ): "<<a<<" cannot be matched"<<endl;}else{cout<<"ERROR(LINE "<<getLine()<<" ): Unexpected ending"<<endl;ofs<<"ERROR(LINE "<<getLine()<<" ): Unexpected ending"<<endl;}cout<<"This is invalid!"<<endl<<endl;ofs<<"This is invalid!"<<endl<<endl;return 0;}}}}}实验结果：●输入（in.txt）●输出1输出2（out.txt）实验总结：原本以为处理四则运算赋值将会很困难，但在使用LL（1）后发现，思路还是挺清晰简单的，但在实验过程中，由于LL（1）不能出现左递归和左公因子，不得不将其消除，原本简单的产生式一下变多了，而在产生式理解上也没有原来直观，不过其状态复杂度没有LR高，故仍选择该方法。