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通りくらいあるの。
-
自前で簡単なインタプリタをもつ
-
C の関数を生成してリンクする
-
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. 課題
-
トークン生成のところに、整数と 1e20 のような小数点以下がなくて指数
がある浮動小数点数を認識する規則を追加せよ。
-
関数 (例えば sqrt と exp) を追加せよ。
-
(オプションではなくてソースプログラムの中で)このインタプリタで使え
る関数を追加する方法を考えてみよ。
-
複数の引数をもつ関数も実装できるようにせよ。
15.2. まとめ
-
再帰下降型構文解析により、粒子データの物理量から新しい量を計算する
関数を作り、それを画面表示できるようにした。
-
構文解析には、トークン化(字句解析)と文法解析がある。
今回は、トークン化には正規表現を、文法解析には再帰下降型構文解析を
実装することでおこなった。
-
is_a? 関数である変数の型をチェックできる。チェックしてそれが
正しいブロックの中では、その型を引数にする関数を使える。
15.3. 参考資料
低レイヤを知りたい人のためのCコンパイラ作成入門
Crystal のclass Regex
pcre2pattern man page Crystal が使っている正規表現ライブラリの文法解説