首先,关于解析和构建 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
如何构建解析器(构建 AST)问题的标准答案是阅读编译时的标准文本。 Aho 和 Ullman 的《Dragon》编译器书非常经典。如果您没有耐心获得最好的参考资料,您将会遇到更多麻烦,因为它们提供了理论并研究了微妙之处。但这是我的答案 https://stackoverflow.com/a/25106688/120163对于匆忙的人来说,构建递归下降解析器。
人们可以构建具有内置错误恢复功能的解析器。关于这类事情有很多论文,这是 20 世纪 80 年代的热门话题。查看谷歌学术搜索,寻找“语法错误修复”。基本思想是,解析器在遇到解析错误时,会跳到一些众所周知的信标(“;”语句分隔符在类似 C 的语言中非常流行,这就是为什么您在评论中被问到您的语言是否有语句终止符),或者提出各种输入流删除或插入以克服语法错误点。此类计划的多样性令人惊讶。关键思想通常是考虑尽可能多的信息around尽可能的指出错误点。我见过的最有趣的想法之一two一个解析器先于另一个解析器运行 N 个标记,寻找语法错误地雷,第二个解析器在遇到语法错误之前根据可用的 N 个标记进行错误修复。这使得第二个解析器可以在出现语法错误之前选择不同的行为。如果没有这个,大多数解析器都会丢弃剩余的上下文,从而失去修复的能力。 (我从未实施过这样的计划。)
要插入的内容的选择通常可以从用于构建解析器的信息中得出(通常是First and Follow集)放在第一位。对于 L(AL)R 解析器来说,这相对容易做到,因为解析表包含必要的信息,并且解析器在遇到错误时可以使用它们。如果你想了解how为此,您需要了解如何构造解析器的理论(哎呀,又是那本编译器书)。 (这个方案我已经成功实施过好几次了)。
无论你做什么,语法错误修复都没有多大帮助,因为几乎不可能猜测解析文档的作者的实际意图。这表明花哨的计划不会真正有帮助。我坚持简单的;人们很高兴收到错误报告和一些半优雅的解析继续。
为真正的语言开发自己的解析器的一个真正的问题是,真正的语言是令人讨厌的混乱的东西;由于现有的代码库,构建实际实现的人们会犯错并被冻结,或者坚持改变/改进语言(标准是针对弱者的,好东西是针对营销的)因为它很酷。预计会花费大量时间根据真实代码的基本事实重新校准您认为的语法。作为一般规则,如果您想要一个可用的解析器,最好获得一个有跟踪记录的解析器,而不是自己动手。
大多数一心想要构建解析器的人都没有得到一个教训,那就是如果他们想做的话anything对于解析结果或树很有用,它们需要比解析器更多的基本机制。检查我的简历“解析后的生活”。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)