Ekspresi aritmatika transformasi tata bahasa

Dalam artikel Parsing Expressions by Recursive Descent oleh Theodore Norvell (1999) penulis mulai dengan tata bahasa berikut untuk ekspresi aritmatika:

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

yang sangat buruk, karena ambigu dan kiri-rekursif. Jadi dia mulai menghilangkan rekursi kiri dari sana, dan hasilnya adalah seperti ini:

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

Tapi saya tidak tahu bagaimana dia bisa mencapai hasil ini. Ketika saya mencoba untuk menghapus rekursi kiri sendiri, saya melakukannya dengan cara berikut:

Pertama, saya mengelompokkan produksi yang tidak memiliki rekursi dalam satu kelompok, dan lainnya (rekursif kiri) dalam kelompok lain:
```
E --> E "+" E | E "-" E | E "*" E | E "/" E | E "^" E     // L-recursive
E --> v | "(" E ")" | "-" E
```

Selanjutnya, saya beri nama dan faktor untuk manipulasi yang lebih mudah:

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

Sekarang saya hanya perlu berurusan dengan dua produksi pertama, yang sekarang lebih mudah untuk ditangani.

Saya menulis ulang dua produksi pertama dengan memulai dari produksi non-L-rekursif (yang sederhana P, ekspresi Primer) dan mengikutinya dengan Tail opsional T, yang saya definisikan sebagai sisa produksi asli kurang dari non-rekursif kiri-rekursif pertama (yaitu, hanya B E) diikuti oleh Ekor T, atau yang bisa kosong:
```
E --> P T
T --> B E T |
```
(perhatikan alternatif kosong untuk ekor).
Dua produksi ini sekarang saya dapat menulis ulang di EBNF seperti ini:
```
E --> P {B E}
```
yang hampir seperti apa yang penulis dapatkan, tetapi saya memiliki Ealih - alih Pdi dalam pola pengulangan nol atau lebih (Ekor). Produksi lain yang saya dapatkan sama persis seperti yang dia dapatkan:
```
P --> v | "(" E ")" | U E
B -> "+" | "-" | "*" | "/" | "^"
U -> "-"
```
tapi di sini juga saya miliki Edaripada Pdi produksi pertama untuk P.

Jadi, pertanyaan saya adalah: Apa yang saya lewatkan? Transformasi aljabar apa pada sintaks yang saya perlukan untuk melanjutkan sekarang untuk mendapatkan bentuk yang sama persis dengan yang didapat autor? Saya mencoba substitusi E, tetapi itu hanya membuat saya menjadi loop. Saya menduga bahwa saya perlu entah bagaimana untuk menggantikan Puntuk E, tapi saya tidak tahu apapun transformasi hukum untuk membenarkan itu. Mungkin Anda tahu apa langkah terakhir yang hilang?

formal-languages context-free formal-grammars left-recursion SasQ
sumber

Silakan pertimbangkan menggunakan LaTeX untuk memformat. Lihat di sini untuk primer . (Lihat di sini untuk diskusi tentang kesesuaian LaTeX dalam kasus ini.)

Raphael

Langkah yang hilang:

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

tulis ulang E dalam T:

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

Sederhanakan T:

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

Setara dengan:

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

Dan itu dia.

kena
sumber

Terima kasih atas jawaban yang bagus :-) Sekarang saya melihat apa yang saya lewatkan: Saya menggantinya sebaliknya dan itulah masalahnya. Tetapi saya masih tidak mengerti satu bagian kecil: Bagaimana Anda tahu bahwa Anda dapat dengan aman menggabungkan Tbersama menjadi satu T? Apakah ada aturan untuk itu? (Saya menduga itu bisa mirip dengan aturan dalam logika aljabar Boolean yang mengatakan "aa = a".)

SasQ

BTW mengapa postingan ini dipindahkan dari cstheory.sx dan apa bedanya? Saya ingin tahu untuk menghindari kesalahan di masa depan.

SasQ

@SasQ CSTheory hanya untuk pertanyaan tingkat penelitian dalam ilmu komputer teoretis, lihat FAQ CSTheory untuk detailnya.

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

@ Raphael: Apakah ada hubungannya dengan aturan idempotence *? Saya melihat di "Buku Naga" (3.3, hal.91) itu x** = x*. Apakah itu aturan yang sama yang Anda gunakan?

SasQ

Ekspresi aritmatika transformasi tata bahasa

Jawaban: