Parse the Grammar of Non-stripped C

完整的C文法的确复杂。前段时间试图理解却发现始终无法找到切入点。昨晚想试一下自己写的SLR语法分析器的功能，看它能不能自动构造出C语言的SLR分析表。于是用下载的C文法替换掉自定义的文法放到文法规则输入文件中。（改格式就花了不少工夫，还好Visual Studio强大的正则表达式替换功能为我节省了大量的体力）

怀着忐忑的心情第一次运行，居然堆栈Overflow？用Debug模式一步步调试发现在自动构造分析表的过程中求解First/Follow集的时候出现了循环的递归的问题。第一个错误出现在求Follow(cast_expression)的时候。cast_expression->unary_expression->cast_expression。检查文法产生式，发现了如下这两条：

• unary_expression->unary_operator cast_expression
• cast_expression->unary_expression

这样循环才怪呢！首先注释掉第一条可以暂时屏蔽这个问题。后来在statement的地方也出现了类似的循环递归，简单修改文法得以回避掉了。

构建分析表的时候还出现了两个分析表冲突，一个是对于’:’的，注释掉statement->IDENTIFIER :可以解决，原因暂时不明。其次是

• statement->if ( expression ) statement else statement
• statement->if ( expression ) statement

的地方，这个冲突是来自if语句自身的二义性。由于SLR分析法只适用于非二义文法，教科书上的解决办法是手工修改分析表，依据else的最近匹配原则，在出现冲突的地方令其移入而不是规约。但由于现在是自动构建分析表，只能从产生式中去掉statement->if ( expression ) statement这一条。这样，语言中所有if语句都必须匹配else，即使没有else也要加上else ;（多少看上去有点怪异）。

所有错误和冲突都消除之后，终于可以对C的源程序进行语法分析了。不过受限于简陋的词法分析器，字符串和浮点数和一些双符号的运算符（如+=,*=）都不能支持。我的CPU是Pentium M 1.6GHz，内存1GB。构建分析表的时候CPU满负荷（占用率100%）工作了近11秒钟，可见的确实一个复杂的文法呀！

结果是令人振奋的。除了不支持浮点数、字符串还有须强制匹配If-Else之外，所有ANSI C的特性都能够被正确的解析——不管是for，还是switch；不管是struct/union/enum定义，还是指针类型的使用，通通给我显示出正确的文法结构来！

抛开由于二义性导致的冲突和来自词法分析器的局限来看，我写的SLR(1)分析器还是相当优秀的。有自动构建分析表的强大灵活性，这个分析器可以分析任何文法，即使是那么复杂的C语言，只要这样的文法适用于做SLR分析。