Previous ToC Next

15. 柔軟な表示プログラム

赤木 :というわけでさくさく時間積分できるようになったから、色々なもの をプロットできるプログラムとか作れないか、という話ね。

学生C:x, y の代わりに x, z とか、速度空間とか、そういう話ですね?例え ば -x pos[0] -y pos[1] みたいなこととかですよね?

赤木 :そうなんだけど、もうちょっと色々、例えば -x 'pos[0]*vel[1]-pos[1]*vel[0]' で角運動量とか、そういうのができると 便利じゃない?

学生C:便利なのはわかりますが、どうやるんですか? Ruby とか Python な らもちろん、インタプリタだからこの文字列を実行時に評価、でいいわけです が、Crystal だとそうはいかないですよね?

赤木 :そうね。なので、考え方が多分3通りくらいあるの。

  1. 自前で簡単なインタプリタをもつ
  2. C の関数を生成してリンクする
  3. Crystal の関数を生成して全体をコンパイルしなおして実行する

学生C:どれがいいんでしょうか?

赤木 :ちょっと迷ってるから色々書いてみたんだけど、、、1はもちろん 安全で、あんまり難しくないんだけど、遅いのね。2は速度はいいんだけど、 どれくらい色々なことができるかはちょっとやってみないと。 3 は、毎回 Crystal のプログラム全体をコンパイルしなおしになるから さすがちょっと、、、

学生C:そういわれると2しかなさそうですが、、、

赤木 :あと、これ、プロットするプログラムが知らないデータ、つまり、 pos とか vel ではなくて、突然 密度とか温度とかストレスとか指定しても プロットできて欲しいじゃない?

学生C:でも、そうすると、型は与えるわけですね?

赤木 :そうね、必要ね。まあでも、浮動小数点数だけでもいいかも。

学生C:そうすると、Cでコードだしても、Crystal の側では結局 YAML の、ま だ構造体になってないデータから値を取り出すか、あるいはコマンドライン オプションで与えた型情報から粒子クラスを作ってコンパイルするかですよ ね、、、なんかインタプリタのほうがまだ簡単?

赤木 :まあ勉強も兼ねていわゆる LL(1) パーザ自分で書くのはどうかしら?そ んなに難しいことないはず。

学生C:なんかこう車輪の再発明感がありますが、、、、

赤木 :まあでも一度やってみないと、文法とか構文解析とか意味がわからな いから。

どういうことをしたいかというと、

  r[0]*v[1]-r[1]*vl[0]
とか

  sqrt(pos*pos)
とかいった表現から、Particle を読んでできてくるハッシュ構造からこれを 計算するためのデータ構造にしたいわけね。BNFっぽい文法で適当に書くと例 えばこんな感じ。

  expression -> [sign] term { add_op term}
  sign -> +|-
  add_op -> +|-
  term -> factor {mul_op factor}
  mul_op -> *|/
  factor -> variable|element|constant|function| (expression) 
  function -> function_name(parameter {,parameter})
  parameter -> expression
これ、 a+b+c みたいなのが expression で、

  expression -> [sign] term { add_op term}
は、最初の sign はあってもなくてもよくて、そのあとに term がきて、 そのあとに add_op term が0回以上繰り返す、という感じね。 で、 sign も add_op も + か - であると。 term も同じようにするけど今度は * か / で、 factor というものになると。で、factor は、 ここでは variable, element, constant, function と、あと expression に 括弧つけたもの、variable, element, constant はここで定義 してないけど、ここでは 1.5*m*(r[0]*v[1]-r[1]*v[0]) みたいなのがあるとすると、 m とか r[0] とか 1.5 とかを正規表現のパターンマッチで読むことにしましょ う。

学生C:すみません、全然わかりますません。

赤木 :まあもうちょっとまって。これで、何がほしいかというと、 1.5*m*(r[0]*v[1]-r[1]*v[0])が

  *--1.5
  |--*--m
     |--"-"--*--r[0]
         |   |--v[1]
         |-*--r[1]
           |--v[0]
みたいなツリー構造になって欲しいわけね。このツリー構造だと、 r[0]とかが実数値になれば、あとは演算子をみて計算していけるでしょ?

学生C:これになればいい、というのはわかりますが、どうすればこれになる のかは、、、

赤木 :まあその辺がコンパイラの理論のわりと本質だしね。 1.5*m*(r[0]*v[1]-r[1]*v[0])が 、 ["1.5", "*", "m", "*", "(", "r[0]", "*", "v[1]", "-", "r[1]", "*", "v[0]", ")"] と配列になってたとしましょう。これは正規表現のパターンマッ チだけでできるから。そうすると、これを左から順番に読むのがLL(1)構文解析なの ね。最初は 1.5 ね。

あ、正規表現って知っている?

学生C:なんか // の中に謎な文字列を書いてなんかするものというくらいで すが、、、

赤木 :そう。=~ っていう比較演算子が文字列と正規表現の間にあって、例え ば /aaa/ =~ "aaabbbccc" だと、単純に aaa が aaabbbcccの中にあれば場所 を返すし、/[a-z]/ =~ "a+b" だと a-z の間の文字が1つ最初にでてくる、こ の場合には a なので場所0、 /[a-z]+/ だとa-z の間の文字が1つ以上の繰り返し、みたいなのね。あと /([a-z]+)/ に括弧でくくると、そのパターンにあたる文字列が$1 みたいな特 別な変数に入るの。これは Perl 由来かしらね。あと、この例でわかるように 「[」とか「+」は正規表現の中で解釈されるから、文字としてその辺使うには 「\[」みたいにするの。あとは[a-z0-9]みたいにしてアルファベット小文字と 数字とかにできる、+ の代わりに * だと「0回」も対応、?だと0か1回、とか くらいかな?あ、あと、「^」が文字列の先頭、これ今回使うから、と 「$」が文字列の最後。まだ無限に沢山文法や機能があるけどこれくらいで 今回使うものには十分かな。

で、最初は一番上の expression かな?というとこから解析を始めるわけ。 なので、 expression という関数があって、これが、次の term を呼ぶ、だか ら

   def expression(token)
     if token[0].type == sign
       n = Node.new(operator= token[0], lhs=nil)
       token.shift
       n.rhs = expression(token)
     else
       n = term(token)
       while token[0].type == sign
          token.shift
          n=Node.new(token[0], n, term(token))
       end
     end
     n
   end
でいいのかしら?なんかこんな感じで動かないかなと。

学生C:あんまりわかってないですが、ちょっと書いてみます、、、

(数日後)

なんかできたかな、、、

   tokens= scan_expression_string( "1.5*m*(r[0]*v[1]-r[1]*v[0])")
   x= expression(tokens)
   x.ppp
と書くと
   gravity> crystal parser0.cr
           1.5(Constant)
       *
           m(Variable)
   *
               r[0](Element)
           *
               v[1](Element)
       -
               r[1](Element)
           *
               v[0](Element)
       a(Variable)
   Apply
               b(Variable)
           ,
               c(Variable)
       ,
           d(Variable)
   x # => #<NacsParser::Node:0x7ff200512c60
    @lhs=#<NacsParser::Token:0x7ff20050bc80 @s="a", @t=Variable>,
    @operator=#<NacsParser::Token:0x7ff20050bb60 @s="Apply", @t=Fapply>,
    @rhs=
     #<NacsParser::Node:0x7ff200512c90
      @lhs=
       #<NacsParser::Node:0x7ff200512cc0
        @lhs=#<NacsParser::Token:0x7ff20050bc20 @s="b", @t=Variable>,
        @operator=#<NacsParser::Token:0x7ff20050bc00 @s=",", @t=Comma>,
        @rhs=#<NacsParser::Token:0x7ff20050bc60 @s="c", @t=Variable>>,
      @operator=#<NacsParser::Token:0x7ff20050bbe0 @s=",", @t=Comma>,
      @rhs=#<NacsParser::Token:0x7ff20050bbc0 @s="d", @t=Variable>>>
   :481:7 in 'write_string'
     from /usr/share/crystal/src/string.cr:5022:5 in 'to_s'
     from /usr/share/crystal/src/io.cr:174:5 in '<<'
     from /usr/share/crystal/src/io.cr:188:5 in 'print'
     from /usr/share/crystal/src/kernel.cr:125:3 in 'print'
     from mkplummer.cr:172:3 in '__crystal_main'
     from /usr/share/crystal/src/crystal/main.cr:115:5 in 'main_user_code'
     from /usr/share/crystal/src/crystal/main.cr:101:7 in 'main'
     from /usr/share/crystal/src/crystal/main.cr:127:3 in 'main'
     from /lib/x86_64-linux-gnu/libc.so.6 in '__libc_start_main'
     from /home/makino/.cache/crystal/crystal-run-mkplummer.tmp in '_start'
     from ???
がでます。これはツリー構造を親ノードを左、子供を右の上下に書く コードで出力してます。

パーサーが、YACC の入力で与えられてるわけじゃなくて プログラムなので、本当にこれ?みたいなところがありますが、括弧ありで式 に直すと

  (1.5*m)*((r[0]*v[1])-(r[1]*v[0]))
で、大丈夫そうな気がします。

赤木 :これ関数とかもあるの?もうちょっと色々テストケースとかも必要ね。 まあでもとりあえず話を進めましょう。プログラムどんなの?

学生C:現状ではテストというか簡単なドライバもつけて

    1:module NacsParser
    2:  extend self
    3:include Math
    4:  # Grammar  
    5:  # expression -> [sign] term { add_op term}
    6:  # sign -> +|-
    7:  # add_op -> +|-
    8:  # term -> factor {mul_op factor}
    9:  # mul_op -> *|/
   10:  # factor -> variable|element|constant|function| (expression) 
   11:  # function -> function_name(parameters)
   12:  # parameters -> expression {,expression}
   13:  
   14:  extend self
   15:  enum Ttype
   16:    Add
   17:    Mul
   18:    Variable
   19:    Element
   20:    Constant
   21:    Open_Paren
   22:    Close_Paren
   23:    Comma
   24:    Fapply
   25:  end  
   26:
   27:  class Token
   28:    property s, t
   29:    def initialize(s : String,t : Ttype)
   30:      @s=s
   31:      @t=t
   32:    end
   33:    def ppp(currentindent : Int64 = 0,  indent : Int64 = 4)
   34:      print " "*currentindent, @s,"(#{@t.to_s})\n"
   35:    end
   36:  end
   37:
   38:  def scan_expression_string(s)
   39:    original_s=s
   40:    s= s.delete(" ")
   41:    tokens=Array(Token).new
   42:    while s.size>0
   43:      len = 1
   44:      if s[0] == '('
   45:        tokens.push(Token.new("(", Ttype::Open_Paren))
   46:      elsif s[0] == ')'
   47:        tokens.push(Token.new(")", Ttype::Close_Paren))
   48:      elsif  /^([1-9][0-9]*\.[0-9]*e[+-]?[0-9]+)/ =~ s
   49:        tokens.push(Token.new($1, Ttype::Constant))
   50:        len = $1.size
   51:      elsif  /^([1-9][0-9]*\.[0-9]*)/  =~ s
   52:        tokens.push(Token.new($1, Ttype::Constant))
   53:        len = $1.size
   54:      elsif  /^([1-9][0-9]*)/  =~ s
   55:        tokens.push(Token.new($1, Ttype::Constant))
   56:        len = $1.size
   57:      elsif /^([a-z_][a-z_0-9]*\[[0-9]+\])/ =~ s
   58:        tokens.push(Token.new($1, Ttype::Element))
   59:        len = $1.size
   60:      elsif /^([a-z_][a-z_0-9]*)/ =~ s
   61:        tokens.push(Token.new($1, Ttype::Variable))
   62:        len = $1.size
   63:      elsif /^([\+-])/ =~ s
   64:        tokens.push(Token.new($1, Ttype::Add))
   65:      elsif /^([\*\/])/ =~ s
   66:        tokens.push(Token.new($1, Ttype::Mul))
   67:      elsif s[0] == ','
   68:        tokens.push(Token.new(",", Ttype::Comma))
   69:      else
   70:        STDERR.print "Error unrecognizable expression\n"
   71:        pp! original_s
   72:        STDERR.print "Error at", s, "\n"      
   73:        exit
   74:      end
   75:      s = s[len..(s.size-1)]
   76:    end
   77:    tokens
   78:  end
   79:
   80:  class Node
   81:    property :operator, :lhs, :rhs
   82:    def initialize(operator : Token, lhs : (Node|Token|Nil) ,
   83:                   rhs : (Node|Token|Nil) )
   84:      @operator=operator
   85:      @lhs = lhs
   86:      @rhs = rhs
   87:    end
   88:    def ppp(currentindent : Int64 = 0,  indent : Int64 = 4)
   89:      @lhs.ppp(currentindent+indent, indent) if @lhs
   90:      print " "*currentindent, @operator.s,"\n"
   91:      @rhs.ppp(currentindent+indent, indent) if @rhs
   92:    end
   93:  end                                                                   
   94:  
   95:
   96:  def expression(token)
   97:    signs = Array(Token).new
   98:    while token[0].t== Ttype::Add
   99:      signs.push  token[0]
  100:      token.shift
  101:    end
  102:    n =  term(token)
  103:    while signs.size >0
  104:      op = signs.pop
  105:      n = Node.new(op, nil, n)
  106:    end
  107:    while token.size >0 && token[0].t== Ttype::Add
  108:      op= token.shift
  109:      n=Node.new(op, n, term(token))
  110:    end
  111:    n
  112:  end
  113:
  114:  def term(token)
  115:    n = factor(token)
  116:    while  token.size > 0 &&  token[0].t == Ttype::Mul
  117:      op= token.shift
  118:      n=Node.new(op, n, factor(token))
  119:    end
  120:    n
  121:  end
  122:
  123:  def factor(token)
  124:    if token[0].t== Ttype::Variable||token[0].t== Ttype::Element||
  125:       token[0].t== Ttype::Constant
  126:      n=token.shift
  127:      if token.size >1 &&token[0].t == Ttype::Open_Paren
  128:        token.shift
  129:        n=Node.new(Token.new("Apply", Ttype::Fapply), n, parameters(token))
  130:        if token[0].t == Ttype::Close_Paren
  131:          token.shift
  132:        else
  133:          print "error"
  134:          pp! n
  135:          pp! token
  136:        end
  137:      end
  138:    elsif token[0].t== Ttype::Open_Paren
  139:      token.shift
  140:      n=expression(token)
  141:      if token[0].t == Ttype::Close_Paren
  142:        token.shift
  143:      else
  144:        print "error"
  145:        pp! n
  146:        pp! token
  147:      end
  148:    end
  149:    n
  150:  end   
  151:
  152:  def parameters(token)
  153:    n = expression(token)
  154:    while  token.size > 0 &&  token[0].t == Ttype::Comma
  155:      op= token.shift
  156:      n=Node.new(op, n, expression(token))
  157:    end
  158:    n
  159:  end
  160:
  161:  def eval_expression(e : (Node|Token|Nil), t : YAML::Any)
  162:    val=0.0
  163:    if e.is_a?(Token)
  164:      if e.t == Ttype::Constant
  165:        val= e.s.to_f
  166:      elsif e.t == Ttype::Variable
  167:        val = t[e.s].as_f
  168:      elsif  e.t == Ttype::Element
  169:        /^([a-z_][a-z_0-9]*)\[([0-9]+)\]/ =~ e.s
  170:        vname=$1
  171:        index = ($2).to_i
  172:        val = t[vname][index].as_f
  173:      end
  174:    elsif e.is_a?(Node)
  175:      lhval=0.0
  176:      rhval=0.0
  177:      if e.operator.s== "Apply"
  178:        val = eval_function(e.lhs, e.rhs, t)
  179:      else
  180:        lhval = eval_expression(e.lhs, t) unless e.lhs.is_a?(Nil)
  181:        rhval = eval_expression(e.rhs, t) unless e.rhs.is_a?(Nil)
  182:        if e.operator.s== "+"
  183:          val = lhval+rhval
  184:        elsif e.operator.s== "-"
  185:          val = lhval-rhval
  186:        elsif e.operator.s== "*"
  187:          val = lhval*rhval
  188:        elsif e.operator.s== "/"
  189:          val = lhval/rhval
  190:        end
  191:      end
  192:    end      
  193:    val
  194:  end
  195:  
  196:  def eval_function(f : (Node|Token|Nil),
  197:                args : (Node|Token|Nil),
  198:                t : YAML::Any)
  199:    val=0.0
  200:    if f.is_a?(Token)
  201:      fname= f.s
  202:      vals=Array(Float64).new
  203:      while args.is_a?(Node) && args.operator.s == "Apply"
  204:        vals.unshift eval_expression(args.rhs, t)
  205:        args = args.lhs
  206:      end
  207:      vals.unshift eval_expression(args, t)
  208:      if fname == "sqrt"
  209:        val = sqrt(vals[0])
  210:      elsif fname == "exp"
  211:        val = exp(vals[0])
  212:      elsif fname == "log"
  213:        val = log(vals[0])
  214:      elsif fname == "exp"
  215:        val = exp(vals[0])
  216:      elsif fname == "pow"
  217:        val = vals[0]**vals[1]
  218:      end
  219:    end
  220:    val
  221:  end
  222:end
  223:
  224:struct  Nil
  225:  def ppp(currentindent : Int64 = 0,  indent : Int64 = 4)
  226:  end
  227:end
  228:
  229:include NacsParser
  230:
  231:tokens= scan_expression_string( "1.5*m*(r[0]*v[1]-r[1]*v[0])")
  232:
  233:x= expression(tokens)
  234:x.ppp
  235:
  236:
  237:
  238:token = 
  239:
  240:x= expression(scan_expression_string "a(b,c,d)")
  241:  
  242:x.ppp
  243:
  244:pp! x
  245:exit
  246:
  247:
  248:x= expression(scan_expression_string( "x(y,z)+f(xy)+r[0]*v[1]"))
  249:x.ppp
  250:
  251:x= expression(scan_expression_string( "x(y,z)+f(xy)+r[0]*v[a]"))
  252:x.ppp
  253:
  254:x= expression(scan_expression_string( "x(y,z)+f(xy)+r[0]*v[]"))
  255:x.ppp
です。中身ですが、NacsParser というモジュールにして、まず Ttype ですね。これは enum というやつで、C言語にもありますが、 0, 1, 2 ... に人にわかりやすい名前つける、というだけのものです。 Add が0、Mulが1みたいな。で、これはトークン、つまり、 a + b + c を "a", "+", "b", "+", "c" みたいにバラバラにしたあとで それぞれがどういう種類か、というものです。

その次は class Token で、トークンに対応する文字列と上の種類をもつクラ スを作ってます。あと、表示用の ppp という関数で、文字列と種類を表示し ます。enum を to_s でその名前の文字列にできるのは地味に便利ですね。 この辺は Ruby はなくて Python はあるというか 3.4 からだから割合最近?

で、その次の scan_expression_string が、文字列をトークンの配列に変換す る関数です。Lex とかのツール使うのが本当かもしれませんが、Cのプログラ ムでてきても面倒だし、Crystal 用のはないっぽいので正規表現とか文字の比 較で作りました。

まず、今回の文法ではスペースに意味がないので全部とります。なので、

 f ( x y )

 f(xy)
と同じみたいなだいぶアレな書き方もできます。

赤木 :昔の FORTRAN みたいね。

学生C:あ、そうだったんでしたっけ?

赤木 :そう。昔の FORTRAN だと

       E N D
とか

       R E T U R N
とか書いてあるコードがたまにあるわ。

学生C:できるからってしたらいいというものでもない気がしますが、、、

赤木 :まあね。でもそうすると、先頭の空白だけとるほうがよくない?

学生C:まあそうかもしれません。とりあえずこのまま説明すると、あと

      if s[0] == '('
        tokens.push(Token.new("(", Ttype::Open_Paren))
みたいなのが延々続きます。「()+-*/,」はこの文字が先頭にあったらその トークンと決まってるので、それだけです。あ、「+-」は正規表現ですね。

      elsif /^([\+-])/ =~ s
// の中が正規表現、 =~ が正規表現が文字列にマッチするかどうかの演算子、 「^」は文字列の先頭、 [xy]は文字 x と文字 y のどっちかですが、 + は特 別な意味があるので \+ とします。 - はしなくていいみたいです。 「*/」も同様で、これは両方とも \ でエスケープです。あと、 $1 は、正規 表現の中で括弧 () でくくった部分にマッチした文字列、というやつです。 括弧が複数あれば順番に $1, $2 となるんだと思います。

赤木 :

      elsif  /^([1-9][0-9]*\.[0-9]*e[+-]?[0-9]+)/ =~ s
は何?

学生C:これは、[1-9]で1から9まで、 次は [0-9]* ですが、ここでの * は前の文字が0回以上、次の \. は文字としての「.]、そのあとまた[0-9]が0回以上あって、「e]があって、 [+-]? は + か - が、0または1回、あとまた数字が、今度は + なので1回以上 ですね。要するに

 1.5e+10
みたいな、指数つきの浮動小数点数です。

赤木 :指数なしの 1.5 とか、小数点がない 10 とか、小数点がないけど指数 はあるとかは?

学生C:まだその辺全部は作ってないです。指数なしの 1.5 は

      elsif  /^([1-9][0-9]*\.[0-9]*)/  =~ s
かな。あと、今回の文法では a[1] みたいなのはもうトークンとして、という 話だったので、

      elsif /^([a-z_][a-z_0-9]*\[[0-9]+\])/ =~ s
で、文字または 「_」で始まって、文字または「_」または数字がきて、 そのあと「[」+数字(1個以上)+「]」を Element として、「[]」がないのを Variable としてます。

赤木 :定数の表現はまだちゃんとできてない、ということね。

学生C:はい。とりあえずなんか動いて欲しかったので。

赤木 :これの実行結果は?

学生C:例えば

  print tokens.map{|t| "[#{t.s},#{t.t}]"}.join(", "),"\n"
で書くと

  [1.5,Constant], [*,Mul], [m,Variable], [*,Mul], [(,Open_Paren],
  [r[0],Element], [*,Mul], [v[1],Element], [-,Add], [r[1],Element],
  [*,Mul], [v[0],Element], [),Close_Paren] 
ですね(適当に改行いれました)

赤木 :いい感じね。文法本体は?

学生C:LL(1) パーサを、ということだったので再帰下降パーサを 低レイヤを知りたい人のためのCコンパイラ作成入門 の再帰下降構文解析のとこを参考にしながら作りました。

まず class Node ですが、operator, lhs, rhs、つまり演算子、左側、右側を もつとします。左側、右側はそれぞれ Node か Token か nil としてます。 あと、印刷する関数を ppp で、再帰的に ppp を呼ぶ形で作りました。

赤木 :もうちょっと格好よくグラフの表示とかにして欲しい気もするけど、 テキストだけですむのはそれはそれで便利よね。パーサ本体は?

学生C:まず expression ですね。

  def expression(token)
    signs = Array(Token).new
    while token[0].t== Ttype::Add
      signs.push  token[0]
      token.shift
    end
    n =  term(token)
    while signs.size >0
      op = signs.pop
      n = Node.new(op, nil, n)
    end
    while token.size >0 && token[0].t== Ttype::Add
      op= token.shift
      n=Node.new(op, n, term(token))
    end
    n
  end
LL(1)文法に対する再帰下降パーサーって、基本的には、左側が 一段おりたもの、この場合には最初の

      n =  term(token)
なんですが、この文法では expression は 符号+ expression というのがある ので最初のトークンが符号にあたる Ttype::Add だったら符号憶えておきます。 複数符号あったら一応複数憶えておきます。 これ、赤木さんが最初に書いたやつ全然間違っててちょっと苦労しました。

赤木 :あら、そう?ごめんなさいね、、、

学生C:赤木さんのは再帰みたいにしてたんですが、それだと最初の符号が そのあとの式全体にかかるので式の意味が変わっちゃってました。今の コードはこれで多分正しいと思いますが、最初にでてきた term に、符号があれば

    while signs.size >0
のループで符号つけて新しいノードにしてます。

で、最後に、

    while token.size >0 && token[0].t== Ttype::Add
のループで、次の term をその前にある + か - で追加してます。これで、 沢山加算とか減算しても、ちゃんと正しく符号が考慮されます。

で、次が term で、これは符号がなくて演算子が */ だという以外は expression と同じで、但し term ではなくて factor を呼び出すことになり ます。その次がfactor で、これは

  factor -> variable|element|constant|function| (expression)
と、色々な可能性があるので少し複雑です。まず、 最初のトークンが Variable, Element, Constant のどれかの時ですが、 まだ関数かもしれないわけです。関数かどうかは次が括弧かどうかでみるとの で、これが 118 行目です。この時はさらに parameters を呼び出します。 parameters mの呼び出しから帰ってくると次のトークンは「)」のはずなので、 それをチェックします。

それ以外は、本当に Variable か Constant なので、そのトークン自体が factor の返り値になります。

そうでなければ最初が「(」のはずで、この時には expression のはずなので、 ということですね。ここで、 1*(2+3) みたいなのが処理できるわけです。

parameters は「,」を演算子として引数は expression であるとして並べてい く、という形で、これで引数が複数ある関数も書けます。

あと、このモジュールの外側ですが、 ppp が Nil に対して定義されてないと 文句いわれたので定義してます。

赤木 :まあ答がもっともらしいからとりあえず使えそうね。

学生C:再帰下降パーサって、全部できて、いわゆる終端記号、要するにトー クンですね、そこまで辿りつかないと何をするのか全然分からないのが なんか気持ち悪いというか、なんでこれで動くのかなという気がします。

動作をたどっていくと確かに動くんですが、、例えば f(x) みたいなのだと 最初のトークンは 「f」 で、 expression→ term → factor ときて、 ここで Variable なので、となって、次のトークンは 「(」だからここでは ツリー構造としては Type::Fapply を生成して、「(」まで読んでから parameters を呼ぶ、そうするとまた expression を呼んで、 ずーっとまた factor まできて、「x」 なのでまたVariable で 今度は次は「)」だからここで factor が 「x」を返す、で、 term に戻ってきて、次のトークンは「)」で */ じゃないので term も expression に戻って、次のトークンは「)」で */ じゃないので expression は parameters に戻って、ここでも 次のトークンは「)」で 「,」 じゃないので factor にもどって、 ここでちゃんと次は「)」で、これでちゃんと上手くできて もうトークンないので expression まで戻って抜ける、と確かにこうなるんで すが、なんかすごい複雑ですよね。

  expression 
    term     
       factor
          parameters
             expression
               term
                  factor
みたいに、これだけ関数呼ばれるわけで、、、

赤木 :そうねえ。これ、演算子の優先順位とあと括弧を表現するのに、 expression, term, factor という3種類の規則を作って、それに対応 して関数3個あるから、この3つの関数は必ずセットで呼ばれる、1つのもの みたいなところはあるわね。

でも、そうできた分、3つの関数のそれぞれは簡単になってるわけ。

ここまでできたら、後は粒子データとこの構文木から値を計算するだけね。

学生C:だけっていうのは簡単ですけどプログラム書くのは、、、まあやって みます。

(数時間後)

あれ、なんか簡単でした。YAML::Any と Node 渡して評価する関数が

  def eval_expression(e : (Node|Token|Nil), t : YAML::Any)
    val=0.0
    if e.is_a?(Token)
      if e.t == Ttype::Constant
        val= e.s.to_f
      elsif e.t == Ttype::Variable
        val = t[e.s].as_f
      elsif  e.t == Ttype::Element
        /^([a-z_][a-z_0-9]*)\[([0-9]+)\]/ =~ e.s
        vname=$1
        index = ($2).to_i
        val = t[vname][index].as_f
      end
    elsif e.is_a?(Node)
      lhval=0.0
      rhval=0.0
      lhval = eval_expression(e.lhs, t) unless e.lhs.is_a?(Nil)
      rhval = eval_expression(e.rhs, t) unless e.rhs.is_a?(Nil)
      if e.operator.s== "+"
        val = lhval+rhval
      elsif e.operator.s== "-"
        val = lhval-rhval
      elsif e.operator.s== "*"
        val = lhval*rhval
      elsif e.operator.s== "/"
        val = lhval/rhval
      end
    end      
    val
  end
これだけです。これは再帰的に自分を呼び出すんですが、 引数の e が Token だったら粒子データを見にいきます。 といっても Constant だったら浮動小数点文字列のはずなので to_f するだけ、 Variable なら、 YAML::Any はハッシュなので、 変数名で検索して返ってきた値を as_f で浮動小数点数にします。 Element なら、変数名と添字の値を取り出してから、 同様にハッシュから値を取り出します。

e がノードなら、演算子なわけで、あ、関数まだ書いてないので、 左側と右側のノードを評価してから、演算子に応じて計算するだけです。

これ使って絵書く関数は

    1:require "grlib"
    2:require "clop"
    3:require "./nacsio.cr"
    4:require "./parser.cr"
    5:include Math
    6:include GR
    7:include Nacsio
    8:
    9:optionstr= <<-END
   10:  Description: Plot program for multiple nacs snapshot
   11:  Long description: Plot program for multiple nacs snapshot
   12:
   13:  Short name:-w
   14:  Long name:  --window-size
   15:  Value type:  float
   16:  Variable name:wsize
   17:  Default value:1.5
   18:  Description:Window size for plotting
   19:  Long description:
   20:    Window size for plotting orbit. Window is [-wsize, wsize] for both of
   21:    x and y coordinates
   22:
   23:  Short name:-x
   24:  Long name:  --x_expression
   25:  Value type:  string
   26:  Variable name:xexp
   27:  Default value:r[0]
   28:  Description:Expression to use as x coordinate
   29:  Long description:     Expression to use as x coordinate
   30:
   31:  Short name:-y
   32:  Long name:  --y_expression
   33:  Value type:  string
   34:  Variable name:yexp
   35:  Default value:r[1]
   36:  Description:Expression to use as y coordinate
   37:  Long description:     Expression to use as y coordinate
   38:
   39:END
   40:
   41:clop_init(__LINE__, __FILE__, __DIR__, "optionstr")
   42:options=CLOP.new(optionstr,ARGV)
   43:include NacsParser
   44:
   45:pp! options
   46:
   47:xexp = expression(scan_expression_string(options.xexp))
   48:yexp = expression(scan_expression_string(options.yexp))
   49:
   50:update_commandlog
   51:ENV["GKS_DOUBLE_BUF"]= "true" 
   52:  
   53:wsize=options.wsize
   54:setwindow(-wsize, wsize,-wsize, wsize)
   55:setcharheight(0.05)
   56:setmarkertype(4)
   57:setmarkersize(1)
   58:sp= CP(Particle).read_particle
   59:while sp.y != nil
   60:  pp=[sp.y]
   61:  time = sp.p.time
   62:  pp! time
   63:  while (sp= CP(Particle).read_particle).y != nil && sp.p.time == time
   64:    pp.push sp.y
   65:  end
   66:  clearws() 
   67:  box
   68:  mathtex(0.5, 0.06, "x")
   69:  mathtex(0.06, 0.5, "y")
   70:  text(0.6,0.91,"t="+sprintf("%.3f", time))
   71:  polymarker(pp.map{|p| eval_expression(xexp,p)},
   72:             pp.map{|p| eval_expression(yexp,p)})
   73:  updatews()
   74:end
   75:c=STDERR.gets
で、これは前の単に x,y プロットするのとの違いをみたほうが早いですね。

   gravity> diff -C0 nacsplot1.cr nacsplot2.cr
   *** nacsplot1.cr2020-05-24 18:52:29.933399329 +0900
   --- nacsplot2.cr2020-05-26 00:43:36.661914327 +0900
   ***************
   *** 3 ****
   --- 4 ----
   + require "./parser.cr"
   ***************
   *** 20 ****
   --- 22,38 ----
   + 
   +   Short name:-x
   +   Long name:  --x_expression
   +   Value type:  string
   +   Variable name:xexp
   +   Default value:r[0]
   +   Description:Expression to use as x coordinate
   +   Long description:     Expression to use as x coordinate
   + 
   +   Short name:-y
   +   Long name:  --y_expression
   +   Value type:  string
   +   Variable name:yexp
   +   Default value:r[1]
   +   Description:Expression to use as y coordinate
   +   Long description:     Expression to use as y coordinate
   + 
   ***************
   *** 24 ****
   --- 43,49 ----
   + include NacsParser
   + 
   + pp! options
   + 
   + xexp = expression(scan_expression_string(options.xexp))
   + yexp = expression(scan_expression_string(options.yexp))
   + 
   ***************
   *** 35,36 ****
   !   pp=[sp.p]
   !   time = pp[0].time
   --- 60,61 ----
   !   pp=[sp.y]
   !   time = sp.p.time
   ***************
   *** 39 ****
   !     pp.push sp.p
   --- 64 ----
   !     pp.push sp.y
   ***************
   *** 45,46 ****
   !   text(0.6,0.91,"t="+sprintf("%.3f",pp[0].time))
   !   polymarker(pp.map{|p| p.pos[0]}, pp.map{|p| p.pos[1]})
   --- 70,72 ----
   !   text(0.6,0.91,"t="+sprintf("%.3f", time))
   !   polymarker(pp.map{|p| eval_expression(xexp,p)},
   !              pp.map{|p| eval_expression(yexp,p)})
parser.cr を require して、オプションで式を与えるのを x, y の 2個追加してます。それから、粒子クラスの sp.p じゃなくて、 YAML のままの sp.y のほうを配列にいれます。で、最後、 x座標が p.pos[0] だったのが eval_expression(xexp,p)、 y座標も同様ですね。なんか思ったより簡単でした。

赤木 :まあこれエラー処理とかしてないし、まだ関数ないし、速度も あんまり、みたいなところはあるわね。でも、よくできました。大変結構。

15.1. 課題

  1. トークン生成のところに、整数と 1e20 のような小数点以下がなくて指数 がある浮動小数点数を認識する規則を追加せよ。
  2. 関数 (例えば sqrt と exp) を追加せよ。
  3. (オプションではなくてソースプログラムの中で)このインタプリタで使え る関数を追加する方法を考えてみよ。
  4. 複数の引数をもつ関数も実装できるようにせよ。

15.2. まとめ

  1. 再帰下降型構文解析により、粒子データの物理量から新しい量を計算する 関数を作り、それを画面表示できるようにした。
  2. 構文解析には、トークン化(字句解析)と文法解析がある。 今回は、トークン化には正規表現を、文法解析には再帰下降型構文解析を 実装することでおこなった。
  3. is_a? 関数である変数の型をチェックできる。チェックしてそれが 正しいブロックの中では、その型を引数にする関数を使える。

15.3. 参考資料

低レイヤを知りたい人のためのCコンパイラ作成入門

Crystal のclass Regex

pcre2pattern man page Crystal が使っている正規表現ライブラリの文法解説
Previous ToC Next