去除模糊

我有以下野牛語法（如更復雜的語法的一部分）：去除模糊

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

回答

相關問題