2008-05-09

Recursive Decent & Semantical Analysis

なんとか、GW明けの課題群を越えました。
んじゃさっそくintern用のエッセイでも書くかな。

書類選考で落とされる可能性は大だが、
やらないよりはやったほうが後悔はしない。



----- Language Processor note 2008/05/02 -----
[Recursive Decent]
-誤り処理のアルゴリズム-

・recursive callで書こうとすると失敗したときの修正は絶望的。
→最初に原則を決めることが大事!
人間にできること→プログラムが原則にあっているかどうかを確かめること。

・最長部分を読みしてる。
B = o | ( {B} )
何回Bがくるかは、わからない。

oまたは(がこなかったら誤り。

再帰降下法が適応できないときは、構文規則を書き直す。

書き直しができない場合もある
例3 最後まで見ないとわからないから無理
→ただし、プログラム的には、最後まで読んだ後、cの数を数えて、
最後の文字を判定すればできないこともない。

例4 無理

つまり、再帰降下法がすべてに適応できるわけではない。
interpriterのデザインパターンを見ると再帰降下法を使え!
という内容がある。
→再帰降下法は理解していなければならない。

・再帰降下法が適応出るためには
一字先読みだけで、判定できなくてはいけない。
繰り返しがあるかどうかを判定したいとき、+だったら繰り返せばよい。

繰り返しがなかったらAの終わりを示す終端記号を調べる必要がある。
→Aの次は;または)

・Bの次にくるものは、+またはAの次にくるもの。

follow()→次にくるものを読み取る関数?

・まとめ
駄目なものは、直せるかもしれないし、直せないかもしれない。

・念のためのerror()
実行を打ち切る関数。
C言語の場合はexit(n);
引数n;システムに終了状態を報告
→OSにmain()を返す。
OSに変える値。
普通は0があれば、問題なし。
0以外であれば、何かしら起こる可能性がある(Unix,またはLinuxの場合)

自分の制御している画面に戻りたいとき。
setjmp, longjmp(C lang)
longjmpを呼ぶと、setjmpしたところに戻ってくる。

javaの場合のtry-catch文と同じ。

[誤り処理(error handling)]
エラーを発見したときに、それを出力するのは簡単。
ただし、一個ずつそれをやっていくのは格好が悪い。
→エラーが発見されたあとも、読み続ける処理があると便利。


----- Language Processor note 2008/05/09 -----
[Semantical Analysis]

・区画構造
徹底した人間でも、間違えは犯す。
凡人であれば、さらに多く間違えを犯す。
block = 区画
↑これを一塊とする。

関数を定義してる区画の外には、
仮引数の名前が宣言されている。
→目に見えない区画が存在している。
それらが並んだものがプログラム。

C言語では、ひとつのファイルでは
C自身には関数というユニットしかない。
Unitをひとまとめにするにはファイルしかない。
Fileを超えるものはLibraryしかない。

プログラムは、これらを使って仕事をしている。
→source fileはひとつでも、Libraryを使えば、
ほかのファイルを使っていることになる。

・「make」という仕組み
どのファイルとどのファイルをコンパイルしろ。
一個の機械語のファイルとしてまとめろ。
以上の作業をするディレクトリをここにおけ。
これを製品として、どこそこにおけ。
↑こういった振る舞いをする

例;makeを実行して、Installしてください。

・fileの外にも仮想的な領域が存在する。
→標準関数とか


・同じファイルが違う宣言してはいけない。
int real;
int real;
↑二重宣言の禁止


・有効な宣言
括弧構造の中で、もっとも最小単位のものが最優先。
次に、それを包む区画が優先される。
最終的には、標準関数などがおかれている区画までいく。


・名表-区画ごとに
区画のそとにはglobal宣言とかがある。
★の部分では、b,cが使える。
xを使いたいときは、その外の区画を見て、xがあるから使える・
aを使うときは、仮引数が使われる。
bを使うときは、もっとも内側のbが適用される。
最内区画(if文)のひとつ外の区画でbをつかおうとすれば、int b[]が適用される。

それぞれのtableには変数とその性質が書かれている。
{}を出たり入ったりする度に、何表か重なった構造を書き換えなくてはいけない。
→各表が入ったり消えたりする。
→名前の表は階層構造になっている!

宣言が増えたときは、表を見てその変数があるかどうをかを調べる。
次に、外の表を見て、あれば二重宣言として禁止する。

変数を使うときも同様の手順で、表をparseしていく。

表を扱うときは、データ構造とアルゴリズムで習った内容にそって設計する。
→つまり、ハッシュ法が最も早くなるので、ハッシュ法をつかう?
→たかだか、2回か3回調べるだけでよい。

・構文解析で誤りがあったときの対処法
変数がなかった場合;
関数として使っているのか、変数として使っているのかわからん!
最終的に誤りがあれば実行はしないわけだが、通常の場合、
ひとつの宣言を忘れたとき、それを扱ったすべての文を起こることになる。
→誤りを一度error処理したら、それは変数として宣言したものとする。
型はオールマイティな型とする。

・具現
「表を引く」作業を行うとき、
その名前がどういう形で宣言されているかということが「表に書かれていれば」よい。
→訂正するときはハッシュ表を書き換えればよい。
手間をかけるところは、
宣言されたときにハッシュ表に登録すること。
区画を抜けたときにハッシュ表から取り除くこと。

番号を見て、ハッシュ表から検索し、
各表の中にはpointerでその性質を指しておけば、一回で出てくる!

[注意!]
表が消えるときには、状態を以前の状態に戻さなくてはいけない!
→以前の状態の中にpointerを置き、そのpointerの先に新たな状態を宣言すれば、
 以前の状態に戻すときは、pointerを外すだけでよくなる!
それぞれの表から、名前のつづりを逆向きのpointerで指す。
なければNULLを入れればよい。

methodやunitやlibraryが構造化されている。

大事なこと↓
名前の表を調べるときは、最内区画から調べていく。
余計なことをせずに、判定できるようにする。

bという名前が出てきたと場合、
同じ表にあれば、pointerが重なり失敗する。
違う表にあれば、pointerが異なるので、現在の表に登録する。
→表全体を調べるようなnaiveな動作はしてはいけない!

・式の処理
一字先読みしたときに、配列なのか、変数なのか、関数なのかわからなくて花r内。
→処理した部分の種別を返す必要がある!

enum{
none,
constant,
variable,

}
という形になる。

・引数の仕様
Cではpointerがあるが、WLではそんなものないので、
しかもintがたしかないので、引数仕様は
int: 1
int[]: 2
として1,2列表現にして3進法で表すだけでよい。

・source code
k = none;
none: オールマイティ

・続き
最初にligicalの区画がきて、
次にwhileの区画がある。
whileがない場合
eval()では中身を確認している。
→引数が配列や変数であれば、r-valueであるべき
→"r-value expected"を出力

・続き
変数であればよいが、オールマイティでもよいこととする。

・続き
kが配列であることが望ましいが、k=noneでもよいこととする。
k=variable;
で変数として扱えますよ、ってことにする。

k=expr;
返す値は、一般の式になる。

・定数式
WLでは列挙宣言の定数を使っている。
定数式は別の構文解析の関数を使う。
int const_expr()の場合、
+,-*,/のみ使える。
配列に入れたりすることはできない。WLだから。
→k=constantでなければerror
そうでなければ、表を持っているはずなので、
表を参照する。

その後、本当に定数が書かれていれば、そのまま適用する。
errorのとき、v=1なのは、vを除算で使っているのでエラーが出てしまうため。
そんなにたいした意味はない。

・文の処理
if_statement()
eval()でちゃんと式として計算できるものであるかをチェックする。

・翻訳系のmain
みんなが使ったものは、誰かが作ったプログラム。
Cのmainプログラムでは、与えられたコマンドを処理するためだけの
パラメータ設定をするだけ。

つまり、mainぷろぐらむでは、コマンドライン引数を処理するだけ。
ただし、<,>,>&,>>,>>&とかはOSでサポートしている。
>&: 標準出力+警告出力
>>&:標準出力+警告出力を追加する。

・諸指定
%wlが引数に指定されれば、入力をstdinとして、出力をa.outとする。

・まとめ
区画構造を用いて、名前の表を管理する機能をつける。
表の中をひとつずつ調べていく検索方法は採用してはいけない!


・宿題
電卓作ってください!

・仕様
四則演算ができる。
ガウス記号もできる。
代入もできる。
代入先は、英数字。
→名前の表を自分で管理しなければならない。
→宣言していない変数を使った場合の処理を自分で考える。
→プログラムはCで作る。
→switch文も使えるので、使おう
・入力の構文規則をちゃんと書くこと。
・字句解析、構文解析、誤りの処理などの方法を適用した上で、電卓を設計する。
・できたプログラムを説明する。
ヒント:整数計算をするサンプルは用意してあるので、目処の立たない人は参考にすること。

来週は、教授が海外出張なので、動画でがんばってくれる。
小テストもある。

再来週は中間試験。
電源の面倒は見ないので、バッテリーの状態には十分注意すること。
何でも持ち込み可能。laptopも可。
ただし、laptopはlocalでしか使ってはいけない。
連絡はカンニングとみなす。

0 件のコメント: