IT小白

这个屌丝很懒，什么也没留下！

热门标签

编译原理复习——语法分析(自底向上)_lr分析法自底向上规约可找出出错的地方

作者：IT小白 | 2024-04-29 12:58:54

踩

lr分析法自底向上规约可找出出错的地方

方法描述

自左向右逐个扫描输入串，一边把输入符号 移进 分析栈 ，一边检查位于栈顶的一串符号是

否与某个产生式的右部相同，如果相同，就把 栈顶的这串符号 归约 为左部的非终结符；如果

不同，则继续移入输入符号，进行判断。上述 过程一直重复到 输入串结束 ，栈内 恰好为 S 。

归约

自底向上分析法是“移进 — 归约”法

①移进 ——读入一单词并压入栈内，指针下移一位

②归约 ——检查栈顶若干符号是否为分析表中产生式右部， 若是，用左部替换

③识别成功 ——栈内为文法开始符号，指针指向#

④其他出错

自底向上分析的思路

在自左向右移进输入串的过程中，一旦发现 栈 顶呈现可归约串 就立即归约。

所以自底向上分析的中心问题是：

怎么判断栈顶符号串的可归约性和 如何归约

句柄的另一种定义 :

句型的句柄是和某产生式右部匹配的子串，并且， 把它归约成该产生式左部的非终结符代表了 最右推 导过程的逆过程 的一步

规范规约

假定 α 是文法 G 的一个句子，称序列 α n ， α n － 1， … α 0 是 α 的一个规范归约，则此序列满足：

α n ＝ α

α 0 为文法开始符，即 α 0 ＝ S

对任何 i ， 0<i≤n， α i － 1 是从 α i 经把句柄 替换为 相应 产生式 的左部 符号而得到的

最右推导的逆过程 等价于 最左归约 等价于 规范归约

在求解语法分析自顶向下分析中我们采用的是LL(1)分析，那么在语法分析自底向上分析中我们采用的是LR(1)分析。

LR(K)

L : 自左向右扫描输入串

R : 最右推导的逆过程 ( 规范归约，最左规约 )

K : 向右查看 输入串符号的个数 (K 省略时 , 表示 K 等于 1 ，当 K=1 时，能满足当前绝大多数 高级语言编译程序的需要 )

LR 分析过程是规范归约过程

LR 分析法的特点

LR 分析器（程序）基本上 可以识别所有 上下 文无关文法写的编程设计语言的结构，分析能 力强且适用范围广

LR 分析法是当前 最一般 “ 移进 - 归约 ”分析方 法

LR 分析法在 自左向右 扫描输入串时能发现其 中错误，并能 指出出错地点

LR 分析程序可以自动生成

LR 分析表的分类

LR(0) ：最简单分析表，分析表的局限性大 , 是其它 LR 分析法的 基础

SLR(1) ：简单分析表，分析表稍有局限性， 但较易实现

LR(1) ：分析表能力最强，但代价过高

LALR(1) ：称为向前看 LR 分析表，分析表能 力介于 SLR(1) 和 LR(1)之 间，适用于大多数程 序设计语言的结构，并且可以比较有效地实现

说明：四种分析表对应四类文法

LR 分析方法的基本思想

LR 分析器的每一步工作都是由 栈顶状态 和现 行输入 符号 所唯一决定的。

一个 LR 分析器实质上是一个 DFA

S是移进操作 r是规约操作 GOTO则是状态转换的操作当一个状态遇到了非终结符是会进行GOTO

下面是一个LR分析表来举一下例子：

最后我们也是希望通过学习得到这样的一个分析表来实现

我们看到有两个部分一个是ACTION部分还有一个是GOTO状态转换部分

Action[s n , a i ]: 当前状态 s n 面对输入符号 a i 时采叏的动作

(1) 移进 – s j

(2) 归约 – r j

(3) 接受 – acc

(4) 报错 – 空白 / ‘出错’ / ‘error’ 一般都是空白

(1) 移进 – Action[s n , a i ] = s j

把现行输入符号 a i 和下一状态 j 分别移进状态栈和符号栈

状态栈和符号栈的个数是一样的

GOTO [ s n ， a i ] = j

(2) 归约 - Action[s n , a i ] = r j

用第 j 条产生式 A→ β 归约 . |β| =r

(3) 接受 – Action[s n , a i ] = acc, 宣布分析成功

(4) 报错 – Action[s n , a i ] = 空白，出错标识，报错

例子：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/507866