词法分析与句法分析
词法分析和句法分析构成了编译器的前端，它们将源文本分解成标记，并将其语法结构识别为解析树或语法树。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
词法分析是将输入字符分组为标记的阶段，而句法分析（解析）是根据语法确定这些标记是否以及如何构成有效程序，并生成语法树的阶段。
Scope
本主题涵盖词法分析，它使用正则语言和有限自动机将字符流转换为标记；以及句法分析（解析），它根据上下文无关文法识别程序的短语结构。它包括自顶向下（LL）和自底向上（LR）解析、解析器生成器、歧义和错误恢复，以及抽象语法树的构建。
Core questions
- 正则语言和上下文无关语言如何用于描述程序结构？
- LL和LR解析之间的权衡是什么？
- 如何检测和处理歧义和解析错误？
- 如何从标记流构建抽象语法树？
Key theories
- LR解析
- 高德纳引入了LR解析，这是一种自底向上的技术，它以线性时间确定性地解析广泛的LR文法，构成了许多解析器生成器的基础。
- 通用上下文无关解析
- 厄尔利算法解析任意上下文无关文法，包括有歧义的文法，当受限的确定性解析器不足时，它提供了一种通用方法。
- 前端的正则和上下文无关基础
- 《龙书》系统化地阐述了使用正则表达式和有限自动机进行词法分析以及使用上下文无关文法进行句法分析的方法，包括标准的LL和LR构建算法。
Clinical relevance
词法分析和解析不仅是编译器的基础，也是解释器、代码检查器、格式化工具、集成开发环境（IDE）和数据格式处理器的基础。具有良好错误恢复能力的健壮解析对于任何语言工具的开发者体验都至关重要。
History
乔姆斯基在20世纪50年代后期提出的形式语言层次结构为正则语言和上下文无关语言提供了理论基础。高德纳于1965年将LR解析形式化，而厄尔利于1970年提出了一种通用的上下文无关算法。像yacc这样的解析器生成器使LR解析变得实用，而后续的工作则探索了解析表达式文法和基于组合子的解析器。
Debates
- 生成式解析器与手写解析器
- 实践者们就使用基于形式文法的解析器生成器（其简洁且可验证）与手写递归下降解析器（通常能提供更好的错误消息和控制，但代码量更大）展开争论。
Key figures
- Donald Knuth
- Jay Earley
- Alfred Aho
- Noam Chomsky
Related topics
Seminal works
- knuth1965
- earley1970
- aho2006
Frequently asked questions
- 词法分析器和解析器有什么区别？
- 词法分析器将原始字符分组为标识符和运算符等标记，而解析器则根据语言的语法将这些标记排列成层次结构的语法树。
- LL和LR解析有什么区别？
- LL解析器自顶向下工作，从输入前缀预测产生式；而LR解析器自底向上工作，归约已识别的子字符串；LR处理的文法类别严格更大，但构建起来更复杂。