计划用于生产项目里的编译器设计，适合用 LL(1)手写递归下降来实现解析器吗？

[netabare]

以前有零星做过一些玩具型的编程语言设计和编译器实现，也用过 ANTLR 和 parser combinator 等技巧。

不过感觉 ANTLR 为代表的 parser generator ，或者 parser combinator ，或多或少都有不少比较让我介意的问题。parser generator 的问题有比较受限于既有技术栈，和我自己的代码风格不一定相融，还有可 hack 能力比较低，parser combinator 的最大问题就是封装过于严实，感觉简单的语法还好，要是遇到复杂的可能就寄了。

所以这次的思路大概是用手写递归下降的办法来自己实现解析器，这个说实话也没难度只是体力活而已。倒是也有听说在大型项目和实际工程里确实更多会手写递归下降而不是用其他的技巧？

然后确实也有想过用 monad 例如 reader 或者 state 啥的来封装一个比较浅的抽象层，但就不考虑引入 parser combinator 了……

但是与此同时也会担心 LL(1)的表达力是否足以覆盖大型项目里面可能会出现的复杂语法。虽然自己手推了一遍似乎没太大问题，而且例如左递归这种经典问题也能比较好的处理了。但还是不太有底气就是，或者说，像是 C++、C#、Java 这些语言没记错的话都有一些语法特征是 LL(1)难以处理的吧？实际工程里，遇到复杂语法，一般会怎么处理呢？还是也会上 parser generator （不过这种大型语言应该没 pg 可用）？

所以有点好奇这个问题，不知道有没有比较有相关经验的人能给点思路呢？

emmmm ，好像那个「生产项目」产生歧义了，其实我是想造自己的语言，提到「生产项目」只是说这个语言想要作为长期项目和用于实际开发的目的，而不是为了造一个 toy lang （所以感觉很多东西会很复杂比较难考虑）

[letianqiu]

编译器是由语言决定的，你首先要搞清楚你设计的语言是什么样的。

[glcolof]

由语法决定+1
C++、C#、Java 这类的都需要 LL(n)才行。
要在生产环境用的话，我还是建议找成熟的编译器改改。从头写的代价太高了。我们公司有个脚本语言，是老板设计实现的，parser 是老板手写的递归下降分析器，至今已经维护了十来年了，还经常遇到 bug 。不过最大的问题是，没有好的 IDE 支持，以前是老板自己用 C#写了一个编辑器，现在用的是 VSCode ，只有基本的代码着色+智障补完。

[Orlion]

不一定非要 LL ，也可以手写 LR 吧

[ftfunjth]

先用 Flex + Bison 快速实现一套前端， 然后补充大量的 unit test 后，推倒重写。 这部分前端纯体力活，上 GLR 一般都可以解决。 遇到二义性，也可以延迟到 semantic checking 阶段修复。

[qieqie]

先把语言 spec 定稿写出来，有没有可能 parser generator 搞不定的语法从设计上就是错的？

[mahaoqu]

其实不少语言已经是上下文有关语法了，而且语法最简单的 Go 也不是 LL(1)的。

LL(k) 除了处理左递归剩下的都挺直观的吧，现在几乎所有编程语言解析都是手写递归下降（可能是为了报错误信息比较方便），用 Pratt 算法的话还挺方便的。

[w568w]

问题无关，好奇什么样的项目需要自己从头实现新语言和编译器才好做

[levelworm]

@glcolof 老板年轻的时候玩的很爽啊。。。

[glcolof]

@levelworm 他入行早，吃到了很多红利。当然能力也确实强，很多技术都会，C++水平一流。

[cooltechbs]

这坛子还真厉害，编译器这么垂直的话题都十来个回复了。学习中。

[namonai]

看源语言的语法复不复杂，能不能用 LL(1)cover 住

[X_Del]

好奇场景，除非是数据结构特殊，感觉九成场合都能用 Ruby JS 一类现成的的动态语言，写几个函数直接搓一个 DSL 出来，效率还更高。

[jones2000]

大学不是有编译原理的课程， 根据这个来搞，比较好。 我看楼主描述的估计需求都不明确，就不要考虑偷懒的方法，根据标准的流程来搞（ 词法分析、语法分析、语义分析及中间代码的生成、优化、目标代码的生成），这样后续你要扩展加新的语法都还是很方便的。

[netabare]

@letianqiu
@glcolof

打算做的是纯函数式编程，语法接近 ML 系或 Scala 或 Haskell （肯定没那么精简，我也在看哪些语法叠起来相对简单而不那么容易产生二义性）。长期的规划以后再看了，也许可以添加少量 OOP 功能，但肯定不是 Java 的路子。

话说过来 C++、C#和 Java 的解析难度是跟那个泛型标记有关吗？如果从我的路子讲倒是不太用担心这个问题……？毕竟按照 ML 系的类型推导，大部分时候并不需要显式标记类型，类型标记语法也可以设计成避免出现尖括号嵌套这种情况的样子。不过我不确定其他地方是否会遇到别的 LL(1)无能为力的例子了。

@Orlion

手写 LR 也可以的吗？记得都说 LR 语法好像不太适合手写反而比较适合 pg ？但我并不打算现在就考虑设计 pg 的事情。

@ftfunjth

我这边的话，快速实现可能就靠 parser combinator 了，这倒是我原先就有的路径，快速出活是真的快，但这也就回到题目里面的问题……快速写完原型后，这个原型能够长期不断扩展嘛？推倒重写应该还是基于相似的技术选型和路径，而不是说比如今天用了 flex+bison 明天改成 parsec 这样的吧。主要担心的是会不会到头来推倒重做的难度会后期逐步加大，然后语法已经复杂到重构的代价很高昂了。

@qieqie

我没有说「 parser generator 」搞不定我的语法，我想说的是我不太想用 parser generator ，因为不想被技术栈限制或者被 pg 的设计思路所限制（这是以前我遇到过的问题）。

@mahaoqu

也就是说这个问题的回答可以说是「手写递归下降足以覆盖」嘛？明白了，多谢。

@w568w

是在实现自己的语言……目前的进度大概是跳过了 parser ，实现了个解释器和类型系统。大概是计划三五年做出能真的用得上的语言（而不是简单的 toy lang ）。

@jones2000

我做的流程应该相当标准了，只是我觉得其他部分跟我想讨论的话题无关而已。解释器和类型系统我都实现了，但为了节省时间我直接跳过了 parser 步骤手写了百来个硬编码的 AST 树的测试用例，然后现在想回过头复查一下 parser 话题而已。至于中间代码和优化那些又是别的话题了。

[glcolof]

@netabare C 语言家族类型声明语法是 LL(1)不够用的首要原因，比如 parser 看到“int a”的时候是无法判断 a 是变量还是函数的。C++及其后继的泛型语法加重了这个问题。
函数式编程语言大概率会停留在 toy lang 的阶段，希望 OP 可以克服，加油。

[Orlion]

@netabare 能手写，不过写出来跟个 parser generator 差不太多了😄，可以参考我多年前搞的小玩意： https://github.com/Orlion/merak （一堆 bug 勿使用）