Грамматика для арифметических выражений

Question

Мне было поручено создать синтаксический анализатор для арифметических выражений (с круглыми скобками и унарными операторами). Поэтому я просто хочу знать, правильна ли эта грамматика или нет, и находится ли она в форме LL (1), и у меня есть реальные проблемы при создании таблицы разбора для этого

 S  -> TS'
 S' -> +TS' | -TS' | epsilon
 T  -> UT'
 T' -> *UT' | /UT' | epsilon
 U  -> VX
 X  -> ^U | epsilon
 V  -> (W) | -W | W | epsilon
 W  -> S | number

---

Старшинство (от высокого к низкому)

 (), unary –
 ^
 *, /
 +, -

Ассоциативность для бинарных операторов

 ^ = right
 +, -, *, / = left

---

Answer 1

Это в форме LL (1)?

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

Например, рассмотрим это правило:

X --> X | x | epsilon

Это явно не может быть частью грамматики LL (1), так как она рекурсивна слева, если вы применяете самый левый выпуск. Но как насчет этого?

X --> Y | x
Y --> X + X

Это также не грамматика LL (1), но она более тонкая: сначала вы должны применить X -> Y, затем применить Y -> X + X, чтобы увидеть, что теперь у вас есть X -> X + X, который является леворекурсивным.

Answer 2

Вы, похоже, ничего не упустили для унарного оператора плюс. Попробуйте вместо этого ...

V -> (W) | -W | + W | эпсилон