编译原理：自下而上语法分析

发表于 更新于 分类于

移进 - 归约

  1. 当前单词（Token）入栈
  2. 查看栈顶是否有产生式的候选可以归约
    1. 有的话则进行归约，用与替换栈顶元素或串
    2. 没有的话跳转到 1

短语、直接短语

短语就是可归约串

直接短语是可立即归约的串

可以构成非终结符的终结符序列

对照于语法树上，两代以上的子树的叶子从左到右排列为短语，两代子树为直接短语

分析过程

G(E)

E → T | E+T

T → F | T*F

F → (E) | i

分析 i * i + i

步骤 符号栈 输入串 可用产生式
0 # i*i+i#
1 #i *i+i# i 入栈
2 #F *i+i# F → i
3 #T *i+i# F → T
4 #T* i+i# *入栈
5 #T*i +i# i 入栈
6 #T*F +i# F → i
7 #T +i# T → T*F
8 #E +i# E → T
9 #E+ i# + 入栈
10 #E+i # i 入栈
11 #E+F # F → i
12 #E+T # T → F
13 #E # E → E+T
14 #E # 接受

LR 分析法

L：从左到右扫描

R：自下而上归约

  1. 产生分析表
  2. 语法分析

句柄

自下而上自左向右应该立即归约的短语

规范归约

用句柄来归约

称序列 αn,αn−1,...,α0\alpha_n, \alpha_{n-1},...,\alpha_0 是 α\alpha 的一个规范归约，如果此序列满足

  1. αn=α\alpha_n = \alpha
  2. α0\alpha_0为文法的开始符号，即 α0\alpha_0 = S
  3. 对任何 i，0<i≤n0<i\leq n，αi−1\alpha_{i-1} 是从 αi\alpha_i 经把句柄替换成为相应产生式左部符号而得到的（就是新的归约是从前一个归约的句柄替换为产生式的左部得到的）

LR 分析

关键问题：寻找句柄

  • 历史信息：已经在分析栈内的内容
  • 展望信息：根据产生式预测未来可能的输入符号
  • 现实信息：现在的输入字符

历史和展望 抽象为 状态，根据栈顶状态和现行的输入符号唯一确定每一步的工作。

两个栈：分析栈（栈顶为移进或归约产生的最近的符号）、状态栈（栈顶为当前状态）

LR分析表：核心，根据栈顶状态和输入查表

  • 移进 Or 归约以及需要的信息
  • ACTION[s , a] 当状态 s 面临输入符号 a 时，应该采取的动作
  • GO[s, X] 状态 s 面对 X 时，X为非终结符，下一状态是什么

si：移进，新的状态为 i

ri：归约，用 i 号产生式归约，然后查 GO 表 [当前状态，归约后的新符号] 可以查到新的状态

总结：拿着当前状态和当前输入查 ACTION 表，查应该归约还是应该移进还是接受，如果是归约的话，需要将现在的分析栈栈顶和状态栈栈顶弹出，压入归约后的文法符号，然后拿着现在栈顶的状态和新压入的文法符号查 GOTO 表查出新的状态压入状态栈

栈内的符号串和扫描剩下的输入符号串构成了一个规范句型

句柄只能在栈顶

LR 文法

可以构造每个入口均是唯一确定的文法就称为 LR 文法

  • 无二义性

前缀

前缀：字的任意首部

活前缀：规范句型的一个前缀

分析栈中总是活前缀，证明分析是正确的

构造 DFA 识别文法的活前缀

LR(0) 项目

  • 在每个产生式的右部添加一个远点
  • 表示我们再分析过程中看到了产生式的多大部分 点左边是已经看到的
  • A→α⋅A \rightarrow \alpha \cdot 称为归约项目
  • S′→αS' \rightarrow \alpha 接受项目
  • A→α⋅aβA \rightarrow \alpha \cdot a \beta 移进项目
  • A→α⋅BβA\rightarrow\alpha \cdot B\beta 待约项目（等待归约 B）

构造 LR 分析表