编译原理实验二：LL(1)语法分析器 |
您所在的位置：网站首页 › 求follow集需要消除左递归吗 › 编译原理实验二：LL(1)语法分析器 |
编译原理实验二：LL(1)语法分析器
|
一、实验要求
1. 提取左公因子或消除左递归（实现了消除左递归） 2. 递归求First集和Follow集 其它的只要按照课本上的步骤顺序写下来就好（但是代码量超多...），下面我贴出实验的一些关键代码和算法思想。 二、基于预测分析表法的语法分析 2.1 代码结构 2.1.1 Grammar类功能：主要用来处理输入的文法，包括将文法中的终结符和非终结符分别存储，检测直接左递归和左公因子，消除直接左递归，获得所有非终结符的First集，Follow集以及产生式的Select集。 #ifndef GRAMMAR_H #define GRAMMAR_H #include #include #include #include #include #include #include using namespace std; const int maxn = 110; //产生式结构体 struct EXP{ char left; //左部 string right; //右部 }; class Grammar { public: Grammar(); //构造函数 bool isNotTer(char x); //判断是否是终结符 int getTer(char x); //获取终结符下标 int getNonTer(char x); //获取非终结符下标 void getFirst(char x); //获取某个非终结符的First集 void getFollow(char x); //获取某个非终结符的Follow集 void getSelect(char x); //获取产生式的Select集 void input(); //输入文法 void scanExp(); //扫描输入的产生式，检测是否有左递归和左公因子 void remove(); //消除左递归 void solve(); //处理文法，获得所有First集，Follow集以及Select集 void display(); //打印First集,Follow集,Select集 void debug(); //用于debug的函数 ~Grammar(); //析构函数 protected: int cnt; //产生式数目 EXP exp[maxn]; //产生式集合 set First[maxn]; //First集 set Follow[maxn]; //Follow集 set Select[maxn]; //select集 vector ter_copy; //去掉$的终结符 vector ter; //终结符 vector not_ter; //非终结符 }; #endif 2.1.2 AnalyzTable类功能：得到预测分析表，判断输入的文法是否是LL(1)文法，用预测分析表法判断输入的符号串是否符合刚才输入的文法，并打印出分析过程。 #ifndef ANALYZTABLE_H #define ANALYZTABLE_H #include "Gramma.h" class AnalyzTable:public Gramma { public: AnalyzTable(); void getTable(); //得到分析表 void judge(); //判断是否是LL(1)文法 void analyExp(string s); //分析输入串 void displayTable(); //打印表 void inputString(); //输入符号串 ~AnalyzTable(); protected: string s; //符号串 vector stack; //分析栈 vector left; //剩余输入串 int detect[maxn][maxn]; //检测表 int table[maxn][maxn]; //预测分析表 }; #endif 2.2 记号和规定非终结符：大写字母'A'~'Z' 终结符：除大写字母之外的所有字符 空串：$ 符号栈终止符：# 规定第一个产生式的左边那个非终结符就是开始符号 输入的产生式需要分开写(比如A->a|b, 要输入A->a和A->b才能处理) 2.3 算法思想 2.3.1 求First集的算法思想遍历每一个左部为x的产生式 如果产生式右部第一个字符为终结符，则将其计入左部非终结符的First集 如果产生式右部第一个字符为非终结符 求该非终结符的First集 将该非终结符的去掉$的First集计入左部的First集 若存在$，继续往后遍历右部 若不存在$，则停止遍历该产生式，进入下一个产生式 若已经到达产生式的最右部的非终结符（即右部的First集都含有空串），则将$加入左部的First集 处理数组中重复的First集中的终结符//求出非终结符的First集 void Gramma::getFirst(char x){ cout=0;i--){ left.push_back(s[i]); } //把#和开始符push进分析栈 stack.push_back('#'); stack.push_back(not_ter[0]); //如果剩余输入串长度不为0，就一直循环 while(left.size()>0){ //输出分析栈内容 string outputs = ""; for(int i=0;i |
【本文地址】