学习 bison 原理(四)
第5步: 转变第 4 步的状态机为确定的 LALR 状态机.
在(三)中我们已经看到 LR0 状态机很可能有 r/r 冲突, s/r 冲突,
那这关键的第5步就是用 lookahead(LA) 符号来试图解决 LR0 文法的
不足而导致的冲突.
程序实现在 Lalr.cs 中, 要理解这部分程序, 必须要先理解论文1给出的
概念和算法. 包括如下几个主要概念:
Direct Read 关系 (DR)
reads 关系
includes 关系
digraph -- 通过高效算法计算传递闭包(Transitive Closure)
主入口函数为 Lalr.lalr(), 其主要步骤如下:
1. 为计算 lalr 做准备工作: 建立 states[] 等数组.
2. 初始化需要 LA 的状态, 规则的数组. 建立 goto 数据,
即 (p, A) -- 从状态 p 经非终结符 A 的转移.
3. 构造 F[,] 矩阵, 根据 Direct Read, reads 关系计算出 Read.
结果在 F[,] 中.
4. 构造 includes, lookback 关系(以稀疏矩阵方式存储).
5. 根据 F, includes 关系计算出每个 (p, A) 的 FOLLOW[] 集合.
6. 根据 FOLLOW[], lookback 关系计算出每个(p, A->w) 的 LA[] 集.
再次强调的是, 要细读论文1, 因为 bison 这里使用的算法就是该文中的算法.
我刚看这里代码的时候, 无法和编译原理龙书上的东西对照起来, 以至于即使
看懂了每行代码, 可还是不能理解在做什么, 直到找到了该论文. 这里再给出链接:
http://3e8.org/pub/scheme/doc/parsing/Efficient%20Computation%20of%20LALR(1)%20Look-Ahead%20Sets.pdf
这里描述的几种关系, 矩阵, 图算法在论文中都有详细的说明, 我能理解部分,
但没有能力转述出来, 所以还是请参见原文. 另就是看看我写的代码注解, 也许
能帮助理解一点.
程序中, digraph() 函数给出了一种图的求传递闭包的高效算法, 是值得学习的.
另程序中 Warshall.TC(), Warshall.RTC() 也是求传递闭包的, 但是时间复杂度
是 O(n^3), 所以可以参照对比来学习的.
在求取出 LA 之后, 剩下的问题是解决仍然存在的冲突了, 位于文件 Conflicts.cs 中.
那里 %prec 指定的优先级, %left, %right, %nonassoc 指定的结合性就在那里发生效用,
尤其是对表达式中的各种运算符. 这里能够帮助我们理解为何会产生冲突, 而解决方法则
可以建立在对冲突的本质原因的深刻理解的基础上.
在之后, 程序输出可能的冲突提示/解决信息, 及或一个解析器的代码. 这些略(cs 中也没有
写这些了). 需要了解的要去看 bison c 的源代码. 但我略略的看了一下 bison 2.65
似乎里面还可以输出状态的图形化表示? 以及 xml, json 格式的? 实在没有仔细了解.
但是如果真能如此, 那真是更方便了使用者了, 真是又进几大步了......
下面给出我改写的 c# 的代码, 供大家参考. 如果前后有不一致的地方, 请多谅解, 因为
看前面的时候总有不理解的地方, 就会打问号乱理解的...