编译原理语法分析 LL1

Sekiro

C/C++编译原理

发布于：2020年9月2日

次浏览

字数：1.6k字

时长：6分钟

本文是编译原理C语言LL1语法分析器的简单实现项目。

一、需求

拓展需求：还能自动够造LL1文法的first集和follow集，为LL1文法自动构造预测分析表。

二、运行环境

电脑硬件配置：

处理器：Intel i7 7700HQ
显卡：NVIDIA GeForce GTX 1050 Ti
内存：16GB

软件：

编程语言：C++
IDE：Microsoft Visual Studio 2019
Windows SDK版本：10.0
平台工具集：Visual Studio 2019（v142）

三、核心算法

1、整个程序的模型如图所示

分析栈、分析表的数据结构详见【变量和函数】。

2、first集的构造

使用深度优先遍历递归的方法，当遍历完所有的非终结符的产生式右部，first集构造完成。详见注释。

点击查看代码

3、follow集的构造

不能采用深度优先遍历的方法，否则求给出的测试样例【其它文法1】会无限循环，因为非终结符之间的follow集是互相依赖的，因而采用了另一种方法解决了这个问题。就是无限循环求所有非终结符的follow集，直到所有的follow集都不再增大为止，跳出循环。详见注释。

点击查看代码

4、预测分析表的构造算法

利用课本上的算法4.2

5、预测分析控制程序算法

利用课本上的算法

但是该算法有点小瑕疵，就是最后while循环的出口判断条件有问题，不应该是只是【栈顶文法符号X不为‘$’】，而应为【栈顶文法符号X不为‘$’&&所指向的输入符号a不为‘$’】。

6、输入形式：

先输入文法的产生式个数，然后输入产生式，该文法必须为LL1文法（消除左递归和左公因子），然后输入1或0，决定是否要进行分析，然后再输入要分析的字符串，该字符串需要用i代表数字，以‘$’结尾。
输入的文法默认第一个输入的产生式的左部为起始符，非终结符仅为一个大写字母，终结符仅为一个小写字母和各种符号，且用~代替epsilon,且输入的文法必须满足LL1文法的条件。输入的要分析的字符串需要用i代表数字，以‘$’结尾。我认为没有必要把i也就是题目中的num细化为数字，因为这些操作已经在词法分析中完成了，语法分析只需完成分析类似于这种字符串的输入是否被接受就可以了。

7、输出形式：

先输出该文法的first集和follow集，再输出该文法的LL1预测分析表，最后输出用户输入的待分析字符串的分析过程

四、变量和函数

1、类

点击查看代码

class PF//Production formula,产生式的类
{
public:
	string left;//产生式的左部
	set<string> right;//产生式的右部
	PF(char s[])//构造函数，确定产生式左部
	{
		left = s;
	}
	void insert(char s[])//插入产生式右部的函数
	{
		right.insert(s);
	}
};

2、全局变量

点击查看代码

vector<PF> PF_vector;//产生式
使用一个vector数组，每个元素为PF类的对象，来存放输入的产生式。
map<string, set<char> > first;//first集
map<string, set<char> > follow;//follow集
使用了map哈希key的类型为string，存放产生式的左部，value的类型为char的set,用来存放对应key的first集和follow集。
vector<map<char, string>> predict_table;//LL1分析表
//使用一个vector数组，每个元素为一个map，该vector的每一个map分别对应PF_vector中每个产生式的左部的非终结符所在的预测分析表的行，map的key为终结符，value为对应表项中的产生式的右部
vector<char> A;//分析栈
vector<char> B;//剩余串
map<string, int> PF_map;//存储每个非终结符对应的编号，key为非终结符，value为编号
vector<char> letter;//所有的终结符,在构造预测分析表的时候创建完毕
int B_point = 0, input_len = 0;//B_point为输入串指针，input_len为输入串长度

3、函数

点击查看代码

//first集的构造：
void first_construction() //构造并输出first集
void DFS(int x)//为构造first集深度优先遍历PF，递归调用

//follow集的构造：
void follow_construction()//构造并输出follow集
void add_follow(const string& str1, const string& str2)//将str1的follow集加入到str2的follow集中

//预测分析表的构造：
void predict_table_construction()//构造并输出LL1分析表
bool check_first(const string& str, char ch)//检查ch是否属于str的FIRST集合
bool check_follow(const string& str, char ch)//检查ch是否属于str的FOLLOW集合

//预测分析控制程序：
void analyse()//预测分析控制程序
void print_A()//输出分析栈
void print_B()//输出剩余串

//主函数：
int main()

PS：关于每个函数内部详细实现详见main.cpp中写好了详细的注释，我几乎对每一步操作的目的和函数的目的都写了详细的注释。

五、测试样例：

这个语法分析程序普适性较高，不仅对课本上的算数运算文法能实现求first集和follow集，自动生成预测分析表，以及对字符串进行分析，还对几乎所有的LL1文法都可以实现，只要输入的文法按照【核心算法】中的【输入形式】的要求即可。

在这里我以课本上的算数运算文法为例。其它文法1为follow集循环依赖文法（求follow集不可以用递归求，否则该文法会无限循环），其它文法2为起始符可推空文法（如果不按严格算法4.2构造分析表，也就是作业中把A->~产生式加入到A的follow集所对应的终结符的表项中的做法其实是不准确的，而应把A可以推空的产生式加入到A的follow集所对应的终结符的表项中，否则就会导致无法识别某些字符串的错误，例如其它文法2就是无法识别空串的错误，但该文法确实可以识别空串）。