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

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（resp.Trailing）产生一组终端，这些终端可以（递归地）在该非终端的生产中的第一个（相应的最后一个）终端。

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

例如，标准表达式语法（这是一个运算符语法;没有生产有两个连续的非终端）：

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

从term开始，ID和(从一开始就可以看到，从最后可以看到ID和)。 expr从任何一方都看不到，因为它被终端隐藏，所以我们不需要考虑它。

从factor，+从两端可见，factor也继承了term的前导和尾随集，因为从两端可以看到term。 （factor本身也是可见的，但是不能在Trailing集中添加任何新内容。）

最后，从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之间没有联系。优先关系不是反对称的，不幸的是它们传统上拼写的符号看起来像数字比较。）

Answer 2

领先（A）= {a，b}因为：

1. A - > YaZ和'a'是第一个终端;
2. A - > B和B - > b，所以：i）b在前导（B）中（b是集合前导（B）的元素），和ii）前导（B）属于前导（A）（前导（B） ）是Leading（A）的子集。

也就是说，A => * YaZ且A => * b，因此{a，b} =前导（A）。