阅读目录(Content)
基于虎书实现LALR(1)分析并生成GLSL编译器前端代码(C#)
为了完美解析GLSL源码，获取其中的信息（都有哪些in/out/uniform等），我决定做个GLSL编译器的前端（以后简称编译器或FrontEndParser）。
以前我做过一个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-102 <S> ::= <V> "=" <E> ;3 <S> ::= <E> ;4 <E> ::= <V> ;5 <V> ::= "x" ;6 <V> ::= "*" <E> ;
下面是6个符合此文法的代码：
1 x2 *x3 x = x4 x = * x5 *x = x6 **x = **x
输出结果是此文法的编译器代码(C#)。这主要是词法分析器LexicalAnalyzer和语法分析器SyntaxParser两个类。
之后利用C#的CSharpCodeProvider和反射技术来加载、编译、运行生成的代码，用一些例子（例如上面的*x = x）测试是否能正常运行。只要能正常生成语法树，就证明了我的LALR(1)Compiler的实现是正确的。
例如对上述文法的6个示例代码，LALR(1)Compiler可以分别dump出如下的语法树：
能够正确地导出这些结果，就说明整个库是正确的。其实，只要能导出这些结果而不throw Exception()，就可以断定结果是正确的了
所以我的开发步骤如下：
虎书中已有了文法3-1（如下）的分析表和一个示例分析过程，所以先手工实现文法3-1的分析器。从这个分析器的代码中抽取出所有LR分析器通用的部分，作为LALR(1)Compiler的一部分。
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> ;
经此之后就对语法分析器的构成心中有数了。下面实现虎书中关于自动生成工具的算法。
最妙的是，即使开始时不理解这些算法的原理，也能够实现之。实现后通过测试用例debug的过程，就很容易理解这些算法了。
首先有两个基础算法。Closure用于补全一个state。Goto用于找到一个state经过某个Node后会进入的下一个state。说是算法，其实却非常简单。虽然简单，要想实现却有很多额外的工作。例如比较两个LR(0)Item的问题。
然后就是计算文法的状态集和边集（Goto动作集）的算法。这个是核心内容。
用此算法可以画出文法3-8的状态图如下：
1 // 虎书中的文法3-82 <S> ::= "(" <L> ")" ;3 <S> ::= "x" ;4 <L> ::= <S> ;5 <L> ::= <L> "," <S> ;
最后就是看图作文——构造分析表了。有了分析表，语法分析器的核心部分就完成了。
在A->α.可以被归约时，只在下一个单词是Follow(A)时才进行归约。看起来很有道理的样子。
LR(1)项（A->α.β,x）指出，序列α在栈顶，且输入中开头的是可以从βx导出的符号。看起来更有道理的样子。
LR(1)的state补全和转换算法也要调整。
然后又是看图作文。
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, userDefinedType18 // 这几个标识符就是ContextfreeGrammar的关键字19 <Vt> ::= "null" | "identifier" | "number" | "constString" | "userDefinedType"| constString ;
算法看起来还是很简单的。即使不理解他也能实现他。但是实现过程中还是出现了不少的问题。
如何判定两个对象（LR(0)Item）相同？
这是个不可小觑的问题。
必须重写==、!=运算符，override掉Equals和GetHashCode方法。这样才能判定两个内容相同但不是同一个对象的Item、State相等。
对于LR(0)Item的比较，在计算过程中有太多次，这对于实际应用（例如GLSL的文法）是不可接受的。所以必须缓存这类对象的HashCode。
如何判定两个集合（LR(0)State）相同？
一个LR(0)State是一个集合，集合内部的元素是没有先后顺序的区别的。但是为了比较两个State，其内部元素必须是有序的（这就可以用二分法进行插入和比较）。否则比较两个State会耗费太多时间。为了尽可能快地比较State，也要缓存State的HashCode。
有序集合的应用广泛，因此独立成类。
其中有个TryBinaryInsert的扩展方法，用于向 IList<T> 插入元素。这个方法我经过严格测试。如果有发现此方法的bug向我说明，我愿意奖励￥100元。
虎书中的算法大量使用了迭代到不动点的方式。
这个方法虽好，却仍有可优化的余地。而且这属于核心的计算过程，也应当优化。
优化方法也简单，用一个Queue代替"迭代不动点"的方式即可。这就避免了很多不必要的重复计算。
以前我总喜欢做个非常精致的GUI来测试。现在发现没那个必要，简单的Console就可以了。
详细的测试结果导出到文件里，可以慢慢查看分析。
测试完成后，就可以磨刀霍霍向GLSL文法了。由于GLSL文法比那些测试用的文法规模大的多，最初的版本里，计算过程居然花了好几个小时。最终出现内存不足的Exception，不得不进行优化。
书中给的GLSL文法也是比较奇葩。或许是有什么特别的门道我没有看懂吧。总之要降低难度先。
思路是，把grammar拆分成几个部分，分别处理。
首先是Expression，这是其他部分的基础。Expression部分是符合SLR的，非常好。
然后是statement，statement里有个else悬空的问题，幸好虎书里专门对这个问题做了说明，说可以容忍这个冲突，直接选择Shift，忽略Reduction即可。也非常好。
然后是function_definition，出乎意料的是这部分也是符合SLR的。Nice。
最后是declaration，这里遇到了意想不到的大麻烦。GLSL文法里有个<TYPE_NAME>。这个东西我研究了好久，最后发现他代表的含义竟然是"在读取源代码时动态发现的用户定义的类型"。比如 struct LightInfo{ … } ，他代表的是 LightInfo 这种类型。如果简单的用identifier代替<TYPE_NAME>，文法就会产生无法解决的冲突。
我只好就此打住，先去实现另一种更强的分析方式——同步分析。
现在，我的词法分析、语法分析是分开进行的。词法分析全部完成后，才把单词流交给语法分析器进行分析。为了及时识别出用户自定义的类型，这种方式完全不行，必须用"分析一个单词->语法分析->可能的语义分析->分析一个单词"这样的同步分析方式。例如下面的代码：
1 struct LightInfo { 2 vec4 Position; // Light position in eyecoords. 3 vec3 La; // Ambient light intensity 4 vec3 Ld; // Diffuse light intensity 5 vec3 Ls; // Specular light intensity 6 }; 7 uniform LightInfo Light;
在读到第二个单词"LightInfo"后，就必须立即将这个"LightInfo"类型加到用户自定义的类型表里。这样，在继续读到"uniform LightInfo Light"里的"LightInfo"时，词法分析器才会知道"LightInfo"是一个userDefinedType，而不是一个随随便便的identifier。（对照上文的文法的文法，可见为实现一个看似不起眼的userDefinedType需要做多少事）
既然要同步解析了，那么词法分析和语法分析就是结结实实绑在一起的过程，所有用个FrontEndParser封装一下就很有必要。其中的UserDefinedTypeCollection就用来记录用户自定义的类型。
1 /// <summary> 2 /// 前端分析器。 3 /// 词法分析、语法分析、语义动作同步进行。 4 /// </summary> 5 public class FrontEndParser 6 { 7 private LexicalAnalyzer lexicalAnalyzer; 8 private LRSyntaxParser syntaxParser; 9 10 public FrontEndParser(LexicalAnalyzer lexicalAnalyzer, LRSyntaxParser syntaxParser)11 {12 this.lexicalAnalyzer = lexicalAnalyzer;13 this.syntaxParser = syntaxParser;14 }15 16 /// <summary>17 /// 词法分析、语法分析、语义动作同步进行。18 /// </summary>19 /// <param name="sourceCode"></param>20 /// <param name="tokenList"></param>21 /// <returns></returns>22 public SyntaxTree Parse(string sourceCode, out TokenList tokenList)23 {24 tokenList = new TokenList();25 UserDefinedTypeCollection userDefinedTypeTable = new UserDefinedTypeCollection();26 this.lexicalAnalyzer.StartAnalyzing(userDefinedTypeTable);27 this.syntaxParser.StartParsing(userDefinedTypeTable);28 foreach (var token in this.lexicalAnalyzer.AnalyzeStep(sourceCode))29 {30 tokenList.Add(token);31 this.syntaxParser.ParseStep(token);32 }33 34 SyntaxTree result = this.syntaxParser.StopParsing();35 return result;36 }37 }
词法分析器需要每读取一个单词就返回之，等待语法分析、语义分析结束后再继续。C#的 yield return 语法糖真是甜。
每次只获取一个新单词，据此执行可能的分析步骤。如果分析动作还绑定了语义分析（这里是为了找到自定义类型），也执行之。
此时武器终于齐备。
为下面的GLSL文法生成解析器，我的笔记本花费大概10分钟左右。
语义分析是不能自动生成的。此时需要的语义分析，只有找到自定义类型这一个目的。
在GLSL文法里，是下面这个state需要进行语义分析。此时，分析器刚刚读到用户自定义的类型名字（identifier）。
1 State [172]:2 <struct_specifier> ::= "struct" identifier . "{" <struct_declaration_list> "}" ;, identifier "," ")" "(" ";" "["
语义分析动作内容则十分简单，将identifier的内容作为自定义类型名加入UserDefinedTypeTable即可。
1 // State [172]:2 // <struct_specifier> ::= "struct" identifier . "{" <struct_declaration_list> "}" ;, identifier "," ")" "(" ";" "["3 static void state172_struct_specifier(ParsingStepContext context)4 {5 SyntaxTree tree = context.TreeStack.Peek();6 string name = tree.NodeType.Content;7 context.UserDefinedTypeTable.TryInsert(new UserDefinedType(name));8 }
当然，别忘了在初始化时将此动作绑定到对应的state上。
1 static GLSLSyntaxParser() 2 { 3 // 将语义动作绑定的到state上。 4 dict.Add(new LR1ShiftInAction(172), state172_struct_specifier); 5 } 6 static Dictionary<LRParsingAction, Action<ParsingStepContext>> dict = 7 new Dictionary<LRParsingAction, Action<ParsingStepContext>>(); 8 9 protected override Action<ParsingStepContext> GetSemanticAction(LRParsingAction parsingAction)10 {11 Action<ParsingStepContext> semanticAction = null;12 if (dict.TryGetValue(parsingAction, out semanticAction))13 {14 return semanticAction;15 }16 else17 {18 return null;19 }20 }
下面是上文的LightInfo代码片段的词法分析结果。请注意在定义LightInfo时，他是个identifier，定义之后，就是一个userDefinedType类型的单词了。
1 TokenList[Count: 21] 2 [[struct](__struct)[struct]]$[Ln:1, Col:1] 3 [[LightInfo](identifier)[LightInfo]]$[Ln:1, Col:8] 4 [[{](__left_brace)["{"]]$[Ln:1, Col:18] 5 [[vec4](__vec4)[vec4]]$[Ln:2, Col:5] 6 [[Position](identifier)[Position]]$[Ln:2, Col:10] 7 [[;](__semicolon)[";"]]$[Ln:2, Col:18] 8 [[vec3](__vec3)[vec3]]$[Ln:3, Col:5] 9 [[La](identifier)[La]]$[Ln:3, Col:10]10 [[;](__semicolon)[";"]]$[Ln:3, Col:12]11 [[vec3](__vec3)[vec3]]$[Ln:4, Col:5]12 [[Ld](identifier)[Ld]]$[Ln:4, Col:10]13 [[;](__semicolon)[";"]]$[Ln:4, Col:12]14 [[vec3](__vec3)[vec3]]$[Ln:5, Col:5]15 [[Ls](identifier)[Ls]]$[Ln:5, Col:10]16 [[;](__semicolon)[";"]]$[Ln:5, Col:12]17 [[}](__right_brace)["}"]]$[Ln:6, Col:1]18 [[;](__semicolon)[";"]]$[Ln:6, Col:2]19 [[uniform](__uniform)[uniform]]$[Ln:7, Col:1]20 [[LightInfo](__userDefinedType)[LightInfo]]$[Ln:7, Col:9]21 [[Light](identifier)[Light]]$[Ln:7, Col:19]22 [[;](__semicolon)[";"]]$[Ln:7, Col:24]
下面是LightInfo片段的语法树。你可以看到单词的类型对照着叶结点的类型。
再加上其他的测试用例，这个GLSL解析器终于实现了。
解析GLSL源代码，是为了获取其中的信息（都有哪些in/out/uniform等）。现在语法树已经有了，剩下的就是遍历此树的事了。不再详述。
故事，其实是事故。由于心急，此项目第一次实现时出现了几乎无法fix的bug。于是重写了一遍，这次一步一步走，终于成功了。
LALR(1)State集合在尝试插入一个新的State时，如果已有在LALR(1)意义上"相等"的状态，仍旧要尝试将新state的LookAhead列表插入已有状态。
否则，下面的例子就显示了文法3-8在忽视了这一点时的state集合与正确的state集合的差别（少了一些LookAhead项）。
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词法分析器代码的代码是最绕的。要处理注释（//和/**/）是其中最复杂的问题。这段代码写好了我再也不想动了。
LR分析法确实比LL强太多。其适用各种现今的程序语言，对文法的限制极少，分析器结构还十分简单。奇妙的是，稍微改动下文法，就可以减少LR分析的state，精简代码。
例如ContextfreeGrammarCompiler的文法，稍微改改会有不同的state数目。
实现了LALR(1)分析和GLSL解析器。
今后做任何语言、格式的解析都不用愁了。
| 微信捐赠二维码： Donate by microMsg: |
联系客服
