Конфликт между сдвигом конкатенации и уменьшением

У меня есть простая грамматика для парсера JavaCUP LR (1), который распознает выражения конкатенации идентификаторов и строк. Я также хочу добавить несколько пустых вызовов функций в качестве возможного аргумента конкатенации. Однако, когда я пытаюсь это сделать, это приводит к конфликту сдвига / уменьшения.

Грамматика:

precedence left PLUS;

e ::= e exp
      | exp;

exp ::= concat
      | literal;

concatenation ::= exp PLUS exp
                | LPAREN exp RPAREN;


literal ::= IDENTIFIER
          | STRING
          | IDENTIFIER LPAREN RPAREN; // THIS PRODUCES THE ERROR

Ввод:

x + x + (x)            // match
"foo" + x              // match
(("goo") + (((y))))    // match

function_name() + x + "foo" + (other_func())    // what I also want

Конфликт:

Warning : *** Shift/Reduce conflict found in state #12
between literal ::= IDENTIFIER (*) 
and     literal ::= IDENTIFIER (*) LPAREN RPAREN  
under symbol LPAREN

Я пробовал много разных вещей, например, скрывать идентификатор, например IDENTIFIER second в буквальном смысле и second ::= | LPAREN RPAREN;, но я не могу заставить его работать.


parsing compiler-construction context-free-grammar shift-reduce-conflict cup
person matrix    schedule 15.03.2016    source источник
comment
Вы привязаны к JavaCUP? Или вам просто нужен способ разбирать простые выражения?   -  person Stefan Haustein    schedule 16.03.2016
comment
К сожалению только JavaCUP   -  person matrix    schedule 16.03.2016

Ответы (2)


arrow_upward
1
arrow_downward

Контекст, в котором это, кажется, возникает в таких выражениях, как

x + x()

где синтаксический анализатор, увидев x + x, не может сказать, должен ли он уменьшить x + x обратно до exp или сдвинуть (. Другими словами, он не может сказать, следует ли интерпретировать выражение как

x + [x()]

or as

[x + x]()

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

person templatetypedef    schedule 17.03.2016
comment
Фактически, вам нужно, чтобы '(' имел более высокий приоритет, чем IDENTIFIER, а не '+'. (Но '+' необходимо объявить как левоассоциативное из-за неоднозначности производства concat: exp '+' exp) - person rici; 20.03.2016

arrow_upward
0
arrow_downward

Bison обрабатывает следующую грамматику без конфликтов сдвига / сокращения:

%token IDENTIFIER STRING
%left IDENTIFIER
%left '('
%left '+'
%%

e      : e exp
       | exp

exp    : concat
       | literal

concat : exp '+' exp
       | '(' exp ')'

literal: IDENTIFIER
       | IDENTIFIER '(' ')'
       | STRING

Необходимо предоставить объявление приоритета для IDENTIFIER, чтобы дать приоритет продукции literal: IDENTIFIER.

Я нашел грамматику немного странной, поскольку она, похоже, не позволяет заключать конкатенации в скобки. Но я уверен, что на то есть причины.

Вышеупомянутое будет работать нормально, пока вызовы функций не имеют аргументов, но оно не позволит вызывать функции с аргументом, поскольку это было бы неоднозначно. (Это может считаться хорошей причиной не разрешать использование невидимого оператора конкатенации.) Как бы то ни было, awk, который имеет как функции, так и конкатенацию без оператора, решает эту двусмысленность лексически: идентификатор, за которым сразу следует (, без пробелов, обозначается как FUNC_NAME, а идентификатор, за которым следует пробел или любой другой символ, кроме (, обозначается как NAME.

Другим возможным решением было бы потребовать объявления функций перед использованием, а затем использовать таблицу символов и лексическую обратную связь (т. Е. Передачу информации обратно от синтаксического анализатора к лексеру; в этом случае тот факт, что данный идентификатор является функцией) .

person rici    schedule 20.03.2016