-
编译原理复习——词法分析(自底向上)
方法描述自左向右逐个扫描输入串，一边把输入符号 移进 分析栈 ，一边检查位于栈顶的一串符号是否与某个产生式的右部相同，如果相同，就把 栈顶的这串符号 归约 为左部的非终结符；如果不同，则继续移入输入符号，进行判断。上述 过程一直重复到 输入串结束 ，栈内 恰好为 S 。归约自底向上分析法是“移进 — 归约”法①移进 ——读入一单词并压入栈内，指针下移一位②归约 ——检查栈顶若干符号是否为分析表中产生式右部， 若是，用左部替换③识别成功 ——栈内为文法开始符号，指针指向#④其他出错自底向上分析的思路在自左向右移进输入串的过程中，一旦发现 栈 顶呈现可归约串 就立即归约。所以自底向上分析的中心问题是：怎么判断栈顶符号串的可归约性和 如何归约句柄的另一种定义 :句型的句柄是和某产生式右部匹配的子串，并且， 把它归约成该产生式左部的非终结符代表了 最右推 导过程的逆过程 的一步规范规约假定 α 是文法 G 的一个句子，称序列 α n ， α n － 1， … α 0 是 α 的一个规范归约，则此序列满足：α n ＝ αα 0 为文法开始符，即 α 0 ＝ S对任何 i ， 0最右推导的逆过程 等价于 最左归约 等价于 规范归约在求解语法分析自顶向下分析中我们采用的是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 分析器实质上是一个 DFAS是移进操作 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 ] = 空白，出错标识，报错例子：
-
相关阅读:
定期清理ES
FME&ArcGIS版本兼容性
Matlab高效编程：向量化(vectorization)、矩阵化、变量预定义
【Java集合框架】16 ——NavigableSet 接口
LabVIEW使用视觉采集软件从GigE视觉相机进行采集 1
计算机组成原理_浮点数的表示与运算
.locked勒索病毒的最新威胁：如何恢复您的数据？
python 爬虫的开发环境配置
【idea】 java: 找不到符号
购买窗帘时哪些可以不做？-江南爱窗帘十大品牌
- 原文地址：https://blog.csdn.net/m0_53345417/article/details/127671768