什么是可以解析C代码的最简单解析算法？

Question

什么是可以解析C代码的最简单解析算法？

10

有人知道能够解析C代码的最弱的广泛使用的解析算法族吗？也就是说，C语法是LL(1)、LR(0)、LALR(1)等等哪一种？我很感兴趣，因为作为一个副业项目，我想写一个解析器生成器，以便最终能够解析C代码用于另一个副业项目。

答：目前已知的对C语言进行解析的算法族中，LALR(1)和GLR是比较常用的，而LL(1)和LR(0)则不太适合处理C语言这种复杂的文法。

- templatetypedef

大多数解析器都是以识别“过多”的方式构建的，超额部分会被解析器外的其他检查拒绝。在这种情况下，正则表达式“[.]*”是最弱的解析器，尽管需要进行大量的附加语义检查才能解析C。一旦明确了这一点，就应该清楚，您可以使任何解析器生成器处理C，除了额外的黑客攻击。（编写一个接受太少内容作为起点的解析器似乎完全疯狂）。 - Ira Baxter

我又被这个问题绊倒了。显而易见的实用答案是，“手写自顶向下递归”。我敢打赌，第一个C解析器就是这样构建的（早在YACC之前）。除此之外，还需要多少技巧才能完成呢？ - Ira Baxter

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Weiser · Accepted Answer

似乎Bison使用LALR(1)解析器。LALR解析器比LL解析器更强大，但也更复杂。因此我猜测LALR(1)可能是能够解析C代码的最弱解析算法。

除非你真的想自己编写识别器，否则ANTLR可能是你最好的选择。ANTLR使用LL*算法（实际上是LALR）。