Wyrażenia arytmetyczne transformacja gramatyczna

W artykule Parsing Expressions by Recursive Descent autorstwa Theodore Norvell (1999) autor zaczyna od następującej gramatyki wyrażeń arytmetycznych:

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

co jest dość złe, ponieważ jest dwuznaczne i lewostronne. Zaczyna więc od usunięcia lewej rekurencji, a jego wynik jest następujący:

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

Ale nie mogę zrozumieć, jak doszedł do tego wyniku. Kiedy próbuję samodzielnie usunąć lewą rekurencję, robię to w następujący sposób:

Firs, grupuję razem produkcje, które nie opuściły rekurencji w jednej grupie, a inne (lewostronne) w innej grupie:
```
E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E     // L-recursive
E --> v | "(" E ")" | "-" E
```

Następnie nazywam je i biorę pod uwagę łatwiejsze manipulacje:

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 --> "-"

Teraz muszę zajmować się tylko dwoma pierwszymi produkcjami, z którymi łatwiej sobie poradzić.

Te dwie pierwsze produkcje przepisuję, zaczynając od produkcji nierekurencyjnej (która jest po prostu Ppierwotnym wyrażeniem), a następnie opcjonalnym ogonem T, który definiuję jako resztę oryginalnej produkcji, pomniejszoną o pierwszą nieterminalną rekurencyjną lewą (czyli po prostu B E), po którym następuje ogon T, lub który może być pusty:
```
E --> P T
T --> B E T |
```
(zwróć uwagę na pustą alternatywę dla ogona).
Te dwie produkcje mogę teraz przepisać w EBNF w następujący sposób:
```
E --> P {B E}
```
co jest prawie tym, co dostaje autor, ale Ezamiast tego mam Pwewnątrz wzorca zero lub więcej powtórzeń (Ogon). Inne produkcje, które otrzymuję, są takie same jak on:
```
P --> v | "(" E ")" | U E
B -> "+" | "-" | "*" | "/" | "^"
U -> "-"
```
ale tutaj też mam Ezamiast Pw pierwszej produkcji P.

Moje pytanie brzmi: czego brakuje? Jaką transformację algebraiczną w składni muszę teraz przejść, aby uzyskać dokładnie taką samą formę, jak autor? Próbowałem substytucji E, ale prowadzi mnie to tylko do pętli. Podejrzewam, że muszę jakoś zastąpić Pza E, ale nie znam żadnej transformacji prawnego uzasadnienia. Może wiesz, jaki jest ostatni brakujący krok?

formal-languages context-free formal-grammars left-recursion SasQ
źródło

Proszę rozważyć użycie LaTeXa do formatowania. Zobacz tutaj podkład . (Zobacz tutaj dyskusję na temat przydatności LaTeXa w tym przypadku.)

Raphael

Brakujący krok:

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

przepisz E w T:

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

Uprość T:

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

Równoważny:

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

I proszę bardzo

kena
źródło

Dzięki za dobrą odpowiedź :-) Teraz widzę, co przeoczyłem: zastąpiłem to na odwrót i to był problem. Ale wciąż nie rozumiem jednego małego kawałka: skąd wiesz, że możesz bezpiecznie połączyć je Tw jeden T? Czy jest na to jakaś reguła? (Podejrzewam, że może to być jakoś podobne do reguły logiki algebraicznej Boolean, która mówi „aa = a”.)

SasQ

BTW, dlaczego ten post został przeniesiony tutaj z cstheory.sx i jaka jest różnica? Chciałbym wiedzieć, aby uniknąć błędów w przyszłości.

SasQ

@SasQ CSTheory służy wyłącznie do pytań na poziomie badawczym w teoretycznej informatyce, szczegółowe informacje znajdują się w FAQ CSTheory.

Juho,

@SasQ: generuje podobnie jak . Bardziej ogólnie, dla dowolnego języka. Zauważ, że kluczowe znaczenie ma puste słowo prawej stronie; nie dotyczy to wszystkich fragmentów gramatycznych, ponieważ .

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^+$

Raphael

@Raphael: Czy to ma coś wspólnego z regułą idempotencji *? Widziałem to w „Dragon Book” (3.3, s. 91) x** = x*. Czy to ta sama reguła, której użyłeś?

SasQ

Wyrażenia arytmetyczne transformacja gramatyczna

Odpowiedzi: