编译原理：C++构造简单的LL(1)语法分析器 |
您所在的位置：网站首页 › 编译原理实验二语法分析LL(1) › 编译原理：C++构造简单的LL(1)语法分析器 |
|
以下为个人实验代码，肯定有疏忽遗漏之处，欢迎大家一起交流探讨www~ 参考资料：编译原理实验二：LL(1)语法分析器 - Chris-Zhang - 博客园 项目文件：main.cpp,LLdefine.h,LLfun.cpp 项目源代码详见资源：LLone.zip（简单的LL(1)语法分析器）-C/C++文档类资源-CSDN下载 程序功能：用户输入文法，消除直接左递归（不包括间接左递归），计算FIRST和FOLLOW集，生成分析表，判断用户输入句子是否符合文法。 运行结果： Please enter VN:E F T Please enter the start VN:E Please enter VT:+ * ( ) i Please enter Grammar(empty:@,end with #): E->E+T|T T->T*F|F F->(E)|i # *****check Left Recursion***** direct Recursion is found in 'E->E+T'.Grammar has changed. direct Recursion is found in 'T->T*F'.Grammar has changed. *****First Set***** E : ( i F : ( i T : ( i E' : + @ T' : * @ + : + * : * ( : ( ) : ) i : i *****Follow Set***** E : # ) F : # ) * + T : # ) + E' : # ) T' : # ) + *****Analytical Table***** + * ( ) i # E E->TE' E->TE' F F->(E) F->i T T->FT' T->FT' E' E'->+TE' E'->@ E'->@ T' T'->@ T'->*FT' T'->@ T'->@ Please enter a sentence:98+99+90 *****Analyse the sentence***** Analytical Stack Rest Sentence Grammar Used #E i+i+i# E->TE' #'ET i+i+i# T->FT' #'E'TF i+i+i# F->i #'E'Ti i+i+i# #'E'T +i+i# T'->@ #'E +i+i# E'->+TE' #'ET+ +i+i# #'ET i+i# T->FT' #'E'TF i+i# F->i #'E'Ti i+i# #'E'T +i# T'->@ #'E +i# E'->+TE' #'ET+ +i# #'ET i# T->FT' #'E'TF i# F->i #'E'Ti i# #'E'T # T'->@ #'E # E'->@ # # Success:The sentence belongs to the grammar.1、数据结构说明 构建LL(1)语法分析器可分为五部分。第一部分为用户输入文法的若干规则，生成文法；第二部分为检测左递归（此处只检测直接左递归），若识别到直接左递归，则对文法进行变换；第三部分为求解FIRST集和FOLLOW集；第四部分为构建LL(1)分析表；第五部分为用户输入句子，构建分析栈和余留字符串栈，对句子的合法性进行分析。 因此建立类LLone，以封装存储终结符、非终结符、文法规则等数据，同时建立成员函数实现上述各部分功能。同时，为了方便存储文法规则，建立结构体grammar，将一条规则的左部和右部分开存放，便于后续程序功能的实现。结构体和类的定义如下所示： #pragma once #include #include #include #include #include #include #include using namespace std; //文法结构体 struct grammar { string left; //左部 vector right; //右部 }; //LL(1)类 class LLone { public: vectorvt;//终结符 vectorvn;//非终结符 setvt_s; setvn_s; string start; string usr_in; vectorproduction;//产生式集合 mapfirst;//first集 mapfollow;//follow集 settoEmpty;//vn能否推出空 setisFirst;//是否已求过first集 mapvnTnum;//vn在分析表中下标 mapvtTnum;//vt在分析表中下标 vector < vector> table;//分析表 stackana; //分析栈 stacksen; //余留输入串 void getInfo();//获取vt,vn,grammar void checkLRE();//检测并消除左递归 void allFirst();//获取全部First集（外部接口） int getFirst(string vn_f);//递归获取First集 void allFollow();//获取全部Follow集（外部接口） void printFirst();//打印First集 void printFollow();//打印Follow集 void makeTable();//构建LL(1)分析表 void printTable();//打印分析表 void usrInput();//获取用户输入的句子 void analyse();//分析句子 void printStack();//打印栈的内容 };2、算法分析过程 （1）识别用户输入的若干文法规则，并生成文法 由于用户输入的文法规则为字符串，程序无法区分终结符、非终结符等字符，因此需要用户在输入规则之前，先输入文法中出现的所有终结符和非终结符。因为后续构造FOLLOW集和分析栈时，初始化都需要使用开始符号，因此也需要用户告知文法中的开始非终结符。在上述信息采集完毕后，用户再输入文法规则，由于空符号串ε难以输入，因此程序中用’@’进行替代。程序识别一条规则时，将其拆分成左部和右部，左部用一个string存储，删除字符串中“->”后，识别右部，以识别到“|”为分割，将多个右部加入到vector中。又因为规则数量未知，因此规则的输入以’#’作为结尾。
（2）检测直接左递归，并将其转换 含直接左递归的文法规则形如A::=Aa|b，可以通过引入一个新的非终结符A’来消除左递归。引入A’，将A::=Aa|b可等价写成 A::=bA’ A’::=aA’|ε 由此可以消除直接左递归。因而对vectorproduction中存储的所有文法规则进行遍历，若任一右部第一个字符等于左部，则说明发现直接左递归。接着在左部的基础上加入’\’’，构成新的非终结符（防止与其他非终结符重名，所以采用这种方式），按上述规则对该条文法进行改写。将A形如Aa的右部改写成aA’|ε添加到A’的右部中，同时在A的右部中删去。再将A所有形如b的右部改写成bA’，完成左递归的消除。 （3）求解FIRST集和FOLLOW集 求解FIRST集 在已消除直接左递归的基础上，对文法求FIRST集。对于文法中的每一个文法符X∈(VN∪VT)，构造FIRST(X)时，只要连续使用下列规则，直至FIRST集不再扩大为止。 ·若X∈VT，则FIRST(X)={X}。 ·若X∈VN，则有形如X::=aα规则（a∈VT），或X::= ε的规则，把a或ε加入FIRST(X)中。 ·设文法G中有形如X::Y1Y2…Yk的规则，若Y1∈VN，则将FIRST(Y1)中一切非ε符号加进FIRST(X)中，对于一切2 α”。 ·把M中所有不能按上述两条规则定义的元素均置为出错。 因此，可按上述三条规则构建行数为非终结符数、列数为终结符数加1（加上#）的分析表M。 （5）分析用户输入句子 首先读入用户输入的字符串，对于算术文法，若用户输入字符串中包含数字，则将一整个数字替换成终结符’i’。例如：用户输入98+99+80，则程序将其处理为i+i+i。 接着建立两个堆栈，分析栈和余留字符串栈。初始化两个堆栈，对于分析栈，分别将#和开始符号E压入栈；对于余留字符串栈，先压入#，再逆序将处理后的用户输入字符串压入栈。接着读取两个栈的栈顶，查LL(1)分析表，若查得文法规则，则将分析栈的栈顶pop出，将文法规则的右部逆序压入分析栈。若没有查得规则，则报错退出，说明输入的句子不属于该文法。循环上述过程，若两个栈栈顶元素相同，则消去，进行下一轮循环；若两个栈栈顶元素均为终结符，且不相等，则报错退出。若循环结束后，两个栈中元素的数量均为0，则说明该句子能被文法所接收，匹配成功。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |