解析木の形式について

質問

最近コンパイラの自作に興味を持ち、良い勉強にもなるだろうと思い作ってみようと考えたのですが、構文解析の結果を木構造で管理しようとしたとき疑問に思ったので、質問させていただきます。
内容は、解析木を作るときどれだけの単位で木を作ればいいのかということです。
例えばプログラム一つに一つの木なのか、一つの文に一つの木なのか…
もし自由ということであれば、それぞれのメリットやデメリットも教えていただけるとありがたいです。

回答No.4

Tacosan

本当はなんらかの本を調達した方がいいような気がします.
トップレベルには外部変数の宣言やら構造体の宣言やら関数の宣言やらが並ぶのですが, ここでは宣言の順序が重要なので「順序が保存できるようなデータ構造」を使うことになります. 木でも線形リストでも OK. 意味的には線形リストだけど, イメージ的には木かなぁ.
また, これらの宣言にはたいてい「名前」がつきます. 変数の宣言なら変数名だし, 関数の宣言なら関数名です. で, プログラム中ではこの名前でしかアクセスしないので, 「名前から宣言の内容がアクセスできる」データ構造, いわゆる「記号表」も持つことになります. もちろん関数や構造体には「その中でのみ有効な名前」があるので, これらはそれぞれで独自の記号表を持ちます.
なお, C++ にしろ Java にしろ, 構文解析・意味解析そのものはあまり C と変わらないんじゃないかな....

お礼

回答ありがとうございます。
今考えている段階では、変数はローカル変数のみで、関数・構造体は順番を気にせず使えるように作りたいと思っていますから、既存の言語と仕様が異なることが多い気はしています。
また、記号表に関しては調べた結果、構文解析や意味解析を通して作るつもりです。
とりあえずプログラム全体で木を作りながら、必要な情報を記号表に追加していくということで作っていきたいと思います。

他にも意見があったら参考にしたいので、回答は募集します。

回答No.3

Tacosan

回答を募集するのはいいんだけど, それと並行して実際にプログラムを組み出すべきだと思います. 実際に組んでみるとどうすればいいかってのもそれなりに見えるかもしれない.
あと, #2 で「C などの手続き型言語では」って書いたんだけど, これは「どのようなプログラム言語を作ろうとしているのか」によって形が変わる可能性があるということを念頭に置いています. たとえば多くのスクリプト言語では関数定義などの非実行文とそれ以外の実行文とが混在できるので, そのようなものの場合には「非実行文は非実行文でまとめ, 実行文はそれだけでまとめる」という構成でいくとあとが楽になるかもしれません.
APL とか J は変態なので無視.

お礼

ご指摘ありがとうございます。
作り始めて構文解析にとりかかったところで、疑問に思ったので質問しました。
本当はC++やjavaのようなオブジェクト指向が作りたいのですが、難しいと思ったのでCのような言語を作ったうえでオブジェクト指向に変えていこうと考えています。(CがC++になったような感じで)

回答No.2

Tacosan

専門家でもないしこの辺は言語によるかもしれないしと逃げを打ちつつ....
C などの手続き型言語ではトップレベルの宣言ごとに構文木を作るかなぁ. トップレベルの宣言だと名前を持っていて「名前でアクセスする」ことが多いので, 木構造で管理する必要はないと思う. むしろ「名前でアクセスする」ことに特化したデータ構造 (ハッシュや 2分探索木など) でそれぞれの解析結果を管理する方が楽になるんじゃないかな.
逆に, if や for のように「部分構造として文を含む文」が存在するので, 「1つの文に 1つの木」というのはちょっと無理があると思う. いや, もちろん「木」は作るんだけど, それが単独で存在するんじゃなくって「ほかの木の一部になる」ってこと. もちろん
{ a; b; c; }
という複合文に対し a, b, c の 3つの文 (から作った構文木) をリストなどで持つことは十分考えられます.

お礼

回答ありがとうございます。

ますます悩んできましたが、とりあえず一つのプログラムを一つの木にし、関数や変数は別の表のようなもので管理してみることにします。

回答は引き続き募集します。

回答No.1

beefisdead

私は専門家でもないのであまり覚えていませんが、プログラム全体で木を作るはず。
BNFをそのまんま木にすることを考えてください。（※）
http://www.hpcs.is.tsukuba.ac.jp/~msato/lecture-note/comp-lecture/tiny-c-note1.html

プログラム全体でひとつの構文木を持つ場合、解析器にプログラムを投げたら、そのプログラムの構文木が出てきます。解析器の中では、再帰的に文法を解釈し、構文木を作っていきます。
文ひとつひとつで構文木を作る場合、プログラム全体はどのようなデータ形式で持つのでしょうか？結局木を持つことになりませんか？
関数名などを解釈するのはこのさらに次の段階になります。それらも一気にやってしまいたいなら後者の手法もありかも知れませんが、それは前者の方法でも可能なことです。

あとは専門家の方に・・・。

※厳密さに関する言い訳
BNFは文法の表示形式のひとつです。これだけで全ての文法が表せるわけではありません。また、構文木はBNFとはさらに異なる概念です。

お礼

回答ありがとうございます。

>>文ひとつひとつで構文木を作る場合、プログラム全体はどのようなデータ形式で持つのでしょうか？結局木を持つことになりませんか？

確かにその通りですね。
一つ考えていたのは、配列か何かで多く木を管理することも考えたのですが、全体を気にしたほうが簡単な気がしました。

引き続き回答は募集します。