对LR语法分析错误恢复的一些思考1
需积分: 0 84 浏览量
2022-08-08
22:45:39
上传
评论
收藏 18KB DOCX 举报
史文翰 No.2014211218 Cla.2014211304
对 LR 语法分析错误恢复的一些思考——规约动作的填入
以龙书 P169 的 SLR1 分析表为例（其实与教材上相同），试图探讨以下几个问题：
1、 在状态 3/7/8/9 中，规约动作被扩展至一行，这是为什么？有什么好处？
2、 用另一种方法，比如填入 e 类信息（已有的或新设计的报错指针 e1,e2,e3…）而不进行
规约，是否可以？
3、 什么条件下可以进行这样的扩展？
1、 首先观察这些状态的特征：有且只有一个规约动作（可能含有移进动作，若含有，则这
个状态本质上是没有产生移进-规约冲突的状态，但是不能含有其他的规约动作）。这暗
示了一个含义：无论当前输入字符是否是可进行规约的字符，如果想规约的话，只能用
唯一的式子来规约。这种状态中的空白格子的含义是：当前输入字符不可能出现在 规
约式（产生式）左边 的右侧，这是因为 SLR 最浅层次的规约要求就是利用 规约式左边
符号的 FOLLOW 集，而 FOLLOW 集代表着可能出现在这个非终结符之后的所有终结符。
当遇到错误时，说明一个不可能出现在其之后的输入符号出现了，例如，符号栈顶为
E+E，状态栈栈顶为 7，此时遇到了输入字符 a，由于分析表的空白，即使进行规约也是
无效的（FOLLOW 集告诉我们，a 永远不可能出现在规约之后符号 E 的右边）。但是若
强行进行规约，未尝不可：首先，当前输入的字符并不干扰符号栈内的状态；其次，就
算进行了（唯一）规约，a（错误的输入）也绝不可能移入栈中。这是因为规约之后的
符号和状态 面对这个 a 的时候，一定只有两个选择：其一，再次进行其他的（唯一）
规约，其二，在其他状态中接触到 e 类报错指针（e1,e2,e3…）。会不会规约之后这个错
误就消失了？这是不可能的，因为 FOLLOW 集是规约条件的本质，这个错误会传递，而
不是消失。这样做的好处是显而易见的：以延迟报错为代价，换取报错种类的减少和集
中。可以说的更本质一些，这些新填入的规约动作，将所有错误都引到了便于设计的 e
类错误信息中（也就是某些状态，这些状态中只出现移进动作，没有规约动作）。
2、 如果想给（上述）这样的状态添加 e 类报错信息是困难的，首先，此类状态（3/7/8/9）
的空白格子里并不好用统一的某个 e 来表征，这是因为此类状态中的错误是广义的“非
法”，即出现了 FOLLOW 集（假设为 SLR1）中不存在的字符，这好像是在告诉你：我这
边看到了个非法的字符，你再怎么使劲儿推导，你也推不出这个字符来，至于怎么错的，
这太宽泛了，我无法具体告诉你。所以量身定做一个 e 是麻烦的，不如上述的用规约动
作延迟报错、将错误引入到那些设计好的 e 来处理这个错误更精巧。
3、 可以从以上两个问题中明显看出，这个条件是规约动作的唯一性。如果一个状态中出现
两个或以上不同的规约动作（本质上是没有产生规约-规约冲突的状态），这样的扩展没
办法进行，因为试图做的规约动作已经不再唯一，而此题并不涉及这样的问题。如果有
这样的状态出现，则还需设计相应的 e（或者有其他的方法？）。
一句话小结：利用状态中规约动作的唯一性，将 SLR（或更高层的 LR 分析）退化至 LR0 状
态。以延迟报错的代价，换取程序设计上的简单和精巧。
PS：以上所有观点仅为个人分析与猜想，如有谬误，还请张老师谅解！
评论0