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

日本ソフトウェア科学会 第１回 ディペンダブルソフトウェア ワークショップ Input() : <LB> ( LOOKAHEAD(2) V() )* K() ( M() )* <RB> V() : <TYPEID> <ID> <SEMICOLON> K() : <TYPEID> <LP> ( ParamL() )? <RP> BlockLike() ParamL() : <TYPEID> <ID> ( <COMMA> <TYPEID> <ID> )* M() : ( <TYPEID> | <VOID> ) <ID> <LP> ( ParamL() )? <RP> BlockLike() : ( <ID> | <TYPEID> | <LP> | <RP> | <SUPER> | <THIS> | <DOT> | <EQUAL> | <SEMICOLON> | <COMMA> | <RETURN> | <NEW> | BlockLike() )* ClassParser 漸進的解析器 PackageParser Input() : ( CL() ) * <EOF> CL() : <CLASS> <ID> <EXTENDS> <ID> BlockLike() BlockLike() : <LB> ( <ID> | <LP> | <RP> | <SUPER> | <THIS> | <DOT> | <EQUAL> | <SEMICOLON> | <COMMA> | <RETURN> | <NEW> | BlockLike() )* <RB> 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 日本ソフトウェア科学会 第１回 ディペンダブルソフトウェア ワークショップ