优先级声明是否消除了替代词汇之间的歧义？
Does a priority declaration disambiguate between alternative lexicals?
在我的中，示例中有一个优先级>声明。事实证明这无关紧要，因为那里的解决方案实际上并没有调用优先级，而是通过使备选方案不相交来避免它。在这个问题中，我问的是是否可以优先 select 一种词汇产生式优于另一种产生式。在下面的示例中，产生式 WordInitialDigit 的语言有意是 WordAny 语言的子集。产生式 Word 看起来应该正确地消除两者之间的歧义，但生成的解析树在顶部有一个歧义节点。优先权声明是否能够在不同的词汇缩减之间做出决定，或者它是否需要有共同词汇元素的基础？或者别的什么？
这个例子是人为的（语法中没有动作），但它所产生的情况却不是。例如，我想使用类似这样的东西来进行错误恢复，我可以在其中识别语法单元的自然边界并为其编写产生式。这种通用产品将是优先链中的最后一个元素；如果它减少，则意味着没有有效的解析。更一般地说，我需要能够 select 基于句法上下文的词汇元素。我曾希望，因为 Rascal 是无扫描仪的，所以这将是无缝的。也许是，虽然我现在没有看到它。
我在不稳定的分支上，版本 0.10.0.201807050853。
编辑：这个问题不是关于 > 定义表达式语法。 documentation for priority declarations 主要讨论表达式，但第一句话提供了一个看起来非常清晰的定义：
Priority declarations define a partial ordering between the productions within a single non-terminal.
所以这个例子有两个产生式，它们之间声明了一个顺序，但是解析器仍然在明确存在消歧规则的情况下生成一个歧义节点。因此，为了更好地说明我的问题，我似乎不知道两种情况属于哪种情况。要么 (1) 如果这不应该起作用，那么在记录的语言定义中存在缺陷，编译器的错误报告中存在缺陷，以及介于反直觉和用户敌对之间的语言设计决策。或者 (2) 如果这应该有效，则编译器 and/or 解析器存在缺陷（可能是因为焦点最初在表达式上）并且在某些时候该示例将通过其测试。
module ssce
import analysis::grammars::Ambiguity;
import ParseTree;
import IO;
import String;
lexical WordChar = [0-9A-Za-z] ;
lexical Digit = [0-9] ;
lexical WordInitialDigit = Digit WordChar* !>> WordChar;
lexical WordAny = WordChar+ !>> WordChar;
syntax Word =
WordInitialDigit
> WordAny
;
test bool WordInitialDigit_0() = parseAccept( #Word, "4foo" );
test bool WordInitialDigit_1() = parseAccept( #WordInitialDigit, "4foo" );
test bool WordInitialDigit_2() = parseAccept( #WordAny, "4foo" );
bool verbose = false;
bool parseAccept( type[&T<:Tree] begin, str input )
{
try
{
parse(begin, input, allowAmbiguity=false);
}
catch ParseError(loc _):
{
return false;
}
catch Ambiguity(loc l, str a, str b):
{
if (verbose)
{
println("[Ambiguity] #<a>, \"<b>\"");
Tree tt = parse(begin, input, allowAmbiguity=true) ;
iprintln(tt);
list[Message] m = diagnose(tt) ;
println( ToString(m) );
}
fail;
}
return true;
}
bool parseReject( type[&T<:Tree] begin, str input )
{
try
{
parse(begin, input, allowAmbiguity=false);
}
catch ParseError(loc _):
{
return true;
}
return false;
}
str ToString( list[Message] msgs ) =
( ToString( msgs[0] ) | it + "\n" + ToString(m) | m <- msgs[1..] );
str ToString( Message msg)
{
switch(msg)
{
case error(str s, loc _): return "error: " + s;
case warning(str s, loc _): return "warning: " + s;
case info(str s, loc _): return "info: " + s;
}
return "";
}
>消歧机制用于递归定义，例如表达式语法。
所以就是为了解决下面的歧义：
syntax E
= [0-9]+
| E "+" E
| E "-" E
;
字符串1 + 3 - 4无法解析为1 + (3 - 4)或(1 + 3) - 4。
> 给出了这个语法的顺序，哪个产生式应该在树的顶部。
layout L = " "*;
syntax E
= [0-9]+
| E "+" E
> E "-" E
;
这现在只允许 (1 + 3) - 4 树。
要完成这个故事，1 + 1 + 1怎么样？那可能是 1 + (1 + 1) 或 (1 + 1) + 1.
这就是我们 left、right 和 non-assoc 的目的。它们定义了应该如何处理同一产生式中的递归。
syntax E
= [0-9]+
| left E "+" E
> left E "-" E
;
现在将执行：1 + (1 + 1).
当您采用运算符优先级 table 时，例如这个 c operator precedance table 您几乎可以从字面上复制它们。
请注意，这两个消歧特征并不完全相反。第一个歧义也可以通过将两个产生式放在左组中来解决，如下所示：
syntax E
= [0-9]+
| left (
E "+" E
| E "-" E
)
;
由于树的左侧更受欢迎，您现在将得到一棵不同的树 1 + (3 - 4)。所以它有所不同，但这完全取决于你想要什么。
中找到更多详细信息
很好的问题。
长话短说：
- 规则优先级机制无法对非终端的备选方案进行算法排序。尽管优先级声明生成的附加语法约束中涉及某种偏序，但不存在 "trying" 一条规则先于另一条规则。所以它根本不能那样做。好消息是，优先级机制具有独立于任何解析算法的形式语义，它只是根据上下文无关文法规则和归约踪迹定义的。
- 使用不明确的错误恢复规则或 "robust parsing" 是个好主意。但是，如果此类规则太多，解析器最终将开始显示二次甚至三次行为，解析后的树构建甚至可能具有更高的多项式。我相信生成的解析器 algorithm 应该有一个（参数化的）错误恢复模式，而不是在语法级别表达它。
- 在解析时接受歧义，filtering/choosing 解析后的树是推荐的方法。
- 文档中所有关于 "ordering" 的说法都是误导性的。消除歧义是混淆术语的雷区。现在，我推荐这篇 SLE 论文，它有一些定义：https://homepages.cwi.nl/~jurgenv/papers/SLE2013-1.pdf
详情
无法在备选方案中进行选择的优先机制
使用>运算符和left，right生成相互递归规则之间的偏序，例如在表达式语言中找到，并限制在特定项目位置每个规则：即重叠的最左和最右递归位置。层次结构中较低的规则不允许在语法上扩展为层次结构较高的规则的 "children"。所以在 E "*" E 中，如果 E "*" E > E "+" E，则 E 都不能扩展为 E "+" E。
附加约束不会为任何 E 选择首先尝试的备选方案。不，他们只是不允许某些扩展，假设 other 扩展仍然有效，因此歧义得到解决。
限制特定位置的原因是，对于这些位置，解析器生成器可以"prove"它们会产生歧义，因此通过不允许某些嵌套来过滤两个备选方案之一不会导致额外的解析错误。 （考虑数组索引的规则：E "[" E "]" 不应该对第二个 E 有额外的约束。这就是所谓的 "syntax-safe" 消歧机制。
总而言之，它在算法上是一个非常弱的机制，并且专门为相互递归 combinator/expression-like 语言量身定制。该机制的最终目标是确保我们在整个表达式语言中只使用 1 个非终结符，并且解析树在形状上与抽象语法树非常相似。顺便说一句，Rascal 通过 SDF2 从 SDF 继承了所有这些考虑因素。
当前的实现实际上 "factor" 语法或解析 table 以某种方式无形地获得相同的效果，就好像有人会完全分解语法一样；然而，这些引擎盖下的实现是非常特定于所讨论的解析算法的。 GLR 版本与 GLL 版本完全不同，后者又与 DataDependent 版本完全不同。
Post-解析过滤
当然，任何树，包括解析器生成的模糊解析森林，都可以由 Rascal 程序使用模式匹配、访问等操作。您可以编写任何算法来删除您想要的树。但是，这需要先构建整个森林。这是可能的，而且通常足够快，但还有更快的选择。
由于树是在解析后从解析图中以自下而上的方式构建的，因此我们也可以在树的构建过程中应用"rewrite rules"，并删除某些替代项。
例如：
Tree amb({Tree a, *Tree others}) = amb(others) when weDoNotWant(a);
Tree amb({Tree a}) = a;
第一个规则将匹配所有树的歧义集群，并删除所有 weDoNotWant 的备选方案。如果只剩下一个替代方案，第二条规则将删除集群，让我们最后一棵树 "win".
如果您想在备选方案中进行选择：
Tree amb({Tree a, Tree b, *Tree others}) = amb({a, others} when weFindPeferable(a, b);
如果您不想使用 Tree 但更具体的非终端，如 Statement 也应该可以。
此示例模块在语法定义中使用 @prefer 标记到 "prefer" 规则，这些规则已标记在其他规则之上，如 post-解析重写规则：
使用额外的词法约束进行修改
除了优先级消歧和post-解析重写，我们在工具包中还有词汇级消歧机制：
- `NT\Keywords" - 拒绝来自非终端的有限（关键字）语言
CC << NT, NT >> CC, CC !<< NT, NT !>> CC follow and preceede 限制（其中CC代表character-class，NT代表非终结符)
解决除运算符优先级之外的其他类型的歧义可以用这些来尝试，特别是如果不同子句的长度在不同的选择之间是 shorter/longer，!>> 可以做到"maximal munch" 或 "longest match" 的东西。所以我在大声思考：
lexical C = A? B?;
其中 A 是一个词汇选择，而 B 是另一个。通过对 A 的适当 !>> 限制和对 B 的 !<< 限制，语法可能会被欺骗，总是希望将所有字符放在 A 中，除非它们不适合A 作为一种语言，在这种情况下，它们将默认为 B。
obvious/annoying建议
更加努力地思考明确且更简单的语法。
有时这意味着在语法中抽象并允许更多的句子，避免使用 "type checking" 树的语法。通常最好过度近似语言的语法，然后使用（静态）语义分析（通过更简单的树）来获得你想要的东西，而不是盯着一个复杂的模棱两可的语法。
一个典型的例子：只在开头声明的 C 块比在任何地方都允许声明的 C 块更难明确定义。对于 C90 模式，您所要做的就是不在块开头的标志声明。
这个特殊的例子
lexical WordChar = [0-9A-Za-z] ;
lexical Digit = [0-9] ;
lexical WordInitialDigit = Digit WordChar* !>> WordChar;
lexical WordAny = WordChar+ !>> WordChar;
syntax Word =
WordInitialDigit
| [0-9] !<< WordAny // this would help!
;
总结
问得好，感谢您的耐心等待。希望这对您有所帮助！
在我的>声明。事实证明这无关紧要，因为那里的解决方案实际上并没有调用优先级，而是通过使备选方案不相交来避免它。在这个问题中，我问的是是否可以优先 select 一种词汇产生式优于另一种产生式。在下面的示例中，产生式 WordInitialDigit 的语言有意是 WordAny 语言的子集。产生式 Word 看起来应该正确地消除两者之间的歧义，但生成的解析树在顶部有一个歧义节点。优先权声明是否能够在不同的词汇缩减之间做出决定，或者它是否需要有共同词汇元素的基础？或者别的什么？
这个例子是人为的（语法中没有动作），但它所产生的情况却不是。例如，我想使用类似这样的东西来进行错误恢复，我可以在其中识别语法单元的自然边界并为其编写产生式。这种通用产品将是优先链中的最后一个元素；如果它减少，则意味着没有有效的解析。更一般地说，我需要能够 select 基于句法上下文的词汇元素。我曾希望，因为 Rascal 是无扫描仪的，所以这将是无缝的。也许是，虽然我现在没有看到它。
我在不稳定的分支上，版本 0.10.0.201807050853。
编辑：这个问题不是关于 > 定义表达式语法。 documentation for priority declarations 主要讨论表达式，但第一句话提供了一个看起来非常清晰的定义：
Priority declarations define a partial ordering between the productions within a single non-terminal.
所以这个例子有两个产生式，它们之间声明了一个顺序，但是解析器仍然在明确存在消歧规则的情况下生成一个歧义节点。因此，为了更好地说明我的问题，我似乎不知道两种情况属于哪种情况。要么 (1) 如果这不应该起作用，那么在记录的语言定义中存在缺陷，编译器的错误报告中存在缺陷，以及介于反直觉和用户敌对之间的语言设计决策。或者 (2) 如果这应该有效，则编译器 and/or 解析器存在缺陷（可能是因为焦点最初在表达式上）并且在某些时候该示例将通过其测试。
module ssce
import analysis::grammars::Ambiguity;
import ParseTree;
import IO;
import String;
lexical WordChar = [0-9A-Za-z] ;
lexical Digit = [0-9] ;
lexical WordInitialDigit = Digit WordChar* !>> WordChar;
lexical WordAny = WordChar+ !>> WordChar;
syntax Word =
WordInitialDigit
> WordAny
;
test bool WordInitialDigit_0() = parseAccept( #Word, "4foo" );
test bool WordInitialDigit_1() = parseAccept( #WordInitialDigit, "4foo" );
test bool WordInitialDigit_2() = parseAccept( #WordAny, "4foo" );
bool verbose = false;
bool parseAccept( type[&T<:Tree] begin, str input )
{
try
{
parse(begin, input, allowAmbiguity=false);
}
catch ParseError(loc _):
{
return false;
}
catch Ambiguity(loc l, str a, str b):
{
if (verbose)
{
println("[Ambiguity] #<a>, \"<b>\"");
Tree tt = parse(begin, input, allowAmbiguity=true) ;
iprintln(tt);
list[Message] m = diagnose(tt) ;
println( ToString(m) );
}
fail;
}
return true;
}
bool parseReject( type[&T<:Tree] begin, str input )
{
try
{
parse(begin, input, allowAmbiguity=false);
}
catch ParseError(loc _):
{
return true;
}
return false;
}
str ToString( list[Message] msgs ) =
( ToString( msgs[0] ) | it + "\n" + ToString(m) | m <- msgs[1..] );
str ToString( Message msg)
{
switch(msg)
{
case error(str s, loc _): return "error: " + s;
case warning(str s, loc _): return "warning: " + s;
case info(str s, loc _): return "info: " + s;
}
return "";
}
>消歧机制用于递归定义，例如表达式语法。
所以就是为了解决下面的歧义：
syntax E
= [0-9]+
| E "+" E
| E "-" E
;
字符串1 + 3 - 4无法解析为1 + (3 - 4)或(1 + 3) - 4。
> 给出了这个语法的顺序，哪个产生式应该在树的顶部。
layout L = " "*;
syntax E
= [0-9]+
| E "+" E
> E "-" E
;
这现在只允许 (1 + 3) - 4 树。
要完成这个故事，1 + 1 + 1怎么样？那可能是 1 + (1 + 1) 或 (1 + 1) + 1.
这就是我们 left、right 和 non-assoc 的目的。它们定义了应该如何处理同一产生式中的递归。
syntax E
= [0-9]+
| left E "+" E
> left E "-" E
;
现在将执行：1 + (1 + 1).
当您采用运算符优先级 table 时，例如这个 c operator precedance table 您几乎可以从字面上复制它们。
请注意，这两个消歧特征并不完全相反。第一个歧义也可以通过将两个产生式放在左组中来解决，如下所示：
syntax E
= [0-9]+
| left (
E "+" E
| E "-" E
)
;
由于树的左侧更受欢迎，您现在将得到一棵不同的树 1 + (3 - 4)。所以它有所不同，但这完全取决于你想要什么。
很好的问题。
长话短说：
- 规则优先级机制无法对非终端的备选方案进行算法排序。尽管优先级声明生成的附加语法约束中涉及某种偏序，但不存在 "trying" 一条规则先于另一条规则。所以它根本不能那样做。好消息是，优先级机制具有独立于任何解析算法的形式语义，它只是根据上下文无关文法规则和归约踪迹定义的。
- 使用不明确的错误恢复规则或 "robust parsing" 是个好主意。但是，如果此类规则太多，解析器最终将开始显示二次甚至三次行为，解析后的树构建甚至可能具有更高的多项式。我相信生成的解析器 algorithm 应该有一个（参数化的）错误恢复模式，而不是在语法级别表达它。
- 在解析时接受歧义，filtering/choosing 解析后的树是推荐的方法。
- 文档中所有关于 "ordering" 的说法都是误导性的。消除歧义是混淆术语的雷区。现在，我推荐这篇 SLE 论文，它有一些定义：https://homepages.cwi.nl/~jurgenv/papers/SLE2013-1.pdf
详情
无法在备选方案中进行选择的优先机制
使用>运算符和left，right生成相互递归规则之间的偏序，例如在表达式语言中找到，并限制在特定项目位置每个规则：即重叠的最左和最右递归位置。层次结构中较低的规则不允许在语法上扩展为层次结构较高的规则的 "children"。所以在 E "*" E 中，如果 E "*" E > E "+" E，则 E 都不能扩展为 E "+" E。
附加约束不会为任何 E 选择首先尝试的备选方案。不，他们只是不允许某些扩展，假设 other 扩展仍然有效，因此歧义得到解决。
限制特定位置的原因是，对于这些位置，解析器生成器可以"prove"它们会产生歧义，因此通过不允许某些嵌套来过滤两个备选方案之一不会导致额外的解析错误。 （考虑数组索引的规则：E "[" E "]" 不应该对第二个 E 有额外的约束。这就是所谓的 "syntax-safe" 消歧机制。
总而言之，它在算法上是一个非常弱的机制，并且专门为相互递归 combinator/expression-like 语言量身定制。该机制的最终目标是确保我们在整个表达式语言中只使用 1 个非终结符，并且解析树在形状上与抽象语法树非常相似。顺便说一句，Rascal 通过 SDF2 从 SDF 继承了所有这些考虑因素。
当前的实现实际上 "factor" 语法或解析 table 以某种方式无形地获得相同的效果，就好像有人会完全分解语法一样；然而，这些引擎盖下的实现是非常特定于所讨论的解析算法的。 GLR 版本与 GLL 版本完全不同，后者又与 DataDependent 版本完全不同。
Post-解析过滤
当然，任何树，包括解析器生成的模糊解析森林，都可以由 Rascal 程序使用模式匹配、访问等操作。您可以编写任何算法来删除您想要的树。但是，这需要先构建整个森林。这是可能的，而且通常足够快，但还有更快的选择。
由于树是在解析后从解析图中以自下而上的方式构建的，因此我们也可以在树的构建过程中应用"rewrite rules"，并删除某些替代项。
例如：
Tree amb({Tree a, *Tree others}) = amb(others) when weDoNotWant(a);
Tree amb({Tree a}) = a;
第一个规则将匹配所有树的歧义集群，并删除所有 weDoNotWant 的备选方案。如果只剩下一个替代方案，第二条规则将删除集群，让我们最后一棵树 "win".
如果您想在备选方案中进行选择：
Tree amb({Tree a, Tree b, *Tree others}) = amb({a, others} when weFindPeferable(a, b);
如果您不想使用 Tree 但更具体的非终端，如 Statement 也应该可以。
此示例模块在语法定义中使用 @prefer 标记到 "prefer" 规则，这些规则已标记在其他规则之上，如 post-解析重写规则：
使用额外的词法约束进行修改
除了优先级消歧和post-解析重写，我们在工具包中还有词汇级消歧机制：
- `NT\Keywords" - 拒绝来自非终端的有限（关键字）语言
CC << NT,NT >> CC,CC !<< NT,NT !>> CCfollow and preceede 限制（其中CC代表character-class，NT代表非终结符)
解决除运算符优先级之外的其他类型的歧义可以用这些来尝试，特别是如果不同子句的长度在不同的选择之间是 shorter/longer，!>> 可以做到"maximal munch" 或 "longest match" 的东西。所以我在大声思考：
lexical C = A? B?;
其中 A 是一个词汇选择，而 B 是另一个。通过对 A 的适当 !>> 限制和对 B 的 !<< 限制，语法可能会被欺骗，总是希望将所有字符放在 A 中，除非它们不适合A 作为一种语言，在这种情况下，它们将默认为 B。
obvious/annoying建议
更加努力地思考明确且更简单的语法。
有时这意味着在语法中抽象并允许更多的句子，避免使用 "type checking" 树的语法。通常最好过度近似语言的语法，然后使用（静态）语义分析（通过更简单的树）来获得你想要的东西，而不是盯着一个复杂的模棱两可的语法。
一个典型的例子：只在开头声明的 C 块比在任何地方都允许声明的 C 块更难明确定义。对于 C90 模式，您所要做的就是不在块开头的标志声明。
这个特殊的例子
lexical WordChar = [0-9A-Za-z] ;
lexical Digit = [0-9] ;
lexical WordInitialDigit = Digit WordChar* !>> WordChar;
lexical WordAny = WordChar+ !>> WordChar;
syntax Word =
WordInitialDigit
| [0-9] !<< WordAny // this would help!
;
总结
问得好，感谢您的耐心等待。希望这对您有所帮助！