编译原理语法分析 LR

Sekiro

C/C++编译原理

发布于：2020年9月2日

次浏览

字数：1.1k字

时长：4分钟

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

一、需求

拓展需求：除题目的基础要求外，还额外实现了对任意SLR1文法，自动生成拓广文法，且求该文法的first集和follow集，并且自动生成LR0项目集规范簇和识别该文法所有活前缀的DFA，然后根据该DFA自动生成SLR1分析表。

二、运行环境

电脑硬件配置：

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

软件：

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

三、核心算法

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

手动分析：

首先对文法进行拓广，求first集和follow集，发现该文法是一个SLR1文法。
构造LR0项目集规范簇及识别该文法所有活前缀的DFA
构造识别该文法的SLR0分析表
整个程序的模型如图所示
预测分析控制程序算法

6、输入形式：

文件输入，格式为：

产生式个数n

{

……

第i(1<=i<=n)个产生式（例如A->a，按照输入顺序分别从1到n编号，拓广产生式为0号，规定终结符和非终结符都是一个字符且非终结符都为大写字母）

……

}

要分析的字符串个数n

{

……

第i(1<=i<=n)个要分析的字符串（要求以$结尾）

……

}

7、输出形式：

先输出该文法的拓广文法，再输出该拓广文法的first集和follow集，再输出SLR0分析表，然后输出用户输入的待分析字符串的分析过程。

四、变量和函数

1、类和枚举：

点击查看代码

enum RS//动作的枚举
{
	shift,//移进
	reduce,//规约
	accept//接受
};
//假定非终结符仅为一个大写字母，终结符仅为一个小写字母和各种符号，且用~代替epsilon
class PF//Production formula,产生式的类
{
public:
	char left;//产生式的左部
	string right;//产生式的右部
	PF(char l, string r)//构造函数
	{
		left = l;
		right = r;
	}
};
class ITEM//项目集
{
public:
	ITEM();//默认构造函数
	ITEM(int NO);//构造函数
	int NO;//项目集编号
	set<pair<int, int>> production;//项目，第一个int代表产生式编号，第二个int代表.的位置
	set<pair<char, int>> go_to;//该项目集指向的项目集，第一个char代表箭头上的字符，第二个int代表指向的项目集编号
	bool operator<(const ITEM& item)const;//重载<操作符，以便使用set
};
class action//动作类
{
public:
	action(RS rs,int num);//重写构造函数
	string ret_action();//返回该动作
	action();//初始
	RS rs;//动作
	int num;//移进到哪个状态，或者用哪个产生式规约
};

2、全局变量

点击查看代码

vector<PF> PF_vector;//产生式
map<char, set<char> > first;//first集
map<char, set<char> > follow;//follow集
set<ITEM> DFA;//DFA项目集规范簇
vector<map<char, action>> predict_table_action;//SLR1分析表action
vector<map<char, int>> predict_table_goto;//SLR1分析表goto
vector<char> A_1;//符号栈
vector<int> A_2;//状态栈
vector<char> B;//剩余串
set<char> terminal;//所有的终结符+'$'
set<char> non_terminal;//所有的非终结符
int B_point = 0, input_len = 0;//B_point为输入串指针，input_len为输入串长度

3、函数

点击查看代码

ITEM::ITEM()//默认构造函数
ITEM::ITEM(int NO)//构造函数
bool ITEM::operator<(const ITEM& item)const//重载<操作符，以便使用set
action::action(RS rs, int num) //构造函数
action::action()//默认构造函数
string action::ret_action()//返回该动作
void first_construction()//构造并输出first集
void add_follow(const char& ch1, const char& ch2)//将ch1的follow集加入到ch2的follow集中
void follow_construction()//构造并输出follow集
void DFA_construction()//构造DFA
void predict_table_construction()//构造并输出SLR1预测分析表
void print_A()//输出分析栈
void print_B()//输出剩余串
void analyse()//预测分析控制程序
int main()