algorithm - 如何创建允许语法错误的 AST 解析器？

Question

首先，要阅读有关解析和构建 AST 的哪些内容？

如何为将构建 AST 并允许语法错误的语言(如 SQL)创建解析器？

例如，对于“3+4*5”:

  +
 / \
3   *
   / \
  4   5

对于语法错误的“3+4*+”，解析器会猜测用户的意思是:

  +
 / \
3   *
   / \
  4   +
     / \
    ?   ?

从哪里开始？

SQL:

    SELECT_________________
   /           \           \
  .           FROM        JOIN
 / \           |         /    \
a city_name  people   address  ON
                                |
                                =______________
                               /               \
                              .____             .
                             /     \           / \
                            p  address_id     a  id

Answer 1

如何构建解析器(即构建 AST)的标准答案是阅读有关编译的标准文本。 Aho 和 Ullman 的“Dragon”编译器一书非常经典。如果您没有耐心去获取最好的引用资料，您将会遇到更多的麻烦，因为它们提供理论并研究细微之处。但是here is my answer对于赶时间的人，构建递归下降解析器。

可以构建具有内置错误恢复功能的解析器。这种事情有很多论文，是80年代的热门话题。查看谷歌学术，搜索“语法错误修复”。基本思想是，解析器在遇到解析错误时，会跳到某个众所周知的信标(“;”，语句定界符在类 C 语言中非常流行，这就是为什么你在评论中被问及你的语言是否有语句终止符)，或提出各种输入流删除或插入以越过语法错误点。此类计划的多样性令人惊讶。关键思想通常是尽可能多地考虑围绕错误点的信息。我见过的最有趣的想法之一是两个解析器，一个先于另一个运行 N 个标记，寻找语法错误地雷，第二个解析器是基于 N 的馈送错误修复在遇到语法错误之前可用的 token 。这让第二个解析器在到达语法错误之前选择不同的行为。如果你没有这个，大多数解析器会丢弃左上下文，从而失去修复的能力。 (我从未实现过这样的方案。)

要插入的内容的选择通常可以首先从用于构建解析器(通常是First 和Follow 集)的信息中得出。这对于 L(AL)R 解析器来说相对容易，因为解析表包含必要的信息并且在遇到错误时可供解析器使用。如果您想了解如何执行此操作，则需要了解有关如何构造解析器的理论(哎呀，又是那本编译器书)。 (这个方案我已经成功实现了好几次)。

无论您做什么，语法错误修复都无济于事，因为几乎不可能猜测已解析文档的作者的实际意图。这表明花哨的计划不会真正有用。我坚持简单的；人们很高兴收到错误报告和一些半优雅的解析继续。

为真正的语言使用自己的解析器的一个真正问题是，真正的语言是令人讨厌的困惑事物；构建实际实现的人会因为现有代码库而出错并一成不变，或者因为它很酷而坚持改变/改进语言(标准是为了懦夫，好东西是为了营销)。预计将花费大量时间根据真实代码的基本事实重新校准你认为的语法。作为一般规则，如果您想要一个可用的解析器，最好是获得一个有良好记录的解析器，而不是自己动手。

大多数一心想要构建解析器的人没有得到的教训是，如果他们想对解析结果或树做任何有用的事情，他们将需要很多比解析器更基本的机制。查看我的简历，了解“解析后的生活”。