计算无上下文语法的前导和尾随集

Question

我正在寻找一个详细的算法,描述如何在无上下文语法中为非终端符号生成前导和尾随集.

我发现了这样的东西:https: //pl.scribd.com/doc/51358638/16/Operator-Precedence-Relations 但我不确定它是如何工作的.(见第20页)

假设我们有制作:

A - > YaZ | 乙

B - > b

然后,据说,前导(A)= {a},前导(A)=前导(B)和前导(B)= {b}.我对此表示怀疑:

1. 这是否意味着,领导(A)= {a,b}？ - 我假设在每一步中我们都不会因为'='而替换已生成的集合,而是将两个集合之和.
2. 这是否意味着,领导(B)是{b}还是{a,b}？ - 第三条规则是否意味着我们将前导(B)添加到前导(A)或前导(A)和前导(B)是等效的？

Answer 1

Leading并且Trailing是特定于生成运算符优先级解析器的函数,仅当您具有运算符优先级语法时才适用.运算符优先级语法是运算符语法的特例,运算符语法具有重要的属性,即没有生成具有两个连续的非终端.

(松散地说,运算符优先语法是一个运算符语法,可以用运算符优先级解析器解析:-).但这对现在来说并不重要.)

给定运算符语法,非终端的函数Leading(分别Trailing)产生一组终端,这些终端可以(递归地)在该非终端的生产中的第一(相应的)终端.

另一种方法是,如果终端在生产开始时"可见",那么终端就位于非终端的前导集中.我们认为非终端是"透明的",因此可以通过非终端或通过查看可见的非终端来看到终端.

例如,标准表达式语法(这是一个运算符语法;没有生产有两个连续的非终端):

expr   -> factor '*' expr
expr   -> factor
factor -> term '+' factor
factor -> term
term   -> ID
term   -> '(' expr ')'

从term,ID并且(是从一开始就可见的,并且ID和)来自年底可见.expr从任何一方都看不到,因为它被终端隐藏,所以我们不需要考虑它.

From factor,+从两端可见,并且factor还继承了前导和尾随集,term因为term从两端可见.(factor从结尾本身也可以看到,但是不能向尾随集添加任何新内容.)

最后,from expr,*从两端可见,并expr继承自factor.

所以我们最终得到:

Non-terminal            Leading             Trailing
expr                    *, +, ID, (         *, +, ID, )
factor                  +, ID, (            +, ID, )
term                    ID, (               ID, )

由此,我们将构建优先关系.基本上,如果你找到了

nonterminal TERMINAL

在任何生产,那么你添加优先关系TRAIL ? TERMINAL每一个TRAIL中Trailing(nonterminal).同样,每次出现

TERMINAL nonterminal

生成的关系,TERMINAL ? LEAD为每一个LEAD在Leading(nonterminal).最后,如果你找到了

TERMINAL1 TERMINAL2

要么

TERMINAL1 nonterminal TERMINAL2

那么你就产生了这种关系TERMINAL1 ·=· TERMINAL2.

一旦生成了所有优先关系,就可以查看每对终端T, U.如果在最优先一个关系成立-即,T ? U, T ? U, T ·=· U或者没有从关系T到U-然后你有一个运算符优先级语法.(T, U和之间没有联系U, T.优先关系不是反对称的,不幸的是它们传统上拼写的符号看起来像数字比较.)