# LL1 文法分析程序 **Repository Path**: Morphlng/ll1-grammar-analysis-program ## Basic Information - **Project Name**: LL1 文法分析程序 - **Description**: 编译原理实验2 （1）任给一上下文无关文法，判断是否为LL1文法 （2）若是LL(1)文法，采用预测分析法或递归下降法进行语法分析 （3）若不是LL(1)文法，判断是否有左公因子或左递归，若存在这些特点进行改造，再进一步判断是否为LL(1)文法，若是再进行语法分析，否则放弃。 - **Primary Language**: C++ - **License**: BSD-3-Clause - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 15 - **Forks**: 5 - **Created**: 2020-10-15 - **Last Updated**: 2025-12-05 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # LL1 文法分析程序 *Nie Zili* *Last updated 10.24* ## 介绍 编译原理实验2 1. 任给一上下文无关文法，判断是否为LL1文法 2. 若是LL(1)文法，采用预测分析法或递归下降法进行语法分析 3. 若不是LL(1)文法，判断是否有左公因子或左递归，若存在这些特点进行改造，再进一步判断是否为LL(1)文法，若是再进行语法分析，否则放弃。 ## 一、提取左公因子 对于形如下列的产生式集合，我们一般会进行提取左公因子的操作： 1. S->AB 2. S->ab 3. S->ac 4. A->Bd 5. B->aB 6. B->ε ### 1.1 代入最左非终结符 对于上例中的1式，其右端的第一个字符为A，为非终结符。此时不知道它与2、3式是否有相同的公因子，我们需要将5式代入4式，4式代入1式后，才能最终确定1、2、3式具有公因子a。因此在提取左公因式（包括消除左递归）时，代入最左非终结符应为第一步操作。 **【彻底修改】** 之前版本的代入函数会导致原本LL(1)文法的式子，因为多了几个终结产生式而不是LL(1)，已经彻底摒弃。下面的新版代入函数采用了“排序”的思想，将非终结符排好序，例如 A B S，规定只能够从左向右代入，这样就可以避免来回代入的问题了。 我们以伪代码描述代入过程： ```c++ for(i＝1；i<=n；i++) for(j＝1；j<=i－1；j++) { 把形如Ai→Ajγ的产生式改写成Ai→δ1γ /δ2γ /…/δkγ 其中Aj→δ1 /δ2 /…/δk是关于的Aj全部规则； } ``` ### 1.2 提取左公因式 在我们做完代入的工作之后，下面就可以开始提取左公因式了。关于提取左公因式，我认为有两点需要注意： 1. 在搜索含有左公因式的产生式时，我们应该遵循最长匹配原则。例如：S->abA|abB，那么我们应该直接提取出ab，而不是先提取a，再提取b。 2. 我们加入新生成的产生式后，要删除原有产生式，删除过程应该遵循逆向删除。例如，1、3、6式具有公因式，那么删除时应按照顺序6、3、1进行。 提取公因式的具体做法大家很熟悉了，例如： 1. S->abA 2. S->abB 则提取公因式后： 1. S->abZ 2. Z->A|B 伪代码描述如下： ```c++ while(产生式集合发生变化) { for p1 in 产生式集合 { for length in (p1右部的长度，到1) { 将p1下标记录; for p2 in 产生式集合 { // 如果左端相同，右端长度大于等于当前匹配长度，则看字符串是否相同 if(p1 != p2 && p2.left == p1.left && p2.right.length >= length) { if(p1.right[0,length] == p2.right[0,length]) { 将p2的下标记录; } } } if(记录的下标数量 > 1) { 产生式集合发生变化; 从Z-A，找到一个新的非终结符 从记录下标由大到小，构建新产生式，然后删除原本的产生式 } if(产生式集合发生变化) break; } if(产生式集合发生变化) break; } } ``` ### 1.3 删除不可达产生式 在进行完代入和提取公因式操作后，很有可能出现一些产生式变得不再可达，例如： 1. S->Ab 2. A->a 代入后结果为 S->ab，则第二个产生式成为不可达式。其对于我们判断LL(1)文法不产生影响，出于严谨我们应当将其删除。 伪代码描述如下： ```c++ stack s; // 处理栈 s.push(S); // 初始状态，s中加入开始符号S set nonterminal; // 非终结符集合 while(!s.empty()) { ch = s.top(); for p in 产生式集合 { 如果产生式左端为ch，则扫描其右端所有非终结符， 如果在非终结符集合中没有该非终结符，则将其压入栈s，并加入到非终结符集合中; } } ``` ## 二、消除左递归 左递归分为直接左递归和间接左递归，为了尽可能的减少需要区分的状态，我们在进行消除左递归前应该先调用代入函数，从而将间接左递归转化为直接左递归。 直接左递归的消除，可能有一些较为特殊的情况，下面举例说明。 例一：同一字符多个左递归式 1. S->Sa|Sb|c|d 消除后结果： 1. S->cS'|dS' 2. S'->bS'|aS'|ε 例二：多个不同字符的左递归 1. S->Sa|A 2. A->Ab|c 先对A 1. S->Sa|A 2. A->cA' 3. A'->bA'|ε 再对S 1. S->cA'S' 2. S'->aS'|ε 3. A'->bA'|ε 若先对S，则需要在消除完毕之后再次调用代入函数 考虑到以上较为特殊的情况，消除左递归的伪代码表达如下： ```c++ while(产生式集合发生变化) { for nt in 非终结符 { for p in 产生式集合 { if(p.left == nt) { if(p.right[0] == nt) 左递归集合中记录p; else 非递归集合中记录p; } } if(左递归集合大小 > 0) { 产生式集合发生变化; 从Z-A，找到一个新的非终结符; 对递归集合，构造Z->aZ，以及Z->ε; 对非递归集合，构造S->cZ; 合并递归集合与非递归集合，然后按照下标从大到小的顺序，删除原产生式; } if(产生式集合发生变化) break; } } ``` ## 三、判断LL1文法 我们采用构建预测分析表的方法来判断用户输入文法是否为LL1文法。步骤为： 1. 消除左递归 2. 提取左公因式 3. 求First集合 4. 求Follow集合 5. 求Select集合 6. 求预测分析表，如果预测分析表中某单元格指向多于一个产生式，则输入文法不是LL1文法。若所有单元格均最多指向一个产生式，则是LL1文法 ### 3.1 First集合 根据定义我们应该求每一个产生式的First集合，但是实际上我们只需要求非终结符的First集合即可，因为对于形如S->aB的产生式，其First集合就是终结符a，没有必要进行保存。 我们按照下列规则求First集合: 1. 如果X是终结符，则FIRST(X) = { X } 。 2. 如果X是非终结符，且有产生式形如X → a...，则FIRST(X) = { a }。 3. 如果X是非终结符，且有产生式形如X → ABCdEF...(A、B、C均属于非终结符且包含ε，d为终结符)，需要把FIRST(A)-ε、FIRST(B)-ε、FIRST(C)-ε、FIRST(d)加入到FIRST(X)中。 4. 如果X经过一步或多步推导出空字符ε，将ε加入FIRST(X)。 伪代码描述如下： ```c++ // 该函数应被一个for循环调用，循环中传入的target为所有非终结符 void get_First(char target) { // countEmpty用来记录表达式右端能够推出ε的非终结符个数 countEmpty = 0; for p in 产生式集合 { // 左端与目标匹配 if(p.left == target) { // 终结符直接加入 if(p.right[0]是终结符) First(target).insert(p.right[0]); // 非终结符则需逐字符求解，直到遇到终结符，或者全部能够推出ε else { for ch in p.right { // 遇到终结符停止递归 if(ch是终结符) { First(target).insert(ch); break; } // 若为非终结符，则应先求出该字符的First集合 get_First(ch); // 将First(ch)中，除ε以外的结果加入First(target) First(target)+=First(ch)-ε; if(First(ch)含有ε) countEmpty++; else break; } if(countEmpty == p.right.length()) { First(target).insert('ε'); } } } } } ``` 可以看到，First集合的求解使用的是递归方法，由于First集合的产生规则中不会出现循环递归的可能（因为左递归被我们消除了），因此这是最直观的一种求解方法。另一种完成方式是使用while循环，在求解Follow集合时我们将采取这种方法，如果First集合也想采用这种方法，可以进行参考。 ### 3.2 Follow集合 计算文法符号X的FOLLOW(X)，不断运用以下规则直到没有新终结符号可以被加入任意FOLLOW集合为止： 1. 将'#'加入到FOLLOW(X)中，其中S是开始符号，而'#'是输出右端的结束标记。 2. 如果存在一个产生式S->αXβ，那么将集合FIRST(β)中除ε外的所有元素加入到FOLLOW(X)当中。 3. 如果存在一个产生式 S->αX，或者S->αXβ且FIRST(β)中包含ε，那么将集合FOLLOW(S)中的所有元素加入到集合FOLLOW(X)中。 根据上面的规则描述，如果我们仿照First集合的求解，使用递归进行操作，那么可能会遇到如下问题： 1. A->aB 2. B->bA 则Follow(B)+=Follow(A)，Follow(A)+=Follow(B)，这将导致循环递归。又或者产生式存在右递归(A->aA)，同样会导致Follow(A)+=Follow(A)的循环递归。我们可以设置递归的最大上限来解决这个问题（实际上get_Follow_recur()函数就是这样完成的），但是更好的方法应该是避免使用递归。不使用递归的函数伪代码如下： ```c++ void get_Follow() { while(Follow集合发生变化) { for p in 产生式集合 { // 遍历产生式右端每一个字符 for ch in p.right { if(ch是非终结符) { psize = Follow(ch).size(); if(ch不是右端最后一个字符) // Follow(rj)+=First(brj) { bch = ch的后一个字符 if(bch是终结符) { Follow(ch).insert(bch); } else { Follow(ch)+=First(bch)-ε; if(First(bch)包含ε) // A->aBCD，C若能推出ε，Follow(B)+=Follow(C) { Follow(ch)+=Follow(bch); } } } else // A->aB，Follow(B)+=Follow(A) { Follow(ch)+=Follow(p.left); } if(psize != Follow(ch).size()) Follow集合发生变化; } } } } } ``` ### 3.3 Select集合 计算每个产生式的SELECT集： 1. 如果这个产生式可以推出ε，那么它的SELECT集是{FIRST(该产生式右部)-ε}∪FOLLOW(该产生式左部的非终结符)。 2. 如果这个产生式不能推出ε，那么它的SELECT集是{FIRST(该产生式右部)}。 伪代码描述如下： ```c++ for p in 产生式集合 { countEmpty = 0; // 右端全部能推出ε，则使用 Select(A->a) = First(a)-ε ∪ Follow(A) for ch in p.right { if(ch是终结符) { if(ch!='ε') { Select(p).insert(ch); } else { countEmpty++; } break; } else { Select(p)+=First(ch)-ε if(First(ch)包含ε) { countEmpty++; } } if(countEmpty == p.right.length()) { Select(p)+=Follow(p.left); } } } ``` ### 3.4 预测分析表 求得Select集合后，预测分析表就很容易构造了。预测分析表是一个以终结符作为列首，非终结符作为行首的产生式集合表，如果一个产生式的Select集合中含有终结符a，则在预测分析表以该产生式左端为行首，以终结符a为列首的单元格填写该产生式即可。举例如下： | | a | b | c | d | | :----: | :---: | :---: | :---: | :---:| | A | | | A->Bb | | | B | | | B->cC | | | C | | | | C->d | | S | S->aA | | | | 这只是一个简单的遍历赋值问题，不以伪代码展示了。 ## 四、语法分析 递归下降法我不会实现，因此这里使用预测分析法，在构造完预测分析表后这个算法实现相当容易，我们以文字描述如下： 1. 构造一个运算栈，将'#'和开始符号入栈，从输入语句中读取第一个字符a 2. 取出栈顶元素X，若X属于终结符，则走3; 若X属于非终结符，走4 3. 若X=a，则读取下一个字符，返回2; 反之则匹配错误 4. 若X是'#'，则检查当前读取字符a是否为‘#’，若是则结束，不是则匹配错误; 若X不是'#'，走5 5. 在预测分析表中查找M[X,a]是否有对应产生式，若有则将产生式右部逆序加入运算栈，走2; 反之，匹配错误。 下面有一张图可以更直观的看到整个流程（取自清华大学《编译原理第三版》P93）: