手动编写解析器的最佳方法是什么？
我们使用ANTLR为类似SQL的语法创建解析器，虽然在大多数情况下结果令人满意，但我们需要修复一些边缘情况; 因为我们自己没有编写解析器，所以我们并不能很好地理解它，以便能够做出明智的改变。
所以，我们想编写自己的解析器。 手动编写解析器的最佳方法是什么？ 我们应该使用什么样的解析器 – 建议使用递归下降; 是对的吗？ 我们将用C＃编写它，因此任何用该语言编写解析器的教程都会感激不尽。
更新：我也对涉及F＃的答案感兴趣 – 我一直在寻找在项目中使用它的理由。
我强烈推荐使用F＃语言作为在.NET平台上解析的首选语言。 ML系列语言的根源意味着它对面向语言的编程提供了出色的支持。
受歧视的联合和模式匹配允许您的AST非常简洁和强大的规范。 高阶函数允许定义解析操作及其组成。 对monadic类型的一流支持允许隐式处理状态管理，大大简化了解析器的组成。 强大的类型推断极大地帮助了这些（复杂）类型的定义。 所有这些都可以通过交互方式指定和执行，从而快速进行原型设计。
Stephan Tolksdorf通过他的解析器组合库FParsec将其付诸实践
从他的例子我们看到AST的指定自然：
type expr = | Val of string | Int of int | Float of float | Decr of expr type stmt = | Assign of string * expr | While of expr * stmt | Seq of stmt list | IfThen of expr * stmt | IfThenElse of expr * stmt * stmt | Print of expr type prog = Prog of stmt list 解析器的实现（部分省略）同样简洁：
let stmt, stmtRef = createParserForwardedToRef() let stmtList = sepBy1 stmt (ch ';') let assign = pipe2 id (str ":=" >>. expr) (fun id e -> Assign(id, e)) let print = str "print" >>. expr |>> Print let pwhile = pipe2 (str "while" >>. expr) (str "do" >>. stmt) (fun es -> While(e, s)) let seq = str "begin" >>. stmtList .>> str "end" |>> Seq let ifthen = pipe3 (str "if" >>. expr) (str "then" >>. stmt) (opt (str "else" >>. stmt)) (fun e s1 optS2 -> match optS2 with | None -> IfThen(e, s1) | Some s2 -> IfThenElse(e, s1, s2)) do stmtRef:= choice [ifthen; pwhile; seq; print; assign] let prog = ws >>. stmtList .>> eof |>> Prog
在第二行，作为一个例子， stmt和ch是解析器， sepBy1是一个sepBy1解析器组合器，它接受两个简单的解析器并返回一个组合解析器。 在这种情况下， sepBy1 p sep返回一个解析器，该解析器解析由sep分隔的一个或多个p出现。 因此，您可以看到从简单的解析器中组合强大的解析器的速度有多快。 F＃对重写的运算符的支持也允许简洁的中缀表示法，例如序列组合器和选择组合子可以指定为>>. 和<|> 。
祝你好运，
丹尼
唯一可以由理智的人手写的解析器是递归下降。 也就是说，手写自下而上的解析器仍然是可能的，但是非常不受欢迎。
如果您正在使用RD解析器，则必须validationSQL语法不是左递归的（并在必要时消除递归），然后基本上为每个语法规则编写一个函数。 有关详细参考，请参阅此
将我的声音添加到合唱中，支持递归下降（LL1）。 它们简单，快速，而且IMO，完全不难维护。
但是，请仔细查看您的语言，确保它是LL1。 如果你有像C这样的语法，比如（（（（type））foo）[]）你可能必须先下降多层括号，然后才能发现你是在查看类型，变量还是表达式， LL1将非常困难，自下而上获胜。
递归下降会给你最简单的方法，但我不得不同意mouviciel那种flex和bison并且绝对值得学习。 当你发现你的语法有错误时，在flex / bison中修复语言的定义将比重写你的递归下降代码更容易。
仅供参考，C＃解析器是递归下降的，它往往非常健壮。
递归下降解析器确实是最好的，也许只有解析器，可以手工构建。 您仍然需要了解正式的，无上下文的语言，并将您的语言置于正常forms。 我个人建议你删除左递归并将你的语言放在Greibach Normal Form中 。 当你这样做时，解析器只是写自己。
例如，这个产品：
A => aC A => bD A => eF
变成简单的东西：
int A() { chr = read(); switch char case 'a': C(); case 'b': D(); case 'e': F(); default: throw_syntax_error('A', chr); }
而且这里没有任何更困难的案例（更难的是确保你的语法forms正确，但这可以让你控制你所提到的）。
Anton’s Link也很出色。
如果你想手工编写，递归正确是最明智的方法。
您可以使用表解析器，但这将非常难以维护。
例：
Data = Object | Value; Value = Ident, '=', Literal; Object = '{', DataList, '}'; DataList = Data | DataList, Data; ParseData { if PeekToken = '{' then return ParseObject; if PeekToken = Ident then return ParseValue; return Error; } ParseValue { ident = TokenValue; if NextToken <> '=' then return Error; if NextToken <> Literal then return Error; return(ident, TokenValue); } ParseObject { AssertToken('{'); temp = ParseDataList; AssertToken('}'); return temp; } ParseDataList { data = ParseData; temp = [] while Ok(data) { temp = temp + data; data = ParseData; } }
我建议你不要手写lexer – 使用flex或类似的。 识别令牌的任务并不难以手工完成，但我认为你不会获得太多收益。
正如其他人所说，递归下降解析器最容易手写。 否则，您必须维护每个令牌的状态转换表，这不是人类可读的。
我非常确定ANTLR实现了一个递归下降解析器： 在一篇关于ANTLR 3.0的采访中提到了它。
我还发现了一系列关于用C＃编写解析器的博客文章。 看起来很温柔。
冒着冒犯OP的风险，当有好的解析器生成器工具（例如ANTLR）可用时，为某个特定供应商的SQL编写一个大型语言解析器，这简直就是疯了。 您将花费更多的时间手动重写解析器而不是使用解析器生成器修复“边缘情况”，并且随着SQL标准的移动或者您发现您被误解，您总是必须返回并修改解析器别的。 如果您不能很好地理解您的解析技术，请花时间去理解它。 使用解析器生成器来处理边缘情况并不需要花费数月时间，而且您已经承认它愿意花费数月时间手动执行它。
话虽如此，如果你一心想要手动重做它，使用递归下降解析器是手动完成它的最好方法。
（注意：OP在下面澄清他想要一个参考实现。恕我直言，你不应该在程序上编写一个语法的参考实现，所以递归下降。）
没有“最好的”方式。 根据您的需要，您可能需要自下而上（LALR1）或递归下降（LLk）。 诸如此类的文章给出了个人原因，希望将LALR（1）（自下而上）改为LL（k）。 但是，每种类型的解析器都有其优点和缺点。 通常，LALR会更快，因为有限状态机会生成为查找表。
选择适合你的方法来检查你的情况; 熟悉工具和技术。 从一些LALR和LL维基百科文章开始并不是一个糟糕的选择。 在这两种情况下，您都应该始终在BNF或EBNF中指定语法。 我更喜欢EBNF的简洁性。
一旦你完成了你想要做的事情，以及如何将它表示为语法，（BNF或EBNF）尝试几种不同的工具，并在要解析的代表性文本样本中运行它们。
据传：
但是，我听说LL（k）更灵活。 我从来没有费心去找自己。 从我的几个解析器构建经验中我注意到，如果它是LALR或LL（k），那么选择最适合您需求的最佳方法就是从编写语法开始。 我编写了自己的C ++ EBNF RD解析器构建器模板库，使用了Lex / YACC并编写了一个小的RD解析器。 这是在15年的大部分时间里传播的，我在这三个项目中花费的时间不超过2个月。
在C / Unix中，传统的方法是使用lex和yacc。 使用GNU，相同的工具是flex和bison。 我不知道Windows / C＃。
如果我是你，我将使用GUI ANTLRWorks再次访问ANTLRv3，它为您提供了一种非常方便的语法测试方法。 我们在项目中使用ANTLR，虽然学习曲线在开始学习时可能会有点陡峭但非常方便。 另外，在他们的电子邮件通讯中，有很多人非常乐于助人。
PS。 IIRC他们也有一个你可以看一下的SQL语法。
心连心
好吧，如果你不介意使用像ANTLR这样的其他编译器编译器工具，我建议你看看Coco / R.
我过去用过它，非常好……
您不希望使用表驱动的解析器的原因是您将无法创建合理的错误消息。 这对于生成的语言是可以的，但不适用于涉及人类的语言。 由类似c语言的编译器生成的错误消息提供了充分的证据，表明人们可以适应任何事情，无论多么糟糕。
我也会投票使用现有的解析器+词法分析器。
我手工做的唯一原因是：
- 如果你想要一些相对简单的东西（比如validation/解析一些输入）
- 学习/理解原则。
查看.NET的gplex和gppg，lexer和parser生成器。 它们运行良好，并且基于与lex和yacc相同（并且几乎兼容）的输入，这相对容易使用。
JFlex是Java的flex实现，现在有一个该项目的C＃端口http://sourceforge.net/projects/csflex/ 。 似乎还有一个正在进行CUP的C＃端口，可以在这里找到： http ： //sourceforge.net/projects/datagraph/
我也建议避免手工制作你自己的解决方案。 我曾经尝试过一次非常简单的语言（大学项目的一部分），这非常费时费力。 一旦写完，维护和更改也非常困难。
使用现有的解析器生成器是可行的方法，因为大量的艰苦工作已经完成并且多年来经过了充分的测试。