鸭梨公共文档

主题

第四章：词法分析 3 ​

4.8 自底向上分析概述 ​

4.8.1 移入-归约分析 ​

自底向上的语法分析：

  • 从分析树的底部（叶节点）向顶部（根节点）方向构造分析树
  • 可以看成是将输入串 ww 归约为文法开始符号 SS 的过程
    • 自顶向下的语法分析采用最左推导方式
    • 自底向上的语法分析采用最左归约方式（反向构造最右推导）
  • 自底向上语法分析的通用框架
    • 移入-归约分析（Shift-Reduce Parsing）

4.8.2 移入-归约分析示例 ​

TODO

4.8.3 移入-归约分析的工作过程 ​

过程：

  • 在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串 β\beta 进行归约为止
  • 然后，它将 β\beta 归约为某个产生式的左部
  • 语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空（当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析）为止

TODO

4.8.4 移入-归约分析器可采取的动作 ​

  1. 移入：将下一个输入符号移到栈的顶端
  2. 归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
  3. 接收：宣布语法分析过程成功完成
  4. 报错：发现一个语法错误，并调用错误恢复子例程

4.8.5 移入-归约分析中存在的问题 ​

TODO

4.9 LRLR 分析法概述 ​

4.9.1 LRLR 分析法 ​

LRLR 文法（Knuth, 1963）是最大的、可以构造出相应移入-归约语法分析器的文法类：

  • L：对输入进行从左到右的扫描
  • R：反向构造出一个最右推导序列

LR(k)LR(k) 分析：

  • 需要向前查看 kk 个输入符号的 LRLR 分析
  • k=0k = 0 和 k=1k = 1 这两种情况具有实践意义
  • 当省略 kk 时，表示 k=1k = 1

4.9.2 LRLR 分析法的基本原理 ​

自底向上分析的关键问题是：如何正确地识别句柄？

  • 句柄是逐步形成的
  • 用 “状态” 表示句柄识别的进展程度

例如：

S→bBBS→⋅bBB  (移进状态)S→b⋅BB  (待约状态)S→bB⋅B  (待约状态)S→bBB⋅  (归约状态)\begin{aligned} S &\rightarrow bBB \\ S &\rightarrow \cdot bBB \;(\text{移进状态})\\ S &\rightarrow b \cdot BB \;(\text{待约状态})\\ S &\rightarrow bB \cdot B \;(\text{待约状态})\\ S &\rightarrow bBB \cdot \;(\text{归约状态}) \end{aligned}

TODO 需要补充说明。

LRLR 分析器基于这样一些状态来构造自动机进行句柄的识别。

4.9.3 LRLR 分析器（自动机）的总体结构 ​

LR 自动机

4.9.3 LRLR 分析表的结构 ​

例如：

G:  S→BBB→aBB→b\begin{aligned} G:\; S &\rightarrow BB \\ B &\rightarrow aB \\ B &\rightarrow b \end{aligned}

含义：

  • sns_n ：将符号 aa 、状态 nn 压入栈
  • rnr_n ：用第 nn 个产生式进行归约

例如输入 bab\text{bab} ：

TODO

4.9.4 LRLR 分析器的工作过程 ​

初始化：

  • 状态栈： s0s_0
  • 符号栈： $  \$\;
  • 缓冲区： a1a2⋯an$  a_1 a_2 \cdots a_n\$\;

一般情况：

  • 状态栈： s0s1⋯sms_0 s_1 \cdots s_m
  • 符号栈： $X1X2⋯Xm\$X_1 X_2 \cdots X_m
  • 缓冲区： aiai+1⋯an$  a_i a_{i+1} \cdots a_n\$\;

如果 ACTION[sm, ai]=sx\mathrm{ACTION}\left[s_m,\,a_i\right] = \text{s}x 那么格局变为：

  • 状态栈： s0s1⋯smxs_0 s_1 \cdots s_m x
  • 符号栈： $X1X2⋯Xmai\$X_1 X_2 \cdots X_m a_i
  • 缓冲区： ai+1⋯an$  a_{i+1} \cdots a_n\$\;

如果 ACTION[sm, ai]=rx\mathrm{ACTION}\left[s_m,\,a_i\right] = \text{r}x 表示用第 xx 个产生式 A→Xm−(k−1)⋯XmA \rightarrow X_{m-(k-1)} \cdots X_m 进行归约，那么格局变为：

  • 状态栈： s0s1⋯sm−ks_0 s_1 \cdots s_{m-k}
  • 符号栈： $X1X2⋯XmA\$X_1 X_2 \cdots X_m A
  • 缓冲区： aiai+1⋯an$  a_i a_{i+1} \cdots a_n\$\;

如果 ACTION[sm, ai]=sx\mathrm{ACTION}\left[s_m,\,a_i\right] = \text{s}x 那么格局变为：

如果 ACTION[sm, ai]=acc\mathrm{ACTION}\left[s_m,\,a_i\right] = \text{acc} 那么分析成功。

如果 ACTION[sm, ai]=err\mathrm{ACTION}\left[s_m,\,a_i\right] = \text{err} 那么出现语法错误。

4.9.5 LRLR 分析算法 ​