ebook14-4

4 TINY LL(1) First F o l l o w t o p - d o w n 3 3. 3 backtracking parser predictive parser recursive-descent parsing L L ( 1 ) LL(1) parsing L L ( 1 ) L L ( 1 ) 1 L 2 L 1 L L ( k ) k L L ( 1 ) F i r s t F o l l o w T I N Y 4.1 4.1.1 A A

1 0 6 c a s e i f exp exp addop term t e r m addop + - term term mulop factor f a c t o r mulop * factor ( exp ) n u m b e r factor factor p ro c e d u re factor ; b e g i n case token of ( : m a t c h( () ; exp ; m a t c h( ) ) ; number : else e rro r ; end c a s e ; end f a c t o r ; match (n u m b e r) ; t o k e n m a t c h p ro c e d u re match ( e x p e c t e d Token ) ; b e g i n if token = e x p e c t e d Token t h e n g e t Token ; e l s e e rror ; end if ; end match ; m a t c h f a c t o r e rro r match (( ) f a c t o r match (n u m b e r) e x p e c t e d To k e n t o k e n match ()) t o k e n f a c t o r e x p e x p t e r m t e r m f a c t o r f a c t o r e x p f a c t o r E B N F

4 107 4.1.2 E B N F i f if-stmt i f ( exp ) s t a t e m e n t p ro c e d u re ifstmt ; b e g i n match (i f) ; match (() ; exp ; match ( )) ; statement ; i f token = e l s e t h e n m a t c h (e l s e) ; statement ; end if ; end ifstmt ; i f ( exp ) statement e l s e s t a t e m e n t i f e l s e e l s i f E B N F if-stmt if ( exp ) statement [ e l s e statement ] B N F E B N F i f S t m t E B N F E B N F e l s e B N F e x p exp exp addop term t e r m e x p e x e x p t e r m exp exp addop term exp t e r m E B N F exp term { addop term } p ro c e d u re exp ; b e g i n term ; while token = + or token = - do

1 0 8 match (t o k e n) ; term ; end while ; end exp ; t e r m E B N F p ro c e d u re term ; b e g i n factor ; while token = * d o match (t o k e n) ; factor ; end while ; end term ; term factor { mulop factor } addop m u l o p addop + - mulop * e x p t e r m B N F function exp : integer ; var temp : integer ; b e g i n temp := term ; while token = + or token = - do case token o f + : match (+) ; temp := temp + term ; - : match (-) ; temp := temp term ; end case ; end while ; return temp ; end exp ; t e r m 4-1

4 109 C g e t c h a r s c a n f g e t T o k e n 4-1

1 1 0 E B N F 4. 4 T I N Y e x p t e r m t e r m 1 t o k e n t o k e n m a t c h g e t To k e n E B N F 3 + 4 + 5 5 3 4 e x p

4 111 function exp : s y n t a x Tree ; var t e m p, newtemp : s y n t a x Tree ; b e g i n temp := term ; while token = + or token = - d o case token o f + : match (+) ; newtemp := m a k e O p N o d e(+) ; l e f t C h i l d(n e w t e m p) := temp ; r i g h t C h i l d(n e w t e m p) := term ; temp := newtemp ; - : match (-) ; newtemp := m a k e O p N o d e(-) ; l e f t C h i l d(n e w t e m p) := temp ; r i g h t C h i l d(n e w t e m p) := t e r m ; temp := newtemp ; end case ; end while ; return temp ; end exp ; function exp : s y n t a x Tree ; var t e m p, newtemp : s y n t a x Tree ; b e g i n temp := term ; while token = + or token = - d o newtemp := m a k e O p N o d e(t o k e n) ; match (t o k e n) ; l e f t C h i l d(n e w t e m p) := temp ; r i g h t C h i l d(n e w t e m p) := term ; temp := newtemp ; end while ; return temp ; end exp ; m a k e O p N o d e leftchild (t) := p rightchild (t) := p p t e x p e x p e x t e r m t e r m f a c t o r

1 1 2 i f function ifstatement : s y n t a x Tree ; var temp : s y n t a x Tree ; b e g i n match (i f) ; match (() ; temp := m a k e S t m t N o d e(i f) ; t e s t C h i l d(t e m p) := exp ; match ( ) ) ; t h e n C h i l d(t e m p) := statement ; i f token = e l s e t h e n e l s e match (e l s e) ; e l s e C h i l d(t e m p) := statement ; e l s e C h i l d(t e m p) := nil ; end if ; end ifstatement ; 4.1.3 T I N Y C B N F E B N F E B N E B N F B N F A α β... α β A α A β α β F i r s t 4. 3 A A A F o l l o w 4. 3 F i r s t F o l l o w 4-1 ) 3-2 ) e x p t e r m f a c t o r 1 e x p e x p F i r s t

4 113 4.2 LL(1) 4.2.1 LL(1) L L ( 1 ) L L ( 1 ) 3 3. 5 ) S (S) S ( ) 4-1 4 1 2 S $ S 3 E O F 4 4-1 1 $ S ( ) $ S ( S ) S 2 $ S ) S ( ( ) $ 3 $ S ) S ) $ S 4 $ S ) ) $ 5 $ S $ S 6 $ $ $ S t a rt S y m b o l InputString $............ $ $ accept S () B N F 1) A α A 2) 1 g e n e r a t e B N F 2

1 1 4 B N F α 4-1 1 $ S ( ) $ S S ( S ) S S ) S ( $ S ) S ( ( ) $ $ S ) S ) $ 4-1 ( ) S ( S ) S [S ( S ) S] ( ) S ( ) [S ] [S ] 4-1 2 ( S ) S S 4 S 4.2.2 LL(1) A A A L L ( 1 ) (LL(1) parsing table) $ M [N, T ] N T $ M M [N, T ] 1) A α α *aβ a A α M [A, a] 2) A α α S $ βaaγ S a $ A α M [A, a] 1 a α a A α 2 A A α a

4 115 A A α A 2 α= F i r s t F o l l o w 1 (S) 3 $ S S (S)S S M [S, (] 1 S (S) S 2 α= β= (, A = S, a = ) γ = S $ S M [S, )] S $ *S$ S M [S, $] L L ( 1 ) L L ( 1 ) - G L L ( 1 ) L L ( 1 ) (LL(1) grammar) L L ( 1 ) L L ( 1 L L ( 1 ) 4-2 L L ( 1 ) 4-2 e l s e 4-2 L L ( 1 )

1 1 6 i f 3 3. 6 statement if-stmt o t h e r if-stmt if ( exp ) statement else-part e l s e - p a rt e l s e statement exp 0 1 L L ( 1 ) 4-2 ( ) 4-2 i f L L ( 1 ) M [N, T ] i f O t h e r e l s e 0 1 $ s t a t e m e n t s t a t e m e n t s t a t e m e n t i f - s t m t i f - s t m t if-stmt i f ( exp ) s t a t e m e n t e l s e - p a rt o t h e r e l s e - p a rt e l s e - p a rt e l s e - p a rt e l s e s t a t e m e n t e l s e - p a rt e x p Exp 0 exp 1 4-2 M[ e l s e - p a rt, e l s e] e l s e e l s e - p a rt e l s e s t a t e m e n t e l s e - p a rt 4-2 L L ( 1 ) 4-3 L L ( 1 ) if(0) if(1) other else other statement = S if-stmt = I e l s e - p a rt = L exp = E i f = i e l s e = e o t h e r = o ) 4-3 i f L L ( 1 ) $ S i ( 0 ) i ( 1 )oeo $ S I $ I i ( 0 ) i ( 1 )oeo $ I i ( E ) S L $ LS )E (i i(0)i(1)oeo$ $ L S ) E ( ( 0 ) i ( 1 )oeo $ $ L S ) E 0 ) i ( 1 )oeo $ E 0 $ LS )o 0)i(1)oeo$

4 117 $ LS ) )i(1)oeo$ $ LS i(1)oeo$ S I $ LI i(1)oeo$ I i ( E ) S L $ LL S )E (i i(1)oeo$ I i ( E ) S L $ LL S )E (i i(1)oeo$ $ L L S ) E ( ( 1 )oeo$ $ LL S )E 1)oeo$ E 1 $ LL S ) )oeo$ $ LL S oeo$ S o $ LL o oeo$ $ L L eo $ L e S $ LS e eo$ $ L S o $ S o $ L o o $ $ L $ L $ $ 4.2.3 L L ( 1 ) L L ( 1 ) E B N F L L ( 1 ) B N F L L ( 1 ) left recursion removal left factoring L L ( 1 ) E B N F L L ( 1 ) 1) exp exp addop term t e r m a d d o p a d d o p exp exp + term exp - term t e r m immediate left recursion e x p A B b... B A a...

1 1 8 1 A Aα β α β A 3. 2. 3 β α n (n 0 A β A Aα β α A βa A αa 4.1 exp exp addop term t e r m A Aα β A = e x p α = addop term β = t e r m exp term exp e x p addop term exp 2 A Aα 1 Aα 2... Aα n β 1 β 2... β m β 1,..., β m A 4.2 A β 1 A β 2 A... β m A A α 1 A α 2 A... α n A exp exp + term exp - term t e r m exp term exp 3 e x p + term exp - term exp c y c l e A α *A A 1,..., A m A i A i A j γ j i 1 m i 4-3

4 119 4-3 4.3 A B a A a c B B b A b d B A = A= B n = 2 4-3 A 1 i = 1 i = 2 i = 1 j A A B a A c A A a A B B b A b d i = 2 j = 1 A B A b A B a A c A A a A B B b B a A b c A b d B A B a A c A A a A B c A b B d B B b B a A b B 4. 1 4 - exp t e r m e x p e x p a d d o p t e r m e x p a d d o p + - t e r m f a c t o r t e r m A 2 t e r m m u l o p f a c t o r t e r m m u l o p * f a c t o r ( exp ) n u m b e r 4-1

1 2 0 3-4 - 5 3 e x p e x p e x 4-1 e x p e x 5-6 e x p - 6 e x p e x p e x p p ro c e d u re exp ; b e g i n t e r m ; e x p ; end exp ; p ro c e d u re e x p ; b e g i n case t o k e n o f + : match ( + ) ; t e r m ; e x p ; - : match ( - ) ;

4 121 t e r m ; e x p ; end case ; end e x p ; function exp : integer ; var temp : integer ; b e g i n temp := t e r m ; return e x p (t e m p) ; end exp ; function e x p ( valsofar : integer ) : integer ; b e g i n if token = + or token = - t h e n case token of + : match ( + ) ; valsofar := valsofar + t e r m ; - : match ( - ) ; valsofar := valsofar t e r m ; end case ; return e x p (v a l s o f a r) ; else return valsofar ; end e x p ; e x p e x p 4. 1 E B N F 4-1 L L ( 1 ) L L ( 1 ) 4-4 4-4 4-1 L L ( 1 ) M [N, T ] ( n u m b e r ) + - * $ e x p exp exp t e r m e x p term exp e x p e x p e x p e x p e x p a d d o p a d d o p t e r m e x p t e r m e x p a d d o p addop a d d o p + -

1 2 2 M [N, T ] ( n u m b e r ) + - * $ t e r m t e r m t e r m f a c t o r f a c t o r t e r m t e r m t e r m t e r m t e r m t e r m t e r m t e r m m u l o p f a c t o r t e r m m u l o p m u l o p * f a c t o r factor f a c t o r ( exp ) n u m b e r 2) A αβ α γ 3 3. 7 stmt-sequence stmt ; stmt-sequence s t m t stmt s i f if-stmt i f ( exp ) s t a t e m e n t i f ( exp ) statement e l s e s t a t e m e n t L L ( 1 ) α A αa A β γ A α β γ α 4-4 4-4

4 123 4.4 stmt-sequence stmt ; stmt-sequence s t m t stmt s s t m t - s e q u e n c e stmt-sequence stmt stmt-seq s t m t - s e q ; s t m t - s e q u e c n e s t m t - s e q u e n c e stmt-sequence stmt-sequence ; stmt s t m t stmt-sequence stmt stmt -s e q s t m t - s e q ; stmt stmt-seq stmt stmt-seq s t m t- s e q u e n c e 4.5 i f if-stmt i f ( exp ) s t a t e m e n t i f ( exp ) statement e l s e s t a t e m e n t if-stmt i f ( exp ) statement else-part e l s e - p a rt e l s e statement 4. 2. 2 4-4.6 + exp t e r m + exp t e r m exp t e r m e x p e x p + exp 4. 4 2 e x p t e r m e x p exp t e r m e x p e x p + t e r m e x p

1 2 4 + 4.7 L L ( 1 ) statement assign-stmt call-stmt o t h e r assign-stmt i d e n t i f i e r := e x p call-stmt identifier ( e x p-list ) i d e n t i f i e r assign-stmt call-stmt 1 L L ( 1 ) i d e n t i f i e r assign-stmt call-stmt statement i d e n t i f i e r := e x p i d e n t i f i e r ( e x p-l i s t ) o t h e r statement identifier s t a t e m e n t o t h e r s t a t e m e n t : = exp ( e x p - l i s t ) s t a t e m e n t L L ( 1 ) L L ( 1 ) L L ( 1 ) 4.2.4 L L ( 1 ) L L ( 1 ) 4. 2. 1 L L ( 1 ) L L ( 1 ) 4.8 B N F E E + n n L L ( 1 ) E n E E + n E

4 125 value stack 1 2 1 m a t c h 2 (#) + E E + n # E E 3 + 4 + 5 4-5 4-5 4. 8 $ E 3 + 4 + 5$ E n E $ $E n 3 + 4 + 5$ / $ $ E + 4 + 5$ E +n# E 3 $ $ E # n + + 4 + 5$ 3 $ $ E # n 4 + 5 $ / 3 $ $ E # + 5 $ 4 3 $ $ E + 5 $ E +n# E 7 $ $ E # n + + 5 $ 7 $ $ E # n 5 $ / 7 $ $ E # $ 5 7 $ $ E $ E e 12 $ $ $ 12 $ 4.3 First F o l l o w L L ( 1 ) L L ( 1 ) F i r s t F o l l o w L L ( 1 ) 4.3.1 First X First (X) 1. X First (X) = {X} 2. X X X 1 X 2... X n First (X) F i r s t (X 1 ) { } i < n First (X 1 ),..., First (X i )

1 2 6 First (X) First (X i + 1 ) { } First (X 1 ),..., First (X n ) First (X) α = X 1 X 2... X n First ( ) First (α) First (X 1 ) - { } i = 2,..., n k = 1,..., i 1 First (X k ) First (α) First (X i ) { } i =1,..., n First (X i ) First (α) A F i r s t (A) First α First n F i r s t n α 4-5 4-5 A First (A) A A X 1... First (A) First (X 1 ) 4-5 k = 1 while 4-6 First (X 1 ) X 2 1 4-6 4-5 A * n u l l a b l e First (A) A A First (A) A A First (A) First ( ) ={ } < n A X 1... X k * n A X 1... X k

4 127 X i X i X i * n i First (X i ) First (A) F i r s t 4.9 exp exp addop t e r m t e r m a d d o p + - t e r m t e r m m u l o p f a c t o r f a c t o r m u l o p * f a c t o r ( exp ) n u m b e r (1) exp exp addop t e r m (2) exp t e r m (3) a d d o p + (4) a d d o p - (5) t e r m t e r m m u l o p f a c t o r (6) t e r m f a c t o r (7) m u l o p * (8) f a c t o r ( exp ) (9) f a c t o r n u m b e r 4-6 1 5 F i r s t 1 First (e x p) First (e x p) 4-6 1 2 First (t e r m) First (e x p) First (t e r m) 3 4 First (a d d o p) + - First (a d d o p) = {+,-} 5 6 First (f a c t o r) First (t e r m) First (f a c t o r) 7 First (m u l o p) * First (m u l o p) = {*} 8 ( First (f a c t o r) 9 n u m b e r First (f a c t o r) First (f a c t o r) = { (, n u m b e r } 1 1 5 ( F i r s t (t e r m) 6 First (f a c t o r) First (t e r m) First (f a c t o r) = {(,n u m b e r } First (t e r m) = {(,n u m b e r } 8 9 1 2 First (t e r m) First (e x p) First (e x p) = {(,n u m b e r } 4 L L ( 1 ) L L ( 1 ) F i r s t F i r s t

1 2 8 F i r s t First (e x p) = {(, n u m b e r } First (t e r m) = {(, n u m b e r } First (f a c t o r) = {(, n u m b e r } First (a d d o p) = { +, - } First (m u l o p) = {*} f a c t o r 4 2 4-6 4-6 4. 9 F i r s t 1 2 3 exp exp a d d o pt e r m e x p t e r m First (e x p) = {(, n u m b e r} a d d o p + First (a d d o p) = {+} a d d o p - First (a d d o p) = {+, -} t e r m t e r m m u l o p f a c t o r t e r m f a c t o r F i r s t (t e r m) = {(, n u m b e r} m u l o p * First (m u l o p) = {*} f a c t o r ( e x p ) First (f a c t o r) = {(} f a c t o r n u m b e r First (f a c t o r) = {(, n u m b e r} 4.10 i f 4. 5 statement if-stmt o t h e r if-stmt i f ( e x p ) statement else-part e l s e - p a rt e l s e statement e x p 0 1 e l s e - p a rt First

4 129 (1) statement i f - s t m t (2) s t a t e m e n t o t h e r (3) if-stmt i f ( e x p ) statement else-part (4) e l s e - p a rt e l s e s t a t e m e n t (5) e l s e - p a rt (6) e x p 0 (7) e x p 1 First First (i f - s t m t) 1 2 o t h e r First (i f - s t m t) First (s t a t e m e n t) = {o t h e r} 3 i f First (i f - s t m t) First (i f - s t m t) = {i f} 4 First (e l s e - p a rt) e l s e First (e l s e - p a rt) = {e l s e} 5 First (e l s e - p a rt) First (e l s e - p a rt) = {e l s e, } 6 7 0 1 First (e x p) First (e x p) = {0, 1} 1 First (i f - s t m t) i f i First (s t a t e m e n t) F i r s t (s t a t e m e n t) = {i f,o t h e r} 2 3 F i r s t First (s t a t e m e n t) = {i f, o t h e r} First (i f - s t m t) = {i f} First (e l s e - p a rt) = {e l s e, } First (e x p) = {0, 1} 4-7 4-6 4-7 4. 10 F i r s t 1 2 statement i f - s t m t First (s t a t e m e n t) = {i f, o t h e r} statement o t h e r First ( s t a t e m e n t) = {o t h e r} if-stmt i f ( e x p ) First ( i f - s t m t) = statement else-part {i f} e l s e - p a rt e l s e First ( e l s e - p a rt) = statement {e l s e} e l s e - p a rt First ( e l s e - p a rt) = {e l s e, } exp 0 First ( e x p) = {0} e x p 1 First (e x p) = {0, 1} 4. 11 4. 4 stmt-sequence stmt stmt-seq s t m t - s e q ; stmt-sequence

1 3 0 s t m t s (1) stmt-sequence stmt stmt-seq (2) s t m t - s e q ; s t m t - s e q u e n c e (3) s t m t - s e q (4) stmt s 1 1 2 3 First (s t m t - s e q ) = {;, } 4 First (s t m t) = {s} 2 1 First (s t m t - s e q u e n c e) = First (s t m t) = {s} 3 F i r s t First (s t m t - e w q u e n c e) = {s} First (s t m t) = {s} First (s t m t - s e q ) = {;, } 4-6 4-7 4.3.2 Follow A F o l l o w (A) $ F o l l o w (A) 1. A $ F o l l o w (A) 2. B αaγ First (γ) - { } F o l l o w (A) 3. B αaγ F i r s t (γ) F o l l o w (A) F o l l o w (B) F o l l o w $ F o l l o w $ F o l l o w F o l l o w F o l l o w F i r s t F o l l o w $ E O F F o l l o w First F o l l o w L L ( 1 ) F o l l o w F o l l o w F i r s t α A A α A F o l l o w A Follow (A) Follow First First A αb Follow (B) ( 3 ) Follow (A) A αb

4 131 First A Bα First (A) First (B) 4-7 F o l l o w F o l l o w 3 F o l l o w 3 First F i r s t 4-7 F o l l o w 4.12 4. 9 F i r s t First (e x p) = {(, n u m b e r } First (t e r m) = {(, n u m b e r } First (f a c t o r) = {(, n u m b e r } First (a d d o p) = { +, - } First (m u l o p) = {*} (1) e x p e x p a d d o p t e r m (2) e x p t e r m (3) a d d o p + (4) a d d o p - (5) t e r m t e r m m u l o p f a c t o r (6) t e r m f a c t o r (7) m u l o p * (8) f a c t o r ( e x p ) (9) f a c t o r n u m b e r 3 4 7 9 F o l l o w Follow (e x p) = {$} F o l l o w 1 3 F o l l o w e x p a d d o p t e r m First (a d d o p) F o l l o w (e x p) Follow (e x p) = {$, +, -} First (t e r m) Follow (a d d o p) Follow (a d d o p) = {(, n u m b e r} Follow (e x p) Follow ( t e r m) F o l l o w (t e r m) = {$, +, -} 2 Follow (e x p) Follow (t e r m) 1 F o l l o w

1 3 2 5 3 First (m u l o p) Follow (t e r m) Follow (t e r m) = {$, +, -, *} First (f a c t o r) Follow (m u l o p) Follow (m u l o p) = {(, n u m b e r} Follow (t e r m) Follow (f a c t o r) Follow (f a c t o r) = {$, +, -, *} 6 5 8 F i r s t ( ) ) = {)} Follow (e x p) Follow (e x p) = {$, +, -, )} 2 1 ) Follow (t e r m) ( Follow (t e r m) = {$, +, -, *, )}) 5 Follow (f a c t o r) ( Follow (f a c t o r) = {$, +, -, *, )}) 3 F o l l o w Follow (e x p) = {$, +, -, )} Follow (a d d o p) = {(, n u m b e r} Follow (t e r m) = {$, +, -, *,)} Follow (m u l o p) = {(,n u m b e r} Follow (f a c t o r) = {$, +, -, *, )} F i r s t 4-8 F o l l o w 4 e x p t e r m t e r m f a c t o r 4-8 4. 12 F o l l o w 1 2 e x p e x p a d d o p Follow ( e x p) = Follow (t e r m) = t e r m {$, +, -} {$, +, -, *, )} Follow ( a d d o p) = {(, n u m b e r} Follow ( t e r m) = {$, +, -} e x p t e r m t e r m t e r m m u l o p Follow ( t e r m) = Follow ( f a c t o r) = f a c t o r {$, +, -, *} {$, +, -, *, )} Follow ( m u l o p) = {(, n u m b e r} Follow ( f a c t o r) = {$, +, -, *} t e r m f a c t o r factor ( e x p ) Follow (e x p) = {$, +, -, )} 4.13 i f 4. 10 F i r s t First (s t a t e m e n t) = {i f, o t h e r} First (i f - s t m t) = {i f} First (e l s e - p a rt) = {e l s e, }

4 133 First (e x p) = {0, 1} (1) statement i f - s t m t (2) statement o t h e r (3) if-stmt i f ( e x p ) statement else-part (4) e l s e - p a rt e l s e s t a t e m e n t (5) e l s e - p a rt (6) e x p 0 (7) e x p 1 2 5 6 7 F o l l o w Follow (s t a t e m e n t) = {$} F o l l o w 1 Follow (s t a t e m e n t) Follow (i f - s t m t) Follow (i f - s t m t) = {$} 3 e x p s t a t e m e n t e l s e - p a rt F o l l o w Follow (e x p) First ()) = {)} Follow (e x p) = {)} Follow (s t a t e m e n t) First (e l s e - p a rt) - { } Follow (s t a t e m e n t) = {$, e l s e} Follow (i f - s t m t) Follow (e l s e - p a rt) Follow (s t a t e m e n t) i f - s t m t 1 Follow (e l s e - p a rt) = {$} 2 4 F o l l o w (e l s e - p a rt) Follow (s t a t e m e n t) 2 1 Follow (s t a t e m e n t) Follow (i f - s t m t) Follow (i f - s t m t) = {$, e l s e} 3 e l s e Follow (e l s e - p a rt) Follow (e l s e - p a rt) = {$, e l s e} 4 3 F o l l o w Follow (s t a t e m e n t) = {$, e l s e} Follow (i f - s t m t) = {$, e l s e} Follow (e l s e - p a rt) = {$, e l s e} Follow (e x p) = {)} 4.14 4. 11 F o l l o w (1) stmt-sequence stmt stmt-seq (2) s t m t - s e q ; s t m t - s e q u e n c e (3) s t m t - s e q (4) stmt s 4. 11 F i r s t First (s t m t - e w q u e n c e) = {s} First (s t m t) = {s} First (s t m t - s e q ) = {;, } 3 4 F o l l o w Follow ( s t m t - s e q u e n c e) = {$} F o l l o w 1 Follow (s t m t) = {;} Follow (s t m t - s e q ) = {$} 2 F o l l o w Follow (s t m t - e e q u e n c e) = {$}

1 3 4 Follow (s t m t) = {;} Follow (s t m t - s e q ) = {$} 4.3.3 L L ( 1 ) L L ( 1 ) 4. 2. 2 1) A α α αβ α A α M [A, a] 2) A S$ Aa β S a $ A M [A, a] 1 a First (α) 2 a Follow (A) LL(1) LL(1) M[N, T] A A α 1) First (α) a A α M [A, a] 2) First (α) Follow (A) a $ A α M [A, a] L L ( 1 ) 4.15 B N F L L(1) LL(1) grammar 1. A α 1 α 2... α n i j 1 i j n i j First (α i ) First (α j ) 2. A First (A) First (A) Follow ( A) 4. 9 e x p t e r m e x p e x p a d d o p t e r m e x p a d d o p + - t e r m f a c t o r t e r m t e r m m u l o p f a c t o r t e r m m u l o p * f a c t o r ( e x p ) n u m b e r F i r s t F o l l o w First (e x p) = {(, n u m b e r} Follow (e x p) = {$, )} First (e x p ) = {+, -, } Follow (e x p ) = {$, )} First (a d d o p) = {+, -} Follow (a d d o p) = {(, n u m b e r} First (t e r m) = {(, n u m b e r} Follow (t e r m) = {$, ), +, -} First (t e r m ) = {*, } Follow (t e r m ) = {$, ), +, -} First (m u l o p) = {*} Follow (m u l o p) = {(, n u m b e r}

4 135 First (f a c t o r) = {(, n u m b e r} Follow (f a c t o r) = {$, ), +, -, *} L L ( 1 ) 4-4 4.16 if s t a t e m e n t i f - s t m t o t h e r i f - s t m t i f ( e x p ) s t a t e m e n t e l s e - p a rt e l s e - p a rt e l s e s t a t e m e n t e x p 0 1 F i r s t F o l l o w 4. 10 4. 13 First (s t a t e m e n t) = {i f, o t h e r} Follow (s t a t e m e n t) = {$, e l s e} First (i f - s t m t) = {i f} Follow (i f - s t m t) = {$, e l s e} First (e l s e - p a rt) = {e l s e, } Follow (e l s e - p a rt) = {$, e l s e} First (e x p) = {0, 1} Follow (e x p) = {)} L L ( 1 ) 4-3 4.17 4. 4 ) s t m t - s e q u e n c e s t m t s t m t - s e q s t m t - s e q ; s t m t - s e q u e n c e s t m t s F i r s t F o l l o w First (s t m t - e w q u e n c e) = {s} Follow (s t m t - e e q u e n c e) = {$} First (s t m t) = {s} Follow (s t m t) = {;, $} First (s t m t - s e q ) = {;, } Follow (s t m t - s e q ) = {$} L L ( 1 ) M [N, T ] s ; $ s t m t - s e q u e n c e s t m t - s e q u e n c e s t m t s t m t - s e q s t m t s t m t s s t m t - s e q s t m t - s e q s t m t - s e q ; s t m t - s e q u e n c e 4.3.4 L L ( k ) k F i r s t k (α) = { w k α * w } w = w k w k w w k F o l l o w k (A) = { w k S$ * αaw} k = 1 L L (k) L L( k) k L L( k) F o l l o w

1 3 6 L L( k) L L( k) L L( k) (Strong LL( k) p a r s i n g ) S L L( k) S L L( k) parsing L L( k) S L L( k) k L L ( 1 ) L L( k) k L L( k) k L L( k) 4.4 TINY B T I N Y 3. 7 4-8 E B N F 3 3-1 4-8 EBNF T I N Y T I N Y 4. 1 p a r s e. h p a r s e. c p a r s e. h B 850 865 TreeNode * parse (void); p a r s e p a r s e p a r s e. c B 900 1114 11 4-8 E B N F s t m t - s e q u e n c e s t a t e m e n t 5 5 4 p ro g r a m p a r s e s t m t _ s e q u e n c e t o k e n m a t c h g e t T o k e n s y n t a x E r r o r p a r s e t o k e n 1 s t m t _ s e q u e n c e s t m t _ s e q u e n c e s t m t _ s e q u e n c e

4 137 s t m t _ s e q u e n c e 3 u t i l. c B 350 526 u t i l. h B 300 335 1) n e w S t m t N o d e 405 421 2) n e w E x p N o d e 423 440 3) c o p y S t r i n g 442 455 C c o p y S t r i n g u t i l. c p r i n t T r e e 473 506 u t i l. c t r a c e P a r s e p r i n t T r e e T I N Y 3 3-3 3-6 t r a c e P a r s e 4-9 4-9 p r i n t Tr e e T I N Y 4.5

1 3 8 r e c o g n i z e r 1 error correction error repair minimal distance error correction 1) 2) 3) error cascade problem 4) 4.5.1 panic mode synchronizing token scan ahead Wirth [1976]

4 139 F o l l o w F o l l o w F i r s t 4. 1. 2 4-1 m a t c h e rro r c h e c k i n p u t s c a n t o p ro c e d u re scanto ( synchset ) ; b e g i n while not ( token i n synchset { $ }) d o g e t Token ; end scanto ; p ro c e d u re checkinput ( f i r s t s e t, followset ) ; b e g i n if not ( token i n firstset ) t h e n e rror ; scanto ( firstset followset ) ; end if ; e n d ; $ E O F e x p f a c t o r s y n c h s e t p ro c e d u re e x p ( synchset ) ; b e g i n checkinput ( { (, n u m b e r }, synchset ) ; if not ( token i n synchset ) t h e n t e r m ( synchset ) ; while token = + or token = - d o match (t o k e n) ; t e r m ( synchset ) ; end while ; checkinput ( s y n c h s e t, { (, n u m b e r }) ; end if; end e x p ; p ro c e d u re f a c t o r ( synchset ) ; b e g i n checkinput ( {(, n u m b e r}, synchset ) ; if not ( token in synchset ) t h e n

1 4 0 case token of ( : match (() ; e x p ( { ) } ) ; m a t c h()) ; n u m b e r : m a t c h (n u m b e r) ; else e rror ; end case ; checkinput ( s y n c h s e t, { (, n u m b e r }) ; end if ; end f a c t o r ; c h e c k i n p u t First F o l l o w s y n c h s e t checkinput e rror ( 2 + - 3 )* 4 - + 5 1 2 s y n c h s e t f a c t o r F o l l o w e x p s y n c h s e t ( 2 + *) C 4.5.2 L L ( 1 ) L L ( 1 ) s y n c h s e t c h e c k i n p u t A F i r s t (A) F i r s t (A) First ) 4-2 c h e c k i n p u t L L ( 1 ) A F i r s t (A) F i r s t (A) First ) 3 1) A 2) 3) c h e c k i n p u t 4. 2. 4

4 141 $ F o l l o w (A) 1 $ F i r s t (A) F o l l o w (A) 2 3 1 p o p 2 s c a n p o p L L ( 1 ) 4-4 4-9 ( 2 + *) L L ( 1 ) 4-10 1 (2 + E e x p E e x p 2 1 4-9 L L ( 1 ) 4-4 M [N, T ] ( n u m b e r ) + - * $ e x p e x p e x p p o p s c a n s c a n s c a n p o p t e r m e x p t e r m e x p e x p s c a n s c a n e x p e x p e x p a d d o p a d d o p s c a n e x p t e r m e x p t e r m e x p a d d o p p o p p o p s c a n a d d o p a d d o p s c a n p o p + - t e r m t e r m t e r m f a c t o r f a c t o r p o p p o p p o p s c a n p o p t e r m t e r m t e r m s c a n s c a n t e r m t e r m t e r m t e r m t e r m m u l o p f a c t o r t e r m m u l o p p o p p o p s c a n s c a n s c a n m u l o p * p o p f a c t o r f a c t o r f a c t o r p o p p o p p o p p o p p o p ( e x p ) n u m b e r 4-10 LL(1) 4-9 $ E T ) E T *)$ $ E T ) E T )$ $ E T ) E )$ E $ E T ) )$ $ E T $ T $ E $ E $ $ 4.5.3 T I N Y B T I N Y

1 4 2 m a t c h s t a t e m e n t f a c t o r p a r s e w r i t e... 5: read x ; 6: if 0 < x then 7: fact := 1; 8: repeat 9: fact := fact * x; 10: x := x - 1 11: until x = 0 ; 12: write fact ; {<- - BAD SEMICOLON! } 13: end 14 : Syntax error at line 13: unexpected token -> reserved word: end Syntax error at line 14: unexpected token -> EOF 2 <... 5: read x ; 6: if 0 x then { <- - COMPARISON MISSING HERE! } 7: fact := 1; 8: repeat 9: fact := fact * x; 10: x := x - 1 11: until x = 0 ; 12: write fact ; 13: end 14 : 4 Syntax error at line 6 : unexpected token -> ID, name = x Syntax error at line 6 : unexpected token -> reserved word: then Syntax error at line 6 : unexpected token -> reserved word: then Syntax error at line 7 : unexpected token -> ID, name = fact T I N Y 1 m a t c h 2 s t m t _ s e q u e n c e E B N F s t a t e m e n t (); while (token==semi) { match(semi);

4 143 } s t a t e m e n t ( ) ; s t m t _ s e q u e n c e statement() ; while ((token!= ENDFILE) && (token!= END) && (token!= ELSE) && (token!= UNTIL)) { match(semi); s t a t e m e n t (); } 4 s t m t_s e q u e n c e F o l l o w F i r s t s t a t e m e n t f a c t o r F o l l o w F i r s t 1 s t m t _ s e q u e n c e m a t c h s t a t e m e n t f a c t o r 4.1 4. 1. 2 e x p t e r m f a c t o r 4.2 A (A) A 4.3 s t a t e m e n t assign-stmt c a l l - s t m t o t h e r a s s i g n - s t m t identifier := e x p c a l l - s t m t identifier ( e x p - l i s t ) 4.4 lexp n u m b e r ( op lexp -seq ) op + - * lexp -seq lexp -seq lexp lexp e x p 3 3. 1 4.5 4-4 L L ( 1 ) a. 3 + 4 * 5-6 b. 3 * ( 4-5 + 6 ) c. 3 - ( 4 + 5 * 6 ) 4.6 4. 2. 2 1 L L ( 1 ) a. ( ( ) ) ( ) b. ( ( ) ( ) ) c. ( ) ( ( ) ) 4.7 A (A)A a. A F i r s t F o l l o w b. L L ( 1 ) 4.8

1 4 4 a. lexp a t o m l i s t a t o m n u m b e r i d e n t i f i e r l i s t ( lexp -s e q ) lexp -s e q lexp -s e q lexp lexp b. F i r s t F o l l o w c. L L ( 1 ) d. L L ( 1 ) e. (a (b (2)) (c)) L L ( 1 ) 4.9 4. 8 lexp atom l i s t atom n u m b e r i d e n t i f i e r list ( lexp - seq ) lexp -seq lexp, lexp -seq lexp a. b. F i r s t F o l l o w c. L L ( 1 ) d. L L ( 1 ) e. (a, (b, (2)), (c)) L L ( 1 ) 4.10 C declaration type var- l i s t type i n t f l o a t v a r-list i d e n t i f i e r, v a r-list i d e n t i f i e r a. b. F i r s t F o l l o w c. L L ( 1 ) d. L L ( 1 ) e. int x,y,z L L ( 1 ) 4. 11 4-4 L L ( 1 ) default entry 4-4 4.12 a. L L ( 1 ) b. L L ( 1 )

4 145 c. L L ( 1 ) 4.13 L L ( 1 ) 4.14 4. 3. 3 F i r s t F o l l o w 4.15 S 1 S 2 S 1 S 2 = { First (x y) x S 1, y S 2 } a. A B F i r s t (A B) = First (A) F i r s t (B) b. 4. 3. 3 A α A β (First (α) F o l l o w (A) ) ( F i r s t (β) F o l l o w (A)) 4.16 A a. b. c. F i r s t F o l l o w L L ( 1 ) 4.17 4.18 4. 3. 3 4. 1 6 4.19 4. 15 F i r s t F o l l o w 4.20 a. 4. 7 F i r s t F o l l o w b. ( a ) L L ( 1 ) 4.21 A a A a ε a. L L ( 1 ) b. p ro c e d u re A ; b e g i n if token = a t h e n g e t Token ; A ; if token = a then g e t Token ; else e rror ; else if token < > $ then e rror ; end A ; c. b a c k t r a c k i n g u n G e t t o k e n A A a A a A (b) a a a a$ 4.22 4-8 T I N Y T I N Y

1 4 6 if 0 then write 1>0 else x := (x<1)+1 end T I N Y i f r e p e a t w r i t e a s s i g n 4.23 a n d o r n o t 4-8 T I N Y 3. 5 4.24 4. 23 T I N Y 4. 22 4. 23 4. 22 4.25 4. 5. 1 w h i l e ( 2 )( 3 ) 2 4.26 4-9 ( 2 + - 3 )* 4 - + 5 L L ( 1 ) 4.27 4-2 L L ( 1 ) ( 2 + - 3 )* 4 - + 5 4.28 a. T I N Y s t m t _ s e q u e n c e T I N Y ) x := 2 y := x + 2 b. x 2 y := x + 2 c. s t m t _ s e q u e n c e s t a t e m e n t (); w h i l e ( t o k en ==S E M I ) { match(semi); s t a t e m e n t (); } s t m t _ s e q u e n c e a b 4.29 4-1 a. / b. % c. ^ d. - 3. 12 4.30 4-1 4.31 4-1

4 147 4.32 a. 4-1 3. 3. 2 b. a 4.33 4-1 4-4.34 lexp n u m b e r ( o p lexp -s e q ) o p + - * lexp -seq lexp -s e q lexp lexp L I S P 3 4-3 * 42 (- 34 (* 3 42)) 4.35 a. b. a 4.36 a. 3. 4 N FA T h o m p s o n 2 b. N FA a D FA c. ( b ) D FA g r e p 4.37 < = > = < > T I N Y 4.38 4. 22 T I N Y 4.39 4. 23 T I N Y 4.40 a. 4-1 4. 5. b. a 4.41 T I N Y m a t c h m a t c h m a t c h s y n t a x E r r o r s y n t a x E r r o r m a t c h 4.42 4. 5. 1 T I N Y 4.43 L L ( 1 ) Wirth [1976] C

1 4 8 typedef struct rulerec { struct rulerec *next, *other; int istoken; u n i o n { Token name ; struct rulerec *rule ; } attr ; } Rulerec ; n e x t o t h e r f a c t o r ( e x p ) n u m b e r e x p a. 4-1 b. c. B N F 20 60 A l g o 160 [ N a u r, 1963] B N F H o a r e [ 1962 ] H a s k e l l M i r a n d a Peyton Jones Lester [1992] Hutton [1992] Wirth [1976] E B N F L L ( 1 ) 20 60 70 Lewis S t e a r n s

4 149 [ 1968 ] Fischer LeBlanc [1991] L L ( k ) S L L ( 2 ) L L ( 2 ) P a r r D i e t z Cohen [1992] L L ( k ) G r a h a m H a r r i s o n Ruzzo [1980] Wirth [1976] Stirling [1985] L L ( k ) Burke Fisher [1987] Fischer and LeBlanc [1991] Lyon [1974] 5 Ya c c A n t l r Purdue Compiler Construction Tool Set(PCCTS) P a r r D i e t z a n d Cohen [1992] A n t l r E B N F Fischer LeBlanc [1991] L L G e n L L ( 1 )