一、LR 分析器模型
LR 分析器是自底向上语法分析的一种高效实现，广泛应用于编译器构造中。其核心思想是从左到右扫描输入符号串，使用最右推导的逆过程进行归约（Left-to-right, Rightmost derivation in reverse）。
LR 分析器模型组成：
- 输入缓冲区：存放待分析的词法单元序列，通常以
#作为结束标志。 - 输出：语法分析的结果（如语法树或归约序列），也可用于触发语义动作。
- 栈结构：
- 状态栈（State Stack）：保存当前识别文法状态的编号（对应于DFA状态）。
- 符号栈（Symbol Stack）：保存与状态对应的文法符号（终结符或非终结符）。
- 两栈同步操作，共同表示当前“格局”（configuration）。
- 分析表（Parsing Table）：
- ACTION 表：决定在某个状态遇到某输入符号时应执行的动作（移进、归约、接受、报错）。
- GOTO 表：指出当归约出一个非终结符后，下一状态应转入何处。
- 驱动器（控制程序）：根据当前状态和输入符号查表，执行相应动作，更新栈内容。
初始格局为(S₀, #; 输入串)，目标格局为(S₀ S₁...Sm, #S; #)且 ACTION[Sm, #] = accept。
二、LR 分析的 4 种动作详解：
移进（Shift s）
- 当前状态和输入符号查 ACTION 表得 “shift s”。
- 将当前输入符号压入符号栈，状态 s 压入状态栈。
- 输入指针前移一位。
- 示例：若当前栈为
[S₀, a]，输入为b...，ACTION[S₀, b] = shift 3，则将b和状态 3 入栈。
归约（Reduce A → β）
- 栈顶出现句柄
β（长度为 r），查 ACTION 表得 “reduce A → β”。 - 弹出栈顶 r 个符号和 r 个状态，得到新栈顶状态
S_i。 - 查 GOTO[S_i, A] 得到新状态
s_j，将非终结符 A 和状态s_j压入栈。 - 此步模拟了文法规则的一次反向推导。
- 栈顶出现句柄
接受（Accept）
- 表示整个输入已被成功归约为文法开始符号 S，且输入已全部读取完毕。
- 分析成功，结束过程。
报错（Error）
- 在当前状态无法进行任何有效动作（ACTION 表项为空）。
- 触发错误恢复机制或直接终止分析。
三、语法制导翻译（Syntax-Directed Translation, SDT）
是将语法分析与语义处理结合的技术，通过在文法规则中嵌入“语义动作”或“语义规则”，在分析过程中逐步计算属性值，生成中间代码或进行类型检查等静态语义分析。
基本概念：
- 属性文法（Attribute Grammar）：上下文无关文法 + 属性 + 语义规则。
- 两类属性：
- 综合属性（Synthesized Attributes）：由子节点传递给父节点（自下而上传递）。
- 继承属性（Inherited Attributes）：由父节点或兄弟节点传递给当前节点（自上而下或横向传递）。
- 语义规则：定义如何根据产生式中的符号计算其属性值。
- 语义动作：插入在产生式中的代码片段，在特定时刻执行（如归约后）。
应用示例：表达式求值
E → E₁ + T { E.val = E₁.val + T.val } E → T { E.val = T.val } T → num { T.val = num.lexval }上述规则为每个非终结符赋予一个综合属性val，在归约时执行相应的语义动作完成数值计算。
其他形式化语义描述方法包括：
- 操作语义（Operational Semantics）：通过抽象机的执行步骤定义语言含义。
- 公理语义（Axiomatic Semantics）：用逻辑断言（前置条件/后置条件）描述程序行为，常用于程序验证。
- 指称语义（Denotational Semantics）：将语言构造映射到数学对象（函数、集合等）。