情報科学(10-11) 言語処理系と仮想機械

目次 数式を読み込んで式木を生成する 式木からその式の値を計算する，仮想機械の機械語プログラムを生成する 仮想機械を作り，生成された機械語プログラムを実行する

while true do p eval(gets) end Ruby Rubyで書くと， while true do p eval(gets) end ...それはともかく

木構造（tree） 復習 式木と呼ぶ 数式の構造は木構造になじむ ÷ － ＋ 1 3 × 5 × 冪 2 数式を扱おうとすると，因数分解や展開でどんど ん数式の形が変わる このようにあらかじめデータの大きさも形も予測 できない場合，ポインタを使って自由に大きさを 変えられるとうれしい 冪 2

ここで対象とする数式 数値: 自然数(0を含む) 演算: 四則演算(+, -, *, /) 演算の順序 カッコ内の演算を優先: (1+2)*3では + を * より先に計算 *, / を +, - より優先: 1+2*3は，1+(2*3)と解釈 左を右より優先: 1-2-3は(1-2)-3と解釈

数式から式木への変換の流れ 1 - 2 * 3 文字列: "1-2*3" 字句解析 トークン列: 1, -, 2, *, 3 構文解析 式木: 1 - 2 * 3

字句解析 字句解析: 入力の文字列を解析して，数値や識別子などのトークンに変換すること トークンは有限(状態)オートマトンを使って切り出す "123" や "MyName" のように複数文字をまとめる 「123」は数値，「MyName」は識別子というように種別を判定する トークンは有限(状態)オートマトンを使って切り出す

有限オートマトン 状態遷移による計算は，計算が状態空間を移動してゆくものと考えられる 有限オートマトンに対応 → 数理的なモデル 復習 　　→ 数理的なモデル 状態空間 f'(4,4) →f'(3,12) → f'(2,24) →f'(1,24) → 24

自然数を受理する有限オートマトン 受理状態 初期状態 0,1,2,3,4,5,6,7,8,9 0,1,2,3,4,5,6,7,8,9 入力が"123+567"の場合，1を読むだけでも受理状態になるが，通常は進めなくなるまでどんどん（greedy）に進める

準備: 次の文字を見る # 文字列$lineの先頭文字を覗く # 次回も同じ文字が見える Ruby # 文字列$lineの先頭文字を覗く # 次回も同じ文字が見える def peekChar() $line[0..0] end 先頭の文字 $line[0]は文字コードになって しまうので注意 # $lineの先頭文字を使う # 次回は次の文字が見える def getChar() 　　 ch = peekChar 　 $line[0..0] = "" return ch end 先頭の文字を除く 準備: 次の文字を見る

# 自然数の読み取り def getNumber value = getChar.to_i Ruby =~で一致するかどうか計算する． # 自然数の読み取り def getNumber value = getChar.to_i while peekChar =~ /[0-9]/ value = 10*value+(getChar.to_i) end return value end /[0-9]/は0から9の間の文字，つまり数字 to_iで文字列から数値に変換 初期状態 0,1,2,3,4,5,6,7,8,9 受理状態

字句解析 $type: トークンの種別 自然数なら :NUMBER 記号なら :SYMBOL Ruby 字句解析 def nextToken if peekChar =~/ [0-9]/ $type = :NUMBER; $value = getNumber else $type = :SYMBOL; $value = {"+"=>:+, "-"=>:-, "*"=>:*, "/" =>:/, "("=>:lpar, ")"=>:rpar}[getChar] end getChar の値が "+" なら {…}[getChar] の値は :+ となる {“+”=>:+,...} はハッシュ．f["+"]=:+ となる関数 f $type: トークンの種別　自然数なら :NUMBER 記号なら :SYMBOL $value: トークンが自然数ならその値，記号なら記号を表すシンボルを保持する

構文解析 構文解析: トークンがどのように組み合わさっていくかを解析 組み合わさり方は文法で定義する

再帰的データ構造 リスト構造 ::= セル | nil | 数や文字列などの基本データ型 セル ::= リスト構造とリスト構造の対 木構造 復習 再帰的データ構造 ::= は「定義」の意味 | （縦棒）は「または」と読む リスト構造 ::= セル | nil | 数や文字列などの基本データ型 セル ::= リスト構造とリスト構造の対 木構造 ::= 変数名 | 数 | 木構造と演算子と木構造の3組 このような記法はBNF(Backus-Naur Form) と呼ばれ，文法の記述によく使われる

BNF トークン(終端記号): 字句要素 例: 0, 1 生成規則: 非終端記号 ::= トークンと非終端記号の列 左辺から右辺を導出できることを示す 左辺が等しいものは右辺を「|」で区切ってまとめる 例: <B> ::= 0 <B> | 1 <B> | ε 開始記号: 非終端記号の一つ 例: <B> εは空列を表す

数式（式）のBNF 優先順位を表すために以下の非終端記号を導入する <E>: 式(expression) 例 8-4/(7-5) <T>: 項(term) 例 4/(7-5) <F>: 因子(factor) 例 8 例 (7-5)

式のBNF 簡単のため 変数はない <E> ::= <E> + <T> | <E> - <T> | <T> <T> ::= <T> * <F> | <T> / <F> | <F> <F> ::= NUMBER | ( <E> ) トークンは赤で示した NUMBER は数値のトークン 開始記号から生成規則を使って導出を繰り返すことで木ができる．この木を解析木という． 解析木の葉を左から右に順に並べたトークン列は，この文法で受理されるという． 受理されるトークン列を全て集めたものを，この文法が定義する言語という．

8+4/(7-5)は式か? 開始記号 <E> <E> + <T> <T> <T> <T> ::= <T> / <F>で導出 <T> <T> / <F> ( <E> ) <F> <F> NUMBER:8 <E> <T> - NUMBER:4 8+4/(7-5)は受理される つまり，8+4/(7-5)は式 <T> <F> <F> NUMBER:5 NUMBER:7

1++2は式か? <E> <E> <T> + ？ <T> <F> NUMBER:1 + が2つ並ぶような解析木は作れないので，1++2は受理されない つまり，1++2 は（ここで考えている）式ではない．

ここでα，β，γは終端記号あるいは非終端記号の列を意味する 文法の階層(チョムスキー階層) 政治的発言も しています． ここでα，β，γは終端記号あるいは非終端記号の列を意味する Noam Chomsky タイプ-0文法: チューリングマシンが受理する言語 タイプ-1文法: 文脈依存文法 生成規則: αAβ ::= αγβの形式 タイプ-2文法: 文脈自由文法 生成規則: A ::= γの形式 タイプ-3文法: 正規表現 有限オートマトンが受理する言語 指定できる範囲が広い(強い) 今やっているのはこれ 指定できる範囲が狭い(弱い)

FAQ Q. 正規表現より文脈自由文法の方が強力なのであれば，字句解析を構文解析にまとめてしまえるのではないか？

解析木の作り方 開始記号 <E> <E> + <T> <E> + <T> いくら導出しても，入力トークン列の先頭と比較するところがでてこない 開始記号から下向きに式の解析木を作ろうとすると堂々巡りになって止まらない (悪い再帰)

左再帰の問題 左再帰: ある非終端記号<A>から導出(生成規則の左辺を右辺に置き換えること)を繰り返した時に，<A>γ のように，最も左に同じ非終端記号Aが生じることがあるなら，文法は左再帰であるという この堂々巡りは，対象(この例では式)の性質ではなく，文法(の書き方）の性質

左再帰の除去 <E> ::= <T> <E’> 文法を書き換えることで，言語を変えずに，左再帰を除去できることがある εは空列 <E> ::= <T> <E’> <E’> ::= + <T> <E’> | - <T> <E’> | ε <T> ::= <F> <T’> <T’> ::= * <F> <T’> | / <F> <T’> | ε <F> ::= NUMBER | ( <E> )

<E’> ::= + <T> <E’> | - <T> <E’> | ε <T’> ::= * <F> <T’> | / <F> <T’> | ε <F> ::= NUMBER | ( <E> ) 一部の再掲 この文法では，一つの非終端記号に対して，複数の生成 規則がある場合，トークンを一つ先読みすれば どの生 成規則を使うべきか分かる 再帰下降構文解析: 開始記号から出発して，先読みしたトークンにより決まる生成規則を使って解析木を作る方法 以下では，解析木の一部を消しながら式木を作る

部分木の作り方は少し違う．「-」などの四則演算は 以下では，解析木の一部を消しながら式木を作る 1-2-3の解析木 前のページでこのように書いたが， 部分木の作り方は少し違う．「-」などの四則演算は 左結合なので左から先にノードを作る． <E> <T> <E’> 1-2-3の式木 <E'> <F> <T'> - <T> - 3 1 ε <T> <E'> <F> <T'> - 1 - 2 ε <F> <T'> 2 ε 逆になってる 3 ε

再帰的データ構造定義の例 # 中置記法の数式に合わせて Ruby 再帰的データ構造定義の例 復習 # 中置記法の数式に合わせて Expr = Struct.new(:left, :operator, :right) # 1-2-3から得られるデータ構造 Expr.new(Expr.new(1, :-, 2), :-, 3)) このExprを使って式木を表現する

Ruby <E> ::= <T> <E’> <E’> ::= + <T> <E’> | - <T> <E’> | ε $level = { :+ => 1, :- => 1, :* => 2, :/ => 2, :lpar => 3, :rpar => 0 } def e node = t while $type==:SYMBOL and $level[$value]==1 op = $value; nextToken node = Expr.new(node,op,t) end return node end e や t はメソッド :+ と :- は優先度 1

<T> ::= <F> <T’> Ruby <T> ::= <F> <T’> <T’> ::= * <F> <T’> | / <F> <T’> | ε $level = { :+ => 1, :- => 1, :* => 2, :/ => 2, :lpar => 3, :rpar => 0 } def t node = f while $type==:SYMBOL and $level[$value] == 2 op = $value; nextToken node = Expr.new(node,op,f) end return node end :* と :/ は優先度 2 e の定義と，$levelが2，e が t, t が fにずれただけで形は同じ

<F> ::= NUMBER | ( <E> ) Ruby <F> ::= NUMBER | ( <E> ) $level = { :+ => 1, :- => 1, :* => 2, :/ => 2, :lpar => 3, :rpar => 0 } def f if $type==:NUMBER then value = $value; nextToken; return value elsif $type==:SYMBOL and $level[$value]==3 nextToken; node = e; nextToken return node end :lpar は優先度 3

式木の生成 8 + 4 / 7 - 5 node $line=gets nextToken node=e Ruby 式木の生成 node 8 + 4 / $line=gets nextToken node=e として 8+4/(7-5) を入力すると右の式木ができる． 7 - 5

Ruby e 呼び出し t f $type: :NUMBER $value: 8 $line: +4/(7-5)

if $type==:NUMBER then value = $value; nextToken; return value … Ruby e t f def f if $type==:NUMBER then value = $value; nextToken; return value … $type: :NUMBER $value: 8 $line: +4/(7-5)

while $type==:SYMBOL and $level[$value] == 2 … Ruby e t 前のスライドで ここが終わった node $level[:+] は1 なので 満たさない 8 def t node = f while $type==:SYMBOL and $level[$value] == 2 … $type: :SYMBOL $value: :+ $line: 4/(7-5)

while $type==:SYMBOL and $level[$value]==1 … Ruby e node 前のスライドで これが終わった $level[:+] は1 なので 満たす 8 def e node = t while $type==:SYMBOL and $level[$value]==1 … $type: :SYMBOL $value: :+ $line: 4/(7-5)

node = Expr.new(node,op,t) end … Ruby t 8 f op = $value; nextToken node = Expr.new(node,op,t) end … ここで t が 呼び出される $type: :NUMBER $value: 4 $line: /(7-5)

elsif $type==:SYMBOL and $level[$value]==3 node op=:+ Ruby t node op=:/ 8 $level[:lpar] は優先度 3 def f … elsif $type==:SYMBOL and $level[$value]==3 nextToken; node = e; nextToken ... 4 f $type: :SYMBOL $value: :lpar $line: 7-5)

nextToken; node = e; nextToken $type: :NUMBER $value: 7 $line: -5) op=:+ Ruby t node op=:/ 8 4 f e ここでeが 呼び出される def f … nextToken; node = e; nextToken $type: :NUMBER $value: 7 $line: -5)

e node op=:+ t node op=:/ 8 4 f e node 7 $type: :SYMBOL $value: :- Ruby t node op=:/ 8 4 f e node $level[:-] は1 なので 繰り返しを実行 7 def e node = t while $type==:SYMBOL and $level[$value]==1 op = $value; nextToken node = Expr.new(node,op,t) end $type: :SYMBOL $value: :- $line: 5)

node = Expr.new(node,op,t) Ruby t node op=:/ ちょっと飛ばして e中の node = Expr.new(node,op,t) の実行結果 8 4 f e node 7 - 5 $type: :SYMBOL $value: :rpar $line:

node = Expr.new(node,op,f) Ruby t node 8 t 中の node = Expr.new(node,op,f) の実行結果 4 / 7 - 5 $type: $value: $line: 空

node = Expr.new(node,op,t) Ruby e 8 + e 中の node = Expr.new(node,op,t) の実行結果 4 / 7 - 5 $type: $value: $line:

pr(node)を実行すると，式木nodeを辿って数式を表示 Ruby 式木の表示 (中置記法) def pr(node) if node.kind_of?(Fixnum) then print node else 　　print "(" 　　pr(node.left); print node.operator; pr(node.right) 　　print ")" end pr(node)を実行すると，式木nodeを辿って数式を表示

if node.kind_of?(Fixnum) then print node else pr(node.left); print " " Ruby 式木の表示(後置記法) def pr(node) if node.kind_of?(Fixnum) then print node else pr(node.left); print " " pr(node.right); print " " print node.operator end 空白を出力 8+4/(7-5) は後置記法では，8 4 7 5 - / + と表記される (カッコが不要)

式木から式の値の計算 def calc(node) if node.kind_of?(Fixnum) return node else Ruby 式木から式の値の計算 def calc(node) if node.kind_of?(Fixnum) return node else return { :+ =>proc{|a,b| a+b}, :- =>proc{|a,b| a-b}, :* =>proc{|a,b| a*b}, :/ =>proc{|a,b| a/b}} [node.operator]. call(calc(node.left), calc(node.right)) end proc{|a,b| a+b}はf(a,b)=a+b なる関数 f {…}[:+]の値がf(a,b)=a+bなる 関数fとなるハッシュ node.operatorが :+ ならf(a,b)=a+b となる 関数 f となる node.operator が :+ なら， calc(node.left)+calc(node.right) を計算

コード生成 式木から式を計算する機械語を生成する ターゲットとする計算機: ED21 http://lecture.ecc.u-tokyo.ac.jp/ johzu/joho/ed21/

高水準言語 高水準言語 コンパイラ(compiler) 人間が理解しやすい形でプログラムを読み書きできる言語 復習 高水準言語 コンピュータが直接実行できるのは 機械語なので，高水準言語は 機械語に変換してから実行する． 変換するプログラムを コンパイラという 高水準言語 人間が理解しやすい形でプログラムを読み書きできる言語 “コンパイラ”を使うことで機械語に変換する 高水準言語の例： C言語，C++言語 コンパイラ(compiler) プログラム言語で書かれたプログラム(ソース)を機械語(オブジェクト)に変換（翻訳）するソフトウェア Rubyはちょっと 違うので後で…

ここでは以下のコンパイラを作ってみる 高水準言語：式木 機械語：計算機シミュレータED21

「計算機シミュレータED21」 http://lecture.ecc.u-tokyo.ac.jp/johzu/joho/ed21/

ED21の機械語 load A ACにA番地の内容を読みこむ loadi D ACに数値Dを直接セットする store A add A, sub A, mul A ACの内容にA番地の内容を加算/減算/乗算する． div A 同じく除算する．下位16ビットが商，上位16ビットが余りとなる． shiftr D, shiftl D ACの内容をDビット右/左にシフトする j A A番地にジャンプする jz A ACが0の時，A番地にジャンプする stop 0 プログラムを停止する ED21の機械語

1+2を計算する機械語プログラム 実行結果 アドレス 1 2 3 loadi 1 add 3 stop 0 2

式木からその値を計算する機械語の生成 各頂点(葉)の値を計算した結果をACに残す機械語を生成するには， ACの内容をメモリmに一時的に保存する機械語を生成する．（左の部分式を計算しないといけないので，ACを空ける．） 左の部分式を計算した結果をACに残す機械語を生成する．(その間メモリmの値を変更しないように，m+1以降のメモリを作業用に使う．) その頂点の演算をACとメモリmに対して行う機械語を生成する．

機械語 式木 LOADI 5 5 式木と生成される機械語

7 - 5 式木 機械語 式木と生成される機械語 LOADI 5 STORE 20 LOADI 7 SUB 20 作業用のメモリの 番地．機械語と 重ならない所に． 7 - 5 式木と生成される機械語

4 / 7 - 5 式木 機械語 式木と生成される機械語 LOADI 5 STORE 20 LOADI 7 SUB 20 LOADI 4 DIV 20 SHIFTL 16 SHIFTR 16 20番地の内容は使ったので， 次に別の用途で使ってもよい 4 / 7 - 5 余りを消す 式木と生成される機械語

8 + 4 / 7 - 5 式木 機械語 式木と生成される機械語 LOADI 5 STORE 20 LOADI 7 SUB 20 DIV 20 SHIFTL 16 SHIFTR 16 LOADI 8 ADD 20 8 + 4 / 7 - 5 式木と生成される機械語

node.operator が :+ ならADD命令を表示 Ruby 式木nodeを計算する機械語を出力 作業用のメモリはbase以降を使用 右の部分式の機械語を生成 def code(node, base) if node.kind_of?(Fixnum) print "LOADI ",node,"¥n" else code(node.right, base) print "STORE ",base,"¥n" code(node.left, base+1) print ({ :+ => "ADD", :- => "SUB", :* => "MUL", :/ => "DIV" }　 　　　　　 　　 [node.operator], " ", base, { :+ => "¥n", :- => "¥n", :* => "¥n", :/ => "¥nSHIFTL 16¥nSHIFTR 16¥n" }[node.operator]) end 右の部分式を計算した値をbaseに保存 左の部分式をbase+1以降を使って 計算する機械語を生成 DIVの場合は余りを消すために SHIFTL, SHIFTR生成 node.operator が :+ ならADD命令を表示 コード生成

8+4/(7-5) (8+(4/(7-5))) LOADI 5 STORE 20 LOADI 7 SUB 20 LOADI 4 DIV 20 SHIFTL 16 SHIFTR 16 LOADI 8 ADD 20 入力した式 式木を中置記法で表示したもの ①貼付け ②実行 ③実行結果

仮想機械 仮想機械: ソフトウェアにより仮想的に実現したコンピュータ 例 インタープリタ：高級言語を機械語とする仮想機械 シミュレータ，エミュレータ：現実にある（かもしれない）マシンを模倣する仮想機械 例 ED21（ED21の機械語を実行するシミュレータ） Java VM（Virtual Machine=仮想機械） ruby（Rubyのプログラムを実行するインタープリタ）

これから作る仮想機械の機械語ED21' 機械語 命令 loadi D 0x1000+D(下位8ビット,2の補数) store A 0x1800+A(下位8ビット,非負,以下同じ) add A 0x3000+A sub A 0x3800+A mul A 0x4000+A div A 0x4800+A(ED21と異なりACには商のみを置くことにする) stop 0

Ruby 式木nodeを計算するED21'の機械語をcodepから生成．作業用のメモリはbase以降を使用．生成した機械語の次のアドレスを返す def codeBin(node,codep,base) if node.kind_of?(Fixnum) $mem[codep] = 0x1000+node #loadi else codep = codeBin(node.right,codep,base) $mem[codep] = 0x1800+base #store codep = codeBin(node.left,codep+1,base+1) $mem[codep] = {:+ => 0x3000, :- => 0x3800, :* => 0x4000, :/ => 0x4800}[node.operator]+ base end return codep+1 負の場合の配慮は省略 node.operator が :+ なら 0x3000 を返す コード生成

ED21'の仮想機械のインタプリタ 仮想機械の状態を表すPC，AC，レジスタ，メインメモリ(配列$mem)を用意する $mem[PC]を読み出して，命令，オペランドに分解する 命令に応じた処理を行う 停止命令の場合はここで実行終了 ジャンプ命令以外の場合は，PCの値を増やす 2から繰り返す

16進数FFとandを取って下8ビットを取り出す． これがオペランド Ruby def sim pc = ac = 0 while $mem[pc] != 0 oprand = $mem[pc] & 0xff case $mem[pc] & 0xffffff00 when 0x1000 # loadi ac = oprand; pc += 1 when 0x1800 # store $mem[oprand] = ac; pc += 1 else ac = { 0x3000 => proc {|a,b| a+b}, 0x3800 => proc {|a,b| a-b}, 0x4000 => proc {|a,b| a*b}, 0x4800 => proc {|a,b| a/b} } [ $mem[pc] & 0xffffff00].call(ac,$mem[oprand]) pc += 1 end return ac 上位24ビットが命令の指定 case A when B B' when C C' else D は if A==B 　　then B' 　　elsif A==C then C' else D の意味（場合分け） 命令が0x3000なら f(a,b)=a+bなる関数fを返す 仮想機械のインタプリタ

もう一歩先へ 文献: Aho, Appel, ... ツール: lex, yacc, bison, SableCC, JavaCC BNF rules for Java, ...