/grammar

基于java的词法分析器-支持LL(1)语法分析、LR(1)语法分析

Primary LanguageJava

grammar

基于java的词法分析器-支持LL(1)语法分析、LR(1)语法分析

LL(1)语法分析-构造预测分析表

算法基础

输入：文法G

输出：分析表M

步骤：

  1. 对G中任意一个产生式 A --> α 执行第2步和第3步
  2. for 任意a ∈ First(α)，将 A --> α 填入M[A,a]
  3. if ε ∈ First(α) then 任意a ∈ Follow(A)，将 A --> α 填入M[A,a]
  4. 将所有没有定义的M[A,b] 标上出错sync标志

类设计

  1. Symbol类 -> 标识符类

定义变量：

  • c: 存储读入字符
  • isTerminator: 判断是否为终结符
  • END: 特殊结尾符号
  • EMPTY: 特殊空符号
  • 定义方法：
  • toString: 转换函数
  • isNonTerminator: 返回是否为非终结符
  1. Terminator类 -> 终结符类

继承Symbol类变量与方法

  1. NonTerminator类 -> 非终结符类 继承Symbol类变量与方法

  2. Rule类 -> 文法分析类

定义变量：

  • SYNC : 错误标识
  • Lhs : ‘->’左部符号
  • Rhs：’->’ 右部符号表
  • 定义方法：见代码
  1. Grammar类

综合聚合了符号表规则、终结符与非终结符、符号表、起始符、文法规则元素，将输入符号串分为终结符与非终结符，方便后续分析处理，同时将一个句子按照‘->’左右分为lhs与rhs两个部分。

算法设计

first集计算

每次扫描时都将集合中非终结符已有的终结符first集加入，非终结符也加入，如果加入的非终结符与当前的字符相等，将其删除，避免死循环。

空处理：

如果当前非终结符可以推空，则向后扫描rhs中的下一个字符，如果一直扫描至整个句子的末尾，则我们可以知道当前非终结符的first集中有空；如果扫描到终结符停止，则将这个终结符加入到当前字符的first集中。

后续处理：

在处理空的时候我们会发现，实际上的first集并不止是看当前可退的符号集那么简单，如果当前符号的first集中的非终结符可推空，那么它的first集需要再考虑此非终结符后的终结符，这样我们实际上求的是first(rhs)。

follow集计算

follow集计算实际实现较为复杂，书上给的算法基本是人眼看出来的，实际设计时需要考虑多种条件，幸运的是我们已经有了可以求一条产生式的first集算法。步骤如下：

  1. 将$加入到起始元素的follow集中
  2. 逐文法扫描，如果扫描到非终结符，则将下一个符号的first集加入到当前非终结符的follow集中，且继续看下一位的first是否包含空.
  3. 如果first集包含空，继续向后扫描（注意这里可以直接将空消掉）
  4. 否则将当前lhs字符的follow集加入到该非终结符中。

实验结果

输入所给文法：

1.	private static Grammar g1 =  
2.	            new Grammar(Set.of(E, T, B, A, F, mul, divide, plus, minus, e, n, lb, rb), E, Set.of(r1, r2, r3, r4, r5, r6, r7, r8, r9, r10));  
3.	  
4.	public static void main(String[] args) {  
5.	        Printer.printLLTable(LLAnalysis.analysis(g1));  
6.	}

即可得到预测分析表

LL(1)预测分析程序

算法基础

步骤：

  1. 如果 X = a = $ 则分析成功并停机
  2. 如果 X = a != $ 则弹出栈顶符号X, 并将输入指针移到下一个符号上
  3. 如果 X != a，查询分析表M[X,a] , 如果 M[X,a] = {X --> ABC}， 则用ABC (A在栈顶) 替换栈顶符号 X。如果 M[X,a] = error或空， 则分析器调用错误处理程序。

算法设计

设计输入栈与状态栈，首先将$放入栈中，再将起始状态、输入字符串分别放入，接着根据我们的预测分析表，当X ！= a时如果找到相应规则则按规则进行分析，否则进行错误处理，若二者相等，则弹出并将指针后移。

LR(1)语法分析-识别所有活前缀的DFA

算法设计

首先拓广文法，如果I是拓广文法G‘的一个项目集，定义和构造I的闭包CLOSURE(I)，若A->α · Bβ属于CLOSURE(I)，则每一形如B-> · r的项目也属于CLOSURE(I)。循环终止条件是项目集不再扩大。

只需要首先定义flag -> changed = false每次添加都使其变为true，下一次循环重置，当某次扫描时没有发生变化，则可跳出循环。

LR(1)语法分析-分析程序

算法设计

基本思路如下：

初始化，初始状态S0在分析栈栈顶，输入串W#的第一个符号读入a中。

while( ACTION[S,a] != acc)
{ if( ACTION[S,a] == Si)
    {状态i和输入符号a进栈；将下一个输入符号读入a中；}
  else if (ACTION[S,a] == rj)
            { 用第j条规则A –> a 归约；将|a|个状态和|a|个输入符号退栈；当前栈顶状态为S’，将A和GOTO[S’，A] = S’’进栈；
  Else if(ACTION[S,a]==ERROR) error();
}

实验总结

LR分析相比LL（1）更具有难度，在求闭包和goto转换函数时需要经常少考虑，经过多次debug最终收获了成功。在实验中也可以看到，书本上的状态栈中的符号栈实际上已经蕴含在了输入与状态栈的分析中，所以不需要另外单开栈用于存储。 最后在状态的输出上也下了一些功夫，建模在了LRResult中，使得其不影响正确性也保证了其他建模的完备性。

北邮编译原理的课程实验，自己从零写了一份，感觉还挺有意思，加深了课程理解，仅供参考。

-Giria