( ) ( ) lex LL(1) LL(1)

Size: px

Start display at page:

Download "( ) ( ) lex LL(1) LL(1)"

なおいりぐら
4 years ago
Views:

1 () () lex LL(1) LL(1)

2 1 () / (front end) (back end) (phase) (pass) 1 2

3 1 () () var left, right; fun int main() { left = 0; right = 10; return ((left + right) / 2); } VAR ID:left, ID:right ; FUN INT ID:main ( ) { ID:left = NUM:0 ; ID:right = NUM:10 ; RETURN ( ( ID:left + ID:right ) / NUM:2 ) ; } / PROG VAR SEQ SEQ FUN left SEQ INT main SEQ right = SEQ left 0 = SEQ right 10 RET / + 2 left right 3

4 1 () () = val / * m + + n 1 n 1 tmp1 = n + 1 tmp2 = n + 1 tmp3 = tmp1 * tmp2 val = tmp3 / m tmp1 = n + 1 tmp3 = tmp1 * tmp1 val = tmp3 / m LD R1 n ADD R1 1 ST tmp1 R1 LD R1 tmp1 MUL R1 tmp1 ST tmp3 R1 LD R1 tmp3 DIV R1 m ST val R1 4

5 2 () Σ ϵ a Σ a R S (R S) (R S) (R ) < < ϵ { } a { a } R S L R L S R S { xy x L R, y L S } R { x 1 x 2 x n n 0, x 1, x 2,..., x n L R } ( 0 ) xy x y R S L R L S 2 2 { 0, 1 } ::= 0 1 ( 0 1 ) I 2 J. R. J J. E. F

6 2 () 1 () (Q, Σ, δ, q 0, F ) Q Σ δ q a δ(q, a) q 0 q 0 Q F F Q 2 a,b,0,1,% a,b A B 0,1,% % C a,b,0,1 Q = { A, B, C } Σ = { a, b, 0, 1, % } δ q 0 = A F = { B } δ a b 0 1 % A B B C C C B B B B B C C C C C C C 1 () ab1 A, B, B, B B b0%a A, B, B, C, C C I 2 J. R. J

7 2 () () () 0 1 ( 0 1 ) () B 0 C A E 1 F G H I 0 J M 1 N K L D () 0, 1 0, 1 { C, D } { } 0 { A, B, E } { F, G, H, I, M, L, D } 1 { J, K, H, I, M, L, D } { N, K, H, I, M, L, D } 0 1 () 0 0, 1 1 0, 1 0, 1 7

8 2 () lex lex lex lex /* * cprime.l -- CPrime flex * * flex cprime.l && gcc lex.yy.c -lfl &&./a.out < input.txt */ %% var printf("var "); fun printf("fun "); void printf("void "); int printf("int "); if printf("if "); else printf("else "); while printf("while "); return printf("return "); "==" printf("eq "); "!=" printf("neq "); "<=" printf("leq "); ">=" printf("geq "); [+\-*/%<>=(){},;] printf("%c ", *yytext); [0-9]+ printf("num:%s ", yytext); [_a-za-z][_a-za-z0-9]* printf("id:%s ", yytext); [ \t\n]+ /* */. printf("??? "); /* */ %% int main(void) { yylex(); printf("\n"); return 0; } if else while return var fun void int + - * / % > >= < <= ==!= = ( ) { }, ; 123 var x; fun void main() { x = 5; } IF ELSE WHILE RETURN VAR FUN VOID INT + - * / % > GEQ < LEQ EQ NEQ = ( ) { }, ; NUM:123 ID:value??? VAR ID:x ; FUN VOID ID:main ( ) { ID:x = NUM:5 ; } 8

9 3 () (context-free grammar) (V, T, P, S) V (variable)() T (terminal symbol) P (production rule) A α A V, α (V T ) S (start symbol)s V V T α 0 () ID NUM 1 : E ( E + E ) 5 : E ID 2 : E ( E - E ) 6 : E NUM 3 : E ( E * E ) 4 : E ( E / E ) V = { E } T = { (, ), +, -, *, /, ID, NUM } P 6 E E ( E + E ) ( E - E ) ( E * E ) ( E / E ) ID NUM () E ( E + E ) ( ( E * E ) + E ) ( ( NUM * E ) + E ) ( ( NUM * ID ) + E ) ( ( NUM * ID ) + NUM ) 1, 3, 6, 5, 6 { w T S w } 9

10 CPrime () C var ; fun ( ) { } void int ID ( ) ; ID = ; if ( ) else if ( ) while ( ) { } return ; return ; NUM ( ) ID ( ) ID ==!= > < >= <= + - * / % ID, ID, I 2 J. R. J

11 3 () 1 : E ( E + E ) 5 : E ID 2 : E ( E - E ) 6 : E NUM 3 : E ( E * E ) 4 : E ( E / E ) E ( E / E ) 4 ( ( E + E ) / E ) 1 ( ( ID + E ) / E ) 5 ( ( ID + ID ) / E ) 5 ( ( ID + ID ) / NUM ) 6 E ( E / E ) 4 ( E / NUM ) 6 ( ( E + E ) / NUM ) 1 ( ( E + ID ) / NUM ) 5 ( ( ID + ID ) / NUM ) 5 E E E E E ( ( ID + ID ) / NUM ) 1 : E E + E 6 : E ID 2 : E E - E 7 : E NUM 3 : E E * E 4 : E E / E 5 : E ( E ) E E E E E E E E E E E E E E E E ( ID + ID ) / NUM ID + ID / NUM ID + ID / NUM 11

12 4 () () 1 1 () 1 : exp exp && exp 2 : exp! exp 3 : exp VAR 4 : exp CON exp! exp! exp && exp! VAR && exp exp! exp exp && exp! VAR && CON VAR CON () exp exp exp exp exp! exp! exp! exp! exp exp && exp exp && exp exp && exp VAR VAR CON 12

13 4 () () 1 1 () 1 : exp exp && exp 2 : exp! exp 3 : exp VAR 4 : exp CON exp exp && exp exp && CON! exp && CON! VAR && CON exp exp && exp! exp CON VAR exp exp exp exp exp && exp exp! exp! exp CON! exp CON () VAR VAR VAR VAR 13

14 4 () () exp! exp exp && exp ( ( exp!, exp exp ( VAR ) ) ), &&, exp( CON ) VAR CON def traverse( T ) visit( T ) n = T for i = 1 to n traverse( T i ) traverse( exp(!, exp( exp( VAR ), &&, exp( CON ) ) ) ) visit( exp ) 1 exp traverse(! ) visit(! ) 2! traverse( exp( exp( VAR ), &&, exp( CON ) ) ) visit( exp ) 3 exp traverse( exp( VAR ) ) visit( exp ) 4 exp traverse( VAR ) visit( VAR ) 5 VAR traverse( && ) visit( && ) 6 && traverse( exp( CON ) ) visit( exp ) 7 exp traverse( CON ) visit( CON ) 8 CON 14

15 4 () () exp! exp exp && exp ( ( exp!, exp exp ( VAR ) ) ), &&, exp( CON ) VAR CON def traverse( T ) n = T for i = 1 to n traverse( T i ) visit( T ) traverse( exp(!, exp( exp( VAR ), &&, exp( CON ) ) ) ) traverse(! ) visit(! ) 1! traverse( exp( exp( VAR ), &&, exp( CON ) ) ) traverse( exp( VAR ) ) traverse( VAR ) visit( VAR ) 2 VAR visit( exp ) 3 exp traverse( && ) visit( && ) 4 && traverse( exp( CON ) ) traverse( CON ) visit( CON ) 5 CON visit( exp ) 6 exp visit( exp ) 7 exp visit( exp ) 8 exp 15

16 4 () () 1 : exp ( exp op exp ) 2 : exp! exp 3 : exp VAR 4 : exp CON 5 : op 6 : op && def parse_exp(): read_token() exp() if token_type()!= END_TOKEN: error() def exp(): if token_type() == ( : print( 1: exp -> ( exp op exp ) ) read_token() exp() op() exp() if token_type() == ) : read_token() else: error() elif token_type() ==! : print( 2: exp ->! exp ) read_token() exp() elif token_type() == VAR : print( 3: exp -> VAR ) read_token() elif token_type() == CON : print( 4: exp -> CON ) read_token() else: error() def op(): if token_type() == : print( 5: op -> ) read_token() elif token_type() == && : print( 6: op -> && ) read_token() else: error() 16

17 token_type() read_token() error() END_TOKEN read_token() 1 ( CON && (! VAR VAR ) ) () 1: exp -> ( exp op exp ) 4: exp -> CON 6: op -> && 1: exp -> ( exp op exp ) 2: exp ->! exp 3: exp -> VAR 5: op -> 3: exp -> VAR exp ( exp op exp ) 1 ( ( CON op exp ) 4 ( CON ( CON && exp ) 6 ( CON && ( CON && ( exp op exp ) ) 1 ( CON && ( ( CON && (! exp op exp ) ) 2 ( CON && (! ( CON && (! VAR op exp ) ) 3 ( CON && (! VAR ( CON && (! VAR exp ) ) 5 ( CON && (! VAR ( CON && (! VAR VAR ) ) 3 ( CON && (! VAR VAR ( CON && (! VAR VAR ) )! VAR && VAR 2: exp ->! exp 3: exp -> VAR syntax error at token && 17

18 4 () 2 () (factoring) 1 : stm ID = NUM 2 : stm ID = ID 1 : stm ID = atom 2 : atom NUM 3 : atom ID ID = 1 2, 3 1 : exp ( exp + exp ) 2 : exp ( exp * exp ) 3 : exp VAR 4 : exp NUM 1 : exp ( exp op exp ) 2 : exp VAR 3 : exp NUM 4 : op + 5 : op * 1, 2 ( exp exp ) 1 1, 2 4, 5 A αβ 1 γ A αβ 2 γ A αbγ B β 1 B β 2 γ α 18

19 : A + Aα A V α (V T ) 0 1 : list list NUM 2 : list 1 : list NUM list 2 : list 1 1 : seq seq, NUM 2 : seq NUM 1 : seq NUM seq 2 : seq, NUM seq 3 : seq seq seq seq NUM, NUM, NUM seq seq seq seq NUM, NUM, NUM NUM, NUM 0, NUM 0 NUM βα α A Aα A β A βαa A αa A A. V. M. S. R. J. D

20 5 () LL(1) LL(1) ID = NUM ID = ID ID = NUM ID 1 + NUM ( + ) NUM NUM NUM + NUM () 1 () () ( NUM + NUM + NUM 2 ) α First(α) A α A α First(α) First(α ) = 20

21 NUM NUM NUM NUM NUM LL(1) A α α α A α First(α) { {a T α aβ β (V T ) } (α ) First(α) := {a T α aβ β (V T ) } {} (α ) S A Follow(A) Follow(A) := {a T {$} S$ αaaβ α T, β (V T {$}) } $ $ V T Director(A α) { First(α) (α ) Director(A α) := First(α) \ {} Follow(A) (α ) A α A α Director(A α) Director(A α ) = LL(1) LL(1) A. V. M. S. R. J. D

22 5 () LL(1) LL(1) First Follow Director 3 LL(1) LL(1) () First ( ) A α First(α) NUM + - () α () α First () First Follow ( $) A α NUM + - First(α) {+, -, NUM} {} {+, -, NUM} {+} {-} {} Follow(A) () $ () A First () A Follow Director ( $) A α First(α) Follow(A) Director(A α) {+, -, NUM} {$, +, -, NUM} {} NUM {+, -, NUM} {$, +, -, NUM} + {+} {NUM} - {-} {} () α First () α First A Follow 22

23 LL(1) () A α First(α) Follow(A) Director(A α) NUM + - LL(1) () CON => LL(1) First A α => ( ) CON First(α) {(, CON} {(, CON} {(} {CON} ( CON LL(1) LL(1) () First, Follow, Director 3 A α First(α) Follow(A) Director(A α) {(, CON} {$, )} {(, CON} => {=>} {$, )} {=>} {} {$, )} ( ) {(} {$, ), =>} {(} CON {CON} {CON} ( Director LL(1) ) {=>} {$, )} {(} {CON} LL(1) 23

() / (front end) (back end) (phase) (pass) 1 2

1 () () lex http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compiler/ 2018 4 1 () / (front end) (back end) (phase) (pass) 1 2 () () var left, right; fun int main() { left = 0; right = 10; return ((left