Bagaimana tata bahasa LL (1) ini?

12

Ini pertanyaan dari Buku Naga. Ini adalah tata bahasanya:

SAaAbBbBa
Aε
Bε

Pertanyaannya adalah bagaimana menunjukkan bahwa itu LL (1) tetapi tidak SLR (1).

Untuk membuktikan bahwa itu adalah LL (1), saya mencoba membangun tabel parsingnya, tetapi saya mendapatkan beberapa produksi dalam sel, yang merupakan kontradiksi.

Tolong beritahu bagaimana LL ini (1), dan bagaimana membuktikannya?

Vinayak Garg
sumber
6
L={ab,ba}
@ Nejc: Ya sepertinya begitu!
Vinayak Garg

Jawaban:

11

Pertama, mari beri nomor produksi Anda.

SAaAb
SBbBa
Aε
Bε

Mari kita hitung yang pertama dan ikuti set pertama. Untuk contoh kecil seperti ini, menggunakan intuisi tentang set ini sudah cukup.

FIRST(S)={a,b}FIRST(A)={}FIRST(B)={}FOLLOW(A)={a,b}FOLLOW(B)={a,b}

LL(1)LL(1)

    a | b |
-----------
S | 1 | 2 |
A | 3 | 3 |
B | 4 | 4 |

LL(1)

SLR(1)LR(0)

state 0SAaAbSBbBaABA1B5
state 1SAaAba2
state 2SAaAbAA3
state 3SAaAbb4
state 4SAaAbb
state 5SBbBab6
state 6SBbBaBB7
state 7SBbBaa8
state 8SBbBa

SLR(1)S

    a     | b     | A | B |
---------------------------
0 | R3/R4 | R3/R4 | 1 | 5 |
1 | S2    |       |   |   |
2 | R3    | R3    | 3 |   |
3 |       | S4    |   |   |
4 | R1    | R1    |   |   |
5 |       | S4    |   |   |
6 | R4    | R4    |   | 7 |
7 | S8    |       |   |   |
8 | R2    | R2    |   |   |

SLR(1)LALR(1)a LALR(1)b

LL(1)LALR(1)

Alex ten Brink
sumber
Terima kasih! Saya telah membuat First & Follow dengan benar, tetapi saya membuat kesalahan dalam membuat tabel.
Vinayak Garg
10

Jika Anda tidak diminta, Anda tidak harus membuat tabel LL (1) untuk membuktikan bahwa itu adalah tata bahasa LL (1). Anda baru saja menghitung set FIRST / FOLLOW seperti yang dilakukan Alex:

FIRST(S)=a,bFIRST(A)=εFIRST(B)=εFOLLOW(A)=a,bFOLLOW(B)=a,b

Dan kemudian, menurut definisi tata bahasa LL (1) harus:

  1. Jika dan adalah dua aturan tata bahasa yang berbeda, maka seharusnya . Oleh karena itu, dua set tidak memiliki elemen yang sama.AaAbFIRST(a)FIRST(b)=
  2. Jika untuk simbol non-terminal Anda memiliki , maka itu harus menjadi . Oleh karena itu, jika ada nol produksi untuk simbol non-terminal, maka set FIRST dan FOLLOW tidak dapat memiliki elemen umum.AΑεFIRST(A)FOLLOW(A)=

Jadi, untuk tata bahasa yang diberikan:

  1. Kami memiliki karena sementara dan mereka tidak memiliki elemen umum.FIRST(AaAb)FIRST(BbBa)=FIRST(AaAb)={a}FIRST(BbBa)={b}
  2. PERTAMA ( A ) = { a , b } IKUTI ( A ) = PERTAMA ( B ) IKUTI ( B ) = PERTAMA ( B ) = { ε } IKUTI ( B ) = { a , b }FIRST(A)FOLLOWA)= sejak sementara , dan sekarang sejak sementara .FIRST(A)={a,b}FOLLOW(A)=FIRST(B)FOLLOW(B)=FIRST(B)={ε}FOLLOW(B)={a,b}

Adapun analisis SLR (1) saya pikir itu sempurna!

Ethan
sumber
Selamat datang! Untuk meningkatkan jawaban ini, mengapa Anda tidak menerapkan apa yang Anda nyatakan pada tata bahasa yang ada?
Raphael
Senang berada di sini!! Menjawab permintaan Anda dan saya pikir saya memberikan penjelasan yang menyeluruh!
Ethan
Terima kasih! Perhatikan bahwa kita dapat menggunakan LaTeX di sini, seperti yang saya lakukan sunting untuk matematika Anda.
Raphael
Wow terima kasih! ini penjelasan yang bagus. Tapi saya pikir ada beberapa kesalahan dalam aplikasi. Bukankah Pertama (A) = {epsilon}? Saya pikir Anda menukar PERTAMA dan IKUTI.
Vinayak Garg
FIRST (A) memang epsilon tetapi karena Anda mencari untuk menghitung set FIRST anggota seluruh hak, A -> ε hanya menunjukkan bahwa kami memiliki produksi kosong dan simbol terminal pertama yang Anda lihat (dan karena itu set FIRST itu) adalah simbol terminal a. Semoga ini bisa membantu!
Ethan
0

Cari kondisi yang cukup yang membuat tata bahasa LL (1) (petunjuk: lihat set FIRST).

Cari kondisi yang diperlukan yang harus dipenuhi oleh semua tata bahasa SLR (1) (petunjuk: lihat set FOLLOW).

Pemrogram
sumber