プログラミング言語のスコープ階層を反映した構造化解析器

プログラミング言語のスコープ階層を反映した構造化解析器
神谷年洋† 石尾隆* 井上克郎* †科学技術振興機構さきがけ *大阪大学大学院情報科学研究科 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

背景：ソースコードを処理するCASEツール
コンパイラ、lint リバースエンジニアリングツール「ソースコードからドキュメントを作成する」影響波及解析、スライスソースコードを処理するための手法字句解析、プリプロセッシング、構文解析、意味解析 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ
コンパイラ・コンパイラの利用ソースファイル（文字の並び）トークンの並び AST等出力字句規則（正規表現）字句解析規則（BNF）字句解析構文解析意味解析コンパイラ・コンパイラソースコード処理ツール … 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

問題点コンパイラ・コンパイラを使ってもなお、複雑なプログラミングを要求される構文エラーからの回復処理の記述構文解析器の内部処理に関する知識が必要 OOPLのスコープおよびアクセス制御前方参照の解消曖昧な構文の処理 (型)式型<型, …> 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

スコープおよびアクセス制御パッケージクラス不可視またはアクセス不可メソッド自動変数可視かつアクセス可能他のメソッド公開されている場合インスタンス変数公開されている場合他のクラス公開されている場合 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

アプローチ漸進的解析器 OOPLのスコープとアクセス制御の階層性＝解析器のクラス階層ソースコードの外側から内側へと解析を進めるパッケージ → クラス → メソッド 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

漸進的解析器の構成ソースコード中でクラスを定義している部分すべて見つけだす。 parseInterface()を呼び出して、それらをInterfaceParser に渡す。クラスのインターフェイス（公開メソッドのシグネチャや公開インスタンス変数の型）を調べてPackageParser に返す。 PackageParser はその情報をinterfaces に追加していく。 ClassParser #instanceVars #methods #parseClass(partialSrc):code #parseMethod(partialSrc):code PackageParser #interfaces -code +parse(partialSrc):code #parserInterface(partialSrc) :interface MethodParser #parameters InterfaceParser #parseInterface (partialSrc):interface 実行順序 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

漸進的解析器の利点構文エラーの処理＝構造化例外処理パッケージ ← クラス ← メソッド前方参照の問題が生じない／識別子が変数、メソッド、型のいずれかであるかを利用した文法を使うことができるメソッドを解析する前に、インスタンス変数が判明している繰り返し開発・回帰テストへの対応パッケージの解析器から順に開発していく 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

例題: Featherweight Java
class C extends Object { Object value; C() { super(); this.value = new Pair(new A(), new B()).setfst(new B()); } class Pair extends Object { Object fst; Object snd; Pair(Object fst, Object snd) { this.fst = fst; this.snd = snd; Pair setfst(Object newfst) { return new Pair(newfst, this.snd); class A extends Object { A() { super(); } class B extends Object { B() { super(); } FWJ[7]の漸進的解析器を開発する階層的なスコープを持ち強く型付けされた非常に単純な構文規則 (Javaのサブセット)を持つ [7] Igarashi, A., Pierce, B., and Wadler, P.: Featherweight Java: A Minimal Core Calculus for Java and GJ, ACM Trans. Programming Languages and Systems, 23(3), pp (2001). 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

通常の解析器構文規則 Input() : // 開始シンボル ( CL() )* <EOF> CL() : // クラス定義 <CLASS> <ID> <EXTENDS> <ID> <LB> ( LOOKAHEAD(2) <ID> <ID> <SEMICOLON> )* K() ( M() )* <RB> K() : // コンストラクタ <ID> <LP> ( ParamL() )? <RP> <SUPER> <LP> ( ArgL() )? <RP> <SEMICOLON> ( <THIS> <DOT> <ID> <EQUAL> e() <SEMICOLON> )* ParamL() : // パラメータの並び <ID> <ID> ( <COMMA> <ID> <ID> )* ArgL() : // 実引数の並び e() ( LOOKAHEAD(2) <COMMA> e() )* M() : // メソッド定義 <ID> <ID> <LP> ( ParamL() )? <RP> <LB> <RETURN> e() <SEMICOLON> <RB> e() : // 式・・・字句規則 SKIP : { " " | "\t" | "\n" | "\r" | "\f" } TOKEN : { < LP: "(" > | < RP: ")" > | < LB: "{" > | < RB: "}" > | < COMMA: ","> | < SEMICOLON: ";" > | < DOT: "." > | < EQUAL: "=" > | < CLASS: "class" > | < EXTENDS: "extends" > | < NEW: "new" > | < RETURN: "return" > | < SUPER: "super" > | < THIS: "this" > | < ID: ( <LETTER> )+ > | < #LETTER: ["\u0041"-"\u005a", "\u005f", "\u0061"-"\u007a" ] > 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

構文エラーを含む入力例 1: class A extends Object { 2: C() { super(); } 3: } 4: class Pair extends Object { 5: Object fst; 6: Object snd; 7: Pair(Object fst, Object snd) { 8: super(); 9: this.fst = fst; 10: this.snd = snd; 11: } 12: Pair Pair(Object newfst) { 13: return new Pair(newfst, this.snd); 14: } 15: } 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

課題技術的な問題 JavaCCは構文解析器をクラス階層内に作り込むことを想定していない本質的に曖昧な名前への対応クラス、メソッド、フィールドが同じ名前の場合 BNFで与えられた構文全体から、PackageParser, InterfaceParser等のための部分規則を自動的に作り出す方法 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

まとめ「漸進的解析器」を提案したスコープやアクセス制御＝クラス階層構文エラーからの回復を構造化例外によって処理する識別子が型であるか無いかで異なった構文であると見なす構文規則を利用できる返し型開発、テスト駆動型開発とも親和性がある例題を通じて、その開発の詳細を説明した 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

終わり 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

QA「関連技術」 [Q] 構文解析というのは古典的な領域ですので，提案されている着想がなぜいままでなされていなかったかについて，若干のコメントがあればと思います．よくわかりません。ただし、近年、従来の字句解析・意味解析・意味解析という境界を崩そうとする試みが徐々に登場しています。 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

QA 「曖昧な名前」 [Q] 型名と識別子の区別についてですが，例えば，以下のCプログラムは正しいですが，どう思います? struct sss { short mmm; }; typedef int mmm; mmm foo(struct sss s){ return s.mmm; } 型名となってもフィールド名としても使えないといけないです．このような、同じ名前の型とフィールドを区別するためには、字句解析にヒューリスティックを導入するしかありません。ただし、これについてはプログラミング言語の変化を待った方が良いとも思います。 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

QA「エラー回復処理」 [Q] クラス内部は後にして，クラス宣言を取り出す部分ですが，括弧の対応をとるというのは，そこを間違ったプログラムに対して困りませんか?「<CLASS>」まで skip するのと比較してどうでしょう? 外側の括弧の対応が崩れているソースコードでは、その場でエラー回復しても大量のエラーメッセージが再生産されるだけなので、そのような場合は考慮していません。構造化例外処理の方が、プログラミング言語の機能を直接使っているという点でシンプルな手法であると思います。 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

QA「クラス階層」 [Q] 後から足す parser はオーバライドで足すとのことですが，それだと後から足す部分が複数あったときに，どのクラスを使ったらよいのか困りませんか? (中略) おそらく関係のないClassParser と，MethodParasr をクラス拡張で関係付けるのは間違っていて，何もしない MethodParasr の代わりにそれを拡張してある程度解析するようにしたStdMethodParser を使いたいなどのときには new StdClassParser (new MethodParser, new VariableParser) ではなく new StdClassParser (new StdMethodParser, new StdVariableParser) のようにする，ということにしたほうがよいと思います．はい、そう思います。現実の利用に堪えるツールを開発することを想定すれば、何かと制約の多い継承（導出）をがんばって使うよりは、インターフェイスによる分離と委譲を使った方が良いでしょう。 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

コンパイラ・コンパイラ 2004/02/24 日本ソフトウェア科学会第１回ディペンダブルソフトウェアワークショップ

プログラミング言語のスコープ階層を反映した構造化解析器

Similar presentations

Presentation on theme: "プログラミング言語のスコープ階層を反映した構造化解析器"— Presentation transcript:

Similar presentations

About project

フィードバック

ログインする

Auth with social network:

プログラミング言語の スコープ階層を反映した 構造化解析器

Similar presentations

Presentation on theme: "プログラミング言語の スコープ階層を反映した 構造化解析器"— Presentation transcript:

Similar presentations

About project

フィードバック

プログラミング言語のスコープ階層を反映した構造化解析器

Presentation on theme: "プログラミング言語のスコープ階層を反映した構造化解析器"— Presentation transcript: