编译原理：基础算法逻辑实现LL（1）的第一部分

实验二：语法分析器

实验名称：LL(1)语法分析器（1）
完成时间：2020.5.8

代码上传了，免费下载，看下我上传页面能不能找到

(1) 语法分析器概述（主要介绍完成的语法分析器的主要功能，使用场景和限制条件）
 实现的主要功能：
对输入的CFG文法消除显式、隐式左递归，提取左因子
 使用场景：
语法分析器第一阶段
 限制条件：对于有些死循环的文法无法使用
(2) 语法分析器使用手册（主要介绍采用软件运行环境、数据准备、使用方法和限制条件）
 软件运行环境：
C++14
 数据准备：
准备文法文法式子若干，其格式为：
将课堂上讲的文法式子中的箭头符号变为冒号‘:’方便识别，不同文法式子用分号‘;’分隔开，或符号‘|’，空符号希腊字母变为‘@’符号，方便读取。每个字符中间不允许有空格！
形如：S:AdD|@;A:aAd|@;D:DdA|b|@;
 使用方法：
在测试文件“test.txt”中输入文法，直接run
 限制条件：有些死循环的文法可能无法使用
(3) 功能分析（主要介绍采用数据结构和设计理由，以及各算法功能；对得意部分请着墨）
 数据结构：

CFG数据结构
说明：根据上课做题中题目的规律，一个文法可以分为：终结符，非终结符，以及每个非终结符对应的产生式，所以CFG数据结构就由这几部分构成，为了编程方便加上了终结符数量、非终结符数量、产生式数量还有文法开始符号start。
这几个属性中别的都用基础数据类型可以表示，只有产生式比较复杂，我的存储方法是将每一个产生式中“|”分隔开的式子都单独存放，形成一个string类型数组element，数组中每个元素即为一个单个的产生式。用length表示用或运算符号“|”隔开的所有产生式的个数。

 核心算法功能：
initCFG函数：
作用是将输入的文法语句转化为CFG数据结构，文法的处理举实例说明，比如对于文法“S:AdD|@;A:aAd|@;D:DdA|b|@;”：
第一步：根据分号将几个文法式子分为几个部分，每个部分为一个产生式数据结构
第二步：将获取到的单个非终结符的产生式，比如：“S:AdD|@”，将开头字母存下，将前两位非终结符和冒号删除，剩余部分根据或符号“|”分为多个部分“AdD”、“@”
第三步：对于每个单个产生式（或运算中的单个因子）调用saveNewProduction函数，该函数作用是将产生式存入对应位置，其过程是，先将单个产生式中所有未在终结符和非终结符中出现过的字母存入终结符集合，然后对比该产生式的开始符号是否已在非终结符集合中存在，如果存在则合并入已存在的产生式中，如果该产生式的开始符号不存在于非终结符集合，要存入cfg该式子中各项终结符，非终结符以及产生式，同时查找该式子的开始符号是否在终结符集合中，如果是要拿出来。
elminAllLeftRecur函数
该函数用来去除所有左递归，包括显式和隐式，去除隐式左递归建立在去除显式左递归的基础上，所以先完成了elminOneLeftRecur函数，是消除一个非终结符对应的产生式中的显式左递归的函数。
消除显式左递归的算法思想很简单，实现主要就是在于字符串的拼接，因为string获取最左元素或者拼接都很方便，所以只要把情况考虑完整就实现成功了。
隐式左递归的显化思想是：在对于当前产生式中，查看已经检查过的非终结符的产生式是否对当前产生式造成间接左递归，如果是就处理一下将已经遍历过的代进来就处理好了，然后再调用处理显式左递归的函数即可。
elimnAllLeftFactor函数：
这个函数用来消除所有左因子，重难点是求左因子，我只想到了两个字符串求最长公共前缀的函数getLongestPremix，这样也可以用for循环实现获得整个产生式的最长前缀，用函数getLeftFactor，这样获取了左因子之后，对于数据结构cfg的修改也仅限于字符串的拼接，与新节点建立等基础操作，只要考虑清楚多种情况即可。
(4) 测试概述
① 测试用例的设计方案
用了4个测试用例：均是ppt上的例题
S:Aa|b;A:Ac|Sd|@
A:aABj|a;B:Bb|d
M:MaH|H;H:b(M)|(M)|b
S:AdD|@;A:aAd|@;D:DdA|b|@
② 测试结果
包括生成的cfg显示，处理左递归过程，消除左递归结果，提取左因子结果
S:Aa|b;A:Ac|Sd|@ 结果1：

A:aABj|a;B:Bb|d结果2：

编译原理：基础算法逻辑实现LL（1）的第一部分

相关推荐