プログラミング言語 8 字句解析器(lexer)と構文解析器(parser)

Size: px

Start display at page:

Download "プログラミング言語 8 字句解析器(lexer)と構文解析器(parser)"

つかさすみだ
5 years ago
Views:

1 8 (lexer) (parser) 1 / 73

2 (lexer, tokenizer) (parser) Web Page (HTML XML) CSV, SVG, config file... ( )! 2 / 73

3 1 1 OCaml : ocamllex ocamlyacc 2 Python : ply 2! 3 / 73

4 ( ) 字句解析器構文解析器ご注文はうさぎさんですか? 文字列接頭詞名詞助詞名詞名詞助動詞助詞記号ご注文はうさぎさんですか? 字句列構文名詞句文名詞句動詞句動詞句接頭詞名詞助詞名詞名詞助動詞助詞記号ご注文はうさぎさんですか? 注 : 動詞句などのラベルは本気にしないでください 4 / 73

5 let_expr expr expr expr expr term term term term term pr pr pr pr pr pr pr LET ID EQ ID PLUS ID PLUS NUM MUL ID IN ID ID let x = a + b + 2 * c in f x let x = a + b + 2 * c in f x 5 / 73

6 ? : : ( ) 6 / 73

7 ocamllex : ocamllex =.mll (OCaml ) (calc lex.mll) 1 { (* : OCaml *) 2 type token = 3 NUM of (int) 4 PLUS 5 EOF 6 } 7 8 (* *) 9 rule lex = parse 10 [ \t \n ] { lex lexbuf } (* *) 11 "+" { PLUS } 12 [ 0-9 ]+ as s { NUM(int_of_string s) } 13 eof { EOF } { (* OCaml *) } 7 / 73

8 .mll { OCaml } (* *) let id =... rule lex = parse { } { }... { } { OCaml } { } : (prefix) ( ) as 1 [ 0-9 ]+ as s { NUM(int_of_string s) } 1 let digit = [ 0-9 ] 1 digit+ as s { NUM(int_of_string s) } 8 / 73

9 ocamllex ( ) 1 ( ) a a [ a b c ] a, b, c [ 0-9 ] 0, 1,..., 9 "abc" abc "abc" "def" abc def "abc"* abc 0 "abc"+ abc 1 ("abc" "def")+ (abc def) 1 eof manual-ocaml-400/manual026.html ( ) manual026.html ( ) 9 / 73

10 : ( ) ( ) A A ( ) ϵ a (a A) a RS (R, S ) R S R S (R, S ) R S R (R ) R 0 ( : (abc def)+) ( ) 10 / 73

11 ocamllex ocamllex (.mll) OCaml (.ml) 1 $ ocamllex calc lex.mll 2 6 states, 267 transitions, table size 1104 bytes 3 $ ls 4 calc lex.ml calc_lex.mll.ml lex (.mll rule lex = parse... ) 1 $ ocaml -init calc_lex.ml 2 OCaml version # lex ;; 5 - : Lexing.lexbuf -> token = <fun> Lexing.lexbuf ( C FILE*) mutable record lex buf buf 11 / 73

12 Lexing.lexbuf 1 Lexing.from string "12+34* 56" 1 Lexing.from channel stdin 1 Lexing.from channel (open_in "exp.txt") 12 / 73

13 $ ocamllex calc_lex.mll 6 states, 267 transitions, table size 1104 bytes $ ocaml -init calc_lex.ml OCaml version # let b = Lexing.from_string " ";; val b : Lexing.lexbuf = {... ( )... } # lex b;; - : token = NUM 12 # lex b;; - : token = PLUS # lex b ;; - : token = NUM 34 # lex b ;; - : token = PLUS # lex b;; - : token = NUM 56 # lex b;; - : token = EOF rule lex = parse [ \t \n ] { lex lexbuf } "+" { PLUS } [ 0-9 ]+ as s { NUM(int_of_string s) } eof { EOF } 13 / 73

14 ocamlyacc : /* + OCaml */ %{ (* OCaml *) %} /* */ %token <int> NUM %token PLUS EOF /* ( ) */ %start program %type <int> program %% /* */ expr : NUM { $1 } expr PLUS NUM { $1 + $3 } program : expr EOF { $1 } %% (* OCaml *) =.mly : %% 3 + OCaml OCaml %token : %start : ( ) %type : ( ) :.mll.mly ( ) 14 / 73

15 ocamlyacc menhir ocamlyacc menhir ocaml ocamlyacc 15 / 73

16 ocamlyacc : 1 expr : expr PLUS NUM {... } : expr ( ) PLUS (1 ) NUM ( ) expr ( ) {...} ( ) : ( ) ( ) expr expr PLUS NUM } } / 73

17 ( ) : T : NT : S NT. a = b 1 b n (n 0, a NT, b i NT T ). : b 1,... bn, a : bi b i 1 ( ) ( ) 17 / 73

18 OCaml $1, $2,... : a = b 1... b n a : 1 expr : expr PLUS NUM { $1 + $3 } : expr PLUS NUM 1 expr( ) 3 NUM( ) 18 / 73

19 ocamlyacc ocamlyacc.mly 2 OCaml (.ml.mli).mli? 1 $ ocamlyacc calc_parse.mly 2 $ ls 3 calc parse.ml calc parse.mli calc_parse.mly.ml.mly %start program program 19 / 73

20 ocamlyacc ( ) 1 $ ocaml -init calc_parse.ml 2 OCaml version # program ;; 5 - : (Lexing.lexbuf -> token) -> Lexing.lexbuf -> int = <fun> Lexing.lexbuf -> token int.mly (%type <int> parse) token token (token ) 20 / 73

21 (lex) (program) 1 # program lex (Lexing.from_string " ") : 1 2 :.mll token.mly token 21 / 73

22 token token.mll 1 $ ocaml -init calc_lex.ml 2 # lex;; 3 - : Lexing.lexbuf -> token = <fun> token calc lex.ml token.mly 1 $ ocaml -init calc_parse.ml 2 # program ;; 3 - : (Lexing.lexbuf -> token) -> Lexing.lexbuf -> int = <fun> calc parse.ml token OCaml 22 / 73

23 token 1:.mll token.mly 2:.mly token.mll 1 23 / 73

24 token calc lex.mll : 1 { 2 (* token *) 3 (* PLUS 4 calc_parse.ml ( ) 5 *) 6 open Calc parse 7 } 8 rule lex = parse 9 [ \t \n ] { lex lexbuf } 10 "+" { PLUS } 11 [ 0-9 ]+ as s { NUM(int_of_string s) } 12 eof { EOF } 24 / 73

25 1 $ ocaml ocaml_lex.ml ocaml_parse.ml # NG 2 $ ocaml -init ocaml_lex.ml -init ocaml_parse.ml # NG : ocaml.ml ocaml.ml ocamlc (.cmo) 25 / 73

26 1 $ ocamllex calc_lex.mll 2 $ ocamlyacc calc_parse.mly 3 # ocamlc 3! 4 # parse, lex 5 $ ocamlc -c calc parse.mli calc parse.ml calc lex.ml 6 # ocaml.cmo 7 $ ocaml calc parse.cmo calc lex.cmo 8 OCaml version # Calc_parse.program;; 11 - : (Lexing.lexbuf -> Calc parse.token) -> Lexing.lexbuf -> int = <fun> 12 # Calc_lex.lex;; 13 - : Lexing.lexbuf -> Calc parse.token = <fun> 1 # Calc_parse.program Calc_lex.lex (Lexing.from_string " ");; 2 - : int = / 73

27 OCaml.ml.ml.cmo ( ) ocaml.cmo ocamlc -c ( ) : calc lex.ml calc parse.ml token calc parse.ml calc lex.ml 27 / 73

28 : ocamlbuild OCaml ( ) 1 $ ocamlbuild calc lex.byte 2 /usr/bin/ocamllex -q calc_lex.mll 3 /usr/bin/ocamldep -modules calc_lex.ml > calc_lex.ml.depends 4 /usr/bin/ocamlyacc calc_parse.mly 5 /usr/bin/ocamldep -modules calc_parse.mli > calc_parse.mli.depends 6 /usr/bin/ocamlc -c -o calc_parse.cmi calc_parse.mli 7 /usr/bin/ocamlc -c -o calc_lex.cmo calc_lex.ml 8 /usr/bin/ocamldep -modules calc_parse.ml > calc_parse.ml.depends 9 /usr/bin/ocamlc -c -o calc_parse.cmo calc_parse.ml 10 /usr/bin/ocamlc calc_parse.cmo calc_lex.cmo -o calc_lex.byte 11 $ ls 12 build/ calc lex.byte calc_lex.mll calc_parse.mly 13 # _build 14 # -I _build 15 $ ocaml -I build _build/*.cmo 16 OCaml version # 28 / 73

29 ocamlmktop *.cmo 1 $ ocaml -I _build _build/*.cmo 2 OCaml version # ocaml 1 $ ocamlmktop -o calc.top _build/*.cmo *.cmo ( calc.top) 1 $./calc.top -I build 2 OCaml version # 29 / 73

30 OCaml ( : abc.ml) ( / etc.) 1: Abc. 2: open Abc ocamlc ocaml ocamlmktop *.cmi *.cmo -I 30 / 73

31 (1) 1 expr : 2 NUM 3 expr PLUS NUM { $1 + $3 }? expr : NUM NUM PLUS expr { $1 + $3 } expr : NUM expr PLUS expr { $1 + $3 } (+) (left associative) : a + b + c = ((a + b) + c) 31 / 73

32 (2) * ( )? 1 expr : 2 NUM 3 expr PLUS NUM { $1 + $3 } 4 expr MUL NUM { $1 * $3 } = (3 + 4) 5 = = 3 + (4 5) = 23 * (term) + (expr) 32 / 73

33 : ocamlyacc %left ( ) %right ( ) 33 / 73

34 3 1 (1 ) 2 OCaml (3 ) 3 OCaml (4 ) ( ) let ( ) 34 / 73

35 ( ) + ( ) + + 0: ( ) 1: (let) 2: 35 / 73

36 1 expr : 2 NUM { $1 } 3 expr PLUS NUM { $1 +. $3 } 1 # parse_string " * 5.6" 2 - : float = ( ) ( ) : : 36 / 73

37 : * 5.6 : + * e 0 +e 1 : e0 の構文木 e1 の構文木 OCaml 1 type expr = Plus of expr * expr 37 / 73

38 ( ). + eval_expr = eval_expr + e0 の構文木 eval_expr e1 の構文木 e0 の構文木 e1 の構文木 : eval expr (e 0 + e 1 ) = (eval expr e 0 ) + (eval expr e 1 ) OCaml : 1 let rec eval_expr e = 2 match e with Plus (e0, e1) -> (eval_expr e0) + (eval_expr e1) 38 / 73

39 x + 1 ( )x NG: : let x = in x : x = 3.3 x : 39 / 73

40 : : {x 3.3, y 4.4} let x = in x : eval expr (let x = in x + 4.4) {} = eval expr (x + 4.4) {x 3.3} = eval expr x {x 3.3} + eval expr 4.4 {x 3.3} = = [ (x, 3.3); (y, 4.4) ] 40 / 73

41 f f x = x * x (f 3) {x 3} x * x eval expr (e 0 e 1 ) e = let f = eval expr e 0 in let v = eval expr e 1 in eval expr (f ) {f v} =, ( ) 41 / 73

42 ? : 1 let make_adder x = 2 let f y = x + y in f 3 ;; 4 let a11 = make_adder 1.1 in 5 a a x + y {y 2.2} (x ) x = 1.1 a11 ( ) (2 ) =, ( ), 42 / 73

43 : 2?? 43 / 73

44 ϵ A = a A = a RS A = RS R S A = R, A = S R A =, A = A R 44 / 73

45 ? ϵ A = a A = a RS A = R S R S A = R, A = S R A =, A = A R? A =, A = AR A =, A = RA (R A ) 45 / 73

46 ? : = A =, A = aab a n b n (n 0) / 73

47 A =, A = aab * ( ) * 1 k a k b k? a ( b) a ( b) aa aaa aabb bb aa aaa aaa aabb bb ab a b a aa aabbb bb aa aabbb aabbb bb 47 / 73

48 OCaml 48 / 73

49 OCaml ( ) : ocamllex, ocamlyacc OCaml (.ml ) OCaml 49 / 73

50 OCaml 3 OCaml 3 1 (ocaml) 2 (ocamlc); 3 (ocamlopt); 50 / 73

51 : (hi.ml) 1 Printf.printf "hello\n" 1 $ ocaml hi.ml 2 hello 1 $ ocaml 2 # #use "hi.ml";; 3 # 1 $ ocaml -init hi.ml 2 # 1 $ ocamlc hi.ml 2 $ ls 3 a.out* hi.cmi hi.cmo hi.ml 4 $./a.out 5 hello 1 $ ocamlopt hi.ml 2 $ ls 3 a.out* hi.cmi hi.cmx hi.ml hi.o 4 $./a.out 5 hello 51 / 73

52 ocamlc ocamlopt.cmi hi.ml ( hi.ml ).cmo hi.ml (.o ).cmx hi.ml (.o ).o a.out 52 / 73

53 -c -o ocamlc, ocamlopt C -o -c ocamlc : {.cmi,.cmo} ocamlopt : {.cmi,.cmx,.o} 53 / 73

54 : 2 msg.ml 1 let greeting = "hello" hi.ml 1 Printf.printf "%s\n" Msg.greeting hi.ml msg.ml greeting ( ) 1: (msg.ml greeting) Msg.greeting. = basename (.ml ) capitalize 54 / 73

55 open open 1 open Msg;; 2 Printf.printf "%s\n" greeting open 55 / 73

56 1: 1 $ ls 2 hi.ml msg.ml 3 $ ocamlc -o greet msg.ml hi.ml 4 $ ls 5 greet* hi.cmi hi.cmo hi.ml msg.cmi msg.cmo msg.ml 2: ( ) 1 $ ls 2 hi.ml msg.ml 3 $ ocamlc -c msg.ml # -> msg.{cmi,cmo} 4 $ ocamlc -c hi.ml # -> hi.{cmi,cmo} 5 $ ocamlc -o greet msg.cmo hi.cmo # -> greet 6 $./greet 7 hello 56 / 73

57 1: 1 $ ocamlc hi.ml msg.ml 2 File "hi.ml", line 1, characters 21-33: 3 Error: Unbound module Msg 2: 1 $ ls 2 hi.ml msg.ml 3 $ ocamlc -c hi.ml 4 File "hi.ml", line 1, characters 14-26: 5 Error: Unbound module Msg 2: ( : hi.ml).cmi ( : msg.cmi) 57 / 73

58 hi.ml msg.ml ( ) OK NG $ ocamlc msg.ml hi.ml $ ocamlc hi.ml msg.ml $ ocamlc -c msg.ml $ ocamlc -c hi.ml $ ocamlc -c hi.ml $ ocamlc -c msg.ml ( ) OK NG $ ocamlopt msg.ml hi.ml $ ocamlopt hi.ml msg.ml $ ocamlopt -c msg.ml $ ocamlopt -c hi.ml $ ocamlopt -c hi.ml $ ocamlopt -c msg.ml 58 / 73

59 (ocaml) 1: ocamlc.cmo ( ) 2: 1 $ ocaml msg.cmo hi.cmo 2 # NG 1 $ ocaml hi.cmo msg.cmo 2 File "_none_", line 1: 3 Error: Reference to undefined global Msg ocamlc.ml 59 / 73

60 ocamlmktop ocamlmktop.cmo 1 $ ocamlmktop -o greet msg.cmo hi.cmo 2 $./greet 3 hello 4 OCaml version #.cmo 60 / 73

61 : OCaml 2 (.ml.mli).ml : ( C.c).mli : ( C.h).mli.ml ( ) ( ) : msg.ml 1 let real_mind = "you a** h*le" 2 let greeting = "glad to see you" msg.mli (real mind ) 1 val greeting : string 61 / 73

62 .mli? ocamlyacc.mli 62 / 73

63 .mli.mli.cmi.ml.cmo 1 $ ocamlc a.ml 1 a.mli a.cmi, a.cmo a.cmi a.ml 2 a.mli a.cmi ( a.mli!).ml.cmi 3: ( : msg.ml) ( : msg.mli) ( : msg.cmi) 63 / 73

64 .mli : 6 a.{mli,ml}, b.{mli,ml}, c.ml, d.ml 1: 1 $ ocamlc -o program b.mli a.mli b.ml a.ml d.ml c.ml 2: 1 $ ocamlc -c b.mli 2 $ ocamlc -c a.mli 3 $ ocamlc -c b.ml 4 $ ocamlc -c a.ml 5 $ ocamlc -c d.ml 6 $ ocamlc -c c.ml 7 $ ocamlc -o program b.cmo a.cmo d.cmo c.cmo 1 $ ocaml b.cmo a.cmo d.cmo c.cmo 1 $ ocamlmktop -o program b.cmo a.cmo d.cmo c.cmo 64 / 73

65 ocamlbuild 1 $ ocamlbuild name.byte name.ml... (ocamldep) name.byte 1 $ ocamlbuild name.native 65 / 73

66 token 1:.mll token.mly.mll token 1: open Calc parse Calc parse ( ) 1 : token Calc parse.plus Calc parse.minus 2:.mly token.mll 2: ocamlyacc menhir menhir --external-tokens 1 $ menhir --external-tokens Calc_lex calc_parse.mly 66 / 73

67 : 1 ( ) calc lex.mll : Calc parse open calc parse.ml 1 { 2 open Calc_parse 3 } 4 rule lex = parse 5 [ \t \n ] { lex lexbuf } 6 "+" { PLUS } 7 "-" { MINUS } 8 [ 0-9 ]+ as s { NUM(int_of_string s) } 9 eof { EOF } 67 / 73

68 : 1 calc lex.mll calc parse.ml Calc parse.plus 1 { 2 } 3 rule lex = parse 4 [ \t \n ] { lex lexbuf } 5 "+" { Calc_parse.PLUS } 6 "-" { Calc_parse.MINUS } 7 [ 0-9 ]+ as s { Calc_parse.NUM(int_of_string s) } 8 eof { Calc_parse.EOF } 68 / 73

69 : 2 : 1 $ menhir --external-tokens Calc_lex calc_parse.mly.mll.mly token 69 / 73

70 : 1, 1 1 $ ocamllex calc_lex.mll 2 $ menhir calc_parse.mly 3 # lex parse parse, lex 4 $ ocamlc -c calc_parse.mli calc_parse.ml calc_lex.ml 5 $ ocaml calc_parse.cmo calc_lex.cmo 6 OCaml version # Calc_parse.program;; 9 - : (Lexing.lexbuf -> Calc parse.token) -> Lexing.lexbuf -> int = <fun> 10 # Calc_lex.lex;; 11 - : Lexing.lexbuf -> Calc parse.token = <fun> 70 / 73

71 : 2 1 $ ocamllex calc_lex.mll 2 6 states, 267 transitions, table size 1104 bytes 3 # calc_parse.ml token calc_lex.ml 4 $ menhir --external-tokens Calc_lex calc_parse.mly 5 # lex, parse 6 $ ocamlc -c calc_lex.ml calc_parse.mli calc_parse.ml 7 $ ocaml calc_lex.cmo calc_parse.cmo 8 OCaml version # Calc_parse.program;; 11 - : (Lexing.lexbuf -> Calc lex.token) -> Lexing.lexbuf -> int = <fun> 12 # Calc_lex.lex;; 13 - : Lexing.lexbuf -> Calc lex.token = <fun> 71 / 73

72 ocamlbuild 1, 1 calc lex.mly calc parse.mll calc lex.byte calc parse.cmo 1 $ ocamlbuild -use-menhir calc lex.byte 2 /usr/bin/ocamllex -q calc_lex.mll 3 /usr/bin/ocamldep -modules calc_lex.ml > calc_lex.ml.depends 4 menhir --raw-depend --ocamldep /usr/bin/ocamldep -modules calc_parse.mly > calc_parse.mly.depends 5 menhir --ocamlc /usr/bin/ocamlc --infer calc_parse.mly 6 /usr/bin/ocamldep -modules calc_parse.mli > calc_parse.mli.depends 7 /usr/bin/ocamlc -c -o calc_parse.cmi calc_parse.mli 8 /usr/bin/ocamlc -c -o calc_lex.cmo calc_lex.ml 9 /usr/bin/ocamldep -modules calc_parse.ml > calc_parse.ml.depends 10 /usr/bin/ocamlc -c -o calc_parse.cmo calc_parse.ml 11 /usr/bin/ocamlc calc_parse.cmo calc_lex.cmo -o calc_lex.byte 12 $ ocaml -I _build _build/*.cmo 13 OCaml version # 72 / 73

73 ocamlbuild 2 calc parse.mly calc lex.mll calc parse.byte calc lex.cmo 1 $ ocamlbuild -use-menhir -yaccflags --external-tokens,calc lex calc parse.byte 2 menhir --raw-depend --ocamldep /usr/bin/ocamldep -modules calc_parse.mly > calc_parse.mly.depends 3 menhir --ocamlc /usr/bin/ocamlc --external-tokens Calc_lex --infer calc_parse.mly 4 /usr/bin/ocamldep -modules calc_parse.mli > calc_parse.mli.depends 5 /usr/bin/ocamllex -q calc_lex.mll 6 /usr/bin/ocamldep -modules calc_lex.ml > calc_lex.ml.depends 7 /usr/bin/ocamlc -c -o calc_lex.cmo calc_lex.ml 8 /usr/bin/ocamlc -c -o calc_parse.cmi calc_parse.mli 9 /usr/bin/ocamldep -modules calc_parse.ml > calc_parse.ml.depends 10 /usr/bin/ocamlc -c -o calc_parse.cmo calc_parse.ml 11 /usr/bin/ocamlc calc_lex.cmo calc_parse.cmo -o calc_parse.byte 12 $ ocaml -I _build _build/*.cmo 13 OCaml version # 73 / 73

: gettoken(1) module P = Printf exception End_of_system (* *) let _ISTREAM = ref stdin let ch = ref ( ) let read () = (let c =!ch in ch := inp

: gettoken(1) module P = Printf exception End_of_system (* *) let _ISTREAM = ref stdin let ch = ref ( ) let read () = (let c =!ch in ch := inp 7 OCaml () 1. 2. () (compiler) (interpreter) 2 OCaml (syntax) (BNF,backus normal form ) 1 + 2; let x be 2-1 in x; ::= ; let be in ; ::= + - ::= * / ::= 7.1 ( (printable characters) (tokens) 1 (lexical