уменьшить / уменьшить конфликт в CUP - PullRequest
Новая
       58

уменьшить / уменьшить конфликт в CUP

0 голосов
/ 08 декабря 2018

Я реализую синтаксический анализатор для подмножества Java, используя Java CUP.

Грамматика похожа на 

vardecl ::= type ID
type    ::= ID | INT | FLOAT | ...
exp     ::= ID | exp LBRACKET exp RBRACKET | ...
stmt    ::= ID ASSIGN exp SEMI

Это прекрасно работает, но когда я добавляю 

stmt ::= ID ASSIGN exp SEMI
        |ID LBRACKET exp RBRACKET ASSIGN exp SEMI

CUP не будет работать, предупреждения: 

Warning : *** Shift/Reduce conflict found in state #122
  between exp ::= identifier (*) 
  and     statement ::= identifier (*) LBRACKET exp RBRACKET ASSIGN exp SEMI 
  under symbol LBRACKET
  Resolved in favor of shifting.

Warning : *** Reduce/Reduce conflict found in state #42
  between type ::= identifier (*) 
  and     exp ::= identifier (*) 
  under symbols: {}
  Resolved in favor of the first production.

Warning : *** Shift/Reduce conflict found in state #42
  between type ::= identifier (*) 
  and     statement ::= identifier (*) LBRACKET exp RBRACKET ASSIGN exp SEMI 
  under symbol LBRACKET
  Resolved in favor of shifting.

Warning : *** Shift/Reduce conflict found in state #42
  between exp ::= identifier (*) 
  and     statement ::= identifier (*) LBRACKET exp RBRACKET ASSIGN exp SEMI 
  under symbol LBRACKET
  Resolved in favor of shifting.

Я думаю, что есть две проблемы:
1. type ::= ID и exp ::= ID, когда анализатор видит идентификатор, онхочет уменьшить его, но не знает, какое уменьшить, type или exp.

stmt ::= ID LBRACKET exp RBRACKET ASSIGN exp SEMI для назначения элемента в массиве, например arr[key] = value;
exp :: exp LBRACKET exp RBRACKET для выражения получения элемента из массива, например arr[key]

Таким образом, в случае arr[key], когда анализатор видит arr, он знает, что это идентификатор, но не знает, должен ли он сдвигаться или уменьшаться до exp.

Однако яПонятия не имею, как это исправить, пожалуйста, дайте мне несколько советов, если у вас есть, большое спасибо.

1 Ответ

0 голосов
/ 08 декабря 2018

Ваш анализ верен.Грамматика - LR (2), потому что объявления не могут быть идентифицированы, пока не будет замечен токен ], который будет вторым-следующим токеном от идентификатора, который может быть типом.

Одно простое решение - взломатьлексер для возврата [] в виде одного токена, когда скобки появляются в виде последовательных токенов.(Лексер, вероятно, должен также разрешать использовать пробелы между скобками, так что это не совсем тривиально, но и не сложно.) Если за [ сразу не следует ], лексер вернет его как обычный [,Это позволяет анализатору легко различать присвоение массиву (который будет иметь токен [) и объявление массива (который будет иметь токен []).

Также возможнопереписать грамматику, но это настоящая неприятность.

Вторая проблема - присвоение индексации массива в сравнении с выражениями индексации массива.Обычно языки программирования позволяют присваивать форму: 

exp [ exp ] = exp

, а не просто ID [ exp ].Внесение этого изменения задержит необходимость сокращения до достаточно позднего времени, чтобы синтаксический анализатор смог определить правильное сокращение.В зависимости от языка, возможно, что этот синтаксис не является семантически значимым, но проверка, которая находится в области проверки типа (семантики), а не синтаксиса.Если есть какой-то синтаксис этой формы, который имеет смысл, тем не менее, нет очевидной причины запрещать его.

Некоторые генераторы синтаксических анализаторов реализуют синтаксические анализаторы GLR.У парсера GLR не будет проблем с этой грамматикой, потому что она не является двусмысленной.Но CUP не такой генератор.

...