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

Question

Я реализую парсер для подмножества 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,

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

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

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

Answer 1

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

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

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

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

exp [ exp ] = exp

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

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