编译原理第三章：词法分析与语法分析详解

编译原理第三章主要涉及词法分析和语法分析两个知识点。

词法分析（Lexical Analysis）：词法分析是编译过程中的第一个阶段，主要负责将输入的源代码按照规则划分为一个个词法单元（Token），例如标识符、关键字、运算符等。词法分析器通常使用有限状态自动机（Finite State Automaton）来实现。
语法分析（Syntax Analysis）：语法分析是编译过程中的第二个阶段，主要负责根据词法分析得到的词法单元序列构建抽象语法树（Abstract Syntax Tree，AST）。语法分析器使用语法规则（文法）来检查源代码是否符合语法规定，并生成相应的语法树。常见的语法分析方法有递归下降分析法、LL(1) 分析法和LR(1) 分析法等。
上下文无关文法（Context-Free Grammar，CFG）：上下文无关文法是描述编程语言语法的形式化工具。它由一组产生式（Production）和一个起始符号（Start Symbol）组成。产生式表示语法规则，起始符号表示语法分析的起点。根据上下文无关文法可以生成语法树。
语法制导翻译（Syntax-Directed Translation）：语法制导翻译是一种将源代码翻译成目标代码的方法，它将翻译动作嵌入到语法分析过程中。语法制导翻译可以使用属性文法（Attribute Grammar）来描述，在语法分析的同时进行语义动作的计算。
常见的语法分析算法：
- 递归下降分析法（Recursive Descent Parsing）：根据产生式的左部开始向右展开，递归地构建语法树。
- LL(1) 分析法：使用预测分析表进行语法分析，LL(1) 文法要求每个非终结符的每个产生式的首符集（First Set）两两不相交。
- LR(1) 分析法：使用移进-归约操作进行语法分析，LR(1) 文法要求每个非终结符的每个产生式的前缀的后继符集（Follow Set）两两不相交。

以上是编译原理第三章的主要知识点，涵盖了词法分析和语法分析的基本概念和方法。