context-free-grammar - 计算上下文无关文法的前导集和尾随集

Question

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

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

假设我们有产品:

A -> YaZ | B

B -> b

然后，据说 Leading(A) = {a}，Leading(A) = Leading(B) 和 Leading(B)={b}。我对此有疑问:

1. 这是否意味着 Leading(A) = {a, b} ？ - 我假设在每一步中我们都不会替换因为“=”而生成的集合，而是对两个集合求和。
2. 这是否意味着 Leading(B) 是 {b} 或 {a, b}？ - 第三条规则是否意味着我们将 Leading(B) 添加到 Leading(A) 或 Leading(A) 和 Leading(B) 是等价的？

Answer 1

Leading和 Trailing是特定于生成运算符优先级解析器的函数，仅当您具有运算符优先级语法时才适用。运算符优先文法是运算 rune 法的特例，运算 rune 法具有重要的性质，即没有产生式有两个连续的非终结符。

(从广义上讲，运算符优先语法是一种可以用运算符优先解析器解析的运算符语法:-)。但现在这并不重要。)

给定一个运算符语法，函数Leading (resp. Trailing) 的非终结符产生一组终结符，这些终结符可以是(递归地)从该非终结符派生的某种句子形式的第一个(resp.last)终结符。

另一个可能更直观的定义是，如果终端从产生式开始就“可见”，则该终端位于非终端的前导集中。非终结符是“透明的”，因此可以通过前导非终结符查看或查看可见的非终结符来查看终结符。

例如，一个标准的表达式文法(这是一个运算 rune 法；没有产生式有两个连续的非终结符):

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

来自 term , ID和 (从一开始就可见，并且ID和 )从末端可见。 expr从两边都不可见，因为它被终端隐藏了，所以我们不需要考虑它。

来自 factor , +从两端可见，factor还继承了前导和尾随集 term因为term从两端可见。 (factor 从末尾本身也是可见的，但不能向尾随集添加任何新内容。)

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