Арифметическая грамматика выражения в префиксном обозначении (Java Cup)

Question

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

precedence right +, -; 
precedence right *, /; 
precedence right uminus; 

E ::= + E E 
    | - E E 
    | * E E 
    |/E E 
    | (E) 
    | - E %prec uminus 
    | id 
    | digit 
    ; 

Но если мой вход - 5 4, это уменьшает 5 в E, рядом уменьшает - E (отрицательный), а затем парсер дает мне ошибку синтаксиса в 4. Правильный должен быть 5 как E, следующий 4 как E, а затем - E E как E. Как я могу решить эту проблему с помощью ассоциативности? или мне нужно переписать мою грамматику?

Answer 1

(Повышен от комментариев)

Ваша грамматика действительно неоднозначна, и декларации старшинства не поможет вам немного.

Рассмотрим Входные данные, состоящий из N- маркеров, а затем M1 маркеров.

- - - - - - - ... - 1 1 1 ... 1 

Для того, чтобы это было выражение, M-1 из - лексем должны быть двоичными, а остальные N-(M-1) унарными, но нет никакого способа узнать, что есть что (если они не являются всеми бинарными).

Даже если угодно сказать, что первые N-(M-1)- s является унарным, вы не можете сказать, что значение N-(M-1) пока вы не читали весь ввод, который означает, что вы не можете разобрать с конечным опережающим просмотром.

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

Вот простой пример:

- 5 - - - 4 3 1 

либо

5 - (- (4 - (3 - 1))) 
5 - ((- (4 - 3)) - 1) 
5 - (((- 4) - 3) - 1) 

В префиксной нотации, вы должны объявить «арность» каждый оператор, либо неявно (каждый оператор имеет известное число аргументов) или явно используя такую ​​запись, взятую из Пролога:

-/2 5 -/2 -/2 -/1 4 3 1 

В качестве альтернативы, вы можете разграничить аргументы обязательные скобки, как и Лисп/Scheme «S-exprs»:

(- 5 (- (- (- 4) 3) 1)) 

Answer 2

Во-первых, удалите все объявления приоритета. Они не нужны в префиксных грамматиках. На самом деле этого должно быть достаточно, чтобы решить проблему в любом генераторе парсеров. Какой из них вы используете, BTW?

Кубок имеет конечный вид. Как указывает @rici, двусмысленность в этом случае не может быть решена. Что вы можете сделать, так это ограничить грамматику, так что можно использовать только один последовательный унарный -.

B ::= E 
     | - E 
     ; 
    E ::= + B B 
     | - B B 
     | * B B 
     |/B B 
     | (B) 
     | id 
     | digit 
     ; 

Пожалуйста, проверьте выше несколько раз, так как я довольно ржавый.