软件设计师 · 高频练习

LR 分析器的栈中为什么保存活前缀?

中级 单选题 第 846 题 中等 软件设计师编译原理LR分析活前缀分析栈
题目

关于 LR 分析器在正常分析过程中已经压入栈中的文法符号,下列说法正确的是()。

A 它们构成某个右句型的活前缀,不会越过该右句型句柄的右端
B 它们始终构成一个完整句子
C 它们必须全部是终结符
D 它们与尚未读取的输入无关,可以任意排列
题目类型:原创高频练习题 用途:用于帮助理解软件设计师相关考点和答案解析,不等同于官方真题。
正确答案
A
答案解析

活前缀是右句型的前缀,并且不超过该右句型句柄的右端。LR 分析栈中的文法符号正是已经识别的活前缀;状态栈则记录识别该活前缀后自动机所处的状态,据此决定下一步移进还是归约。

选项分析

A

正确。活前缀的定义正是右句型中不越过句柄右端的前缀。

B

错误。分析中间状态通常只识别了句子的一部分,不要求已经形成完整句子。

C

错误。归约后非终结符也会进入栈,栈中可以同时出现终结符和非终结符。

D

错误。栈内容按分析顺序形成,并与剩余输入共同决定动作,不能任意排列。

本题为什么容易错

“前缀”容易让人只想到输入串前缀。活前缀针对的是右句型,里面可以有非终结符;“活”表示它仍有机会成为某个正确分析过程的栈内容。

先看结论

简短答案

LR 分析器的栈中为什么保存活前缀,正确答案是 A(它们构成某个右句型的活前缀,不会越过该右句型句柄的右端)。活前缀是右句型的前缀,并且不超过该右句型句柄的右端。LR 分析栈中的文法符号正是已经识别的活前缀;状态栈则记录识别该活前缀后自动机所处的状态,据此决定下一步移进还是归约。

解析

易混淆概念对比表

概念本题判断区别要点记忆提示
它们构成某个右句型的活前缀,不会越过该右句型句柄的右端 本题正确答案 正确。活前缀的定义正是右句型中不越过句柄右端的前缀。 看到题干核心场景时优先联想到它
它们始终构成一个完整句子 本题干扰项 错误。分析中间状态通常只识别了句子的一部分,不要求已经形成完整句子。 看到该词不要急着选,先判断是否真正解决题干问题
它们必须全部是终结符 本题干扰项 错误。归约后非终结符也会进入栈,栈中可以同时出现终结符和非终结符。 看到该词不要急着选,先判断是否真正解决题干问题
它们与尚未读取的输入无关,可以任意排列 本题干扰项 错误。栈内容按分析顺序形成,并与剩余输入共同决定动作,不能任意排列。 看到该词不要急着选,先判断是否真正解决题干问题
本题易混淆选项怎么区分
  • 它们始终构成一个完整句子:错误。分析中间状态通常只识别了句子的一部分,不要求已经形成完整句子。
  • 它们必须全部是终结符:错误。归约后非终结符也会进入栈,栈中可以同时出现终结符和非终结符。
  • 它们与尚未读取的输入无关,可以任意排列:错误。栈内容按分析顺序形成,并与剩余输入共同决定动作,不能任意排列。
复习

知识点详解

LR 分析从左到右读取输入,并按最右推导的逆过程归约。分析栈中的符号序列必须是某个右句型的活前缀,否则说明当前移进归约历史已经不可能通向合法句子。LR 项目自动机识别所有活前缀,状态栈保存自动机沿这些符号转移后的状态,因此 ACTION 和 GOTO 表可以仅凭栈顶状态及当前输入符号决定动作。

备考速记

活前缀可以到句柄末端,但不能越过句柄。

LR分析 在分析栈场景中的作用

LR分析在本题中的核心价值,是解决“关于 LR 分析器在正常分析过程中已经压入栈中的文法符号,下列说法正确的是()”这个场景问题。复习时不要只背选项名称,还要理解它为什么适用于该场景,以及它能解决哪类安全、流程或管理问题。

拓展

同类题怎么考

  • 直接考查活前缀定义和 LR 分析栈的含义。
  • 给出 LR 项目集,判断某状态能够识别哪些活前缀。
  • 比较移进、归约动作对符号栈和状态栈的影响。
LR分析 在软件设计师软考中的考法

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

解题思路

可以把活前缀理解成“目前走到这里还没有走坏”。它既可能还没碰到句柄,也可能刚好走到句柄末端,但不能已经跨过去还假装没有归约。LR 状态把这段历史压缩起来,所以分析器不用每次重新检查整条栈。

考点定位

LR 分析器识别活前缀集合;栈内容表示当前已经识别、仍可能延伸为合法右句型的部分,不能包含句柄右端之后的符号。

易错提醒

  • 把活前缀等同于已经读取的纯终结符输入。
  • 忘记归约会把产生式左部非终结符压回栈中。
  • 认为任何右句型前缀都是活前缀,没有检查是否越过句柄右端。

备考提示

  • 画出右句型并标出句柄,句柄右端左侧的各级前缀才有资格成为活前缀。
  • 结合 LR 项目理解状态:圆点位置表示某条产生式右部已经识别到哪里。

你可能还想了解

  • 活前缀为什么可以包含非终结符?
  • 活前缀与输入前缀有什么区别?
  • LR 项目集怎样识别活前缀?
  • 状态栈和符号栈分别保存什么?

本文小结

LR 分析器栈中的文法符号构成右句型的活前缀:它是仍可能出现在正确分析过程中的前缀,最多到达句柄右端,不能越过句柄后继续不归约。