¤Þ¤º¡¤Èó¾ï¤Ëñ½ã¤Ê¸À¸ì¤È¤·¤Æ¡¤À°¿ô¡¤¿¿µ¶ÃÍ¡¤¾ò·ïʬ´ô¡¤²Ã»»¾è»»¤ÈÊÑ¿ô¤Î »²¾È¤Î¤ß(¿·¤·¤¤ÊÑ¿ô¤ÎÀë¸À¤¹¤é¤Ç¤¤Ê¤¤!)¤ò»ý¤Ä¸À¸ì ML1 ¤«¤é»Ï¤á ¤ë¡¥
ºÇ½é¤Ë¡¤ML1 ¤Îʸˡ¤ò°Ê²¼¤Î¤è¤¦¤ËÍ¿¤¨¤ë¡¥
|
¥×¥í¥°¥é¥à¤Ï¡¤;;¤Ç½ª¤ï¤ë¤Ò¤È¤Ä¤Î¼°¤Ç¤¢¤ë¡¥¼°¤Ï¡¤¼±Ê̻Ҥˤè¤ëÊÑ¿ô »²¾È¡¤À°¿ô¥ê¥Æ¥é¥ë¡¤¿¿µ¶ÃÍ¥ê¥Æ¥é¥ë(true¤Èfalse)¡¤¾ò·ïʬ´ô¤Î ¤¿¤á¤Îif¼°¡¤¤Þ¤¿¤ÏÆó¹à±é»»»Ò¼°¡¤³ç¸Ì¤Ç°Ï¤Þ¤ì¤¿¼°¤Î¤¤¤º¤ì¤«¤Ç¤¢¤ë¡¥ ¼±Ê̻Ҥϡ¤±Ñ¾®Ê¸»ú¤Ç»Ï¤Þ¤ê¡¤¿ô»ú¡¦±Ñ¾®Ê¸»ú¡¦¡Ö'(¥¢¥Ý¥¹¥È¥í¥Õ¥£)¡× ¤òʤ٤¿¡¤Í½Ìó¸ì¤Ç¤Ï¤Ê¤¤Ê¸»úÎó¤Ç¤¢¤ë¡¥¤³¤ÎÃʳ¬¤Ç¤ÏͽÌó¸ì¤Ï if, then, else, true, false ¤Î5¤Ä¤Ç¤¢¤ë¡¥Î㤨¤Ð¡¤°Ê²¼ ¤Îʸ»úÎó¤Ï¤¤¤º¤ì¤âML1 ¥×¥í¥°¥é¥à¤Ç¤¢¤ë¡¥
3;; true;; x;; 3 + x';; (3 + x1) * false;;
¤Þ¤¿¡¤+, * ¤Ïº¸·ë¹ç¡¤·ë¹ç¤Î¶¯¤µ¤Ï¡¤¶¯¤¤Êý¤«¤é¡¤*, +, <, if¼° ¤È¤¹¤ë¡¥
¤½¤ì¤Ç¤Ï¡¤¹½Ê¸¤Ë´Ø¤¹¤ëÉôʬ¤«¤é½ç¤Ë¡¤6¤Ä¤Î¥Õ¥¡¥¤¥ë¤ò¸«¤Æ¤¤¤¯¡¥
¾å¤Îʸˡ¤ËÂФ¹¤ë¡¤Ãê¾Ý¹½Ê¸ÌڤΤ¿¤á¤Î¥Ç¡¼¥¿·¿¤Ï¿Þ1¤Î ¤è¤¦¤ËÀë¸À¤µ¤ì¤ë¡¥
id ¤ÏÊÑ¿ô¤Î¼±Ê̾ðÊó¤ò¼¨¤¹¤¿¤á¤Î·¿¤Ç¡¤¤³¤³¤Ç¤ÏÊÑ¿ô¤Î̾Á°¤òɽ¤¹Ê¸»úÎó ¤È¤·¤Æ¤¤¤ë¡¥(¤è¤ê¸½¼ÂŪ¤Ê¥¤¥ó¥¿¥×¥ê¥¿¡¦¥³¥ó¥Ñ¥¤¥é¤Ç¤Ï¡¤ÊÑ¿ô¤Î·¿¤Ê¤É¤Î ¾ðÊó¤â²Ã¤ï¤ë¤³¤È¤¬Â¿¤¤¡¥) binOp¡¤exp¡¤program ·¿¤Ë´Ø¤·¤Æ¤Ï ¾å¤Îʸˡ¹½Â¤¤ò(³ç¸Ì¼°¤ò½ü¤¤¤Æ)¤½¤Î¤Þ¤Þ¼Ì¤·¤¿·Á¤ÎÀë¸À¤Ë¤Ê¤Ã¤Æ¤¤¤ë¤³¤È¤¬ ¤ï¤«¤ë¤À¤í¤¦¡¥
ocamlyacc ¤Ï¡¤yacc ¤ÈƱÍͤˡ¤LALR(1) ¤Îʸˡ¤òÄêµÁ¤·¤¿¥Õ¥¡¥¤¥ë¤«¤é¹½Ê¸ ²òÀÏ¥×¥í¥°¥é¥à¤òÀ¸À®¤¹¤ë¥Ä¡¼¥ë¤Ç¤¢¤ë¡¥¤³¤³¤Ç¤Ï¡¤LALR(1) ʸˡ¤ä¹½Ê¸²òÀÏ ¥¢¥ë¥´¥ê¥º¥à¤Ê¤É¤Ë´Ø¤·¤Æ¤ÎÀâÌÀ¤Ê¤É¤Ï³ä°¦¤·(¥³¥ó¥Ñ¥¤¥é¤Î¶µ²Ê½ñ¤Ê¤É¤ò»² ¾È¤Î¤³¤È)¡¤Ê¸Ë¡ÄêµÁ¥Õ¥¡¥¤¥ë¤ÎÀâÌÀ¤ò parser.mly ¤ò¶ñÂÎÎã¤È¤·¤Æ¹Ô¤¦¡¥
ʸˡÄêµÁ¥Õ¥¡¥¤¥ë¤Ï°ìÈ̤ˡ¤°Ê²¼¤Î¤è¤¦¤Ë4¤Ä¤ÎÉôʬ¤«¤é¹½À®¤µ¤ì¤ë¡¥
%{ <¥Ø¥Ã¥À> %} <Àë¸À> %% <ʸˡµ¬Â§> %% <¥È¥ì¥¤¥é>
<¥Ø¥Ã¥À>, <¥È¥ì¥¤¥é> ¤Ï Objective Caml ¤Î¥×¥í¥°¥é¥à¤ò ½ñ¤¯Éôʬ¤Ç¡¤ocamlyacc ¤¬À¸À®¤¹¤ë parser.ml ¤Î¡¤¤½¤ì¤¾¤ìÀèƬ¡¦ ËöÈø¤Ë¤½¤Î¤Þ¤ÞËä¤á¹þ¤Þ¤ì¤ë¡¥<Àë¸À>¤Ï¥È¡¼¥¯¥ó(½ªÃ¼µ¹æ)¤ä¡¤ ³«»Ïµ¹æ¡¤Í¥ÀèÅ٤ʤɤÎÀë¸À¤ò¹Ô¤¦¡¥parser.mly ¤Ç¤Ï±é½¬¤òÄ̤·¤Æ¡¤ ³«»Ïµ¹æ¤È¥È¡¼¥¯¥ó¤ÎÀë¸À¤Î¤ß¤ò»ÈÍѤ¹¤ë¡¥<ʸˡµ¬Â§>¤Ë¤Ï ʸˡµ½Ò¤È´Ô¸µ»þ¤Î¥¢¥¯¥·¥ç¥ó¤òµ½Ò¤¹¤ë¡¥¥Ø¥Ã¥À¡¦¥È¥ì¥¤¥é¤Ç¤Ï¡¤ ¥³¥á¥ó¥È¤Ï Objective Caml ¤ÈƱÍÍ (* ... *) ¤Ç¤¢¤ê¡¤Àë¸À¡¦Ê¸Ë¡µ¬Â§Éôʬ¤Ç¤Ï C ¸À¸ì¤ÈƱÍͤʵˡ /* ... */ ¤Çµ½Ò¤¹¤ë¡¥
¤½¤ì¤Ç¤Ï parser.mly ¤ò¸«¤Æ¤ß¤è¤¦(¿Þ2)¡¥
%{ open Syntax %} %token LPAREN RPAREN SEMISEMI %token PLUS MULT LT EQ COLONCOLON %token IF THEN ELSE TRUE FALSE %token <int> INTV %token <Syntax.id> ID %start toplevel %type <Syntax.program> toplevel %% toplevel : Expr SEMISEMI { Exp $1 } Expr : IfExpr { $1 } | LTExpr { $1 } LTExpr : PExpr LT PExpr { BinOp (Lt, $1, $3) } | PExpr { $1 } PExpr : PExpr PLUS MExpr { BinOp (Plus, $1, $3) } | MExpr { $1 } MExpr : MExpr MULT AExpr { BinOp (Mult, $1, $3) } | AExpr { $1 } AExpr : INTV { ILit $1 } | TRUE { BLit true } | FALSE { BLit false } | ID { Var $1 } | LPAREN Expr RPAREN { $2 } IfExpr : IF Expr THEN Expr ELSE Expr { IfExp ($2, $4, $6) }
Figure 2: ML1 ¥¤¥ó¥¿¥×¥ê¥¿: parser.mly
¤³¤ÎʸˡÄêµÁ¥Õ¥¡¥¤¥ë¤Ç¤Ï¥È¥ì¥¤¥é¤Ï¶õ¤Ë¤Ê¤Ã¤Æ¤¤¤Æ¡¤¤½¤ÎÁ°¤Î%% ¤Ï¾Êά¤µ¤ì¤Æ¤¤¤ë¡¥
<Èó½ªÃ¼µ¹æ̾> : <µ¹æ̾11> ... <µ¹æ̾1n1> { <´Ô¸µ»þ¥¢¥¯¥·¥ç¥ó1> } | <µ¹æ̾21> ... <µ¹æ̾2n2> { <´Ô¸µ»þ¥¢¥¯¥·¥ç¥ó2> } ...¤Î¤è¤¦¤Ëµ½Ò¤¹¤ë¡¥<´Ô¸µ»þ¥¢¥¯¥·¥ç¥ó>¤Ë¤Ï Objective Caml ¤Î¼°¤òµ½Ò¤¹¤ë¡¥ $i ¤Ç¡¤iÈÖÌܤε¹æ¤Î°À¤ò»²¾È¤¹¤ë¤³¤È¤¬¤Ç¤¤ë¡¥¼°Á´ÂΤÎɾ²Á·ë²Ì¤¬¤³ ¤ÎÈó½ªÃ¼µ¹æ¤Î°À¤È¤Ê¤ë¤Î¤Ç¡¤¼°¤Î·¿¤ÏÁ´¤Æ°ìÃפ·¤Æ¤¤¤ëɬÍפ¬¤¢¤ë¡¥Î㤨 ¤Ð Exp ¤Ï Syntax.exp ·¿¤ÎÃÍ(¤Ä¤Þ¤ê ML1 ¤Î¼°¤ÎÃê¾Ý¹½Ê¸ÌÚ)¤ò° À¤È¤·¤Æ»ý¤Á¡¤³Æ¥¢¥¯¥·¥ç¥ó¤Ç¤Ï¡¤¤½¤ÎÀ¸À®µ¬Â§¤ËÂбþ¤¹¤ëÃê¾Ý¹½Ê¸ÌÚ¤òÀ¸À® ¤¹¤ë¤è¤¦¤Ê¼°¤¬½ñ¤«¤ì¤Æ¤¤¤ë¡¥
¿Þ2¤Îʸˡµ¬Â§¤¬¡¤¾å¤Ç½Ò¤Ù¤¿·ë¹ç¤Î¶¯¤µ¡¤º¸·ë¹ç¤Ê¤É¤ò ¼Â¸½¤·¤Æ¤¤¤ë¤³¤È¤ò³Î¤«¤á¤Æ¤â¤é¤¤¤¿¤¤¡¥
¤µ¤Æ¡¤¤³¤Î¹½Ê¸²òÀÏ´ï¤Ø¤ÎÆþÎϤȤʤë¥È¡¼¥¯¥óÎó¤ò À¸À®¤¹¤ë¤Î¤¬»ú¶ç²òÀÏ´ï¤Ç¤¢¤ë¡¥ocamllex ¤Ï lex ¤ÈƱÍÍ¤Ë ÀµÂ§É½¸½¤ò»È¤Ã¤¿Ê¸»úÎó¥Ñ¥¿¡¼¥ó¤òµ½Ò¤·¤¿¥Õ¥¡¥¤¥ë¤«¤é »ú¶ç²òÀÏ¥×¥í¥°¥é¥à¤òÀ¸À®¤¹¤ë¡¥.mll ¥Õ¥¡¥¤¥ë¤Ï¡¤
{ <¥Ø¥Ã¥À> } let <̾Á°> = <ÀµÂ§É½¸½> ... rule <¥¨¥ó¥È¥ê¥Ý¥¤¥ó¥È̾> = parse <ÀµÂ§É½¸½> { <¥¢¥¯¥·¥ç¥ó> } | <ÀµÂ§É½¸½> { <¥¢¥¯¥·¥ç¥ó> } | ... and <¥¨¥ó¥È¥ê¥Ý¥¤¥ó¥È̾> = parse ... and ... { <¥È¥ì¥¤¥é> }
¤È¤¤¤¦¹½À®¤Ë¤Ê¤Ã¤Æ¤¤¤ë¡¥¥Ø¥Ã¥À¡¦¥È¥ì¥¤¥éÉô¤Ë¤Ï¡¤Objective Caml ¤Î¥×¥í¥°¥é¥à ¤ò½ñ¤¯¤³¤È¤¬¤Ç¤¡¤ocamllex ¤¬À¸À®¤¹¤ë lexer.ml ¥Õ¥¡¥¤¥ë¤ÎÀèƬ¡¦ËöÈø ¤ËËä¤á ¹þ¤Þ¤ì¤ë¡¥¼¡¤Î let ¤ò»È¤Ã¤¿ÄêµÁÉô¤Ï¡¤¤è¤¯»È¤¦ÀµÂ§É½¸½¤Ë̾Á°¤ò ¤Ä¤±¤ë¤¿¤á¤ÎÉôʬ¤Ç¡¤lexer.mll ¤Ç¤Ï²¿¤âÄêµÁ¤µ¤ì¤Æ¤¤¤Ê¤¤¡¥Â³¤¯Éôʬ¤¬¥¨ ¥ó¥È¥ê¥Ý¥¤¥ó¥È¡¤¤Ä¤Þ¤ê»ú¶ç²òÀϤε¬Â§¤ÎÄêµÁ¤Ç¡¤Æ±Ì¾¤Î´Ø¿ô¤¬ ocamllex ¤Ë ¤è¤Ã¤ÆÀ¸À®¤µ¤ì¤ë¡¥µ¬Â§¤È¤·¤Æ¤ÏÀµÂ§É½¸½¤È¤½¤ì¤Ë¥Þ¥Ã¥Á¤·¤¿ºÝ¤Î¥¢¥¯¥·¥ç¥ó ¤ò(Objective Caml ¼°¤Ç)µ½Ò¤¹¤ë¡¥¥¢¥¯¥·¥ç¥ó¤Ï¡¤´ðËÜŪ¤Ë¤Ï(parser.mly ¤ÇÀë ¸À¤µ¤ì¤¿)¥È¡¼¥¯¥ó(Parser.token ·¿)¤òÊÖ¤¹¤è¤¦¤Ê¼°¤òµ½Ò¤¹¤ë¡¥¤Þ¤¿¡¤»ú ¶ç²òÀϤ˻ÈÍѤ¹¤ëʸ»úÎó¥Ð¥Ã¥Õ¥¡¤¬ lexbuf ¤È¤¤¤¦Ì¾Á°¤Ç»È¤¨¤ë¤¬¡¤Ä̾ï¤Ï °Ê²¼¤Î»ÈÍÑË¡¤Ç¤·¤«»È¤ï¤ì¤Ê¤¤¡¥
¤½¤ì¤Ç¤Ï¡¤¶ñÂÎÎã lexer.mll ¤ò»È¤Ã¤ÆÀâÌÀ¤ò¹Ô¤¦¡¥
{ let reservedWords = [ (* Keywords in the alphabetical order *) ("else", Parser.ELSE); ("false", Parser.FALSE); ("if", Parser.IF); ("then", Parser.THEN); ("true", Parser.TRUE); ] } rule main = parse (* ignore spacing and newline characters *) [' ' '\009' '\012' '\n']+ { main lexbuf } | "-"? ['0'-'9']+ { Parser.INTV (int_of_string (Lexing.lexeme lexbuf)) } | "(" { Parser.LPAREN } | ")" { Parser.RPAREN } | ";;" { Parser.SEMISEMI } | "+" { Parser.PLUS } | "*" { Parser.MULT } | "<" { Parser.LT } | ['a'-'z'] ['a'-'z' '0'-'9' '_' '']* { let id = Lexing.lexeme lexbuf in try List.assoc id reservedWords with _ -> Parser.ID id } | eof { exit 0 }
Figure 3: ML1 ¥¤¥ó¥¿¥×¥ê¥¿: lexer.mll
¥Ø¥Ã¥ÀÉô¤Ç¤Ï¡¤Í½Ìó¸ì¤Îʸ»úÎó¤È¡¤¤½¤ì¤ËÂбþ¤¹¤ë¥È¡¼¥¯¥ó¤ÎÏ¢Áۥꥹ¥È¤Ç¤¢ ¤ë¡¤reservedWords ¤òÄêµÁ¤·¤Æ¤¤¤ë¡¥¸å¤Ç¤ß¤ë¤è¤¦¤Ë¡¤List.assoc´Ø¿ô¤ò »È¤Ã¤Æ¡¤Ê¸»úÎ󤫤é¥È¡¼¥¯¥ó¤ò¼è¤ê½Ð¤¹¤³¤È¤¬¤Ç¤¤ë¡¥
¥¨¥ó¥È¥ê¥Ý¥¤¥ó¥ÈÄêµÁÉôʬ¤Ç¤Ï¡¤main ¤È¤¤¤¦(Í£°ì¤Î)¥¨¥ó¥È¥ê¥Ý¥¤¥ó¥È¤¬ ÄêµÁ¤µ¤ì¤Æ¤¤¤ë¡¥ºÇ½é¤ÎÀµÂ§É½¸½¤Ï¶õÇò¤ä¥¿¥Ö¤Ê¤Éʸ»ú¤ÎÎó¤Ë¥Þ¥Ã¥Á¤¹¤ë¡¥¤³ ¤ì¤é¤Ï ML¤Ç¤Ï¶èÀÚ¤êʸ»ú¤È¤·¤Æ̵»ë¤¹¤ë¤¿¤á¡¤¥È¡¼¥¯¥ó¤ÏÀ¸À®¤»¤º¡¤ ¸å³¤Îʸ»úÎ󤫤鼡¤Î¥È¡¼¥¯¥ó¤òµá¤á¤ë¤¿¤á¤Ë main lexbuf ¤ò¸Æ¤Ó½Ð¤·¤Æ ¤¤¤ë¡¥¼¡¤Ï¡¤¿ô»ú¤ÎʤӤ˥ޥåÁ¤·¡¤int_of_string ¤ò»È¤Ã¤Æ¥Þ¥Ã¥Á¤·¤¿Ê¸ »úÎó¤òint ·¿¤Ëľ¤·¤Æ¡¤¥È¡¼¥¯¥ó INTV (°À¤Ï int ·¿)¤òÊÖ¤¹¡¥Â³¤¤ ¤Æ¤¤¤ë¤Î¤Ï¡¤µ¹æ¤Ë´Ø¤¹¤ëÄêµÁ¤Ç¤¢¤ë¡¥¼¡¤Ï¼±Ê̻ҤΤ¿¤á¤ÎÀµÂ§É½¸½¤Ç¡¤±Ñ¾®Ê¸»ú¤Ç »Ï¤Þ¤ë̾Á°¤«¡¤±é»»µ¹æ¤Ë¥Þ¥Ã¥Á¤¹¤ë¡¥¥¢¥¯¥·¥ç¥óÉô¤Ç¤Ï¡¤¥Þ¥Ã¥Á¤·¤¿Ê¸»úÎó ¤¬Í½Ìó¸ì¤Ë´Þ¤Þ¤ì¤Æ¤¤¤ì¤Ð¡¤Í½Ìó¸ì¤Î¥È¡¼¥¯¥ó¤ò¡¤¤½¤¦¤Ç¤Ê¤±¤ì¤Ð(Îã³° Not_found ¤¬È¯À¸¤·¤¿¾ì¹ç¤Ï) ID ¥È¡¼¥¯¥ó¤òÊÖ¤¹¡¥ºÇ¸å¤Î eof ¤Ï¥Õ¥¡ ¥¤¥ë¤ÎËöÈø¤Ë¥Þ¥Ã¥Á¤¹¤ëÆüì¤Ê¥Ñ¥¿¡¼¥ó¤Ç¤¢¤ë¡¥¥Õ¥¡¥¤¥ë¤ÎºÇ¸å¤ËÅþ㤷¤¿¤é exit ¤¹¤ë¤è¤¦¤Ë¤·¤Æ¤¤¤ë¡¥
¤Ê¤ª¡¤¤³¤ÎÉôʬ¤Ï¡¤º£¸å¤â¤¢¤Þ¤êÊѹ¹¤¬É¬Íפ¬¤Ê¤¤¤Î¤Ç¡¤ÀµÂ§É½¸½¤òµ½Ò¤¹¤ë ¤¿¤á¤Îɽ¸½¤Ë¤Ä¤¤¤Æ¤Ï¤¢¤Þ¤ê¿¨¤ì¤Æ¤¤¤Ê¤¤¡¥¶½Ì£¤Î¤¢¤ë¤â¤Î¤Ï lex ¤ò²òÀ⤷ ¤¿ËܤäObjective Caml¥Þ¥Ë¥å¥¢¥ë¤ò»²¾È¤¹¤ë¤³¤È¡¥
¤µ¤Æ¡¤ËÜÀáËÁƬ¤Ç¤â½Ò¤Ù¤¿¤è¤¦¤Ë¡¤²ò¼áÉô¤Ï¡¤ÄêµÁ¤µ¤ì¤ë¸À¸ì¤Î¥»¥Þ¥ó¥Æ¥£¥¯ ¥¹¤òÄê¤á¤Æ¤¤¤ë¡¥¥×¥í¥°¥é¥ß¥ó¥°¸À¸ì¤Î¥»¥Þ¥ó¥Æ¥£¥¯¥¹¤òÄê¤á¤ë¤ËÅö¤¿¤Ã¤Æ½Å Íפʤ³¤È¤Ï¡¤¤É¤ó¤ÊÎत¤ÎÃͤò(ÄêµÁ¤µ¤ì¤ë¸À¸ì¤Î)¥×¥í¥°¥é¥à¤¬Áàºî¤Ç¤¤ë¤« ¤òÄêµÁ¤¹¤ë¤³¤È¤Ç¤¢¤ë¡¥¤³¤Î»þ¡¤¼°¤ÎÃÍ(expressed value)¤Î½¸¹ç¤È ÊÑ¿ô¤¬»Ø¼¨¤¹¤ëÃÍ(denoted value)¤Î½¸¹ç¤ò¶èÊ̤¹¤ë4¡¥º£²ó¤Î¼Â¸³¤ò¹Ô¤¦ÈϰϤǼÂÁõ¤¹¤ëµ¡Ç½¤ÎÈÏ °Ï¤Ç¤Ï¡¤¤³¤Î¤Õ¤¿¤Ä¤Ï°ìÃפ¹¤ë¤¬¡¤¤³¤ì¤é¤¬°Û¤Ê¤ë¸À¸ì¤âÄÁ¤·¤¯¤Ê¤¤¡¥Î㤨 ¤Ð¡¤C ¸À¸ì¤Ç¤Ï¡¤ÊÑ¿ô¤Ï¡¤Ãͤ½¤Î¤â¤Î¤Ë¤Ä¤±¤é¤ì¤¿Ì¾Á°¤Ç¤Ï¤Ê¤¯¡¤Ãͤ¬³ÊǼ¤µ ¤ì¤¿È¢¤Ë¤Ä¤±¤é¤ì¤¿Ì¾Á°¤È¹Í¤¨¤é¤ì¤ë¤¿¤á¡¤ denoted value ¤Ï expressed value ¤Ø¤Î»²¾È¤È¹Í¤¨¤ë¤Î¤¬¼«Á³¤Ë¤Ê¤ë¡¥ML1 ¤Î¾ì¹ç¡¤¼°¤Îɽ¤·¤¦¤ë ½¸¹ç Expressed Value ¤Ï
|
¤ÈÍ¿¤¨¤é¤ì¤ë¡¥+ ¤ÏľÏ¤ò¼¨¤·¤Æ¤¤¤ë¡¥
¤³¤Î¤³¤È¤òɽ¸½¤·¤¿ Objective Caml ¤Î·¿Àë¸À¤ò°Ê²¼¤Ë¼¨¤¹¡¥
(* Expressed values *) type exval = IntV of int | BoolV of bool and dnval = exval
¤â¤Ã¤È¤â´Êñ¤Ê²ò¼áÉô¤Î¹½À®Ë¡¤Î¤Ò¤È¤Ä¤Ï¡¤Ãê¾Ý¹½Ê¸Ìڤȡ¤ÊÑ¿ô¡¦denoted value ¤Î«Çû´Ø·¸¤ÎÁȤ«¤é¡¤¼Â¹Ô·ë²Ì¤ò·×»»¤¹¤ëÊý¼°¤Ç¤¢¤ë¡¥¤³¤Î¡¤ÊÑ¿ô¤Î«Çû ¤òɽ¸½¤¹¤ë¥Ç¡¼¥¿¹½Â¤¤ò´Ä¶(environment)¤È¤¤¤¤¡¤¤³¤ÎÊý¼°¤Ç ¼ÂÁõ¤µ¤ì¤¿¥¤¥ó¥¿¥×¥ê¥¿(²ò¼áÉô)¤ò´Ä¶ÅϤ·¥¤¥ó¥¿¥×¥ê¥¿(environment passing interpreter)¤È¤¤¤¦¤³¤È¤¬¤¢¤ë¡¥
¤³¤³¤Ç¤ÏÊÑ¿ô¤È denoted value ¤Î«Çû¤òɽ¸½¤Ç¤¤ì¤Ð½¼Ê¬¤Ê¤Î¤À¤¬¡¤ ¸åȾ¤Î·¿¿äÏÀ¤Ë¤ª¤¤¤Æ¤â¡¤ÊÑ¿ô¤Ë³äÅö¤Æ¤é¤ì¤¿·¿¤òɽ¸½¤¹¤ë¤¿¤á¤ËƱÍͤΠ¹½Â¤¤òÍѤ¤¤ë¤Î¤Ç¡¤ÈÆÍÑÀ¤ò¹Í¤¨¤ÆÀ߷פ·¤Æ¤ª¤¯¡¥
´Ä¶¤Î·¿¤Ï¡¤ÊÑ¿ô¤Ë´ØÏ¢ÉÕ¤±¤é¤ì¤ë¾ðÊó(¤³¤³¤Ç¤Ï denoted value)¤Î·¿¤ò 'a ¤È¤·¤Æ¡¤'a t ¤È¤¹¤ë¡¥´Ä¶¤òÁàºî¤¹¤ëÃͤä´Ø¿ô¤Î·¿¡¤Îã³°¤ò¼¨¤¹¡¥ (environment.mli¤ÎÆâÍƤǤ¢¤ë¡¥)
type 'a t exception Not_bound val empty : 'a t val extend : Syntax.id -> 'a -> 'a t -> 'a t val lookup : Syntax.id -> 'a t -> 'a val map : ('a -> 'b) -> 'a t -> 'b t val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
ºÇ½é¤ÎÃÍ empty_env ¤Ï¡¤²¿¤ÎÊÑ¿ô¤â«Çû¤µ¤ì¤Æ¤¤¤Ê¤¤¡¤¶õ¤Î´Ä¶¤Ç¤¢¤ë¡¥ ¼¡¤Î extend_env ¤Ï¡¤´Ä¶¤Ë¿·¤·¤¤Â«Çû¤ò¤Ò¤È¤ÄÉÕ¤±²Ã¤¨¤ë¤¿¤á¤Î´Ø¿ô¤Ç¡¤ extend_env id dnval env¤Ç¡¤´Ä¶ env ¤ËÂФ·¤Æ¡¤ÊÑ¿ô id ¤ò denoted value dnval ¤Ë«Çû¤·¤¿¤è¤¦¤Ê¿·¤·¤¤´Ä¶¤òɽ¤¹¡¥´Ø¿ô lookup ¤Ï¡¤´Ä ¶¤«¤éÊÑ¿ô¤¬Â«Çû¤µ¤ì¤¿Ãͤò¼è¤ê½Ð¤¹¤â¤Î¤Ç¡¤lookup id env ¤Ç¡¤´Ä¶ env ¤ÎÃæ¤ò¡¤¿·¤·¤¯²Ã¤ï¤Ã¤¿Â«Çû¤«¤é½ç¤ËÊÑ¿ô id ¤òõ¤·¡¤Â«Çû¤µ¤ì¤Æ¤¤ ¤ëÃͤòÊÖ¤¹¡¥ÊÑ¿ô¤¬´Ä¶Ãæ¤Ë̵¤¤¾ì¹ç¤Ï¡¤Îã³° Not_bound ¤¬È¯À¸¤¹¤ë¡¥
¤Þ¤¿¡¤´Ø¿ô map ¤Ï¡¤map f env ¤Ç¡¤³ÆÊÑ¿ô¤¬Â«Çû¤µ¤ì¤¿ÃÍ¤Ë f ¤òŬÍѤ·¤¿¤è¤¦¤Ê¿·¤·¤¤´Ä¶¤òÊÖ¤¹¡¥fold_right ¤Ï ´Ä¶Ãæ¤ÎÃͤò¿·¤·¤¤¤â¤Î¤«¤é½ç¤Ëº¸¤«¤éʤ٤¿¤è¤¦¤Ê¥ê¥¹¥È¤ËÂФ·¤Æ fold_right ¤ò¹Ô¤Ê¤¦¡¥¤³¤ì¤é¤Ï¡¤¸å¤Ë·¿¿äÏÀ¤Î¼ÂÁõ¤Ê¤É¤Ç»È¤ï¤ì¤ë¡¥
¤³¤Î´Ø¿ô·²¤ò¼ÂÁõ¤·¤¿¤â¤Î¤¬¿Þ4¤Ç¤¢¤ë¡¥´Ä¶¤Î¥Ç¡¼¥¿ ɽ¸½¤Ï¡¤Ã±¤Ê¤ëÏ¢Áۥꥹ¥È¤Ç¤¢¤ë¡¥¤¿¤À¤·¡¤environment.mli ¤Ç¤Ï 'a t ¤ÎÄêµÁ¤ò¼¨¤·¤Æ¤¤¤Ê¤¤¤Î¤Ç¡¤´Ä¶¤ò»È¤¦Â¦¤Ï¡¤¤½¤Î»ö¼Â¤ò³èÍѤ¹¤ë¤³¤È¤Ï¤Ç¤¤Ê¤¤¡¥
type 'a t = (Syntax.id * 'a) list exception Not_bound let empty = [] let extend x v env = (x,v)::env let rec lookup x env = try List.assoc x env with Not_found -> raise Not_bound let rec map f = function [] -> [] | (id, v)::rest -> (id, f v) :: map f rest let rec fold_right f env a = match env with [] -> a | (_, v)::rest -> f v (fold_right f rest a)
Figure 4: ML1 ¥¤¥ó¥¿¥×¥ê¥¿: ´Ä¶¤Î¼ÂÁõ (environment.ml)
°Ê²¼¤Ï¸å½Ò¤¹¤ë main.ml ¤Ëµ½Ò¤µ¤ì¤Æ¤¤¤ë¡¤ ¥×¥í¥°¥é¥à¼Â¹Ô³«»Ï»þ¤Î´Ä¶(Âç°è´Ä¶)¤ÎÄêµÁ¤Ç¤¢¤ë¡¥
let initial_env = Environment.extend "i" (IntV 1) (Environment.extend "v" (IntV 5) (Environment.extend "x" (IntV 10) Environment.empty))
i¡¤v¡¤x ¤¬¡¤¤½¤ì¤¾¤ì 1¡¤5¡¤10 ¤Ë«Çû¤µ¤ì¤Æ¤¤¤ë ¤³¤È¤òɽ¤·¤Æ¤¤¤ë¡¥¤³¤ÎÂç°è´Ä¶¤Ï¼ç¤ËÊÑ¿ô»²¾È¤Î¥Æ¥¹¥ÈÍѤǡ¤(¶õ¤Ç¤Ê¤±¤ì¤Ð)²¿ ¤Ç¤â¤è¤¤¡¥
°Ê¾å¤Î½àÈ÷¤ò¤¹¤ë¤È¡¤»Ä¤ê¤Ï¡¤Æó¹à±é»»»Ò¤Ë¤è¤ë¥×¥ê¥ß¥Æ¥£¥Ö±é»»¤ò¼Â¹Ô¤¹¤ëÉôʬ¤È¼°¤òɾ²Á ¤¹¤ëÉôʬ¤Ç¤¢¤ë¡¥Á°¼Ô¤ò apply_prim, ¸å¼Ô¤ò eval_exp ¤È¤¤¤¦´Ø¿ô¤È¤· ¤Æ¿Þ5¤Î¤è¤¦¤ËÄêµÁ¤¹¤ë¡¥eval_exp ¤Ç¤Ï¡¤À°¿ô¡¦¿¿µ¶ÃÍ¥ê¥Æ¥é¥ë (ILit, BLit )¤Ï¤½¤Î¤Þ¤ÞÃͤˡ¤ÊÑ¿ô¤Ï lookup ¤ò»È¤Ã¤ÆÃͤò¼è¤ê¤À¤·¡¤¥×¥ê ¥ß¥Æ¥£¥ÖŬÍѼ°¤Ï¡¤°ú¿ô¤È¤Ê¤ë¼°(¥ª¥Ú¥é¥ó¥É)¤ò¤½¤ì¤¾¤ìɾ²Á¤· apply_prim ¤ò¸Æ¤ó¤Ç¤¤¤ë¡¥apply_prim ¤ÏÍ¿¤¨¤é¤ì¤¿Æó¹à±é»»»Ò ¤Î¼ïÎà¤Ë¤·¤¿¤¬¤Ã¤Æ¡¤Âбþ¤¹¤ë Objective Caml ¤Î±é»»¤ò¤·¤Æ¤¤¤ë¡¥ if¼°¤Î¾ì¹ç¤Ë¤Ï¡¤¤Þ¤º¾ò·ï¼°¤Î¤ß¤òɾ²Á¤·¤Æ¡¤¤½¤ÎÃͤˤè¤Ã¤Æ thenÀá/elseÀá¤Î¼°¤òɾ²Á¤·¤Æ¤¤¤ë¡¥´Ø¿ô err ¤Ï¡¤ ¥¨¥é¡¼»þ¤ËÎã³°¤òȯÀ¸¤µ¤»¤ë¤¿¤á¤Î´Ø¿ô¤Ç¤¢¤ë(eval.ml »²¾È¤Î¤³¤È)¡¥
eval_decl ¤Ï ML1¤ÎÈϰϤǤÏñ¤Ë¼°¤ÎÃͤòÊÖ¤¹¤À¤±¤Î¤â¤Î¤Ç¤è¤¤¤Î ¤À¤¬¡¤¸å¤Ë¡¤letÀë¸À¤Ê¤É¤ò½èÍý¤¹¤ë»þ¤Î¤³¤È¤ò¹Í¤¨¤Æ¡¤¿·¤¿¤ËÀë¸À¤µ¤ì¤¿ ÊÑ¿ô̾(¤³¤³¤Ç¤Ï¥À¥ß¡¼¤Î"-")¤ÈÀë¸À¤Ë¤è¤Ã¤Æ³ÈÄ¥¤µ¤ì¤¿´Ä¶¤òÊÖ¤¹Àß·×¤Ë ¤Ê¤Ã¤Æ¤¤¤ë¡¥
let rec apply_prim op arg1 arg2 = match op, arg1, arg2 with Plus, IntV i1, IntV i2 -> IntV (i1 + i2) | Plus, _, _ -> err ("Both arguments must be integer: +") | Mult, IntV i1, IntV i2 -> IntV (i1 * i2) | Mult, _, _ -> err ("Both arguments must be integer: *") | Lt, IntV i1, IntV i2 -> BoolV (i1 < i2) | Lt, _, _ -> err ("Both arguments must be integer: <") let rec eval_exp env = function Var x -> (try Environment.lookup x env with Environment.Not_bound -> err ("Variable not bound: " ^ x)) | ILit i -> IntV i | BLit b -> BoolV b | BinOp (op, exp1, exp2) -> let arg1 = eval_exp env exp1 in let arg2 = eval_exp env exp2 in apply_prim op arg1 arg2 | IfExp (exp1, exp2, exp3) -> let test = eval_exp env exp1 in (match test with BoolV true -> eval_exp env exp2 | BoolV false -> eval_exp env exp3 | _ -> err ("Test expression must be boolean: if")) let eval_decl env = function Exp e -> let v = eval_exp env e in ("-", env, v)
Figure 5: ML1 ¥¤¥ó¥¿¥×¥ê¥¿: ɾ²ÁÉô¤Î¼ÂÁõ(eval.ml)¤ÎÈ´¿è
¥á¥¤¥ó¥×¥í¥°¥é¥à main.ml ¤ò¿Þ6¤Ë¼¨¤¹¡¥´Ø¿ô read_eval_print ¤Ç¡¤
½èÍý¤ò·«ÊÖ¤·¤Æ¤¤¤ë¡¥¤Þ¤º¡¤let decl = ¤Î±¦Êդǻú¶ç²òÀÏÉô¡¦¹½Ê¸²òÀÏÉô¤Î ·ë¹ç¤ò¹Ô¤Ã¤Æ¤¤¤ë¡¥lexer.mll ¤ÇÀë¸À¤µ¤ì¤¿ µ¬Â§¤Î̾Á° main ¤¬´Ø¿ô Lexer.main ¤Ë¡¤parser.mly (¤Î %start)¤Ç Àë¸À¤µ¤ì¤¿Èó½ªÃ¼µ¹æ¤Î̾Á° toplevel ¤¬´Ø¿ô Parser.toplevel ¤ËÂбþ ¤·¤Æ¤¤¤ë¡¥Parser.toplevel ¤ÏÂè°ì°ú¿ô¤È¤·¤Æ¹½Ê¸²òÀϴ狼¤é¸Æ¤Ó½Ð¤¹»ú¶ç ²òÀÏ´ï¤ò¡¤ÂèÆó°ú¿ô¤È¤·¤ÆÆɤ߹þ¤ß¥Ð¥Ã¥Õ¥¡¤òɽ¤¹ Lexing.lexbuf ·¿¤ÎÃÍ (¤³¤³¤Ç¤Ïɸ½àÆþÎϤ«¤éÆɤ߹þ¤à¤¿¤á Lexing.from_channel ¤ò»È¤Ã¤Æºî¤é¤ì¤Æ¤¤¤ë)¤ò¤È¤Ã ¤Æ¤¤¤ë¡¥pp_val ¤Ï eval.ml ¤ÇÄêµÁ¤µ¤ì¤Æ¤¤¤ë¡¤Ãͤò¥Ç¥£¥¹¥×¥ì¥¤¤Ë½ÐÎÏ ¤¹¤ë¤¿¤á¤Î´Ø¿ô¤Ç¤¢¤ë¡¥
open Syntax open Eval let rec read_eval_print env = print_string "# "; flush stdout; let decl = Parser.toplevel Lexer.main (Lexing.from_channel stdin) in let (id, newenv, v) = eval_decl env decl in Printf.printf "val %s = " id; pp_val v; print_newline(); read_eval_print newenv let initial_env = Environment.extend "i" (IntV 1) (Environment.extend "v" (IntV 5) (Environment.extend "x" (IntV 10) Environment.empty)) let _ = read_eval_print initial_env
Figure 6: mini Scheme1 ¥¤¥ó¥¿¥×¥ê¥¿: main.ml
iv + iii * ii¤Ê¤É¤ò»î¤·¤Æ¤ß¤è¡¥