编译原理课程设计--LR(0)分析器自动构造程序的实现

1、 衡阳师范学院工科课程设计 -编译原理课程设计报告 题 目： LR(0)分析器自动构造程序的实现 学 号： 13190207 姓 名： 谭金星 班 级： 1302 指导教师： 陈琼老师 日 期： 2016年 6月20日 目 录第一章 概 述4第二章 设计的基本原理52.1 识别文法的LR(0)项目集规范族的构造52.2 LR(0)分析表的构造52.3 LR(0)分析器总控程序构造6第三章 程序设计73.1 程序总体构架73.2 程序存储结构83.2.1 符号表存储结构83.2.2 产生式表存储结构83.2.3 项目集规范族表存储结构93.2.4 LR(0)分析表存储结构93.3 程序

2、算法103.3.1 项目集规范族的构造103.3.2 LR(0)分析表构造11第四章 程序测试124.1 符号表测试124.2 产生式表测试134.3 项目集规范族表测试134.4 LR(0)分析表测试144.5 LR(0)分析器测试14第五章 总结和展望15附录16参考文献17一 概 述本课程设计完成了以下内容：1. 实现了对任意给定的文法，识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2. 判断该文法是否为文法，实现了分析表的构造，并输出到指定文件中；3. 实现了分析器总控程序，对输入的表达式进行文法分析。4.在VC+6.0程序上运行二 设计的基本原理本课程设计的核心算法Error

3、! Reference source not found.主要有三点：1. 识别文法活前缀的、的状态转化矩阵及项目集规范族的构造；2. 分析表的构造；3. 分析器总控程序的构造。2.1 识别文法的LR(0)项目集规范族的构造采用（闭包）的构造一个文法的项目规范簇。假定是文法的任一项目集，定义和构造的闭包的算法：（1）的任何项目都属于；（2）若属于，那么，对任何关于的产生式，项目也属于；（3）重复执行上述两个步骤直至不再增大。其中初始 ，为对文法进行拓广构造而引进的不出现在中的非终结符。定义状态转换函数，的第一个变元是一个项目集，第二个变元是一个文法符号。函数值定义为。其中 = 任何形如的项目|

4、 属于2.2 LR(0)分析表的构造 假定。令每个项目集的下标作为分析器的状态。特别是，令那个包含项目的集合的下标为分析器的初态。分析表的子表和子表可按如下方法构造： （1）若项目属于且，为终结符，则置为“把移近栈”，简记为“”。 （2）若项目属于，那么对于任何终结符（或结束符#），置为“用产生式进行规约”，简记为“”（假定产生式是文法的第j个产生式） （3）若项目属于，则置为“接受”，简记为“acc”。 （4）若，则置。 （5）分析表中凡不能用规则14填入信息的空白处均置上“报错标志”。如果分析表中任何一项被重复填入，则说明分析表的入口不是唯一的，项目集中存在冲突项目，该文法不是文法。2.3

5、 LR(0)分析器总控程序构造分析表包括量部分，“动作”表和“状态转换”表。规定了当状态面临输入符号时应采取什么动作。规定了状态面对文法符号时下一状态是什么。每一项所规定的动作不外乎是下述四种可能之一。（1）移进 把的下一状态和输入符号推进栈，下一输入符号变成现行输入符号。（2）归约 指用某一产生式进行规约。假若的长度为,规约的动作是，去除栈顶的个项，使状态变成栈顶状态，然后把的下一状态推进栈。规约动作不改变现行输入符号。规约动作不改变现行输入符号。（3）接受 宣布分析成功，停止分析器工作（4）报错 发现源程序含有错误，调用出错处理程序。三 程序设计3.1 程序总体构架 本课程设计开发的程序主

6、要由4张表组成，分别为：符号表、产生式表、表和项目集规范簇表。同时，项目集规范簇表包含一个分析栈作为分析器总控程序。产生式表包含符号表作为子表，项目集规范簇表包含产生式表、表作为子表。 程序工作流程：1. 读取含有文法规则的文件，为该文法中的每一个不同的文法符号（终结符和非终结符分配一个编号），记录文法符号的属性（终结符/非终结符），存储于一张符号表中；2. 再次读取文件，将产生式存储于产生式表中；3. 根据产生式构建项目集规范族，存储于表中；4. 根据构建的项目集规范族构建分析表，填写分析表同时检查该文法是否为文法；5. 对于输入的表达式，分析器根据构建的分析表进行文法分析，给出分析结果。3

7、.2 程序存储结构3.2.1 符号表存储结构动态数组下标，同时作为符号的编号标识符是否为非终结符3.2.2 产生式表存储结构产生式标号非终结符标号 （与中的一致）指示当前非终结符的产生式当前非终结符产生式的长度，用于帮助区分一个产生式的不同项目，即项目个数等于指示下一个非终结符一个产生式中的标识符名（与中的一致）一个产生式中的下一个标识符3.2.3 项目集规范族表存储结构 1）定义二元组 ： ：产生式标号，与 中的一致 ：一个产生式的第个项目，可由 中的帮助确定 如：产生式 ： ， 2）结构：当前状态编号 指示下一状态 指示闭包中的项目 闭包中的项目名当前项目的产生的新状态的编号，即状态转移的

8、目的地状态编号闭包中的下一个项目待构造的项目的闭包的待构造的项目的闭包待构造状态的待构造状态的项目3.2.4 LR(0)分析表存储结构指示表头的孩子结点指示表头的后继结点指示该表项的操作指示该表项的操作数指示该表项是否被填写过,用于判断文法是否为文法3.3 程序算法3.3.1 项目集规范族的构造1. （初始化）将初始条件作为该状态头结点的第一个孩子结点，并构造该孩子结点的闭包，连接其后，指向第一个状态头结点，指向第一个状态头结点的第一个孩子结点；2. 查看，若为空，停止；若不为空，转3；3. 查看，若为空，转4；若不为空，构造的，检查该状态与之前构造的状态有无重复，若重复，则停止构造，的填写重

9、复的已存在的状态的编号；若不重复，则作为一个新状态，连接于，并构造其闭包连接其后，指向。转2；4. 指向下一状态，若下一状态为空，则结束，否则，指向下一状态头结点的第一个孩子结点，转3。具体细节：设所指项目为，因为要对其构造闭包，该项目一定不是终态，所以区分项目的圆点符号位于第个标识符的左侧。现在构造的闭包，分两个步骤实现：1. 构造的 ： 查看中编号为的产生式，取得该产生式的长度属性1） 若，则停止构造当前闭包（已是终态），此时 的项填；2） 否则，将作为该闭包的第一个项目，此时 的项填该新状态的状态编号。2. 构造该孩子结点的闭包 ：查看中编号为的产生式的第个标识符，取得该标识符的，查看中

10、该标识符的类别属性3） 若为1（非终结符），则查看非终结符的所有产生 式，记这些产生式的编号为，将所有的加入闭包4） 否则，结束3. 检查该状态与之前构造的状态有无重复 :断言：任意两个状态，只要不同，则即为不同状态。3.3.2 LR(0)分析表构造对于编号为的状态，现依据其项目填写分析表：1. 如果该项目形如，查看该项目的属性，1）若为终结符，则在表的状态对应行，对应列，填写，表示将把 移进栈2）若为非终结符，则在表的状态对应行，对应列，填写，表示状态转移至状态2. 如果该项目形如1）若为起始符号，则置在表的状态对应行，对应列，填写，表示接受。2）否则，对任何终结符或结束符，则在表的状态对应

11、行，对应列，填写，表示用产生式进行规约。四 程序测试以文法G为例：程序模块输入：含上述文法的文件，下面展示个模块的输出结果4.1 符号表测试图6 符号表测试输出结果为 <符号编号，符号，是否为终结符>与预期结果相同图7 产生式表测试4.2 产生式表测试输出结果与读入的文件中的产生式相同，且产生式中符号的编号正确4.3 项目集规范族表测试图8 DFA表测试输出结果为 <状态编号> ：<产生式编号，产生式项目编号，项目转移的目标状态>与预期结果相同4.4 LR(0)分析表测试图9 分析表测试输出结果为分析表，与预期结果相同4.5 LR(0)分析器测试以输入字符串

12、accd#和acad#为例图10 分析器测试表达式的分析结果正确五 总结和展望完成了编译原理课程设计之后，我感到十分的疲惫，但是那一份富有成就感的欣喜却胜过了那十分的疲惫。由于本次选题匆忙，选了一道比较有难度的题目，在做课程设计的过程中，我翻阅了很多相关资料，对课本中点到即止的知识进行了更加深入的学习，有了更加深入的理解。做课程设计的过程是痛苦的，我在这一个星期内多次熬夜战斗，有时甚至顾不上吃饭，只为了揪出程序中的错误，只为了精益求精的完成这个课程设计。就在我写这份总结的时候，我发现自己我一点也不累了，反而很兴奋，很有成就感。通过本次课程设计，我发现实践是检验学习深度、学习成果的唯一途径，课本

13、上的知识点都是浓缩的精华，在理论阐述上不可能做到面面俱到，学到的知识当然也不可能直接运用到实际情况上。在实践的过程中，我们需要将我们学习到的知识进行一定程度的扩充，本次课程设计涉及到算法，LR分析器自动构造程序的机制原理以及C+语言。在用C+语言实现本次课程设计的过程中，我更加熟悉了C+语言的语法机制，语言规范；在实现LR分析器自动构造程序的过程中，我更加熟悉了其构造程序的原理以及与之相关的算法。由于时间匆忙，我完成的课程设计还有很多不足之处，很多工作还可以继续完善，在提交作业之后，我不会把它放在那里一看不看的，我会继续完善它，让它更加人性化，具有可操作性，比如做个可视化的界面出来，丰富它的功

14、能，相信以后的工作将更加多彩丰富，更加有成就感！ 附录说明：本附录中包含了本次课程设计的所有代码34 Closure_List.h#ifndef CLOSURE_LIST_H#define CLOSURE_LIST_H#include "Formula_List.h"#include "LR0_Table.h"struct Item_Name_Typeint Formula_Num; int Formula_Item; ;struct Closure_Child_NodeItem_Name_Type Item_Name;int Destination;

15、Closure_Child_Node *Next_Item;struct Closure_Parent_Nodeint Current_State;Closure_Parent_Node *Next_State;Closure_Child_Node *Item;class Closure_Listprivate:Closure_Parent_Node *Closure_List_head;Closure_Parent_Node *GoToSet_Parent;Closure_Parent_Node *Current_Parent;Closure_Child_Node *GoToSet_Chil

16、d;Closure_Child_Node *Current_Child;int AmountOf_State; Formula_List sub_Formula_List;LR0_Table sub_LR0_Table;public:Closure_List():sub_Formula_List(),sub_LR0_Table()Closure_List_head = NULL;GoToSet_Parent = NULL;Current_Parent = NULL;GoToSet_Child = NULL;Current_Child = NULL;AmountOf_State = 0;Crea

17、te_Closure_List();Closure_List();void print_Closure_List();void make_LR0_Table();void print_LR0_Table();void Output_LR0_Table_ToFile();bool Sentence_Analyse(const char Sentence50);private:void Add_Clousure();bool Add_GoToSet();void Set_Initial_State();bool Is_Same_State_Exist(const int Formula_Num,c

18、onst int Formula_Item,int& Same_State_Num);void Create_Closure_List();void Destroy_Closure_List();#endifFormula_List.h#ifndef FORMULA_LIST_H#define FORMULA_LIST_H#include "Sign_List.h"struct Formula_List_ChildItemint Sign_Name;Formula_List_ChildItem* Next_Sign;struct Formula_List_Paren

19、tItemint Formula_Num; int Vn_Name; int Formula_Length; Formula_List_ParentItem* Next_Vn;Formula_List_ChildItem* Formula;class Formula_Listprivate:Formula_List_ParentItem *Formula_List_head;Formula_List_ChildItem *current_Formula_Item;Formula_List_ParentItem *current_VnNode;Sign_List Sub_Sign_List; p

20、ublic:Formula_List():Sub_Sign_List()Formula_List_head = NULL; current_Formula_Item = NULL; current_VnNode = NULL;Create_Formula_List();Formula_List();void print_Formula_List();int int_check_Sign_Name(const char word);char char_check_Sign_Name(const int Sign_Name);int Get_Formula_Length(const int For

21、mula_Num);int Get_Sign_Name(const int Formula_Num, const int Item_Num);int Get_Formula_LeftVn(const int Formula_Num);bool Is_Sign_Name_Vn(const int Sign_Name);int Get_AmountOf_Identity();private:void Destroy_Formula_List();void Create_Formula_List(); ;#endifLR0_Table.h#ifndef LR0_TABLE_H#define LR0_

22、TABLE_H#include <iostream>#include <fstream>using namespace std;#include "ConstValue.h"struct LR0_Table_Childchar Operation;int Oprand;bool Has_Been_Filled;LR0_Table_Child *Next_Table_Child;struct LR0_Table_ParentLR0_Table_Child *Table_Child;LR0_Table_Parent *Next_Table_Parent;

23、class LR0_Tableprivate:LR0_Table_Parent *LR0_Table_head;LR0_Table_Parent *Current_Parent;LR0_Table_Child *Current_Child;public:LR0_Table();LR0_Table();void initial(const int AmountOf_State, const int AmountOf_Identity);bool Fill_In_Table(const int State_Num, const int Identity_Num,const char char_Op

24、ration, const int int_Oprand);void _OutputToFile();void _print_LR0_Table();void Visit_LR0_Table(const int State_Num, const int Identity_Num, char& char_Opration, int& int_Oprand);private:void Destroy_LR0_Table();#endifSign_List.h#ifndef SIGN_LIST_H#define SIGN_LIST_H#include <iostream>

25、#include <fstream>using namespace std;#include "ConstValue.h"struct Sign_List_itemchar Identity; bool Is_Vn;Sign_List_item *next_Identity;struct Identity_List_itemchar Identity; bool Is_Vn;class Sign_Listprivate:Identity_List_item *Identity_List;int AmountOf_Identity; public:Sign_Lis

26、t();Sign_List();void print_Identity_List();int _int_check_Sign_Name(const char word);char _char_check_Sign_Name(const int Sign_Name);bool _Is_Sign_Name_Vn(const int Sign_Name);int _Get_AmountOf_Identity();private:void Destroy_temp_Sign_List();void Create_Identity_List();private:Sign_List_item *curre

27、nt_Identity; Sign_List_item *head; bool Is_sameIdentity_Exist(const char word);#endifStack.h#ifndef STACK_H#define STACK_Hstruct elemint data;elem *next;class Stackprivate:elem *top;int count;public:Stack();Stack();bool pushElem(const int Data);bool getElem(int &Data); bool popElem();int countEl

28、em()const;#endifClosure_List.cpp#include "Closure_List.h"#include "Stack.h"bool Closure_List:Add_GoToSet()int temp_Formula_Length = sub_Formula_List.Get_Formula_Length(GoToSet_Child->Item_Name.Formula_Num);if (GoToSet_Child->Item_Name.Formula_Item <= temp_Formula_Length)

29、int SameDestination = 0;if (Is_Same_State_Exist(GoToSet_Child->Item_Name.Formula_Num,GoToSet_Child->Item_Name.Formula_Item +1,SameDestination)=true)GoToSet_Child->Destination = SameDestination;return false; Closure_Child_Node *tempChild = new Closure_Child_Node;tempChild->Item_Name.Formu

30、la_Num = GoToSet_Child->Item_Name.Formula_Num;tempChild->Item_Name.Formula_Item = GoToSet_Child->Item_Name.Formula_Item +1;tempChild->Next_Item = NULL;Current_Child = tempChild;Closure_Parent_Node *tempParent = new Closure_Parent_Node;tempParent->Item = tempChild;tempParent->Next_S

31、tate = NULL;tempParent->Current_State = Current_Parent->Current_State +1;Current_Parent->Next_State = tempParent;Current_Parent = tempParent;GoToSet_Child->Destination = Current_Parent->Current_State;+AmountOf_State;return true;elseGoToSet_Child->Destination = -1;return false;void

32、Closure_List:Add_Clousure()int temp_Sign_Name = sub_Formula_List.Get_Sign_Name(GoToSet_Child->Item_Name.Formula_Num,GoToSet_Child->Item_Name.Formula_Item +1);if (temp_Sign_Name=-1)return;if (sub_Formula_List.Is_Sign_Name_Vn(temp_Sign_Name)=true)int temp_Formula_Num = 1;int temp_Vn_Name = 0;whi

33、le (temp_Vn_Name = sub_Formula_List.Get_Formula_LeftVn(temp_Formula_Num)!=-1)if (temp_Sign_Name=temp_Vn_Name)Closure_Child_Node *tempChild = new Closure_Child_Node;tempChild ->Item_Name.Formula_Num = temp_Formula_Num;tempChild ->Item_Name.Formula_Item = 1;tempChild->Next_Item = NULL;Current

34、_Child->Next_Item = tempChild;Current_Child = tempChild;+temp_Formula_Num;void Closure_List:Set_Initial_State()Closure_List_head = new Closure_Parent_Node;Closure_List_head->Current_State = 0;Closure_List_head->Item = NULL;Closure_List_head->Next_State = NULL;GoToSet_Parent = Closure_Lis

35、t_head;Current_Parent = Closure_List_head;Closure_Child_Node *tempChild = new Closure_Child_Node;tempChild ->Item_Name.Formula_Num = 1;tempChild ->Item_Name.Formula_Item = 1;tempChild->Next_Item = NULL;Closure_List_head ->Item = tempChild;GoToSet_Child = tempChild;Current_Child = tempChi

36、ld;+AmountOf_State;int temp_Sign_Name = sub_Formula_List.Get_Sign_Name(1,1);int temp_Formula_Num = 1;int temp_Vn_Name = 0;while (temp_Vn_Name = sub_Formula_List.Get_Formula_LeftVn(temp_Formula_Num)!=-1)if (temp_Sign_Name=temp_Vn_Name)Closure_Child_Node *tempChild = new Closure_Child_Node;tempChild -

37、>Item_Name.Formula_Num = temp_Formula_Num;tempChild ->Item_Name.Formula_Item = 1;tempChild->Next_Item = NULL;Current_Child->Next_Item = tempChild;Current_Child = tempChild;+temp_Formula_Num;void Closure_List:Create_Closure_List()Set_Initial_State();while (GoToSet_Parent!=NULL)if (GoToSet

38、_Child!=NULL)if (Add_GoToSet()=true) Add_Clousure(); GoToSet_Child = GoToSet_Child->Next_Item; elseGoToSet_Parent = GoToSet_Parent->Next_State;if (GoToSet_Parent=NULL)break;GoToSet_Child = GoToSet_Parent->Item;void Closure_List:Destroy_Closure_List()Current_Parent = Closure_List_head;if (Cl

39、osure_List_head = NULL)return;elsewhile (Current_Parent != NULL)Closure_Parent_Node *temp_ToDelete = Current_Parent;Current_Child = Current_Parent->Item;while (Current_Child != NULL)Closure_Child_Node *ToDelete = Current_Child;Current_Child = Current_Child->Next_Item;delete ToDelete;Current_Pa

40、rent = Current_Parent->Next_State;delete temp_ToDelete;Closure_List_head = NULL;GoToSet_Parent = NULL;Current_Parent = NULL;GoToSet_Child = NULL;Current_Child = NULL;void Closure_List:print_Closure_List()Closure_Parent_Node *print_Vn_Node = Closure_List_head;if (Closure_List_head = NULL)return;el

41、sewhile (print_Vn_Node != NULL)cout<<print_Vn_Node->Current_State<<" : "Closure_Child_Node *pirnt_Item_Node = print_Vn_Node->Item;while (pirnt_Item_Node != NULL)cout<<'<'<<pirnt_Item_Node->Item_Name.Formula_Num<<','<<pirnt_Ite

42、m_Node->Item_Name.Formula_Item<<','<<pirnt_Item_Node->Destination<<">, "pirnt_Item_Node = pirnt_Item_Node->Next_Item;cout<<endl;print_Vn_Node = print_Vn_Node->Next_State;bool Closure_List:Is_Same_State_Exist(const int Formula_Num,const int For

43、mula_Item ,int& Same_State_Num)Closure_Parent_Node *Check_Parent_Node = Closure_List_head;while (Check_Parent_Node != NULL)if (Check_Parent_Node->Item->Item_Name.Formula_Item = Formula_Item &&Check_Parent_Node->Item->Item_Name.Formula_Num = Formula_Num)Same_State_Num = Check_

44、Parent_Node->Current_State;return true;Check_Parent_Node =Check_Parent_Node->Next_State;Same_State_Num = -1;return false;void Closure_List:make_LR0_Table()sub_LR0_Table.initial(AmountOf_State,sub_Formula_List.Get_AmountOf_Identity();Closure_Parent_Node *Traverse_Parent = Closure_List_head;Clos

45、ure_Child_Node *Traverse_Child = Closure_List_head->Item;bool No_ErrorOccurIn_FillingTable = true;while (Traverse_Parent!=NULL)Item_Name_Type Traverse_Item; Traverse_Item.Formula_Num = Traverse_Child->Item_Name.Formula_Num;Traverse_Item.Formula_Item = Traverse_Child->Item_Name.Formula_Item;

46、int CurrentFormulalength = sub_Formula_List.Get_Formula_Length(Traverse_Item.Formula_Num);if (Traverse_Item.Formula_Item<=CurrentFormulalength) int Traverse_Sign_Name = sub_Formula_List.Get_Sign_Name(Traverse_Item.Formula_Num, Traverse_Item.Formula_Item);int Goal_State_Num = Traverse_Child->De

47、stination;if (sub_Formula_List.Is_Sign_Name_Vn(Traverse_Sign_Name)=false)No_ErrorOccurIn_FillingTable = sub_LR0_Table.Fill_In_Table(Traverse_Parent->Current_State,Traverse_Sign_Name,'s',Goal_State_Num);elseNo_ErrorOccurIn_FillingTable = sub_LR0_Table.Fill_In_Table(Traverse_Parent->Curr

48、ent_State,Traverse_Sign_Name,'g',Goal_State_Num);else int Traverse_Sign_Name = sub_Formula_List.Get_Sign_Name(Traverse_Item.Formula_Num, Traverse_Item.Formula_Item-1);if (Traverse_Sign_Name=1)No_ErrorOccurIn_FillingTable = sub_LR0_Table.Fill_In_Table(Traverse_Parent->Current_State,sub_For

49、mula_List.Get_AmountOf_Identity(),'a',1);elsefor (int i=0; i<sub_Formula_List.Get_AmountOf_Identity(); +i)if (sub_Formula_List.Is_Sign_Name_Vn(i)=false)No_ErrorOccurIn_FillingTable = sub_LR0_Table.Fill_In_Table(Traverse_Parent->Current_State, i,'r',Traverse_Item.Formula_Num);No

50、_ErrorOccurIn_FillingTable = sub_LR0_Table.Fill_In_Table(Traverse_Parent->Current_State, sub_Formula_List.Get_AmountOf_Identity(),'r',Traverse_Item.Formula_Num);if (No_ErrorOccurIn_FillingTable=false)cout<<"This is not LR(0) Grammarn"exit(1);if (Traverse_Child->Next_Item!=NULL)Traverse_Child = Traverse_Child->Next_Item;elseif (Traverse_Parent->Next_State!=NULL)Traverse_Parent = Traverse_Parent->Next_State;Traverse_Child = Traverse_Paren