PL : pl0 ( ) 1 SableCC ( sablecc ) 1.1 sablecc sablecc Étienne Gagnon [1] Java sablecc sablecc ( ) Visitor DepthFirstAdapter 1 (Depth

Size: px

Start display at page:

Download "PL : pl0 ( ) 1 SableCC ( sablecc ) 1.1 sablecc sablecc Étienne Gagnon [1] Java sablecc sablecc ( ) Visitor DepthFirstAdapter 1 (Depth"

あきひろながだき
5 years ago
Views:

1 PL : pl0 ( ) 1 SableCC ( sablecc ) 1.1 sablecc sablecc Étienne Gagnon [1] Java sablecc sablecc () Visitor DepthFirstAdapter 1 (Depth First traversal) ( ) (breadth first) 2 sablecc 1.2 sablecc sablecc icho (sablecc-3.2.tar.gz) sablecc sablecc 1

2 (bash : $ ) $ export PATH=$PATH:~nakai/sablecc-3.2/bin icho tar $ cd $ tar zxv ~nakai/sablecc-3.2.tar.gz sablecc-3.2 bin lib bin sablecc java -jar lib/sablecc.jar $* 1 Package postfix; 2 3 Tokens 4 number = [ ]+; 5 plus = + ; 6 minus = - ; 7 mult = * ; 8 div = / ; 9 mod = % ; 10 l_par = ( ; 11 r_par = ) ; 12 blank = ( 13 10)+; Ignored Tokens 15 blank; Productions 18 expr = 19 {factor} factor 20 {plus} expr plus factor 21 {minus} expr minus factor; factor = 24 {term} term 25 {mult} factor mult term 26 {div} factor div term 27 {mod} factor mod term; term = 30 {number} number 30 {expr} l_par expr r_par; java -jar ~/sablecc-3.2/lib/sablecc.jar $* $ chmod a+rx sablecc 1.3 sablecc [1] 1 sablecc ( ) 1 package postfix; Java 2 Tokens = ; [ ] Java uni 1: postfix.grammar 14 Ignored Tokens 17 ( = production rule) sablecc 18 expr 3 { } sablecc (lexer) (parser) (node) (analysis) $ sablecc postfix.grammar 2

3 -- Generating parser for postfix.grammar in /home1/nakai/ip2 org.sablecc.sablecc.parser.parserexception: [4,23] expecting: ] at org.sablecc.sablecc.parser.parser.parse(unknown Source) at org.sablecc.sablecc.sablecc.processgrammar(unknown Source) at org.sablecc.sablecc.sablecc.processgrammar(unknown Source) at org.sablecc.sablecc.sablecc.main(unknown Source) 2: sablecc 1 4 ] sablecc ( ) 2 [4, 23] 4 23 expecting : ] ] * * + 1+2*3 = 1+(2*3) 2 ( 1 ) 2 3 * SableCC 3 3 DepthFirstAdapter 1 (node) (analysis) import 4 number 1 package postfix; 2 import postfix.analysis.*; 3 import postfix.node.*; 4 class Translation extends DepthFirstAdapter 5 { 6 public void casetnumber(tnumber node) 7 {// When we see a number, we print it. 8 System.out.print(node); 9 } 10 public void outaplusexpr(aplusexpr node) 11 {// out of alternative {plus} in Expr, // we print the plus. 12 System.out.print(node.getPlus()); 13 } 14 public void outaminusexpr(aminusexpr node) 15 {// out of alternative {minus} in Expr, // we print the minus. 16 System.out.print(node.getMinus()); 17 } 18 public void outamultfactor(amultfactor node) 19 {// out of alternative {mult} in Factor, // we print the mult. 20 System.out.print(node.getMult()); 21 } 22 public void outadivfactor(adivfactor node) 23 {// out of alternative {div} in Factor, // we print the div. 24 System.out.print(node.getDiv()); 25 } 26 public void outamodfactor(amodfactor node) 27 {// out of alternative {mod} in Factor, // we print the mod. 28 System.out.print(node.getMod()); 29 } 30 } 3: Translation.java sablecc T 10 outaplusexpr 3

4 expr = 19 {factor} factor 20 {plus} expr plus factor 21 {minus} expr minus factor; out sablecc A ( {plus}) ( expr) Visitor expr, plus, factor plus getplus DepthFirstAdaptor (main ) parse Start 18 () Start 20 Visitor 1. sablecc package postfix; 2 import postfix.parser.*; 3 import postfix.lexer.*; 4 import postfix.node.*; 5 import java.io.*; 6 public class Compiler 7 { 8 public static void main(string[] arguments){ 9 try { 10 System.out.println ("Type an arithmetic expression:"); 11 // Create a Parser instance. 12 Parser p = 13 new Parser( 14 new Lexer( 15 new PushbackReader( 16 new InputStreamReader (System.in), 1024))); 17 // Parse the input. 18 Start tree = p.parse(); 19 // Apply the translation. 20 tree.apply(new Translation()); 21 } 22 catch(exception e){ 23 System.out.println(e.getMessage()); 24 } 25 } 26 } 4: Compiler.java 2 PL0 sablecc PL0 2.1 icho ~nakai/ip2/pl0d/pl0d README 1. (LIST.java, SymTable.java) 4

5 2. (Information.java) 3. (Code.java, Code- Gen.java, CodePtr.java, Mnemonic.java) 4. (Main.java) 2.2 PL0 ( ) sablecc PL0 10 icho ~nakai/ip2/pl0d/pl0d.grammar pl0 pl0 icho ~nakai/ip2/pl0d/pl0i_src code.output ( INT, 0, 3 ) ( LIT, 0, 3 ) ( CSP, 0, 1 ) ( OPR, 0, 0 ) code.output pl0i PL0 write 3. ( INT, 0, 3 ) 3 3 n 3+n ( LIT, 0, 3 ) 3 ( CSP, 0, 1 ) write () ( OPR, 0, 0 ) sablecc sablecc ( Visitor ) (Hashtable ) 1 Java public Hashbtable<Node, Information> codetable = new Hashtable<Node, Information>(10001); Node Information ( ) CodePtr, String, int ( ) CodePtr 1 Code Code 1 PL0 3 int CodeGen static PL0 Mnemonic PL0 ( ) PL0 SymTable 5

6 addlist search all search block delete block write write PL0 write 3. (.) write write 1 PL0 f = number write statement {write} write expression expression {e} e f t = {f} f e = {t} t write statement block = declparts statement program = block dot write write 3. f = number Translation.java Translation 1 package pl0d; 2 3 import java.util.*; 4 import pl0d.node.*; 5 import pl0d.analysis.*; 6 import pl0d.*; 7 8 public class Translation extends DepthFirstAdapter 9 { public Hashtable<Node, Information> codetable = new Hashtable<Node, Information>(10001); 12 private SymTable st; 13 private int level = 0; public void debug(string s){ 16 System.out.println(s); 17 } Translation(SymTable st){ 20 this.st = st; 21 } } 5: Translation.java DepthFirstAdapter 11 JDK 5.0 <Node, Information> f = number public void outanumberf(anumberf node) (Number) n PL0 ( LIT, 0, n ) public void outanumberf(anumberf node){ int x = Integer.parseInt(node.getNumber().getText()); CodePtr c = new CodePtr(new Code(CodeGen.O_LIT, 0, x)); Information i = new Information(c); codetable.put(node, i); } 6

7 1 2 f = {number} number number node.getnumber() gettext() ( ) Integer.parseInt x number f t = {f} t 1 public void outaft(aft node){ Information tmp = codetable.get(node.getf()); codetable.put(node, tmp); } ( ) (Information ) e = {t} e expression = {e} e statement = {write} write expression PL0 expression write expression 1. expression (CodePtr ) ( ( LIT, 0, n )) 2. write CodePtr add ( CSP, 0, 1 ) Code outanumberf 3. Information block = declparts statement declparts declparts statement write 3 ( INT, 0, 3 + n ) statement write Information program = block dot block ( OPR, 0, 0 ) ( code.output ) CodePtr void printcode() (CodePtr ) printcode write 3. ( INT, 0, 3 ) 7

8 ( LIT, 0, 3 ) ( CSP, 0, 1 ) ( OPR, 0, 0 ) write 1+2*3 f = {number} number t = {mult} t mult f {div} t div f t f PL0 ( OPR, 0, 4 ) ( OPR, 0, 5 ) PL0 ( OPR, 0, 2 ) ( OPR, 0, 3 ) expression 0 1 (f = {par}...) write statement = {}... statement_list writeln statement = {no} writeln writeln ( CSP, 0, 2 ) statement_list {single} {list} statement_list statement ( statement_list) CodePtr add {} statement_list write 3+4; writeln ; 8

9 end 2 10 PL0 (;) level 1 1 SymTable main declparts, declpart, decl, vardecl idlist 1 block ( INT, 0, 3 ) 3 n idlist = {single} id SymTable search_block search_block LIST null LIST ( ) String name int kind int offset int level params LIST prev 1 addlist public void addlist(string name, int kind, int offset, int level, int fparam){ 1 1. id node.getid().gettext() 2. search_block id_list = {list} id_list = {single} id_list id 1 vardecl decl = {variable} declpart = {decl} 9

10 declpart decl declpart = {no} 1 0 declparts SymTable backpatch 1 1 inablock block ( INT, 0, 3 ) 3 var i, j, k;. ( INT, 0, 6 ) ( OPR, 0, 0 ) read read read SymTable search_all read PL0 ( CSP, 0, 0 ) PL0 ( STO, l, o ) l o search_all CSP STO var i; read i; write i; writeln f = {ident} read PL0 PL0 ( LOD, l, o ) l o LIT 10

11 statement = {ident} PL0 := (STO) 4. var i; i:=1*2; i:=i*4; write i; writeln if while 10 condition ( ) condition = {odd} odd 1 PL0 =, <>, <, >, <=, >= = C ( ) <> 1 1 (expression) [left] [right] getleft(), getright() ( OPR, 0, a ) a a = 8 <> 9 < 10 >= 11 > 12 <= 13 if PL0 if else PL0 0 PL0 if JPC ( ) 0( ) ( JPC, 0, ) statement ( LAB, 0, ) CodeGen static int makelabel() 11

12 var i; read i; if odd i then write i; writeln while if while ( LAB, 0, 0 ) ( JPC, 0, 1 ) statement ( JMP, 0, 0 ) ( LAB, 0, 1 ) JMP PL0 const max = 100; id_assign, id_assign_list, constdecl decl = {constant} id_assign (st.constant) number addlist (LIST params) declpart = {decl} decl = {constant} 0 (f = {ident}) (getparams ) PL0 ( LIT, 0, n ) PL0 2.3 PL0 ( ) decl = {function}, funcdecl, fhead, fid fid fid (fid = id) fhead, param param {id_list} id_list Information val 0 id_list id_list 6 f(a, b, c)

13 a a b b c c f 1 f 2 f 3 f 6: f 6 3 f 1 a 3 b 2 c 1 fhead PL0 (CAL) 1 funcdecl SymTable proc_params fhead proc_params 4. funcdecl fhead block fhead block ( OPR, 0, 0 ) decl = {function} declpart, declparts, block declpart = {no} 0 declpart = {decl} declpart decl 1. declpart decl null ( ) 4. declparts block declparts statement 1. declparts, statement declparts 13

14 declparts INT 3 + n n 7. statement f = {emptypar}, f = {identpar} expressionlist f = {emptypar} id 0 PL0 ( CAL, l, o ) l o return return PL0 3 ( RET, 0, a ) a 1 SymTable searchf int 1 return return PL0 return function f() return 101; write f(); writeln expressionlist expressionlist expressionlist {single} expression 1 {list} expressionlist expression expressionlist +1 PL0 7 ( ) 8 ( ) 9 3 PL0 14

15 function f(n) if n < 1 then return 1; return n * f(n - 1); end; var i; read i; if i>0 then write f(i); writeln end 7: function fib(n) if n = 1 then return 1; if n = 2 then return 2; return fib(n - 1) + fib(n - 2); end; var i; read i; write fib(i); writeln 8: n 3 ( ) function fib(n) if n = 1 then return 1; if n = 2 then return 2; return fib(n - 1) + fib(n - 2); end; var i; var j; read i; j := 1; while j<=i do write fib(j); writeln; j := j+1; end 9: n [1] Étienne Gagnon: SABLECC, AN OBJECT- ORIENTED COMPILER FRAMEWORK, Master s thesis, McGill University, Montreal,

16 Package pl0d; Helpers number = [ ]; tab = 9; cr = 13; lf = 10; Tokens lpar = ( ; rpar = ) ; plus = + ; minus = - ; mult = * ; div = / ; semi = ; ; comma =, ; dot =. ; coleq = := ; eq = = ; neq = <> ; lt = < ; gt = > ; le = <= ; ge = >= ; const = const ; var = var ; function = function ; = ; end = end ; if = if ; then = then ; while = while ; do = do ; return = return ; read = read ; write = write ; writeln = writeln ; odd = odd ; id = [ a.. z ] ([ a.. z ] [ ])*; number = number+; blank = ( tab cr lf)+; Ignored Tokens blank; Productions program = block dot; block = declparts statement; declparts = declpart; declpart = {no} {decl} declpart decl; decl = {constant} constdecl {variable} vardecl {function} funcdecl; constdecl = const id_assign_list semi; id_assign_list = {list} id_assign_list comma id_assign {single} id_assign; id_assign = id eq number; vardecl = var id_list semi; id_list = {list} id_list comma id {single} id; funcdecl = function fhead block semi; fhead = fid lpar param rpar ; fid = id; param = {no} {id_list} id_list; statement = {no} {ident} id coleq expression {} statement_list end {if} if condition then statement {while} while condition do statement {return} return expression {read} read id {write} write expression {writeln} writeln; statement_list = {list} statement_list semi statement {single} statement; condition = {odd} odd expression {eq} [left]:expression eq [right]:expression {neq} [left]:expression neq [right]:expression {lt} [left]:expression lt [right]:expression {gt} [left]:expression gt [right]:expression {le} [left]:expression le [right]:expression {ge} [left]:expression ge [right]:expression; expression = {plus} plus e {minus} minus e {e} e; e = {plus} e plus t {minus} e minus t {t} t; t = {mult} t mult f {div} t div f {f} f; f = {number} number {ident} id {emptypar} id lpar rpar {identpar} id lpar expressionlist rpar {par} lpar expression rpar; expressionlist = {list} expressionlist comma expression {single} expression; 10: pl0d.grammar 16

untitled

untitled II 4 Yacc Lex 2005 : 0 1 Yacc 20 Lex 1 20 traverse 1 %% 2 [0-9]+ { yylval.val = atoi((char*)yytext); return NUM; 3 "+" { return + ; 4 "*" { return * ; 5 "-" { return - ; 6 "/" { return / ; 7 [ \t] { /*