自底向上的语法分析

小咪咪 2022-02-05 13:06 180阅读 0赞

### 文章目录 ###

*  概念
 *  移入-规约分析
 *   *  工作过程
     *  可采取的动作
     *  例子
     *  存在的问题

# 概念 #

*  从分析树的 **底部（叶节点）向 顶部（根节点）** 方向构造分析树
 *  可以看成是将输入穿`$w$`规约为文法开始符号`S`的过程
 *  自顶向下的语法分析采用**最左推导方式**
 *  **自底向上的语法分析**采用**最左规约**方式（反向构造最右推导）

# 移入-规约分析 #

## 工作过程 ##

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

## 可采取的动作 ##

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

## 例子 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]

## 存在的问题 ##

*  失败的规约过程：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]

*  失败的原因：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20220205/a64ea042f03d49cf8e73b00acc8a070d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20220205/adcdc93639934407b87bfe19c4f8b733.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]: /images/20220205/9d2a847d801941659940f198de0f886a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 3]: /images/20220205/042ff5b30eaf4b739ed95798b92ef9e2.png