LR 分析器是自底向上语法分析的一种高效实现，广泛应用于编译器构造中

一、LR 分析器模型
LR 分析器是自底向上语法分析的一种高效实现，广泛应用于编译器构造中。其核心思想是从左到右扫描输入符号串，使用最右推导的逆过程进行归约（Left-to-right, Rightmost derivation in reverse）。

LR 分析器模型组成：

1. 输入缓冲区：存放待分析的词法单元序列，通常以#作为结束标志。
2. 输出：语法分析的结果（如语法树或归约序列），也可用于触发语义动作。
3. 栈结构：
   • 状态栈（State Stack）：保存当前识别文法状态的编号（对应于DFA状态）。
   • 符号栈（Symbol Stack）：保存与状态对应的文法符号（终结符或非终结符）。
   • 两栈同步操作，共同表示当前“格局”（configuration）。
4. 分析表（Parsing Table）：
   • ACTION 表：决定在某个状态遇到某输入符号时应执行的动作（移进、归约、接受、报错）。
   • GOTO 表：指出当归约出一个非终结符后，下一状态应转入何处。
5. 驱动器（控制程序）：根据当前状态和输入符号查表，执行相应动作，更新栈内容。

初始格局为(S₀, #; 输入串)，目标格局为(S₀ S₁...Sm, #S; #)且 ACTION[Sm, #] = accept。

二、LR 分析的 4 种动作详解：

1. 移进（Shift s）

   • 当前状态和输入符号查 ACTION 表得 “shift s”。
   • 将当前输入符号压入符号栈，状态 s 压入状态栈。
   • 输入指针前移一位。
   • 示例：若当前栈为[S₀, a]，输入为b...，ACTION[S₀, b] = shift 3，则将b和状态 3 入栈。

2. 归约（Reduce A → β）

   • 栈顶出现句柄β（长度为 r），查 ACTION 表得 “reduce A → β”。
   • 弹出栈顶 r 个符号和 r 个状态，得到新栈顶状态S_i。
   • 查 GOTO[S_i, A] 得到新状态s_j，将非终结符 A 和状态s_j压入栈。
   • 此步模拟了文法规则的一次反向推导。

3. 接受（Accept）

   • 表示整个输入已被成功归约为文法开始符号 S，且输入已全部读取完毕。
   • 分析成功，结束过程。

4. 报错（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）：将语言构造映射到数学对象（函数、集合等）。