基于虎书实现LALR(1)分析并生成GLSL编译器前端(C#)

基于虎书实现LALR(1)分析并生成GLSL编译器前端(C#)

为了完美解析GLSL源码，获取其中的信息（都有哪些in/out/uniform等），我决定做个GLSL编译器的前端（以后简称编译器）。

以前我做过一个CGCompiler，能自动生成LL(1)文法的编译器代码(C#语言的)。于是我从《The OpenGL ® Shading Language》（以下简称"PDF"）找到一个GLSL的文法，就开始试图将他改写为LL(1)文法。等到我重写了7次后发现，这是不可能的。GLSL的文法超出了LL(1)的范围，必须用更强的分析算法。于是有了现在的LALR(1)Compiler。

起源

《现代编译原理-c语言描述》（即"虎书"）中提供了详尽的资料。我就以虎书为理论依据。

虎书中的下图表明了各种类型的文法的范围。一般正常的程序语言都是符合LALR(1)文法的。

由于LR(0)是SLR的基础，SLR是LR(1)的基础；又由于LR(1)是LALR(1)的基础（这看上去有点奇怪），所以我必须从LR(0)文法开始一步一步实现LALR(1)。

输入

给定文法，这个文法所描述的语言的全部信息就都包含进去了。文法里包含了这个语言的关键字、推导结构等所有信息。这也是我觉得YACC那些东西不好的地方：明明有了文法，还得自己整理出各种关键字。

下面是一个文法的例子：

 1 // 虎书中的文法3-10 2 <S> ::= <V> "=" <E> ; 3 <S> ::= <E> ; 4 <E> ::= <V> ; 5 <V> ::= "x" ; 6 <V> ::= "*" <E> ; 

下面是几个符合此文法的代码：

 1 x 2 *x 3 x = x 4 x = * x 5 *x = x 6 **x = **x 

输出

输出结果是此文法的 编译器代码(C#) 。这主要是词法分析器和语法分析器两个类。

之后利用C#的 CSharpCodeProvider 和反射技术来加载、编译、运行生成的代码，用一些例子（例如上面的*x = x）测试是否能正常运行。只要能正常生成语法树，就证明了我的LALR(1)Compiler的实现是正确的。

例如对上述文法的示例代码，LALR(1)Compiler可以dump出如下的语法树：

   1 (__S)[S][<S>]  2  └─(__E)[E][<E>]  3      └─(__V)[V][<V>]  4          └─(__xLeave__)[x][x]  5 (__S)[S][<S>]  6  └─(__E)[E][<E>]  7      └─(__V)[V][<V>]  8          ├─(__starLeave__)[*]["*"]  9          └─(__E)[E][<E>] 10              └─(__V)[V][<V>] 11                  └─(__xLeave__)[x][x] 12 (__S)[S][<S>] 13  ├─(__V)[V][<V>] 14  │  └─(__xLeave__)[x][x] 15  ├─(__equalLeave__)[=]["="] 16  └─(__E)[E][<E>] 17      └─(__V)[V][<V>] 18          └─(__xLeave__)[x][x] 19 (__S)[S][<S>] 20  ├─(__V)[V][<V>] 21  │  └─(__xLeave__)[x][x] 22  ├─(__equalLeave__)[=]["="] 23  └─(__E)[E][<E>] 24      └─(__V)[V][<V>] 25          ├─(__starLeave__)[*]["*"] 26          └─(__E)[E][<E>] 27              └─(__V)[V][<V>] 28                  └─(__xLeave__)[x][x] 29 (__S)[S][<S>] 30  ├─(__V)[V][<V>] 31  │  ├─(__starLeave__)[*]["*"] 32  │  └─(__E)[E][<E>] 33  │      └─(__V)[V][<V>] 34  │          └─(__xLeave__)[x][x] 35  ├─(__equalLeave__)[=]["="] 36  └─(__E)[E][<E>] 37      └─(__V)[V][<V>] 38          └─(__xLeave__)[x][x] 39 (__S)[S][<S>] 40  ├─(__V)[V][<V>] 41  │  ├─(__starLeave__)[*]["*"] 42  │  └─(__E)[E][<E>] 43  │      └─(__V)[V][<V>] 44  │          ├─(__starLeave__)[*]["*"] 45  │          └─(__E)[E][<E>] 46  │              └─(__V)[V][<V>] 47  │                  └─(__xLeave__)[x][x] 48  ├─(__equalLeave__)[=]["="] 49  └─(__E)[E][<E>] 50      └─(__V)[V][<V>] 51          ├─(__starLeave__)[*]["*"] 52          └─(__E)[E][<E>] 53              └─(__V)[V][<V>] 54                  ├─(__starLeave__)[*]["*"] 55                  └─(__E)[E][<E>] 56                      └─(__V)[V][<V>] 57                          └─(__xLeave__)[x][x]  syntax tree

能够正确地导出这些结果，就说明整个库是正确的。其实，只要能导出这些结果而不throw Exception()，就可以断定结果是正确的了

计划

所以我的开发步骤如下：

示例

虎书中已有了文法3-1（如下）的分析表和一个示例分析过程，所以先实现文法3-1的分析器。从这个分析器的代码中抽取出所有LR分析器 通用的部分 ，作为LALR(1)Compiler的一部分。（后来我才发现这个文法竟然不是LR(1)文法）

  1 // 虎书中的文法3-1  2 <S> ::= <S> ";" <S> ;  3 <S> ::= identifier ":=" <E> ;  4 <S> ::= "print" "(" <L> ")" ;  5 <E> ::= identifier ;  6 <E> ::= number ;  7 <E> ::= <E> "+" <E> ;  8 <E> ::= "(" <S> "," <E> ")" ;  9 <L> ::= <E> ; 10 <L> ::= <L> "," <E> ; 

算法

经此之后就对语法分析器的构成心中有数了。下面实现虎书中关于 自动生成工具 的算法。

LR(0)

首先有两个基础算法。 Closure 用于补全一个state。 Goto 用于找到一个state经过某个Node后会进入的下一个state。说是算法，其实却非常简单。虽然简单，要想实现却有很多额外的工作。例如比较两个LR(0)Item的问题。

然后就是计算文法的 状态集 和 边集 （Goto动作集）的算法。这个是核心内容。

用此算法可以画出文法3-8的状态图如下：

 1 // 虎书中的文法3-8 2 <S> ::= "(" <L> ")" ; 3 <S> ::= "x" ; 4 <L> ::= <S> ; 5 <L> ::= <L> "," <S> ; 

最后就是看图作文——构造分析表了。有了分析表，语法分析器的核心部分就完成了。

SLR

在 A->α. 可以被归约时，只在下一个单词是Follow(A)时才进行归约。看起来很有道理的样子。

LR(1)

LR(1)项（ A->α.β,x ）指出，序列α在栈顶，且输入中开头的是可以从βx导出的符号。看起来更有道理的样子。

LR(1)的state补全和转换算法也要调整。

然后又是看图作文。

LALR(1)

LALR(1)是对LA(1)的化简处理。他占用空间比LR(1)少，但文法范围也比LR(1)小了点。

为了实现LALR(1)，也为了提高LR(1)的效率，必须优化LR(1)State，不能再单纯模仿LR(0)State了。

文法

输入的是文法，输出的是编译器代码，这个过程也可以用一个编译器来实现。这个特别的编译器所对应的文法（即 描述文法的文法 ）如下：（此编译器命名为ContextfreeGrammarCompiler）

  1 // 文法是1到多个产生式  2 <Grammar> ::= <ProductionList> <Production> ;  3 // 产生式列表是0到多个产生式  4 <ProductionList> ::= <ProductionList> <Production> | null ;  5 // 产生式是左部+第一个候选式+若干右部  6 <Production> ::= <Vn> "::=" <Canditate> <RightPartList> ";" ;  7 // 候选式是1到多个结点  8 <Canditate> ::= <VList> <V> ;  9 // 结点列表是0到多个结点 10 <VList> ::= <VList> <V> | null ; 11 // 右部列表是0到多个候选式 12 <RightPartList> ::= "|" <Canditate> <RightPartList> | null ; 13 // 结点是非叶结点或叶结点 14 <V> ::= <Vn> | <Vt> ; 15 // 非叶结点是<>括起来的标识符 16 <Vn> ::= "<" identifier ">" ; 17 // 叶结点是用"引起来的字符串常量或下列内容：null, identifier, number, constString 18 // 这几个标识符就是ContextfreeGrammar的关键字 19 <Vt> ::= "null" | "identifier" | "number" | "constString" | constString ; 

设计

算法看起来还是很简单的。即使不理解他也能实现他。但是实现过程中还是出现了不少的问题。

Hash缓存

如何判定两个LR(0)Item相同？

这是个复杂的问题。

必须重写==、!=运算符，override掉Equals和GetHashCode方法。这样才能判定两个内容相同但不是同一个对象的Item、State相等。

对于LR(0)Item的比较，在计算过程中有太多次，这对于实际应用（例如GLSL的文法）是不可接受的。所以必须缓存这类对象的HashCode。

有序集合

如何判定两个LR(0)State相同？

一个LR(0)State是一个集合，集合内部的元素是没有先后顺序的区别的。但是为了比较两个State，其内部元素必须是有序的（这就可以用二分法进行插入和比较）。否则比较两个State会耗费太多时间。为了尽可能快地比较State，也要缓存State的HashCode。

迭代到不动点

虎书中的算法大量使用了迭代到不动点的方式。

这个方法虽好，却仍有可优化的余地。而且这属于核心的计算过程，也应当优化。

优化方法也简单，用一个 Queue 代替"迭代不动点"的方式即可。这就避免了很多不必要的重复计算。

   1         /// <summary>  2         /// LR(0)的Closure操作。  3         /// 补全一个状态。  4         /// </summary>  5         /// <param name="list"></param>  6         /// <param name="state"></param>  7         /// <returns></returns>  8         static LR0State Closure(this RegulationList list, LR0State state)  9         { 10             Queue<LR0Item> queue = new Queue<LR0Item>(); 11             foreach (var item in state) 12             { 13                 queue.Enqueue(item); 14             } 15             while (queue.Count > 0) 16             { 17                 LR0Item item = queue.Dequeue(); 18                 TreeNodeType node = item.GetNodeNext2Dot(); 19                 if (node == null) { continue; } 20  21                 foreach (var regulation in list) 22                 { 23                     if (regulation.Left == node) 24                     { 25                         var newItem = new LR0Item(regulation, 0); 26                         if (state.TryInsert(newItem)) 27                         { 28                             queue.Enqueue(newItem); 29                         } 30                     } 31                 } 32             } 33  34             return state; 35         }  优化后的Closure

测试

以前我喜欢做个非常精致的GUI来测试。现在发现没那个必要，简单的Console就可以了。

详细的测试结果导出到文件里，可以慢慢查看分析。

   1 =====> Processing ./TestCases/3_8.Grammar/3_8.Grammar  2     Get grammar from source code...  3         Dump 3_8.TokenList.log  4         Dump 3_8.Tree.log  5         Dump 3_8.FormatedGrammar.log  6     Dump 3_8.FIRST.log  7     Dump 3_8.FOLLOW.log  8     LR(0) parsing...  9         Dump 3_8.State.log 10         Dump 3_8.Edge.log 11         Dump LR(0) Compiler's source code... 12     SLR parsing... 13         Dump 3_8.State.log 14         Dump 3_8.Edge.log 15         Dump SLR Compiler's source code... 16     LALR(1) parsing... 17         Dump 3_8.State.log 18         Dump 3_8.Edge.log 19         Dump LALR(1) Compiler's source code... 20     LR(1) parsing... 21         Dump 3_8.State.log 22         Dump 3_8.Edge.log 23         Dump LR(1) Compiler's source code... 24     Compiling 3_8 of LR(0) version 25     Test Code 3_8 of LR(0) version 26     Compiling 3_8 of SLR version 27     Test Code 3_8 of SLR version 28     Compiling 3_8 of LALR(1) version 29     Test Code 3_8 of LALR(1) version 30     Compiling 3_8 of LR(1) version 31     Test Code 3_8 of LR(1) version 32 =====> Processing ./TestCases/Demo.Grammar/Demo.Grammar 33     Get grammar from source code... 34         Dump Demo.TokenList.log 35         Dump Demo.Tree.log 36         Dump Demo.FormatedGrammar.log 37     Dump Demo.FIRST.log 38     Dump Demo.FOLLOW.log 39     LR(0) parsing... 40         Dump Demo.State.log 41         Dump Demo.Edge.log 42         Dump LR(0) Compiler's source code... 43         【Exists 5 Conflicts in Parsingmap】 44     SLR parsing... 45         Dump Demo.State.log 46         Dump Demo.Edge.log 47         Dump SLR Compiler's source code... 48         【Exists 2 Conflicts in Parsingmap】 49     LALR(1) parsing... 50         Dump Demo.State.log 51         Dump Demo.Edge.log 52         Dump LALR(1) Compiler's source code... 53         【Exists 2 Conflicts in Parsingmap】 54     LR(1) parsing... 55         Dump Demo.State.log 56         Dump Demo.Edge.log 57         Dump LR(1) Compiler's source code... 58         【Exists 6 Conflicts in Parsingmap】 59     Compiling Demo of LR(0) version 60     Test Code Demo of LR(0) version 61         No need to Test Code with conflicts in SyntaxParser 62     Compiling Demo of SLR version 63     Test Code Demo of SLR version 64         No need to Test Code with conflicts in SyntaxParser 65     Compiling Demo of LALR(1) version 66     Test Code Demo of LALR(1) version 67         No need to Test Code with conflicts in SyntaxParser 68     Compiling Demo of LR(1) version 69     Test Code Demo of LR(1) version 70         No need to Test Code with conflicts in SyntaxParser 71 =====> Processing ./TestCases/GLSL.Grammar/GLSL.Grammar 72     Get grammar from source code... 73         Dump GLSL.TokenList.log 74         Dump GLSL.Tree.log 75         Dump GLSL.FormatedGrammar.log 76     Dump GLSL.FIRST.log 77     Dump GLSL.FOLLOW.log 78     LR(0) parsing...  测试结果（部分）

GLSL

测试完成后，就可以拿GLSL文法开始干活了。由于GLSL文法比那些测试用的文法规模大的多，最初的版本里，计算过程居然花了好几个小时。而且最终出现OutOfMemoryException，根本得不到结果。不得不进行优化。通过缓存HashCode、使用二分法排序集合，计算过程从几个小时缩减到十几分钟。

书中给的GLSL文法也是比较奇葩。或许是有什么特别的门道我没有看懂吧。总之要简化简化。

简化的思路是，把grammar拆分成几个部分，分别处理。

首先是expression，这是其他部分的基础。然后是statement，function_definition。最后是declaraition。

遗憾的是书中的GLSL文法是个超病态的文法，declaration部分实在不知道该怎么处理了。我只好就此打住，等熟悉GLSL的全部功能后再总结一个正常的来。

故事

故事，其实是事故。由于心急，此项目第一次实现时出现了几乎无法fix的bug。于是重写了一遍，这次一步一步走，终于成功了。

LALR(1)State

LALR(1)State集合在尝试插入一个新的State时，如果已有在LALR(1)意义上"相等"的状态，仍旧要尝试将新state的LookAhead列表插入已有状态。

否则，下面的例子就显示了文法3-8在忽视了这一点时的state集合与正确的state集合的差别（少了一些LookAhead项）。

   1 State [1]:  2 <S> ::= . "(" <L> ")" ;, "$"  3 <S'> ::= . <S> "$" ;, "$"  4 <S> ::= . "x" ;, "$"  5 State [8]:  6 <S> ::= "(" <L> ")" . ;, "$"  7 State [4]:  8 <S> ::= "x" . ;, "$"  9 State [6]: 10 <L> ::= <S> . ;, ","")" 11 State [9]: 12 <L> ::= <L> "," <S> . ;, ","")" 13 State [5]: 14 <L> ::= <L> . "," <S> ;, ","")" 15 <S> ::= "(" <L> . ")" ;, "$" 16 State [7]: 17 <S> ::= . "(" <L> ")" ;, ","")" 18 <S> ::= . "x" ;, ","")" 19 <L> ::= <L> "," . <S> ;, ","")" 20 State [2]: 21 <S> ::= . "(" <L> ")" ;, ","")" 22 <S> ::= . "x" ;, ","")" 23 <S> ::= "(" . <L> ")" ;, "$" 24 <L> ::= . <L> "," <S> ;, ","")" 25 <L> ::= . <S> ;, ","")" 26 State [3]: 27 <S'> ::= <S> . "$" ;, "$"  少LookAhead项的

   1 State [1]:  2 <S> ::= . "(" <L> ")" ;, "$"  3 <S'> ::= . <S> "$" ;, "$"  4 <S> ::= . "x" ;, "$"  5 State [8]:  6 <S> ::= "(" <L> ")" . ;, "$"","")"  7 State [4]:  8 <S> ::= "x" . ;, "$"","")"  9 State [6]: 10 <L> ::= <S> . ;, ","")" 11 State [9]: 12 <L> ::= <L> "," <S> . ;, ","")" 13 State [5]: 14 <L> ::= <L> . "," <S> ;, ","")" 15 <S> ::= "(" <L> . ")" ;, "$"","")" 16 State [7]: 17 <S> ::= . "(" <L> ")" ;, ","")" 18 <S> ::= . "x" ;, ","")" 19 <L> ::= <L> "," . <S> ;, ","")" 20 State [2]: 21 <S> ::= . "(" <L> ")" ;, ","")" 22 <S> ::= . "x" ;, ","")" 23 <S> ::= "(" . <L> ")" ;, "$"","")" 24 <L> ::= . <L> "," <S> ;, ","")" 25 <L> ::= . <S> ;, ","")" 26 State [3]: 27 <S'> ::= <S> . "$" ;, "$"  正确的

CodeDom

CodeDom不支持readonly属性，实在是遗憾。CodeDom还会对以"__"开头的变量自动添加个@前缀，真是无语。

  1 // private static TreeNodeType NODE__Grammar = new TreeNodeType(ContextfreeGrammarSLRTreeNodeType.NODE__Grammar, "Grammar", "<Grammar>");  2 CodeMemberField field = new CodeMemberField(typeof(TreeNodeType), GetNodeNameInParser(node));  3 // field.Attributes 不支持readonly，遗憾了。  4 field.Attributes = MemberAttributes.Private | MemberAttributes.Static;  5 var ctor = new CodeObjectCreateExpression(typeof(TreeNodeType),  6     new CodeFieldReferenceExpression(  7         new CodeTypeReferenceExpression(GetTreeNodeConstTypeName(grammarId, algorithm)),  8         GetNodeNameInParser(node)),  9     new CodePrimitiveExpression(node.Content), 10     new CodePrimitiveExpression(node.Nickname)); 11 field.InitExpression = ctor; 

复杂的词法分析器

从算法上说，理解语法分析器要比较理解词法分析器困难的多。但是LR语法分析器的结构却比词法分析器的结构和LL语法分析器的结果简单得多。目前实现dump词法分析器代码的代码是最绕的。要处理注释（//和/**/）是其中最复杂的问题。这段代码写好了我再也不想动了。

LL和LR

LR分析法确实比LL强太多。其适用各种现今的程序语言，对文法的限制极少，分析器结构还十分简单。奇妙的是，稍微改动下文法，就可以减少LR分析的state，精简代码。

例如ContextfreeGrammarCompiler的文法，稍微改改会有不同的state数目。

   1 ====================================================================  2 135 set action items  3 <Grammar> ::= <ProductionList> <Production> ;  4 <ProductionList> ::= <ProductionList> <Production> | null ;  5 <Production> ::= <Vn> "::=" <Canditate> <RightPartList> ";" ;  6 <Canditate> ::= <V> <VList> ;  7 <VList> ::= <V> <VList> | null ;  8 <RightPartList> ::= "|" <Canditate> <RightPartList> | null ;  9 <V> ::= <Vn> | <Vt> ; 10 <Vn> ::= "<" identifier ">" ; 11 <Vt> ::= "null" | "identifier" | "number" | "constString" | constString ; 12 ==================================================================== 13 143 set action items 14 <Grammar> ::= <Production> <ProductionList> ; 15 <ProductionList> ::= <Production> <ProductionList> | null ; 16 <Production> ::= <Vn> "::=" <Canditate> <RightPartList> ";" ; 17 <Canditate> ::= <V> <VList> ; 18 <VList> ::= <V> <VList> | null ; 19 <RightPartList> ::= "|" <Canditate> <RightPartList> | null ; 20 <V> ::= <Vn> | <Vt> ; 21 <Vn> ::= "<" identifier ">" ; 22 <Vt> ::= "null" | "identifier" | "number" | "constString" | constString ; 23 ==================================================================== 24 139 25 <Grammar> ::= <ProductionList> <Production> ; 26 <ProductionList> ::= <ProductionList> <Production> | null ; 27 <Production> ::= <Vn> "::=" <LeftPartList> <Canditate> ";" ; 28 <LeftPartList> ::= <LeftPartList> <LeftPart> | null ; 29 <LeftPart> ::= <Canditate> "|" ; 30 <Canditate> ::= <V> <VList> ; 31 <VList> ::= <V> <VList> | null ; 32 <V> ::= <Vn> | <Vt> ; 33 <Vn> ::= "<" identifier ">" ; 34 <Vt> ::= "null" | "identifier" | "number" | "constString" | constString ; 35 ==================================================================== 36 120 37 <Grammar> ::= <ProductionList> <Production> ; 38 <ProductionList> ::= <ProductionList> <Production> | null ; 39 <Production> ::= <Vn> "::=" <Canditate> <RightPartList> ";" ; 40 <Canditate> ::= <VList> <V> ; 41 <VList> ::= <VList> <V> | null ; 42 <RightPartList> ::= "|" <Canditate> <RightPartList> | null ; 43 <V> ::= <Vn> | <Vt> ; 44 <Vn> ::= "<" identifier ">" ; 45 <Vt> ::= "null" | "identifier" | "number" | "constString" | constString ;  ContextfreeGrammarCompiler

总结

实现GLSL编译器前端这个目的是没能实现。不过万事俱备只欠东风，有机会弄到GLSL文法后就随时可以做出来了。

为了这个目标，所花费的时间精力确实太多。但是这已成为一项重要的积累。因为用到编译原理的地方太多了。算起来还是值得的。

本项目开源地址在（ https://github.com/bitzhuwei/LALR1Compiler/ ）