代码之家 › 专栏 › 技术社区 › eh9

优先级声明是否在可选词汇之间消除歧义?

rascal

1

eh9 · 技术社区 · 6 年前

在我的 previous question ,有优先权 > 示例中的声明。结果证明这无关紧要,因为那里的解决方案实际上并没有调用优先级,而是通过使备选方案不相交来避免优先级。在这个问题中,我问的是优先级是否可以用来选择一种词汇产生而不是另一种。在下面的示例中,生产的语言 WordInitialDigit 有意成为 WordAny . 生产 Word 看起来应该正确地消除这两者之间的歧义,但是结果分析树的顶部有一个歧义节点。优先级声明是否能够在不同的词汇缩减之间作出决定,或者是否需要有共同词汇元素的基础?或者别的什么?

这个例子是人为的(语法中没有动作),但它产生的情况却不是。例如,我想使用类似这样的方法进行错误恢复,在这里我可以识别一个语法单元的自然边界,并为其编写产品。这个通用产品将是优先级链中的最后一个元素;如果它减少,则意味着没有有效的解析。一般来说,我需要能够根据句法上下文选择词汇元素。我本来希望,因为流氓是无扫描的,这将是无缝的。也许是,尽管我现在看不到。

我在不稳定分支,版本0.10.0.201807050853。

编辑:这个问题不是关于 > 用于定义表达式语法。这个 documentation for priority declarations 主要讨论表达,但第一句话提供了一个非常清晰的定义:

优先级声明定义了生产之间的部分排序 在单个非终端内 .

所以这个例子有两个结果,一个是在它们之间声明的顺序,但是解析器仍然在明确存在消歧规则的情况下生成一个歧义节点。所以,为了更准确地回答我的问题,我似乎不知道这两种情况中哪一种适用。或者(1)如果不应该这样做,那么文档中的语言定义就有缺陷,编译器的错误报告也有缺陷,语言设计决策介于反直觉和用户敌意之间。或者(2)如果这是可行的,那么编译器和/或解析器中有一个缺陷(可能是因为最初关注的焦点是表达式),并且在某个时刻示例将通过测试。

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 "";
}

2 回复 | 直到 6 年前

1

Jurgen Vinju 6 年前

好问题。

DR:

规则优先级机制不能对非终端的备选方案进行算法排序。虽然在优先级声明生成的附加语法约束中涉及到某种部分顺序,但没有先“尝试”一个规则,再“尝试”另一个规则。所以它根本做不到。好消息是,优先级机制有一个独立于任何解析算法的形式语义,它只是根据上下文无关的语法规则和简化痕迹定义的。
使用不明确的错误恢复规则或“健壮的解析”是一个好主意。但是,如果这样的规则太多,解析器最终将开始显示二次甚至三次的行为,并且解析后的树构建可能具有更高的多项式。我相信生成的解析器算法应该有一个(参数化的)错误恢复模式,而不是在语法级别表达它。
建议在解析时接受歧义,并在解析后筛选/选择树。
文档中所有关于“排序”的讨论都是误导性的。消除歧义是混淆术语的雷区。目前,我推荐这篇SLE论文,它有一些定义: https://homepages.cwi.nl/~jurgenv/papers/SLE2013-1.pdf

细节

优先机制不能在备选方案中进行选择

使用 > 操作员和 left , right 在相互递归的规则(如表达式语言中的规则)之间生成部分顺序,并限制在每个规则中的特定项位置:即重叠的最左边和最右边的递归位置。层次结构中级别较低的规则不允许以语法方式扩展为层次结构中级别较高的规则的“子级”。所以在 E "*" E ,两者都不是 E 可以解释为 E "+" E 如果 E "*" E > E "+" E .

附加约束不选择任何 e 先试试哪个。不,他们只是不允许某些扩展,假设其他扩展仍然有效,从而解决了模糊性。

在特定位置限制的原因是,对于这些位置,解析器生成器可以“证明”它们将产生歧义,因此通过不允许某些嵌套来过滤两个备选方案中的一个不会导致额外的解析错误。(考虑数组索引规则: E "[" E "]" 对于第二个不应该有额外的限制 e . 这是一种所谓的“语法安全”消歧机制。

从算法上讲,它是一个非常弱的机制,专门为相互递归的组合/表达式类语言定制。该机制的最终目标是确保我们使用的整个表达式语言只能使用1个非终端,并且解析树的形状与抽象语法树非常相似。顺便说一下,Rascal通过sdf2从sdf继承了所有这些考虑。

当前的实现实际上以某种方式无形地“分解”语法或解析表,以获得相同的效果,就好像有人会完全分解语法一样;然而,这些在后台的实现非常特定于所讨论的解析算法。GLR版本与GLL版本有很大的不同,而GLL版本又与数据相关版本有很大的不同。

后分析筛选

当然,任何树,包括解析器生成的不明确的解析林,都可以通过使用模式匹配、访问等的流氓程序来操作。您可以编写任何算法来删除所需的树。然而,这需要首先建造整个森林。这是可能的,而且往往足够快,但有一个更快的选择。

由于树是在解析后从解析图自下而上构建的,因此我们也可以在树的构造过程中应用“重写规则”,并删除某些替代项。

例如:

Tree amb({Tree a, *Tree others}) = amb(others) when weDoNotWant(a);
Tree amb({Tree a}) = a;

第一条规则将匹配所有树的模糊性集群,并删除 weDoNotWant . 如果只剩下一个选项,则第二个规则将删除集群,并让最后一棵树“获胜”。

如果您想在备选方案中进行选择:

Tree amb({Tree a, Tree b, *Tree others}) = amb({a, others} when weFindPeferable(a, b);

如果您不想使用树,而是更具体的非终端类 Statement 这也应该有效。

此示例模块使用 @prefer 语法定义中的标记以“首选”已标记的规则,而不是其他规则,如后解析重写规则:

https://github.com/usethesource/rascal/blob/master/src/org/rascalmpl/library/lang/sdf2/filters/PreferAvoid.rsc

使用其他词汇约束进行黑客攻击

除了优先级消歧和后解析重写之外,我们还有工具箱中的词汇级消歧机制:

` nt\keywords“—拒绝非终端的有限(keyword)语言
CC << NT , NT >> CC , CC !<< NT , NT !>> CC 遵循并处理限制(CC代表字符类,NT代表非终端)

除运算符优先级外,还可以尝试使用这些方法来解决其他类型的歧义,特别是如果不同的可选方案之间的不同子句的长度较短/较长, !>> 可以做“最大咀嚼”或“最长匹配”的事情。所以我大声想:

lexical C = A? B?;

在哪里? A 是一种词汇选择 B 是另一个。用适当的 !>> 限制 一 和 !<< 限制 乙 语法可能被欺骗为总是想把所有字符都放在一个中,除非它们不适合 一 作为一种语言,在这种情况下,它们将默认为 乙 .

明显的/恼人的建议

更仔细地考虑一个明确而简单的语法。

有时这意味着在语法中抽象和允许更多的句子,避免使用语法来“类型检查”树。通常最好是过度近似语言的语法,然后使用(静态)语义分析(在更简单的树上)来获得所需的内容,而不是盯着复杂的、模棱两可的语法。

一个典型的例子:只在开始处有声明的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!
    ;

总结

好问题,谢谢你的耐心。希望这有帮助!

2

1

Davy Landman 6 年前

这个 > 消歧机制用于递归定义,例如表达式语法。

所以要解决以下歧义:

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) .

当你拿一个操作符进位表时,比如这个 c operator precedance table 你几乎可以直接复制它们。

注意这两个消歧功能并不完全相反。 第一个模棱两可的问题也可以通过将两个作品放在这样一个左组中来解决:

syntax E 
   = [0-9]+
   | left ( 
         E "+" E
        | E "-" E
     )
   ;

因为左边的树是受欢迎的,你现在会得到一棵不同的树 1+(3-4) . 所以这是有区别的,但这完全取决于你想要什么。

有关更多详细信息,请参见 tutor pages on disambiguation