Abstract Syntax †

  • Abstract=いかなる実体とも結びついていないもの
  • コンパイラは、文が文法にそっているかをチェックするだけじゃダメ。
  • それ以上のなにか(Semantic Actions)が必要
  • 再帰降下パーサの場合、semantic actionはパーサーのなかにまき散らされている
  • ML-Yaccの場合、生成ルールにくっつけて書かれる
↑

SEMANTIC ACTIONS †

  • 各要素(nonterminal/terminal)は意味的な値(semantic value)の型を持っている
  • semantic actionは、その値を生成する
↑

RECURSIVE DESCENT †

  • semantic action=パーサ関数の返す値と、その関数が起こす副作用
  • 各要素について、実装言語の型が関連づけられている
  • Program 4.1が例ですよ。T'がちょっとトリッキー。左オペランドが書けているので、引数として渡している
↑

ML-Yacc-GENERATED PARSERS †

  • 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 †

  • PROGRAM 1.5でやった言語のインタプリタを作ろう
  • expのsemantic valueはtable->int。これはテーブルを受け取ったらなにか整数を返すということ。
  • 例) x = テーブルをもらったら、そこからxを探して返すよ。42 = テーブルをもらったら、それを無視して42を返すよ。
  • statementは、tableを受け取って、適当なtableを返すよ
  • でもこの構造だと、exp内の代入文がtableを弄れない
↑

AN IMRERATIVE INTERPRETER IN SEMANTIC ACTION †

  • 今までは副作用がなかったから、生成規則ほ右辺の評価順番はどうでもいい
  • LRパーサの場合、評価順番は決まっている。bottom-up、左から右へ。言うなれば、parse treeのpost orderで
  • だから、副作用のある手続き的なsemantic actionも書ける
↑

ABSTRACT PARSE TREES †

  • 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 †

  • 伝統的なワンパス コンパイラは、字句解析とパースと意味解析が同時に進行する
  • 型の不一致などのエラーが発生したとき、発生したソースコード中の位置を表示する
  • 字句解析器は、今どの位置にいるかという情報を保持している
  • 抽象構文木をつかったコンパイラだと、このエラーメッセージの表示が難しい
  • 字句解析器が終わった後に、意味解析が行われるので、字句解析器の情報が使えない
  • 各ノードが、ソースコード中の位置を記憶していなければならない
  • abstract-syntax data structureにposというフィールドを追加する
  • 字句解析器が各トークンの開始位置と終了位置を渡すと、それがML-Yaccで使える
  • FOOという記号があったとき、FOOleftが開始位置、FOOrightが終了位置になる
  • これらがposフィールドの決定のために使われる
↑

ABSTRACT SYNTAX FOR Tiger †

  • 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という減算で表される
  • このような変換をすると、抽象構文木が小さくなるし、意味解析が少なくて済む
  • その代わり、型チェックのエラーメッセージが分かりづらくなる

わからない:

  • 意味解析では、ネストされた関数内でのローカル変数の使用を追跡する必要がある
  • そのために、escapeというフィールドが使われる
  • パーサはescapeがtrueなら、セットされたままにしておく?
  • escapeは、VarDec?(変数定義)、ForExp?(for文)、formal parameter(関数の引数？)で使われる
  • field型は、レコードの各フィールドとformal parametrで使われている。でもレコードの場合は、escapeを無視する
  • escapeはHackだよ。本来はここにあるべきじゃないけど、ほかのとこに置くには余計なデータ構造がいるんだ
↑

PROGRAM: ABSTRACT SYNTAX †

  • 改造したいならtiger.grmを書き換えなさい
  • structure A = Absynとやると楽だよ
ファイル名説明
absyn.smlTigerの抽象構文用のデータ構造
prabsyn.[ch]抽象構文木用のpretty-printer
base.sml今までと同じ
errormsg.sml今までと同じ
tiger.lex.sml自分で書いたやつが動かなかったときは、これを使いなさい
symbol.smlstring->symbolを行うモジュール
sources.cm普通通り(as usual)
parse.smlパーサを起動するドライバ
tiger.grm文法のひな形

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2007-11-27 (火) 23:39:48 (6014d)