去除模糊

我有以下野牛语法（如更复杂的语法的一部分）：去除模糊

classDeclaration : CLASS ID EXTENDS ID LBRACE variableDeclarationList methodDeclarationList RBRACE 
       ; 

variableDeclarationList : variableDeclarationList variableDeclaration 
         | /* empty */ 
         ; 

variableDeclaration : type ID SEMICOLON 
        ; 

type : NATTYPE | ID 
    ; 

methodDeclarationList : methodDeclarationList methodDeclaration 
         | /* empty */ 
         ; 

methodDeclaration : type ID LPAREN parameterDeclarationList RPAREN variableExpressionBlock 
      ;

这是为了描述的类声明，其看起来像这样：

class foo extends object 
{ 
    nat number; 

    nat divide(nat aNumber) 
    { 
     0; 
    } 
}

或这样的：

class foo extends object 
{ 
    nat divide(nat aNumber) 
    { 
     0; 
    } 
}

或本：

class foo extends object 
{ 
}

问题是，有歧义其中变量声明端和方法声明开始（2移/减少冲突）。例如，方法声明看起来像一个变量声明，直到它看到括号。

我怎么可以重写此语法来消除这种不确定性？

澄清：类体可以是空的，唯一的限制是，如果有任何变量声明之前方法声明来临。

来源

2011-10-22 ladookie

另一种方法是甚至不使用空规则，而是使用多个选项，一个使用非终结符和一个没有。

classDeclaration : CLASS ID EXTENDS ID LBRACE RBRACE 
       | CLASS ID EXTENDS ID LBRACE methodDeclarationList RBRACE 
       | CLASS ID EXTENDS ID LBRACE variableDeclarationList RBRACE 
       | CLASS ID EXTENDS ID LBRACE variableDeclarationList methodDeclarationList RBRACE   
       ; 

variableDeclarationList : variableDeclaration 
         | variableDeclarationList variableDeclaration 
         ; 

variableDeclaration : type ID SEMICOLON 
        ; 

type : NATTYPE 
    | ID 
    ; 

methodDeclarationList : methodDeclaration 
         | methodDeclarationList methodDeclaration 
         ; 

methodDeclaration : type ID LPAREN RPAREN variableExpressionBlock 
        | type ID LPAREN parameterList RPAREN variableExpressionBlock 
        ;

来源

2011-10-28 16:43:58 ladookie

我不熟悉的野牛，但你有没有试图使一个规则的规则都在共同的前缀？ “类型ID”以变量和方法模式存在。

所以，如果你有说：

typedId : type ID 
     ;

然后

variableDeclaration : typedId SEMICOLON 
        ; 

methodDeclaration : typedId LPAREN parameterDeclarationList RPAREN variableExpressionBlock 
        ;

这样的变化规律和方法规则不会在直到被看作共同的前缀已经推，而下代币应该是明确的。

我已经很多年没有与这样的事情打我希望这有助于。

来源

2011-10-22 20:09:31 Rob

有趣的理论。尽管如此，野牛仍然有麻烦，仍然有2个转变/减少冲突。 – ladookie

通常，这种左分解仅对基于LL的解析器生成器有用。基于LR的发电机（比如野牛）会自动为你做这件事。 –

此略作修改语法的工作原理：

%token CLASS EXTENDS ID LBRACE RBRACE SEMICOLON NATTYPE LPAREN RPAREN DIGIT COMMA 
%% 
classDeclaration : CLASS ID EXTENDS ID LBRACE declarationList RBRACE 
     ; 

declarationList : /* Empty */ 
     | declarationList declaration 
     ; 

declaration : variableDeclaration 
     |  methodDeclaration 
     ; 

variableDeclaration : parameterDeclaration SEMICOLON 
     ; 

type : NATTYPE | ID 
     ; 

methodDeclaration : parameterDeclaration LPAREN parameterDeclarationList RPAREN 
        variableExpressionBlock 
     ; 

variableExpressionBlock : LBRACE DIGIT RBRACE 
     ; 

parameterDeclarationList : /* empty */ 
     | parameterDeclarationList COMMA parameterDeclaration 
     ; 

parameterDeclaration : type ID 
     ;

你可能想在非终端“parameterDeclaration”重命名为类似“singleVariableDeclaration”，但通过避免连续有两个可能是空的规则（原'variableDeclarationList'和'methodDeclarationList'，你可以避免含糊不清

这确实允许在类的declarationList中与变量交错的方法，如果由于某种原因这是不可接受的，那么考虑做一个语义错误而不是一个语法错误，如果它必须是一个语法错误，那么有人将不得不做一些思考;我投票让你做这个想法。

如果你坚持至少一个方法声明，那么语法是明确的：

methodDeclarationList : methodDeclarationList methodDeclaration 
     | methodDeclaration /* empty */ 
     ;

如果你试图用变量声明列表相同，语法仍然有两个S/R冲突。

一个不被完全忽略的可能性是使用Bison功能%expect 2来指示预计会出现2次移位/减少冲突。

%expect 2 
%token CLASS EXTENDS ID LBRACE RBRACE SEMICOLON NATTYPE LPAREN RPAREN DIGIT COMMA 
%% 
classDeclaration : CLASS ID EXTENDS ID LBRACE variableDeclarationList methodDeclarationList RBRACE 
     ; 

variableDeclarationList : variableDeclarationList variableDeclaration 
     | /* empty */ 
     ; 

variableDeclaration : singleVariableDeclaration SEMICOLON 
     ; 

type : NATTYPE | ID 
     ; 

methodDeclarationList : methodDeclarationList methodDeclaration 
     | /* empty */ 
     ; 

methodDeclaration : singleVariableDeclaration LPAREN parameterDeclarationList RPAREN variableExpressionBlock 
     ; 

variableExpressionBlock : LBRACE DIGIT RBRACE 
     ; 

parameterDeclarationList : /* empty */ 
     | parameterDeclarationList COMMA parameterDeclaration 
     ; 

parameterDeclaration : singleVariableDeclaration 
     ; 

singleVariableDeclaration : type ID 
     ;

来源

2011-10-22 21:15:40

我想我将不得不做更多的思考。你认为我可以以此为出发点，还是必须走完全不同的方向？谢谢您的帮助。 – ladookie

我很欣赏乔纳森的努力。整个类的主体可以是空的，唯一的约束是变量声明在方法声明之前出现，如果有的话。 – ladookie

'％expect 2'是一个不错的选择，因为结果解析器将无法解析任何方法声明的输入... –

这不是模棱两可，其先行的问题。问题是你需要3个令牌的lookahead（直到下一个声明的SEMICOLON或LPAREN），以便解析器找出变量声明列表的结尾，因为它需要在开始解析更多的methodDeclarations之前减少一个空的methodDeclarationList 。

解决这个问题的方法是在方法声明列表的开始，不需要用一个空的减少：

methodDeclarationList : nonEmptyMethodDeclarationList | /*empty */ ; 

nonEmptyMethodDeclarationList : nonEmptyMethodDeclarationList methodDeclaration 
           | methodDeclaration 
           ;

这样，解析器不需要，除非有降低空methodDeclarationList没有任何方法 - 在这种情况下，只需要一个前瞻标记即可看到RBRACE

来源

2011-10-24 02:48:34

回答

相关问题