ebook14-4

Transcription

1 4 TINY LL(1) First F o l l o w t o p - d o w n 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 A A

2 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

3 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

4 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

5 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

6 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 e x p

7 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

8 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 ; 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

9 LL(1) LL(1) L L ( 1 ) L L ( 1 ) ) S (S) S ( ) S $ S 3 E O F $ 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

10 1 1 4 B N F α $ S ( ) $ S S ( S ) S S ) S ( $ S ) S ( ( ) $ $ S ) S ) $ 4-1 ( ) S ( S ) S [S ( S ) S] ( ) S ( ) [S ] [S ] ( S ) S S 4 S 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

11 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 )

12 1 1 6 i f 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 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$

13 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 $ $ 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...

14 A Aα β α β A β α 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

15 A B a A a c B B b A b d B A = A= B n = 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 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

16 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 ( - ) ;

17 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 ) 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 + -

18 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 αβ α γ 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 α β γ α

19 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 exp t e r m + exp t e r m exp t e r m e x p e x p + exp 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

20 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 ) L L ( 1 ) L L ( 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

21 4 125 value stack m a t c h 2 (#) + E E + n # E E $ E $ E n E $ $E n $ / $ $ E $ E +n# E 3 $ $ E # n $ 3 $ $ E # n $ / 3 $ $ E # + 5 $ 4 3 $ $ E + 5 $ E +n# E 7 $ $ E # n $ 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 ) 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 )

22 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 α A First (A) A A X 1... First (A) First (X 1 ) 4-5 k = 1 while 4-6 First (X 1 ) X 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

23 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 F i r s t 1 First (e x p) First (e x p) 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 } ( 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 } 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

24 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 F i r s t 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

25 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, } 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} 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} stmt-sequence stmt stmt-seq s t m t - s e q ; stmt-sequence

26 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 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 ) = {;, } 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

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

28 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) = {$, +, -, *} 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 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 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, }

29 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 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) = {)} 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 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) = {$}

30 1 3 4 Follow (s t m t) = {;} Follow (s t m t - s e q ) = {$} L L ( 1 ) L L ( 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}

31 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 ) 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 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 ) ) 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 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

32 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 E B N F 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 TreeNode * parse (void); p a r s e p a r s e p a r s e. c B 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 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

33 4 137 s t m t _ s e q u e n c e 3 u t i l. c B u t i l. h B ) n e w S t m t N o d e ) n e w E x p N o d e ) c o p y S t r i n g 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 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 t r a c e P a r s e p r i n t Tr e e T I N Y 4.5

34 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) panic mode synchronizing token scan ahead Wirth [1976]

35 4 139 F o l l o w F o l l o w F i r s t 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

36 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 ( )* 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 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

37 4 141 $ F o l l o w (A) 1 $ F i r s t (A) F o l l o w (A) p o p 2 s c a n p o p L L ( 1 ) ( 2 + *) L L ( 1 ) (2 + E e x p E e x p 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 $ $ T I N Y B T I N Y

38 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 : 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 : 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);

39 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 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 L L ( 1 ) a * 5-6 b. 3 * ( ) c. 3 - ( * 6 ) 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

40 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 ) 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 ) L L ( 1 ) default entry a. L L ( 1 ) b. L L ( 1 )

41 4 145 c. L L ( 1 ) 4.13 L L ( 1 ) 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 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 ) F i r s t F o l l o w 4.20 a 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$ T I N Y T I N Y

42 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 T I N Y w h i l e ( 2 )( 3 ) ( )* L L ( 1 ) L L ( 1 ) ( )* 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 a. / b. % c. ^ d

43 a b. a 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 * 42 (- 34 (* 3 42)) 4.35 a. b. a 4.36 a 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 T I N Y T I N Y 4.40 a 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 T I N Y 4.43 L L ( 1 ) Wirth [1976] C

44 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 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 ) Lewis S t e a r n s

45 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 )