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

В статье Теодора Норвелла (1999) « Разбор выражений по рекурсивному спуску» автор начинает со следующей грамматики для арифметических выражений:

E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v

что довольно плохо, потому что это неоднозначно и леворекурсивно. Поэтому он начинает с удаления левой рекурсии, и его результат таков:

E --> P {B P}
P --> v | "(" E ")" | U P
B --> "+" | "-" | "*" | "/" | "^"
U --> "-"

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

Во-первых, я группирую производства, которые не оставили рекурсии в одной группе, и другие (леворекурсивные) в другой группе:
```
E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E     // L-recursive
E --> v | "(" E ")" | "-" E
```
Далее я назову их и фактор для более легкой манипуляции:
```
E --> E B E  // L-recursive; B stands for "Binary operator"
E --> P  // not L-recursive; P stands for "Primary Expression"
P --> v | "(" E ")" | U E   // U stands for "Unary operator"
B --> "+" | "-" | "*" | "/" | "^"
P --> "-"
```
Теперь мне нужно иметь дело только с первыми двумя постановками, с которыми теперь легче иметь дело.
Я переписываю эти первые два производства, начиная с не L-рекурсивного производства (то есть просто P, Первичное выражение) и следуя за ним дополнительным хвостом T, который я определяю как остальную часть исходного производства за исключением первого леворекурсивного нетерминала. (то есть просто B E), за которым следует хвост T, или который может быть пустым:
```
E --> P T
T --> B E T |
```
(обратите внимание на пустую альтернативу для хвоста).
Эти два произведения я теперь могу переписать в EBNF следующим образом:
```
E --> P {B E}
```
это почти то, что получает автор, но у меня есть Eвместо Pэтого внутри шаблона повторения ноль или более (Хвост). Другие постановки, которые я получаю, такие же, как у него:
```
P --> v | "(" E ")" | U E
B -> "+" | "-" | "*" | "/" | "^"
U -> "-"
```
но и здесь у меня Eвместо Pпервого производства для P.

Итак, мой вопрос: что мне не хватает? Какое алгебраическое преобразование синтаксиса мне нужно выполнить сейчас, чтобы получить ту же самую точную форму, которую получает автор? Я пытался заменить на E, но это только приводит меня в петли. Я подозреваю , что мне нужно как - то заменить Pна E, но я не знаю , какой - либо правовой трансформации , чтобы оправдать его. Может быть, вы знаете, какой последний пропущенный шаг?

formal-languages context-free formal-grammars left-recursion SasQ
источник

Пожалуйста, рассмотрите возможность использования LaTeX для форматирования. Смотрите здесь для начинающих . (См. Здесь для обсуждения пригодности LaTeX в этом случае.)

Рафаэль

Недостающий шаг:

E --> P T
T --> B E T |

переписать E в T:

E --> P T
T --> B P T T |

Упростить T:

E --> P T
T --> B P T |

Эквивалентно:

E --> P T
T --> {B P}

И вот вы здесь.

Kena
источник

Спасибо за хороший ответ :-) Теперь я вижу то, что я пропустил: я заменил это наоборот, и это было проблемой. Но все же я не понимаю одного маленького кусочка: откуда ты знаешь, что ты можешь безопасно объединить все Tвместе в один T? Есть ли какое-то правило для этого? (Я подозреваю, что это может быть как-то похоже на правило в булевой алгебраической логике, которое говорит «aa = a».)

SasQ

Кстати, почему этот пост был перенесен с cstheory.sx и в чем разница? Я хотел бы знать, чтобы избежать ошибок в будущем.

SasQ

@SasQ CSTheory предназначен только для вопросов исследовательского уровня в теоретической информатике, подробности см. В разделе часто задаваемых вопросов CSTheory.

Juho

T \to x T T ∣ ε

$T \to xTT \mid \varepsilon$

x^{*}

$x^*$

T \to x T ∣ ε

$T \to xT \mid \varepsilon$

L^{*} L^{*} = L^{*}

$L^*L^* = L^*$

L

$L$

ε

$\varepsilon$

L^{+} L^{+} \neq L^{+}

$L^+L^+ \neq L^+$

@ Рафаэль: Это как-то связано с правилом идемпотентности *? Я видел в «Книге Дракона» (3.3, стр.91) это x** = x*. Это то же правило, которое вы использовали?

SasQ

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

Ответы: