计算上下文无关文法的前导集和尾随集
Computing leading and trailing sets for context-free grammar
我正在寻找一个详细的算法来描述如何在上下文无关语法中为非终端符号生成前导和尾随集。
我发现了这样的东西：
https://pl.scribd.com/doc/51358638/16/Operator-Precedence-Relations
但我不确定它是如何工作的。 （见第 20 页）
假设我们有作品：
A -> YaZ | B
B -> b
那么，据称Leading(A) = {a}，Leading(A) = Leading(B) and Leading(B)={b}。
我对此表示怀疑：
- 这是否意味着 Leading(A) = {a, b} ？ - 我假设在每一步中我们都不会替换因为“=”而生成的集合，而是对两个集合求和。
- 这是否意味着 Leading(B) 是 {b} 或 {a, b}？ - 第三条规则是否意味着我们将 Leading(B) 添加到 Leading(A) 或 Leading(A) 和 Leading(B) 是等价的？
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的Leading and Trailing sets，因为term可见从两端。 （factor 从尾部本身也可见，但不能向尾随集添加任何新内容。）
最后，从expr开始，*两端可见，expr继承自factor。
所以我们最终得到：
Non-terminal Leading Trailing
expr *, +, ID, ( *, +, ID, )
factor +, ID, ( +, ID, )
term ID, ( ID, )
据此，我们将构建优先关系。基本上，如果你找到
nonterminal TERMINAL
在任何产生式中，然后为 Trailing(nonterminal) 中的每个 TRAIL 添加优先关系 TRAIL ⋗ TERMINAL。同样，每次出现
TERMINAL nonterminal
为 Leading(nonterminal) 中的每个 LEAD 生成关系 TERMINAL ⋖ LEAD。最后，如果你发现
TERMINAL1 TERMINAL2
或
TERMINAL1 nonterminal TERMINAL2
然后生成关系 TERMINAL1 ·=· TERMINAL2。
生成所有优先关系后，您将查看每对终端T, U。如果至多有一个优先关系成立——即 T ⋖ U, T ⋗ U, T ·=· U 或不存在从 T 到 U 的关系——那么你就有一个运算符优先语法。 （T, U 和 U, T 之间没有联系。优先关系不是反对称的，不幸的是它们传统上用看起来像数字比较的符号拼写。）
前导 (A) = { a,b } 因为：
- A -> YaZ 并且'a'是第一个终端；
- A -> B 和 B -> b，所以：
i) b in Leading(B)（b 是集合 Leading(B) 的一个元素），以及
ii) Leading(B) 属于 Leading(A)（Leading(B) 是 Leading(A) 的子集）。
也就是说，A =>* YaZ 和 A =>* b，所以 { a,b } = Leading(A)。
我正在寻找一个详细的算法来描述如何在上下文无关语法中为非终端符号生成前导和尾随集。
我发现了这样的东西： https://pl.scribd.com/doc/51358638/16/Operator-Precedence-Relations 但我不确定它是如何工作的。 （见第 20 页）
假设我们有作品：
A -> YaZ | B
B -> b
那么，据称Leading(A) = {a}，Leading(A) = Leading(B) and Leading(B)={b}。 我对此表示怀疑：
- 这是否意味着 Leading(A) = {a, b} ？ - 我假设在每一步中我们都不会替换因为“=”而生成的集合，而是对两个集合求和。
- 这是否意味着 Leading(B) 是 {b} 或 {a, b}？ - 第三条规则是否意味着我们将 Leading(B) 添加到 Leading(A) 或 Leading(A) 和 Leading(B) 是等价的？
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的Leading and Trailing sets，因为term可见从两端。 （factor 从尾部本身也可见，但不能向尾随集添加任何新内容。）
最后，从expr开始，*两端可见，expr继承自factor。
所以我们最终得到：
Non-terminal Leading Trailing
expr *, +, ID, ( *, +, ID, )
factor +, ID, ( +, ID, )
term ID, ( ID, )
据此，我们将构建优先关系。基本上，如果你找到
nonterminal TERMINAL
在任何产生式中，然后为 Trailing(nonterminal) 中的每个 TRAIL 添加优先关系 TRAIL ⋗ TERMINAL。同样，每次出现
TERMINAL nonterminal
为 Leading(nonterminal) 中的每个 LEAD 生成关系 TERMINAL ⋖ LEAD。最后，如果你发现
TERMINAL1 TERMINAL2
或
TERMINAL1 nonterminal TERMINAL2
然后生成关系 TERMINAL1 ·=· TERMINAL2。
生成所有优先关系后，您将查看每对终端T, U。如果至多有一个优先关系成立——即 T ⋖ U, T ⋗ U, T ·=· U 或不存在从 T 到 U 的关系——那么你就有一个运算符优先语法。 （T, U 和 U, T 之间没有联系。优先关系不是反对称的，不幸的是它们传统上用看起来像数字比较的符号拼写。）
前导 (A) = { a,b } 因为：
- A -> YaZ 并且'a'是第一个终端；
- A -> B 和 B -> b，所以： i) b in Leading(B)（b 是集合 Leading(B) 的一个元素），以及 ii) Leading(B) 属于 Leading(A)（Leading(B) 是 Leading(A) 的子集）。
也就是说，A =>* YaZ 和 A =>* b，所以 { a,b } = Leading(A)。