软件设计师 · 高频练习

预测分析表同一单元出现两条产生式说明什么?

中级 单选题 第 838 题 中等 软件设计师编译原理预测分析表LL(1)冲突语法分析
题目

为某文法构造预测分析表时,发现表格单元 M[A,a] 需要同时填入 A→α 和 A→β 两条不同产生式。由此可以直接判断()。

A 该文法不是 LL(1) 文法
B 终结符 a 必须从输入串中删除
C A 一定是开始符号
D 文法一定没有任何左递归
题目类型:原创高频练习题 用途:用于帮助理解软件设计师相关考点和答案解析,不等同于官方真题。
正确答案
A
答案解析

LL(1) 预测分析要求由“栈顶非终结符 A”和“当前输入符号 a”唯一确定一条产生式。M[A,a] 同时需要两条产生式,表示只看一个输入符号无法作出唯一选择,预测分析表存在多重定义,因此该文法不是 LL(1) 文法。

选项分析

A

正确。一个表格单元出现两条产生式,说明预测选择不唯一。

B

错误。a 是合法输入符号,问题来自文法候选式的选择集合冲突,不是删除输入。

C

错误。预测分析表会为所有需要展开的非终结符建立行,发生冲突与 A 是否为开始符号无关。

D

错误。表格冲突不能证明文法没有左递归;相反,左递归等问题往往会妨碍 LL(1) 分析。

本题为什么容易错

预测分析表中的空白、synch 和多重定义含义不同。空白通常表示错误入口,synch 可用于错误恢复,而同一单元多条产生式才是候选选择冲突。

先看结论

简短答案

预测分析表同一单元出现两条产生式说明什么,正确答案是 A(该文法不是 LL(1) 文法)。LL(1) 预测分析要求由“栈顶非终结符 A”和“当前输入符号 a”唯一确定一条产生式。M[A,a] 同时需要两条产生式,表示只看一个输入符号无法作出唯一选择,预测分析表存在多重定义,因此该文法不是 LL(1) 文法。

解析

易混淆概念对比表

概念本题判断区别要点记忆提示
该文法不是 LL(1) 文法 本题正确答案 正确。一个表格单元出现两条产生式,说明预测选择不唯一。 看到题干核心场景时优先联想到它
终结符 a 必须从输入串中删除 本题干扰项 错误。a 是合法输入符号,问题来自文法候选式的选择集合冲突,不是删除输入。 看到该词不要急着选,先判断是否真正解决题干问题
A 一定是开始符号 本题干扰项 错误。预测分析表会为所有需要展开的非终结符建立行,发生冲突与 A 是否为开始符号无关。 看到该词不要急着选,先判断是否真正解决题干问题
文法一定没有任何左递归 本题干扰项 错误。表格冲突不能证明文法没有左递归;相反,左递归等问题往往会妨碍 LL(1) 分析。 看到该词不要急着选,先判断是否真正解决题干问题
本题易混淆选项怎么区分
  • 终结符 a 必须从输入串中删除:错误。a 是合法输入符号,问题来自文法候选式的选择集合冲突,不是删除输入。
  • A 一定是开始符号:错误。预测分析表会为所有需要展开的非终结符建立行,发生冲突与 A 是否为开始符号无关。
  • 文法一定没有任何左递归:错误。表格冲突不能证明文法没有左递归;相反,左递归等问题往往会妨碍 LL(1) 分析。
复习

知识点详解

预测分析表 M 的行对应非终结符,列对应终结符或结束符。分析过程中,栈顶为 A、当前输入为 a 时,分析器查 M[A,a] 决定使用哪条产生式。LL(1) 的确定性要求每个单元至多包含一条产生式。多重定义是文法不满足 LL(1) 条件的结果,但不能单凭一个冲突断言唯一原因;可能是候选式 FIRST 集重叠,也可能是可空候选式与 FOLLOW 集冲突。

备考速记

一格一条规则才可预测;一格两条规则,只看一个字符就不够。

LL(1)冲突 在语法分析场景中的作用

LL(1)冲突在本题中的核心价值,是解决“为某文法构造预测分析表时,发现表格单元 M[A,a] 需要同时填入 A→α 和 A→β 两条不同产生式。由此可以直接判断()”这个场景问题。复习时不要只背选项名称,还要理解它为什么适用于该场景,以及它能解决哪类安全、流程或管理问题。

拓展

同类题怎么考

  • 给出部分预测分析表,判断是否存在 LL(1) 冲突。
  • 根据冲突单元反推哪些候选式的 FIRST/FOLLOW 集发生相交。
  • 选择提取左公因子、消除左递归等文法改写方法。
LL(1)冲突 在软件设计师软考中的考法

软考选择题通常不会只考概念定义,还会把LL(1)冲突放到语法分析场景中,要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时,先抓住题干中的业务场景,再看哪个选项最能解决该场景下的核心问题。

解题思路

这类题不必回头重算整套 FIRST、FOLLOW。表格已经把结论摆出来了:分析器遇到栈顶 A、输入 a 时,有两条规则都声称自己能用。只向前看一个字符当然无法决定,LL(1) 的“1”就在这里失效。

考点定位

预测分析表的每个有效单元最多只能有一条产生式;同一单元多填是 LL(1) 选择冲突的直接证据。

易错提醒

  • 把多重定义误认为分析器可以任选一条产生式。
  • 只检查文法是否左递归,认为没有左递归就一定是 LL(1)。
  • 混淆预测分析表中的错误单元和产生式冲突单元。

备考提示

  • 构表结束后逐格检查,任何单元出现两条产生式都应回查 FIRST/FOLLOW 冲突。
  • 修正文法时先判断冲突来源:公共左前缀、左递归、可空候选式或文法本身的歧义。

你可能还想了解

  • 预测分析表每一行和每一列分别表示什么?
  • 同一单元出现两条产生式为什么不是 LL(1)?
  • 预测分析表空白单元与冲突单元有什么区别?
  • 怎样根据冲突位置修改文法?

本文小结

M[A,a] 同时需要填入 A→α 和 A→β,说明栈顶 A、输入 a 不能唯一确定产生式。预测分析表发生多重定义,因此该文法不是 LL(1) 文法。