编译原理复习——语法分析(自底向上)

方法描述 自左向右逐个扫描输入串，一边把输入符号 移进 分析栈 ，一边检查位于栈顶的一串符号是 否与某个产生式的右部相同，如果相同，就把 栈顶的这串符号 归约 为左部的非终结符；如果 不同，则继续移入输入符号，进行判断。上述 过程一直重复到 输入串结束 ，栈内 恰好为 S 。 归约 自底向上分析法是“移进 — 归约”法 ①移进 ——读入一单词并压入栈内，指针下移一位 ②归约 ——检查栈顶若干符号是否为分析表中产生式右部， 若是，用左部替换 ③识别成功 ——栈内为文法开始符号，指针指向# ④其他出错 自底向上分析的思路 在自左向右移进输入串的过程中，一旦发现 栈 顶呈现可归约串 就立即归约。 所以自底向上分析的中心问题是： 怎么判断栈顶符号串的可归约性和 如何归约 句柄的另一种定义 : 句型的句柄是和某产生式右部匹配的子串，并且， 把它归约成该产生式左部的非终结符代表了 最右推 导过程的逆过程 的一步 规范规约 假定 α 是文法 G 的一个句子，称序列 α n ， α n － 1， … α 0 是 α 的一个规范归约，则此序列满足： α n ＝ α α 0 为文法开始符，即 α 0 ＝ S 对任何 i ， 0 α 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 ] = 空白，出错标识，报错

 例子： 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！