#contents
*Abstract Syntax [#me70950c]
*Abstract Syntax [#x7bf215e]
- Abstract=いかなる実体とも結びついていないもの
- コンパイラは、文が文法にそっているかをチェックするだけじゃダメ。
-それ以上のなにか(Semantic Actions)が必要
- 再帰降下パーサの場合、semantic actionはパーサーのなかにまき散らされている
- ML-Yaccの場合、生成ルールにくっつけて書かれる
**SEMANTIC ACTIONS [#h561570f]
**SEMANTIC ACTIONS [#a1c05920]
- 各要素(nonterminal/terminal)は意味的な値(semantic value)の型を持っている
- semantic actionは、その値を生成する
*** RECURSIVE DESCENT [#z7101afc]
*** RECURSIVE DESCENT [#i9e610ee]
- semantic action=パーサ関数の返す値と、その関数が起こす副作用
- 各要素について、実装言語の型が関連づけられている
- Program 4.1が例ですよ。T'がちょっとトリッキー。左オペランドが書けているので、引数として渡している
*** ML-Yacc-GENERATED PARSERS [#h4100ca5]
*** ML-Yacc-GENERATED PARSERS [#n8e64251]
- ML-Yacc用の文法のsetのそれぞれに、semantic actionがMLの式の形でannotateされる
- パーサがルールを還元するたびに、そのsemantic actionが実行される
- actionは、生成規則の右辺のsemantic valueを参照できる
- 例)expの各semantic actionは、すべて同じ型(今回はint)を返す必要がある
- semantic valueは各シンボルと共にスタック上に保存される
- 還元する場合は、スタックの上からいくつか値をpopする。そして新しい値をpushする
*** A MINI-INTERPRETER IN SEMANTIC ACTIONS [#h3c91352]
*** A MINI-INTERPRETER IN SEMANTIC ACTIONS [#bc8fb010]
- PROGRAM 1.5でやった言語のインタプリタを作ろう
- expのsemantic valueはtable->int。これはテーブルを受け取ったらなにか整数を返すということ。
- 例) x = テーブルをもらったら、そこからxを探して返すよ。42 = テーブルをもらったら、それを無視して42を返すよ。
- statementは、tableを受け取って、適当なtableを返すよ
- でもこの構造だと、exp内の代入文がtableを弄れない
*** AN IMRERATIVE INTERPRETER IN SEMANTIC ACTION [#i4390ad6]
*** AN IMRERATIVE INTERPRETER IN SEMANTIC ACTION [#y98d3e38]
- 今までは副作用がなかったから、生成規則ほ右辺の評価順番はどうでもいい
- LRパーサの場合、評価順番は決まっている。bottom-up、左から右へ。言うなれば、parse treeのpost orderで
- だから、副作用のある手続き的なsemantic actionも書ける
**ABSTRACT PARSE TREES [#se200eb7]
**ABSTRACT PARSE TREES [#hcf395fa]
- semantic actionだけでコンパイラを書くのはダメ
- 読むのとメンテナンスが大変
- パースした順に、プログラムを解析しなければならなくなる
- syntaxの処理(パース)とsemanticsの処理(型チェックやマシンコードへの変換)を分けよう
- そのためにパーサにparse treeを作らせよう
- parse treeの各葉はトークン、幹はパース中に還元された文法規則
- parse treeをそのまま使うのは不便
- いくつかの区切り文字は冗長で、何の情報ももたない
- parse treeは文法に依存しすぎている
- 左再帰などを除去すると、文法は変わる
- このあたりは、parse phaseだけに閉じ込めておくべき
- 抽象構文(abstract syntax)は、パーサと他の部分の間のインターフェースになる
- 抽象構文木は、semanticの解釈に必要な情報だけを運ぶ
- 初期のコンパイラは、メモリ節約のため抽象構文木を使わなかった
- 最近の言語では、先行宣言(forward declaration)は必要ない。これも、抽象構文木のおかげ
- Grammer 4.6が、straight-line-programの抽象構文
- 演算子の順序が曖昧だし、いくつかのキーワードが消えているから、パースには使えない
- 抽象構文は、すでにパースが終わったものなので、曖昧でもかまわない
- 抽象構文木のためのデータ構造はdatatypeで作ろう
- abstract syntax grammerの生成規則が各コンストラクタに対応する
- 各非終端記号がMLの型に対応する
- 相互再帰している比終端記号は、他の抽象構文を参照しているMLの型になる
*** POSITION [#q5e98de4]
*** POSITION [#w4428552]
- 伝統的なワンパス コンパイラは、字句解析とパースと意味解析が同時に進行する
- 型の不一致などのエラーが発生したとき、発生したソースコード中の位置を表示する
- 字句解析器は、今どの位置にいるかという情報を保持している
- 抽象構文木をつかったコンパイラだと、このエラーメッセージの表示が難しい
- 字句解析器が終わった後に、意味解析が行われるので、字句解析器の情報が使えない
- 各ノードが、ソースコード中の位置を記憶していなければならない
- abstract-syntax data structureにposというフィールドを追加する
- 字句解析器が各トークンの開始位置と終了位置を渡すと、それがML-Yaccで使える
- FOOという記号があったとき、FOOleftが開始位置、FOOrightが終了位置になる
- これらがposフィールドの決定のために使われる
*** ABSTRACT SYNTAX FOR Tiger [#b86e03a9]
*** ABSTRACT SYNTAX FOR Tiger [#c8a71ae1]
- Tigerの抽象構文は、Figure4.8のようになります。
- posは、ソースコードの開始から何文字目かを表している
- Tigerは相互再帰関数が書ける
- だからFunctionDecコンストラクタは、関数定義のリストを受け取る
- 同様の理由で、TypeDecコンストラクタは、型定義のリストを受け取る
- &や|の抽象構文は存在していない
- e1 & e2 は if e1 then e2 else 0に、e1 | e2 は if e1 then 1 else e2に変換される
- 単項のマイナス:-iも、0-iという減算で表される
- このような変換をすると、抽象構文木が小さくなるし、意味解析が少なくて済む
- その代わり、型チェックのエラーメッセージが分かりづらくなる
- 字句解析器はIDをstring型で返すが、抽象構文ではsymbol型が欲しい
- Symbol.symbol:string->symbolとSymbol.name:symbol->stringが用意してある
- http://www.cs.princeton.edu/~appel/modern/ml/chap4/symbol.sml
わからない:
- 意味解析では、ネストされた関数内でのローカル変数の使用を追跡する必要がある
- そのために、escapeというフィールドが使われる
- パーサはescapeがtrueなら、セットされたままにしておく?
- escapeは、VarDec(変数定義)、ForExp(for文)、formal parameter(関数の引数？)で使われる
- field型は、レコードの各フィールドとformal parametrで使われている。でもレコードの場合は、escapeを無視する
- escapeはHackだよ。本来はここにあるべきじゃないけど、ほかのとこに置くには余計なデータ構造がいるんだ
***PROGRAM: ABSTRACT SYNTAX [#h7b97035]
- 改造したいならtiger.grmを書き換えなさい
- structure A = Absynとやると楽だよ
- ファイルは$TIGER/chap4にあるよ。http://www.cs.princeton.edu/~appel/modern/ml/chap4/
|ファイル名|説明|h
|absyn.sml|Tigerの抽象構文用のデータ構造|
|prabsyn.[ch]|抽象構文木用のpretty-printer|
|base.sml|今までと同じ|
|errormsg.sml|今までと同じ|
|tiger.lex.sml|自分で書いたやつが動かなかったときは、これを使いなさい|
|symbol.sml|string->symbolを行うモジュール|
|sources.cm|普通通り(as usual)|
|parse.sml|パーサを起動するドライバ|
|tiger.grm|文法のひな形|
![[PukiWiki]](image/caml3.jpg "[PukiWiki]")
