parsing - 计算机科学教科书进行文本/xml/任何解析的方法

Question

它已经在我的脑海里嗡嗡作响了一段时间。

我对 Compilers/Flex/Byson 等进行了一些调查，但我从未找到详细讨论“解析堆栈”或如何实现一个的好参考。

有谁知道我可以赶上的好的参考资料？

编辑：我非常感谢所有编译器参考，我将列出一些书籍，但我的主要关注点是解析本身，而不是你之后用它做什么。

Answer 1

龙书！我最近用它编写了一个编译器（用 PHP！），用于处理用 RTF 编写的模板文件的语言......

Answer 2

这是对您接受为正确答案的 Dima 的回答的回应。虽然说解析与自动机理论有关这不是一个糟糕的答案，但我觉得这里有一些误解。

• 首先，有限状态自动机只能识别正则语言（例如正则表达式）。为了识别上下文无关语言，您需要更强大的下推自动机。有关更多自动机及其与不同语言类别的关系，请参见http://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata 。

• 其次，解析不同于识别。识别字符串只会告诉您该字符串是否是您的语法生成的语言。解析器的目的是生成一个更难且通常更有用的具体语法树。

解析方法种类繁多，因此很难为您提供一份具体的参考资料来告诉您需要了解的内容……总的来说，您应该了解自顶向下解析和自底向上解析之间的区别。但如果您有兴趣，这里是解析器生成器采用的一些常用技术的概述：

• LR Parsing、LL Parsing、SLR Parsing、LALR Parsing、GLR Parsing的维基百科文章
• ANTLR 的LL(*) 解析
• Haskell 中的 Monadic Parsing（用于在函数式编程语言中构建解析器）
• 还有更奇特的Parsing Expression Grammars

EDIT: I'm sorry for bumping this question again, I just happened across two excellent posts describing the relationship between regular languages and finite automata, context-free languages and push-down automata. Might be interesting for people who find this question.

Answer 3

解析器基本上是一个有限状态机，也就是一个有限自动机。你应该找到一本关于计算理论的书，它讨论了有限自动机，以及诸如常规语言、上下文无关语言等之类的东西。

Answer 4

试试亚马逊

编译器构造只是一个很好的例子

Answer 5

查看“Brinch Hansen on Pascal Compilers”。它写于 1985 年，但我去年在编译器课程中使用了它（当然是 Per Brinch Hansen。），发现它非常简洁，对编译器设计很有帮助。