2014/04/18

Recent entries from same category

  1. Zenn で Twitter bot 作成入門を書いた。
  2. プログラマーのための新しい情報共有コミュニティ Zenn で本を書いてみた。
  3. Windows ユーザは cmd.exe で生きるべき 2020年版
  4. Let's Encrypt を簡単操作できる CLI、Lego が MyDNS に対応した。
  5. golang でメモ専用コマンド「memo」作った。

Big Sky :: プログラミング言語の作り方
Big Sky :: プログラミング言語の作り方(2)
Big Sky :: プログラミング言語の作り方(3)
Big Sky :: プログラミング言語の作り方(4)

本来ならばここらあたりでエラー処理とか例外を入れるべきでしたが、先に以下の実装を行いました。
  • 配列
  • ハッシュ
  • 配列要素へのアクセス
  • ハッシュ要素へのアクセス
  • if
  • while
  • for
  • return
  • break
  • continue
現在のシンタックスは以下の通り。 #define STRUCTURE \
"                                                                       \n" \
"number     : /-?[0-9]+(\\.[0-9]*)?(e[0-9]+)?/ ;                         \n" \
"true       : \"true\" ;                                                 \n" \
"false      : \"false\" ;                                                \n" \
"nil        : \"nil\" ;                                                  \n" \
"factor     : '(' <lexp> ')'                                             \n" \
"           | <number>                                                   \n" \
"           | <string>                                                   \n" \
"           | <array>                                                    \n" \
"           | <hash>                                                     \n" \
"           | <true>                                                     \n" \
"           | <false>                                                    \n" \
"           | <nil>                                                      \n" \
"           | <call>                                                     \n" \
"           | <new>                                                      \n" \
"           | <ident> ;                                                  \n" \
"string     : /\"(\\\\.|[^\"])*\"/ ;                                     \n" \
"item       : <factor> ('[' <lexp> ']')+ ;                               \n" \
"prop       : <factor> ('.' <ident>)+ ;                                  \n" \
"cmp        : <factor>                                                     " \
"         (\"!=\" | \"==\" | \"<=\" | \"<\" | \">=\" | \">\" )             " \
"         <factor> ;                                                     \n" \
"call       : <ident> '(' <lexp>? (',' <lexp>)* ')' ;                    \n" \
"anoncall   : <factor> '(' <lexp>? (',' <lexp>)* ')' ;                   \n" \
"methodcall : <prop> '(' <lexp>? (',' <lexp>)* ')' ;                     \n" \
"array      : '[' <lexp>? (',' <lexp>)* ']' ;                            \n" \
"pair       : <string> ':' <lexp> ;                                      \n" \
"hash       : '{' <pair>? (',' <pair>)* '}' ;                            \n" \
"ident      : /[a-zA-Z_][a-zA-Z0-9_]*/ ;                                  \n" \
"                                                                        \n" \
"term       : (<lambda> | <item> | <methodcall> | <cmp> | <prop>           " \
"         | <anoncall> | <call>                                          \n" \
"         | <factor> (('*' | '/' | '%') <factor>)*) ;                    \n" \
"lexp       : <term> (('+' | '-') <term>)* ;                             \n" \
"let_v      : <ident> '=' <lexp> ';' ;                                   \n" \
"let_a      : <item> '=' <lexp> ';' ;                                    \n" \
"let_p      : <prop> '=' <lexp> ';' ;                                    \n" \
"else_if    : \"else\" \"if\" '(' <lexp> ')' '{' <stmts> '}' ;           \n" \
"else       : \"else\" '{' <stmts> '}' ;                                 \n" \
"if_stmt    : \"if\" '(' <lexp> ')' '{' <stmts> '}' ;                    \n" \
"if         : <if_stmt> <else_if>* <else>? ;                             \n" \
"while      : \"while\" '(' <lexp> ')' '{' <stmts> '}' ;                 \n" \
"for_in     : \"for\" '(' <ident> \"in\" <lexp> ')' '{' <stmts> '}' ;    \n" \
"var        : \"var\" <ident> '=' <lexp> ';' ;                           \n" \
"vararg     : \"...\" ;                                                  \n" \
"stmts      : <stmt>* ;                                                  \n" \
"                                                                        \n" \
"lambda     : \"func\"                                                     " \
"         '(' <ident>? (<vararg> | (',' <ident>)*) ')' '{' <stmts> '}' ; \n" \
"func       : \"func\" <ident>                                             " \
"         '(' <ident>? (<vararg> | (',' <ident>)*) ')' '{' <stmts> '}' ; \n" \
"template   : (<var> | <func>)* ;                                        \n" \
"class      : \"class\" <ident> '{' <template> '}' ;                     \n" \
"new        : \"new\" <ident> '(' <lexp>? (',' <lexp>)* ')' ;            \n" \
"                                                                        \n" \
"break      : \"break\" ';' ;                                            \n" \
"continue   : \"continue\" ';' ;                                         \n" \
"return     : \"return\" <lexp> ';' ;                                    \n" \
"comment    : /#[^\n]*/ ;                                                \n" \
"eof        : /$/ ;                                                      \n" \
"stmt       : (<let_v> | <let_a> | <let_p> | <var> | <if>                  " \
"         | <while> | <for_in>                                             " \
"         | <func> | <class> | <return> | <break>                        \n" \
"         | <continue> | <comment> | (<lexp> ';')) ;                     \n" \
"program    : <stmts> <eof> ;                                            \n"
配列 array は簡単ですね。lexp がカンマ区切りになっているだけです。
"array      : '[' <lexp>? (',' <lexp>)* ']' ;                            \n" \
ハッシュは少し難しくなります。まずキーと値を組にした pair という物を宣言し、それの繰り返しという定義となります。 "pair       : <string> ':' <lexp> ;                                      \n" \
"hash       : '{' <pair>? (',' <pair>)* '}' ;                            \n" \
配列、ハッシュの要素へのアクセスですが、実装方法にもよりますが代入左項を lexp として処理してしまい a[1] = 2;
値の参照のみを行ってしまうと、実際に要素を変更する a への変更が出来ません。値の出所をリファレンスで持っておくのも良いですが、面倒なので要素代入というステートメントで処理しています。

if、else if、else はそれぞれ AST を処理しやすい様に以下の構造を作りました。 #!ore
if (0) {
  println("foo");
else if (false) {
  println("boo");
else {
  println("zoo");
}
ref array 1 008CB850

  stmts|> 
    stmt|comment|regex:1:1 '#!ore'
    if|> 
      if_stmt|> 
        string:2:1 'if'
        char:2:4 '('
        lexp|term|factor|number|regex:2:5 '0'
        char:2:6 ')'
        char:2:8 '{'
        stmt|> 
          call|> 
            ident|regex:3:3 'println'
            char:3:10 '('
            lexp|term|factor|string|regex:3:11 '"foo"'
            char:3:16 ')'
          char:3:17 ';'
        char:4:1 '}'
      else_if|> 
        string:4:3 'else'
        string:4:8 'if'
        char:4:11 '('
        lexp|term|factor|false|string:4:12 'false'
        char:4:17 ')'
        char:4:19 '{'
        stmt|> 
          call|> 
            ident|regex:5:3 'println'
            char:5:10 '('
            lexp|term|factor|string|regex:5:11 '"boo"'
            char:5:16 ')'
          char:5:17 ';'
        char:6:1 '}'
      else|> 
        string:6:3 'else'
        char:6:8 '{'
        stmt|> 
          call|> 
            ident|regex:7:3 'println'
            char:7:10 '('
            lexp|term|factor|string|regex:7:11 '"zoo"'
            char:7:16 ')'
          char:7:17 ';'
        char:8:1 '}'
  eof|regex 
AST をそのまま保持しておき、条件を実行した結果でどのステートメント群を実行するかを処理します。 if (is_a(t, "if")) {
  ore_value v;
  int i;
  for (i = 0; i < t->children_num; i++) {
    int r = 0;
    mpc_ast_t* f = t->children[i];
    if (is_a(f, "if_stmt")) {
      r = ore_is_true(ore_eval(ore, f->children[2]));
    } else if (is_a(f, "else_if")) {
      r = ore_is_true(ore_eval(ore, f->children[3]));
    } else {
      r = 1;
    }
    if (r)
      return ore_eval(ore, ore_find_statements(f));
  }
  return ore_value_nil();
}
for や while も同様です。ようやくフィボナッチ数の計算が出来る様になりました。
func fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n-2) + fib(n-1);
}

println(fib(20));
実はリポジトリ内では既にクラスオブジェクトの生成が出来る様になっています。興味のある方はこちらからどうぞ。
mattn/orelang - GitHub

俺言語

https://github.com/mattn/orelang
さて、今日は本当ならばエラー処理を書きたかったのですが実は使っているパーサの mpc が AST から行番号を取れないという問題を見つけ、問題報告していた為に実装出来ませんでした。

Hope to get code location from mpc_ast_t ・ Issue #4 ・ orangeduck/mpc - GitHub

Hey. This should be added in the newest version. You can use the state member of mpc_ast_t . You can...

https://github.com/orangeduck/mpc/issues/4
報告したら実装してくれましたので、今度はエラー処理を書こうと思います。

実は、言語処理系を実装する上で少し面倒なのが return なのです。return は大域脱出になりえます。
例えば関数の中に if 文があり、その中に for 文があり、その中で return 文があると、その if 文や for 文をキャンセルして戻り値と共に大域脱出する必要があります。この実装に longjmp/setjmp を使う言語処理系もありますが、今回は return をエラーと見立ててあらゆる箇所で中断処理を実行させ、関数処理内に戻ってきたらエラー扱いではなく正しい return として処理させるという方法を使っています。
なので例えば関数内でなければ不正なエラーとなる訳です。逆に都合がいいですね。break や continue も同じ手法を使っています。

Posted at by