狠狠撸

16.6 ?????????????????????????? LL(1) ????????
? ?????????????? First ??? Follow ????????????????????????????????????
(Parse Table) ?????????????????????????????????????????? 2 ???? P[i,j]
??? i ?????? j ??????? ????????????????????????????????????????????????
????????????(???????????????????????, error)

????????????????????????????
??????????????????????????????????????????? ???????????? LL(1) ???????
???????????????????????????????????????????????? 1 ????????????? ???
???????????? ?????????????????????????? LL(1) ????????????????? ????????
????? (ambiguous, ?????????) ????????????????????????? ??????????????
(semantic) ????????????????????????????????? ????? ????????????????????????
?????
1. ??? A → w ???????? P[A,a] ????? a ?????? First(w)
2. ??? ? ?????? First(w) ???? ??? A → w ???? P[A,a] ????? a ?????? Follow(A)
3. ??? ? ?????? First(w) ???? $ ?????? Follow(A) ??????? A → w ???? P[A,$]

???????? 16.13 (???????????????????)
? ????????????? ???
S → ASb | C
A → a
C → cC | ?
? ??????????????????
First Follow
S {a,c, ?} {b,$}
A {a} {a,b,c}
C {c, ?} {b,$}
a b c $
S S → ASb S → C S → C S → C
A A → a error error error
C error C → ? C → cC C → ?

Stack Input Action to Perform
$S aaccbb$ Pop, push b, push S, push A
$bSA aaccbb$ Pop, push a
$bSa aaccbb$ Pop, consume
$bS accbb$ Pop, push b, push S, push A
$bbSA accbb$ Pop, push a
$bbSa accbb$ Pop, consume
$bbS ccbb$ Pop, push C
$bbC ccbb$ Pop, push C, push c
$bbCc ccbb$ Pop, consume
$bbC cbb$ Pop, push C, push c
$bbCc cbb$ Pop, consume
$bbC bb$ Pop
$bb bb$ Pop, consume
$b b$ Pop, consume
$ $ Accept
????????????????????????????????

16.7 ?????????????? LL(k)
? ???????????????????????????? LL(k) ??? ??? ?????? ?????????????????????
????????????? ??????????????????????????? ?????????????????? ???
??????????????????? (LL-Left to right scan & Leftmost derivation)
????????????? k ∈ N

16.7 ?????????????? LL(k)
? ???????? LL(k) ? ???????? LL(k+1) ??????? ???????? LL(k) ?????????????
??????????? LL(k+1) ?????????????????????????? Kurki - Shvonio[1969]
??????????????????????????????????

16.7 ?????????????? LL(k)
? Resenkrantz and Stearns[1970] ?????????????? ???????? LL(k) ???
???????????????? ???????????????????????????????
? ???????????????????????????????????????? PDA ????????????????????????????

16.7 ?????????????? LL(k)
? ?????????????????????? LL(k) ???????????
?????? X ??????????????????????????????
???????????????? LL(k) ????????????????????????????? 2 ?????????? ????
S → A | C
? ????? A ???????????????????? an
? ??? C ??????????????????????? ??????????? anbn
? ?????????????????????????????????? ak+1 ??? ak+1bk+1 ?????????????????????????
a ????? k+1 ?????????????????????????????????????????????????
??????????? ??????? ?????????? k ?????????????????????????????????
??????? ????????? S → A ???? S → C

16.8 ?????????????????????? LR(k)
? ???????????? LR(k) ????????????????????????????? LR(k) ???????????
????????????? (bottom-up) ????????????????????????? (rightmost
derivation) ????????????????????????????? S (?????????????? LL(k)) ????????
??????????????????? Knuth[1965]

16.8 ?????????????????????? LR(k)
? ??????????????????????????????????? LR(k) ??? ???????????????????????
???????????????? ??????? (handle) ??????????????????????????????????????????
? ?????????????????? A → aCb ?????????????????????????????????????
????????????????????????????????????????
BaAbc BaaCbbc
? ????? ??? ????????????????????????????? ????????? A → aCb ?????????????
??????? BaaCbbc ?????? BaAbc

16.8 ?????????????????????? LR(k)
? ?????????????????????????????????????????? ?????????????????????????
???? ???? ?????????? aCb ?? BaaCbbc ??? 5 ????????????????????????? ??
??????? A → aCb ?????????????????????????
<A → aCb,5>
? ??????????????????????????? ??????? ??? BaaCbbc

16.8 ?????????????????????? LR(k)
? ????? ??????? ??? ??????????? w ??? ?????????
<A → y,p>
? ????? w ?????????????????????? w = xyz , p ????????????? xy ??? z ???
????? ????????????? ???????????????????
xAz xyz

??????????? 16.14 ???????????????????????????????
(bottom-up parsing)
? ???????????????? ??????
?????????????????????
?????????? ???
? E → E+T | T
? T → T*F | F
? F → (E) | a
???????????????? a+a*a ??????????????????
???????????? (?????) ?????????????????????? E
Sentential Form Handle
a+a*a <F → a,1>
F+a*a <T → F,1>
T+a*a <E → T,1>
E+a*a <F → a,3>
E+F*a <T → F,3>
E+T*a <F → a,5>
E+T*F <T → T*F,5>
E+T <E → E+T,3>
E

16.8 ?????????????????????? LR(k)
? ???????????????????????????? LR(k) ?????????????? ???????????????????
???? (rightmost derivation) ?????????????????????? (unique rightmost
derivation) ???????????????????????????????????????????? ??????? ?????
??????????????????????????? (left to right scan) ??????? LR(k) ??????????
???

16.8 ?????????????????????? LR(k)
? L = Left to right scan (????????????????)
? R = Rightmost derivation (????????????????????????)
? k ????????????? k ??????????????? ??????? (up to k symbol past the
handle)
???????????? ???????? LR(0) ??????????????????????????? ????????????????
??????? Knuth[1965] ????????????????? ??? k ???????????????????????????? LR
???????????????????????????? ??? ???? LR(1) ??????????????????????????

16.8 ?????????????????????? LR(k)
? ????? K ≧ 1 ?????
? ???? LR(k) = ???? LR(1)?
= ?????????????????????????

16.9 ???????????????????????????? LR(k)
? ?????????????????????????????????? LR(k) ???????????? LR(1) ?????????
????????????????? ??? LR(1) ????????????????????????????????????????
??????? ????????????????????????? ??? ?????????????????????????????
????????? ?????????????????????? 1 ????????? (one symbol look
ahead)

16.9 ???????????????????????????? LR(k)
? ????????????????????????????????????? ???????????????????????????????????
????? $ ?????????????? ???????????????????????????????????????? ???? ???
????????? abc ???????? abc$ ?????????
? ???????? LR(1) ????????????????????????????? (table-driven algorithm)
????????????????? ???????????????????????????? (???????????, sentential
form) ??????????????????????

??????????? 16.17 ???????????? ????????
LR(1)
? ???????????
S → aCd | bCD
C → cC | c
D → d
? ??????????????????????? ???????????????
aCd,acn+1Cd,acn+1d,bCD,bCd,bcn+1Cd,bcn+1d.

DFA ?????????????????????????????????????????????????
???

??????????? 16.17 ???????????? ????????
LR(1)
? ?????????????????????????? DFA ??????????? LR(1) ??? ???????????????
????????????????????????????????????? LR(1) ??????
? 1. ?????????? DFA ???????????????????????? ???? ??????? (path) ???
bC ???????????????
o b 6 C 7?
?????????????????? ??????????????????????? DFA ??????????????????????
????? 0 ??????????????????????

??????????? 16.17 ???????????? ????????
LR(1)
? 2. ????????? (shift) ????????????????????????? ??????????????? (reduce
handle) (??????????????????????????????????????? “???-????? ??????” shift-
reduce parsing) ?????????????????????????? ???????????????????????
???????? ?????? ????????? ???????????????????????????????? (?????????
????????? ????????????????

16.18 ??????????????? ???-????? ??????
??????????????????? ??????????? ???-????? ?????? ??????????? 16.17 ???

Stack Input Action to Perform
0 bccd$ Shift 6
0 b 6 ccd$ Shift 4
0 b 6 c 4 cd$ Shift 4
0 b 6 c 4 c 4 d$ Reduce by C → c
0 b 6 c 4 C 5 d$ Reduce by C → cC
0 b 6 C 7 d$ Shift 8
0 b 6 C 7 d 8 $ Reduce by D → d
0 b 6 C 5 D 9 $ Reduce by S → bCD
0 S 10 $ Accept
????????????????????????????????????????

狠狠撸

Parsing techniques

Recommended

More Related Content

Viewers also liked (17)

Parsing techniques