Преобразование заданной грамматики неоднозначного арифметического выражения в однозначный LL(1)

Question

В этом плане у меня есть курс по компиляторам, и в настоящее время мы изучаем синтаксис - различные грамматики и типы синтаксических анализаторов. Я столкнулся с проблемой, которую не могу точно понять, или, по крайней мере, не могу убедиться, что делаю это правильно. Я уже сделал 2 попытки, и контрпримеры были найдены. Мне дана эта неоднозначная грамматика для арифметических выражений: E → E + E | EE | E * E | E / E | E ^ E | -Е | (E) | id | Num, где ^ означает власть.

Я понял, какими должны быть приоритеты. Наивысшим приоритетом являются круглые скобки, за которыми следует мощность, затем унарный минус, затем умножение и деление, а затем - сложение и вычитание. Меня просят преобразовать это в эквивалентную грамматику LL(1). Итак, я написал это:

• E → E + A | EA |
• A → A*B | A/B | В
• B → -C | С
• C → D ^ C | D
• D → (E) | id | Num
  

То, что кажется проблемой с этим, не эквивалентно грамматике первой, хотя это не является двусмысленным. Например: данная грамматика может распознавать ввод: --5, а моя грамматика не может. Как я могу убедиться, что покрываю все дела? Как мне изменить мою грамматику, чтобы она была эквивалентна данной? Заранее спасибо.

Изменить: Кроме того, я бы, конечно, сделал устранение левой рекурсии и левого факторинга, чтобы сделать этот LL(1), но сначала мне нужно выяснить эту основную часть, которую я спросил выше.

Answer 1

Вот тот, который должен работать для вашего случая

E = E+A | E-A | A
A = A*C | A/C | C
C = C^B | B
B = -B | D
D = (E) | id | num

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