时间戳

首页 > 解决方案 > 优先级声明是否可以消除替代词汇之间的歧义？

rascal - 优先级声明是否可以消除替代词汇之间的歧义？

问题描述

在我之前的问题中，示例中有一个优先级>声明。事实证明这并不重要，因为那里的解决方案实际上并没有调用优先级，而是通过使替代方案脱节来避免它。在这个问题中，我在问是否可以使用优先级来选择一个词汇产生而不是另一个词汇产生。在下面的示例中，产生式的语言WordInitialDigit故意是WordAny. 产生Word式看起来应该正确地消除两者之间的歧义，但是生成的解析树在顶部有一个歧义节点。优先声明是否能够在不同的词汇缩减之间做出决定，或者它是否需要有共同词汇元素的基础？或者是其他东西？

这个例子是人为的（语法中没有动作），但它产生的情况不是。例如，我想使用这样的东西来进行错误恢复，我可以识别语法单元的自然边界并为其编写产生式。这种通用生产将是优先链中的最后一个元素；如果它减少，则意味着没有有效的解析。更一般地说，我需要能够根据句法上下文选择词汇元素。我曾希望，因为 Rascal 没有扫描仪，所以这将是无缝的。也许是这样，虽然我现在看不到。

我在不稳定的分支上，版本 0.10.0.201807050853。

编辑：这个问题不是关于>定义表达式语法的。优先级声明的文档主要讨论表达式，但第一句话提供了一个看起来非常清晰的定义：

优先级声明定义了单个 non-terminal中的产品之间的部分排序。

所以这个例子有两个产生式，它们之间声明了一个排序，但是解析器仍然在明确存在消歧规则的情况下生成一个歧义节点。因此，为了更好地说明我的问题，看起来我不知道两种情况中的哪一种有关。（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 "";
}

标签： rascal

解决方案

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

所以它是为了解决以下歧义：

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 运算符优先表，您几乎可以从字面上复制它们。

请注意，这两个消歧特征并不完全相反。第一个歧义也可以通过将两个产生式放在左组中来解决，如下所示：

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

由于树的左侧受到青睐，您现在将得到一棵不同的树1 + (3 - 4)。所以它会有所不同，但这一切都取决于你想要什么。

更多细节可以在关于消歧的导师页面中找到

推荐阅读