устранение двусмысленности

Question

У меня есть следующая грамматика бизонов (как часть более сложной грамматики):

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

илиthis:

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

или this:

class foo extends object
{
}

Проблема состоит в том, что существует неоднозначность, в которой объявления переменных заканчиваются, и объявления методов начинаются (2 конфликта сдвига / уменьшения).Например, объявление метода выглядит как объявление переменной, пока не увидит круглые скобки.

Как я могу переписать эту грамматику, чтобы устранить эту неоднозначность?

Чтобы уточнить: тело класса может быть пустым, единственным ограничением является то, что объявления переменных предшествуют объявлениям методов, если они есть.

Answer 1

Другой способ сделать это - даже не иметь пустых правил, а вместо этого использовать несколько опций, один с нетерминалом, а другой без.

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
                  ;

Answer 2

Это не двусмысленность, это проблема предвидения. Проблема в том, что вам нужно 3 токена упреждения (до SEMICOLON или LPAREN следующего объявления), чтобы синтаксический анализатор мог определить, где находится конец variableDeclarationList, так как ему нужно уменьшить пустой метод methodDeclarationList перед ним. начинает анализировать больше methodDeclarations.

Способ исправить это - устранить необходимость в пустом сокращении в начале списка объявлений метода:

methodDeclarationList : nonEmptyMethodDeclarationList | /*empty */ ;

nonEmptyMethodDeclarationList : nonEmptyMethodDeclarationList methodDeclaration
                              | methodDeclaration
                              ;

При этом синтаксическому анализатору не нужно уменьшать пустой методDeclarationList, ЕСЛИ УКАЗАНО, что методов вообще нет - и в этом случае для просмотра RBRACE

нужен только один токен упреждения.

Answer 3

Эта слегка измененная грамматика работает:

%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', вы избегаете неоднозначности.

Это позволяет синтаксически разрешать методы, чередующиеся с переменными в объявлении класса. Если это по какой-то причине неприемлемо, рассмотрите возможность сделать это семантическойошибка, а не синтаксическая ошибка. Если это должна быть синтаксическая ошибка, то кому-то придется подумать; я голосую, чтобы заставить вас думать.

---

Если вы настаиваете хотя быодно объявление метода, тогда грамматика однозначна:

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

Если вы попытаетесь сделать то же самое со списком объявлений переменных, грамматика по-прежнему будет иметь два конфликта S / R.

Одна возможность, нечтобы быть полностью проигнорированным, это использовать функцию Зубр, %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
        ;

Answer 4

Я не знаком с бизоном, но вы пытались создать правило для общего префикса обоих правил?«идентификатор типа» присутствует и в шаблонах переменных, и в методах.

Итак, если бы вы сказали:

typedId : type ID
        ; 

, а затем

variableDeclaration : typedId SEMICOLON
                    ;

methodDeclaration   : typedId LPAREN parameterDeclarationList RPAREN variableExpressionBlock
                    ;

таким образом,правило переменной и правило метода не будут рассматриваться до тех пор, пока общий префикс не будет передан, и следующий токен будет однозначным.

Я не играл с подобными вещами годами, надеюсь, это поможет.