基于C++实现LR1语法分析程序

# LR1语法分析 *Last Updated 11.28 by Nie Zili* ## 一、数据结构简介 该项目采用面向对象的思想设计数据结构，共设有6个类，其递进关系如下： 1. pstring，产生式类。定义了LR1所需的产生式结构，包含“点位置”与“展望字符” 2. Grammar，文法类。主要用来保存产生式集合，用于最开始用户输入的文法 3. Node，节点类。继承自Grammar，除了一个产生式集合以外，定义了“节点标号”与“分界下标”，“分界下标”的意义是区分原产生式与求闭包后加入的产生式，这样在检查是否需要添加新节点时只需要检查[0,分界处)的部分即可。 4. Edge，边类。包含Node类型的开始与结束节点，还有一个string类型的转换字符 5. DFA，项目集类。包含一个Node集合与一个Edge集合。 6. Table，预测分析表类。包含一个DFA和一个Map集合，表示状态转换。需要用DFA来构造 ## 二、 产生式类pstring 数据成员结构如下： ```c++ class pstring { protected: string left; // 产生式左部 string right; // 产生式右部 int dot; // ·的位置 int No; // 产生式编号 bool valid; // 产生式是否有效（仅用于初始化） string prospection; // 展望字符 } ``` 产生式由用户输入，形如“S-Ab”。对于LR1语法分析过程中需要用到的`·`与`展望字符`做了定义： 1. “·”不显式的插入产生式中，仅用下标表示其所在位置。例如，S-·Ab，则int dot=0，·后字符即，’A’ right[dot]。点的移动使用函数shift_dot() 2. 展望字符使用string类型存储（该项目中几乎都使用string，方便做可能的扩展） 3. pstring类型对`==`做了重载，两个产生式相同的条件为：左部相同、右部相同、展望字符相同、点位置相同。由于此处的规定较为严格，所以在后面规约时不能够使用`==`，只需要匹配左部右部相同即可 ## 三、文法类Grammar 数据成员结构如下： ```c++ class Grammar { protected: vector<pstring> productions; // 产生式集合 string s; // 开始字符 set<string> Vn; // 非终结符集 set<string> Vt; // 终结符集 map<string,set<char>> first_set; // First集 } ``` 文法即产生式集合，提供了手动初始化函数`init()`和从文件读入方式`init_from_file()`，后者将在简单计算器项目中使用。 创建一个文法的正确调用顺序如下： ```c++ int main() { Grammar g; g.init(); // 初始化 g.extent(); // 求扩展文法 g.cal_First(); // 计算First集合 } ``` `cal_First()`用于求取该文法中非终结符的First集合，存储与一个map中。求First集合的意义在于之后对节点求闭包时确定展望字符，在Node中介绍。 此处的计算First集合采用while循环方式，类似于[LL1](https://gitee.com/Morphlng/ll1-grammar-analysis-program/blob/master/Grammar.cpp)中求Follow的方法，因此不会因为左递归而无限循环 ## 四、节点类Node 数据成员结构如下： ```c++ class Node: public Grammar { protected: int number; // 节点编号 int divide_index; // 原始产生式与闭包的分界处 } ``` Node继承于Grammar，但事实上我们只需要产生式集合，Grammar的其余结构并不需要。其数据成员中的`divide_index`表示“原始产生式与闭包的分界”，具体来说就是记录求闭包之前的产生式数量，这样在比较两个节点是否相同时可以只比较`divide_index`之前的部分，减少运算量。 关键的函数是`get_closure()`求取闭包，下面用伪代码描述流程： ```c++ while(产生式集合发生变化) { for p in productions { // 需要添加新的产生式 if(产生式p的·后有字符 && 该字符为非终结符) { ch = p.right[dot]； // 如果当前字符为产生式末尾，则直接以当前产生式的展望字符作为新产生式的展望字符。 prospections = p.get_prospection(); // 如果当前字符不是产生式末尾，则需要对后面求First，确定展望字符集 if(ch不是产生式末尾) { bch = p.right.substr(dot+1) + p.get_prospection(); prospections = get_First(bch); } 将以ch为左端的产生式，以prospections中的字符作为展望字符，添加到产生式集合中。 } } if(产生式集合大小发生变化) 产生式集合发生变化; } ``` 在具体实现时，对流程中的一些细节做了优化，比如我们不是每次都从头遍历产生式集合，而是从上一次的结束位置开始。 在求闭包时有一步求后部产生式First集合来确定展望字符的过程，下面举例说明： 产生式为`S-·ABCd，#`，则点后字符为A，A后部为BCd#，我们需要求First(BCd#)，来获取将加入的以A为左部的产生式的展望字符。 如果First(B)含有空串，则继续看First(C)，直到遇到一个终结符或者First集合不再有空串。 ## 五、边类Edge 数据成员结构如下： ```c++ class Edge { private: Node Start; Node End; string trans; } ``` ## 六、DFA类 数据成员结构如下： ```c++ class DFA { private: vector<Node> node_set; vector<Edge> edge_set; Grammar G; } ``` DFA需要由一个Grammar初始化，之后只需要调用`cal_dfa()`即可。 `cal_dfa()`函数的伪代码描述如下： ```c++ while(加入新边) { for node in 节点集合 { 转移字符集 = 遍历node的产生式集合，找到所有“·”后字符; } for ch in 转移字符集 { 新建节点new_node; for p in node的产生式集合 { 如果p.right[dot] == ch，则向new_node中加入向右移点后的p; } new_node.get_closure(); add_node(new_node); 新建边new_edge; new_edge.Start(node); new_edge.End(new_node); new_edge.trans(ch); if(add_edge(new_edge)) { 加入新边; } } } ``` 这里面`add_node`和`add_edge`函数在添加之前都会查重，因此仅当成功加入边之后才再次循环。 ## 七、预测表类Table 数据成员结构如下： ```c++ class Table { private: vector<map<string,string>> table; DFA graph; } ``` 预测表的抽象结构如下： | | 终结符0 | 终结符1 | # | ... | 非终结符0 | 非终结符1 | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | 状态0 | Sx | | | | m | n | | 状态1 | | r1 | | | | | | 状态2 | | | acc | | | | 代码中用vector的下标表示状态n（DFA一个节点对应一个状态），map表示该状态下一个符号对应的动作。 用DFA初始化一个Table之后，遍历Edge集合计算移入，遍历Node集合计算规约即可。 `predict(string input)`是本项目中用来检查一个输入串是否通过语法分析的函数，在简单计算器项目中将使用另外一个实现语法分析（语义分析），不详述了。