1 プログラミング言語クラス 2-6 言語処理系の機能と構成 稲葉 一浩 自己紹介 2 稲葉 一浩 （いなば かずひろ） @kinaba 言語処理系ハック Nikes (“Name Inference” for Jikes Java Compiler) LuLu (Lua VM on Lua) ReaJ (Reactive JavaScript) Polemy () この時間にやること 3 言語処理系の構成の紹介 主に Ruby を中心に Copyright (c) 2009-2011 SASADA Koichi <ko1 at atdot.net> 言語処理系の構成 4 プログラムを読む 実行する Copyright (c) 2009-2011 SASADA Koichi <ko1 at atdot.net> 言語処理系の構成 5 プログラムを読む プログラム ＝ 大抵はソースコード 「文字列」 を 「処理系が処理しやすいデータ構造」 に整える 実行する プログラムを読む 6 抽象構文木(AST) x=i+rand*4 字句解析 Lexing トークン(Token)列 x = i + rand * 4 構文解析 Parsing 代入 x + i * rand 4 言語処理系の構成 7 プログラムを読む プログラム ＝ 大抵はソースコード 「文字列」 を 「処理系が処理しやすいデータ構造」 に整える プログラムの実行に必要な情報を、色々計算する 実行する プログラムを読む （続き） 8 例えば… 代入 代入 x x これは + i * rand 4 意味解析 Semantic Analysis これは ブロッ ク ローカ ル 変数！ メソッ ド ローカ ル これは 変数！ メソッ ド呼 出！ + i * rand 4 意味解析で解析される情報 9 ローカルに見ただけでは決まらない構文の情 報 この x は変数なのか関数呼出なのか型なのか？ 変数のスコープ この x はローカル変数？グローバル変数？ インスタンス変数？ 型 （C, Haskell などの型のある言語で） この式の型は？ ちゃんと型あってる？ Rubyの場合 10 x=i+rand*4 字句解析 ＆構文解析 ＆意味解析 Rubyの実際の実装では、 すべて同時進行で解析 代入 x これは これは ブロッ ク ローカ ル 変数！ メソッ ド ローカ ル これは 変数！ メソッ ド呼 出！ + i * rand 4 言語処理系の構成 11 プログラムを読む プログラム ＝ 大抵はソースコード 「文字列」 を 「処理系が処理しやすいデータ構造」 に整える プログラムの実行に必要な情報を、色々計算する 実行する （インタプリタ） ASTとRuby 1.8 12 Abstract Syntax Tree Ruby Program Parse a=b+c Ruby 1.8 はAST を単純 にたどるインタプリ タ a= Method Dispatch(:+) b c Copyright (c) 2009-2011 SASADA Koichi <ko1 at atdot.net> 言語処理系の構成 13 プログラムを読む プログラム ＝ 大抵はソースコード 「文字列」 を 「処理系が処理しやすいデータ構造」 に整える プログラムの実行に必要な情報を、色々計算する 「実行に適したデータ構造」に変換する 実行する コンパイラ 14 Ruby 1.9 から コンパイラ追 加 代入 x これは これは ブロッ ク ローカ ル 変数！ メソッ ド ローカ ル これは 変数！ メソッ ド呼 出！ + i * rand 4 Compile getdynamic i putnil send rand putobject 4 send * send + setlocal x Rubyの実際のコンパイル結果を見 る 15 ruby –-dump=insns –e ‘x=1+rand*3’ == disasm: <RubyVM::InstructionSequence:<main>@-e>====================== local table (size: 2, argc: 0 [opts: 0, rest: -1, post: 0, block: -1] s1) [ 2] x 0000 trace 1 ( 1) 0002 putobject 1 0004 putnil 0005 send :rand, 0, nil, 24, <ic> 0011 putobject 3 0013 opt_mult 0014 opt_plus 0015 dup 0016 setlocal x 0018 leave ruby –-dump=parsetree –e ‘x = 1+rand*3’ … コンパイラの流れ : 再帰でGo! compile(右); emit(“setlocal x”); 16 compile(左); compile(右) emit(“send +”); 代入 x + “getdynamic i” “putnil” “send rand” i * rand 4 “putobject 4” Compile compile(左); compile(右) emit(“send *”); getdynamic i putnil send rand putobject 4 send * send + setlocal x 言語処理系の構成 17 プログラムを読む プログラム ＝ 大抵はソースコード 「文字列」 を 「処理系が処理しやすいデータ構造」 に整える プログラムの実行に必要な情報を、色々計算する 「実行に適したデータ構造」に変換する 実行する （仮想マシン（VM）） Ruby 1.9 の全体像 18 … x=i+rand*4 … getdynamic i putnil send rand putobject 4 send * send + setlocal x Ruby プログラム コンパイラ C プログラム YARV 命令列 組み込み クラス・メソッド C コンパイラ VM（実行） 拡張ライブラリ YARV – Stack Machine 19 Ruby Program a=b+c Compile YARV Instructions getlocal getlocal send setlocal b c + a a b+c b c c b+c b YARV Stack Copyright (c) 2009-2011 SASADA Koichi <ko1 at atdot.net> 実行するところ 20 評価器 バイトコードを実行 メソッドフレーム単位での実行 例外処理 C レベルでのインターフェース オブジェクトを管理 クラス・モジュール構造の管理 メソッドの管理 ガーベージコレクション（寿命の自動管理） 組込クラス・メソッド Copyright (c) 2009-2011 SASADA Koichi <ko1 at atdot.net> オブジェクトの管理 21 メモリ管理 OSから借りてくるメモリの管理 オブジェクトの寿命管理 ガーベージコレクション 細かいことはやりません Copyright (c) 2009-2011 SASADA Koichi <ko1 at atdot.net> 言語処理系の構成 22 プログラムを読む プログラム ＝ 大抵はソースコード 「文字列」 を 「処理系が処理しやすいデータ構造」 に整える プログラムの実行に必要な情報を、色々計算する プログラムを変換して効率を上げる 「実行に適したデータ構造」に変換する プログラムを変換して効率を上げる プログラムを変換して効率を上げる 実行する 最適化 23 （詳しくは “3-3 Ruby性能評価/向上技法” で！） getdynamic i putnil send rand putobject 4 send * send + setlocal x Optimize getdynamic i putnil send rand putobject 4 ≪opt_mult≫ ≪opt_plus≫ setlocal x ここまでのまとめ 24 字句解析 構文解析 意味解析 コンパイル 実行 最適化 Design Choices 25 実行方式の選択肢 を直接インタプリタで実行 (Ruby 1.8) CPUの機械語にコンパイルして実行 (C言語等) VM のバイトコードにコンパイルして… AST バイトコードインタプリタで実行 (Ruby 1.9) 実行前に、機械語にコンパイルして実行 (AOT コンパ イラ) 実行中に、機械語にコンパイルして実行 (JITコンパイ ラ) 26 ネイティブコードコンパイラの 構成 基本は インタプリタ/VM 型の言語処理系と同 じ プログラムを読む プログラム ＝ 大抵はソースコード 「文字列」 を 「処理系が処理しやすいデータ構造」 に整える プログラムの実行に必要な情報を、色々計算する 「実行に最適化に適したデータ構造」に変換する プログラムを変換して効率を上げる 「機械語」 or 「アセンブリ」 or 「C言語」 等に 変換する Design Choices 27 構文解析の方法 Top-down 手書き (下降型) vs Bottom-up(上昇型) Parser vs 自動生成 or ライブラリ 仮想マシンの命令セット スタックマシン vs レジスタマシン
© Copyright 2024 ExpyDoc
