关于可行前缀的说明

Question

在Ullman的编译器书中,在shift reduce parsing中,给出了可行前缀的定义:

"可以出现在shift-reduce解析器堆栈上的右句子形式的前缀集称为可行前缀.可行前缀的等效定义是它是右句子形式的前缀,不会继续通过右边该句子的最右边句柄的末尾.通过这个定义,总是可以在可行前缀的末尾添加终端符号以获得正确的句子形式.因此,只要该部分可用,就显然没有错误.看到给定点的输入可以减少到可行的前缀."

我无法理解这个定义.有人可以通过一个例子解释可行前缀的含义吗？
特别是,请解释
"可行前缀的等效定义是,它是右句子形式的前缀,不会继续超过该句子最右边句柄的右端"

Answer 1

编辑(或实际重写):你要求澄清的句子是一个主要的毛球!我需要对语言和自动化进行一些复习,以便将毛球分开.我发现这些讲义在这方面非常有用.

它也不会使术语在自上而下的扩展方面更容易定义,而最右边的派生通常用于自下而上的解析!

我将使用以下表达式语法来说明:

    expr -> expr + term | term
    term -> term * factor | factor
    factor -> NUMBER | ( expr )

• 甲右句型是句型其可以通过最右推导,这是另一种方式来描述仅最右边非末端符号的反复膨胀继续进行自顶向下时能得出.这是最右边的推导,因此其中的所有形式都是右翼形式:

    expr -> expr + term
         -> expr + term * factor
         -> expr + term * NUMBER
         -> expr + factor * NUMBER
         -> expr + NUMBER * NUMBER
         -> expr + term + NUMBER * NUMBER
         -> expr + NUMBER + NUMBER * NUMBER
         -> term + NUMBER + NUMBER * NUMBER
         -> NUMBER + NUMBER + NUMBER * NUMBER

• 甲前缀一个句型(无论右或其他)的输入符号序列减少到该句型的零个或多个前导符号.空序列通常是每个句子形式的前缀,构成句子形式的完整符号序列也通常是它的前缀.

• 一个简单的短语是单个非终结符号的扩展,它以句子形式保存一个位置.例如,term * factor是一个简单的短语,因为它是一个扩展term,并且term本身发生在三个作品中.

• 句子形式的句柄是该形式中最左边的简单短语.(我承认,我发现"句柄"这个术语在这里有点令人困惑.)在最右边的派生中,句柄很容易识别 - 它是由最近扩展的非终结符号产生的符号序列.如果你按照shift-reduce解析器的方式自下而上工作,那么句柄就是下一个需要减少的简单短语.(从下往上阅读上面的派生表,看看减少了哪些符号,看看我的意思.)

• 一个可行的前缀右句型的是没有超出这种形式的句柄的前缀-换句话说,该前缀是有效的,不包含任何还原简单的短语,与手柄本身可能是个例外,如果说前缀延伸到恰好是手柄的末端.

从shift-reduce解析器的角度来看,只要你在堆栈上有一个可行的前缀,你还没有被迫将堆栈顶部的(可能不完整的)简单短语减少为新的非终结符或失败解析如果不能减少.如果移动下一个符号会产生除可行前缀之外的其他符号,那么您必须在此时减少或失败.

如果你正在解析一个无上下文的语言,那么有一个相当方便的属性可以帮助构建一个由表驱动的shift-reduce解析器:一个无上下文语言的所有可行前缀的集合本身就是一种常规语言! 因此,您可以构建一个有限自动机,该自动机识别可行前缀的常规语言,并使用它来确定何时移位以及何时缩小.堆栈和有限状态机的这种组合本质上是一个下推式自动机,它正是识别无上下文语言所需的自动机类.

Answer 2

考虑书中给出的语法(我在这里重述)

E -> E+T | T
T -> T*F | F 
F -> (E) | id

通过在其中添加E' - > E来增强

现在来看看这个推导,

E' -> E
   -> E+T
   -> E+T*F

索赔E + T*是可行的前缀

参数:这种推导是一种正确的句子形式,而E + T*是它的前缀.句柄当前是T*F(将T*F减少到T我们可以达到开始符号并因此成功解析)

因此,E + T*是一个可行的前缀,因为它是正确的句子形式的前缀,并且没有延伸到这个句子形式的最右边的句柄.:)

定义它的其他方法是:

The prefixes of right sentential forms that can appear on the stack of a shiftreduce
parser are called viable prefixes.