pergerakan ll(1) parser dengan input abba
DESCRIPTION
Pergerakan LL(1) Parser dengan input abba. S aBa B bB | . stack input output. abba$. $. S. Pergerakan LL(1) Parser dengan input abba. a. S aBa B bB | . S. stack input output $S a bba$. S aBa. $ S. S aBa. $ aBa. $ aB a. $. a bba$. Pop( a ). - PowerPoint PPT PresentationTRANSCRIPT
Pergerakan LL(1) Parser dengan input abba
stack input output
a b $
S S aBa
B B B bB
S aBa B bB |
S $ abba$
Pergerakan LL(1) Parser dengan input abba
stack input output$S abba$
a b $
S S aBa
B B B bB
S aBa B bB |
S aBa
S
a
$
S aBa
abba$$aB
Pop(a)bba$
$S$aBa$aBa
Pergerakan LL(1) Parser dengan input abba
stack input output$S abba$
a b $
S S aBa
B B B bB
S aBa B bB |
S aBa
B
b
$aBa$
B bB
abba$$aB
Pop(a)bba$ B bBbba$$aB
$a ba$Bb ba$ b Pop(b)$aB a$
Pergerakan LL(1) Parser dengan input abba
stack input output$S abba$
a b $
S S aBa
B B B bB
S aBa B bB |
S aBa
B
a
$aBa$
B
abba$$aB
Pop(a)
bba$ B bBbba$$aB$a ba$Bb ba$ b Pop(b)$aB a$$aB a$ B $a a$$a Pop(a)$ $
Pergerakan LL(1) Parser dengan input abba
stack input output$S abba$
a b $
S S aBa
B B B bB
S aBa B bB |
S aBa$aBa$ abba$$aB
Pop(a)
bba$ B bBbba$$aB$a ba$Bb ba$ b Pop(b)$aB a$$aB a$ B $a a$$a Pop(a)$ $$ $ Accepted
Parsing Sukses
Pergerakan parsing dengan input abba
S
S aBa
a B a
b B
b
B bB
B
Derivasi language: Input: abba
Parse tree:
Pergerakan LL(1) Parsing
id + * ( ) $
E E TE’ E TE’
E’ E’ +TE’ E’ E’
T T FT’ T FT’
T’ T’ T’ *FT’ T’ T’
F F id F (E)
stack input output$E id+id$
E
id
E TE’
E TE’
$E’T id+id$
T
id
T FT’
T FT’
$E’T’F id+id$
F
id
F id
F id
$E’T’id id+id$ Pop(id)
$E’T’ +id$
T’
+
T’ $E’ +id$
E’
+
E’ +TE’
E’ +TE’
$E’T+ +id$ Pop(+)
$E’T id$
T
id
T FT’
T FT’
$E’T’F id$
F
id
F id
F id$E’T’id id$ Pop(id)
$E’T’ $
T’
$
T’
T’ $E’ $
E’
$
E’
E’ $ $ accepted
T’
Input: id + id
E
T E’
F + T E’
id F T’
id
Parse tree:
Tabel parsing:Contoh Top down parsing
E TE
E +TE
T FT
T FT
F (E) id
Contoh mencari FIRST
First(E) = First(TE) = First(T)
First(T) = First(FT) = First(F)
First(F) = { ( , id }= First(‘(E)’) | First(id)
First(E) = First(+TE) | First() = { + , }
First(T) = First(FT) | First() = { , }
Contoh mencari FOLLOW (pada non terminal)
E TE’
E’ +TE’ |
T FT’
T’ *FT’ |
F (E) | id
Rules:
1. If S is the start symbol $ is in FOLLOW(S)
2. If A B is a production rule everything in FIRST() is FOLLOW(B) except
3. If ( A B is a production rule ) or ( A B is a production rule and is in FIRST() )
everything in FOLLOW(A) is in FOLLOW(B).
E start simbol Follow(E) = { $ }
Derivasi:
(Rule 1)
Contoh mencari FOLLOW (pada non terminal)
Rules:
1. If S is the start symbol $ is in FOLLOW(S)
2. If A B is a production rule everything in FIRST() is FOLLOW(B) except
3. If ( A B is a production rule ) or ( A B is a production rule and is in FIRST() )
everything in FOLLOW(A) is in FOLLOW(B).
E start simbol Follow(E) = { $ }
F (E) Follow(E) = { ) } Follow(E) = { ), $ }
E TE
E (Rule 3) Follow(T) = Follow(E) = { $, ) }
E +TE (Rule 2) Follow(T) = First(E) - = { + }
Follow(T)= { +, ), $ }
T FT’
T’
T’ *FT’
(Rule 3) Follow(F) = Follow(T) = {+, ), $ }
(Rule 2) Follow(F) = First(T) - = {*}
Follow(F)={*,+, ), $}
(Rule 2)
Contoh mencari FOLLOW (pada non terminal)
Rules:
1. If S is the start symbol $ is in FOLLOW(S)
2. If A B is a production rule everything in FIRST() is FOLLOW(B) except
3. If ( A B is a production rule ) or ( A B is a production rule and is in FIRST() )
everything in FOLLOW(A) is in FOLLOW(B).
E TE’
T FT’
(rule 3) Follow(E’) = Follow(E) = { ), $ }
(rule 3) Follow(T’) = Follow(T) = { +, ), $ }
dengan = T
dengan = F
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
Follow(E) = { $, ) }
Follow(E’) = { $, ) }
Follow(T) = { +, ), $ }
Follow(T’) = { +, ), $ }
Follow(F) = {+, *, ), $ }
First(E) = { (, id }
First(E’) = { +, }
First(T) = { (, id }
First(T’) = { , }
First(F) = { (, id }
Pembuatan tabel parsing top-down
id + * ( ) $
E
E’
T
T’
F
E TE’
E’ +TE’
E’
T FT’
T’ *FT’
T’
F (E)
F id
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
First(TE’) = { (, id } dengan aturan 1
id + * ( ) $
E
E’
T
T’
F
E’ +TE’
E’
T FT’
T’ *FT’
T’
F (E)
F id
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
First(+TE’) = { + } dengan aturan 1
E TE’E TE’
id + * ( ) $
E
E’
T
T’
F
E’
T FT’
T’ *FT’
T’
F (E)
F id
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
Follow(E’) = { $, ) } dengan aturan 2
E TE’E TE’
E’ +TE’
id + * ( ) $
E
E’
T
T’
F
T FT’
T’ *FT’
T’
F (E)
F id
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
First(FT’) = { (, id } dengan aturan 1
E TE’E TE’
E’ +TE’ E’ E’
id + * ( ) $
E
E’
T
T’
F
T’ *FT’
T’
F (E)
F id
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
First(*FT’) = { * } dengan aturan 1
E TE’E TE’
E’ +TE’ E’ E’ T FT’T FT’
id + * ( ) $
E
E’
T
T’
F
T’
F (E)
F id
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
Follow(T’) = { +, ), $ } dengan aturan 2 & 3
E TE’E TE’
E’ +TE’ E’ E’ T FT’T FT’
T’ *FT’
id + * ( ) $
E
E’
T
T’
F
F (E)
F id
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
First(“(E)”) = { ( } dengan aturan 1
E TE’E TE’
E’ +TE’ E’ E’ T FT’T FT’
T’ *FT’T’ T’ T’
id + * ( ) $
E
E’
T
T’
F
F id
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
First(id) = { id } dengan aturan 1
E TE’E TE’
E’ +TE’ E’ E’ T FT’T FT’
T’ *FT’T’ T’ T’ F (E)
id + * ( ) $
E
E’
T
T’
F
•for each production rule A of a grammar G
1. for each terminal a in FIRST() add A to M[A,a]
2. If in FIRST() for each terminal a in FOLLOW(A) add A to M[A,a]
3. If in FIRST() and $ in FOLLOW(A) add A to M[A,$]
•All other undefined entries of the parsing table are error entries.
Algoritma pembuatan tabel parsing:
Selain itu adalah error
E TE’E TE’
E’ +TE’ E’ E’ T FT’T FT’
T’ *FT’T’ T’ T’ F (E)F id
error error error errorerror errorerror
error error error errorerror error
error error error error
Self Assessment1. Jika diketahui grammar dengan derivasi sbb:
S aBa B bB |
Maka nilai First(B) adalah: a.) a b.) b c.) $ d.) S
2. Dari soal no.1 nilai dari First(S) adalah:a.) a b.) b c.) $ d.) S
3. Dari soal no. 1 nilai dari Follow(S) adalah:a.) a b.) b c.) $ d.) S
4. Simbol yang digunakan sebagai tanda akhir input dalam pergerakan parsing adalah:
a.) a b.) b c.) $ d.) S
Summary
• Top down parsing melakukan parsing dari start simbol sehingga terbentuk parse tree
• Untuk melakukan top down parsing dengan stack pertama-tama isi stack adalah $ dan start simbol
• Untuk membuat tabel parsing harus dicari dulu nilai first dan follow dari setiap non terminal simbol.