『コンパイラ・スクリプトエンジン』　相談室 2

>>931
誤爆スマソ。

>>932
ちなみに誤爆元はどこ?

>>933
漫画板の某スレ。
全くのスレ違いでないことを示すために、トリビアを紹介しとく。

グラフカラーリングによるレジスター割付アルゴリズムを考案した
Gregory J. Chaitinは、リーマン予想についての記事を書いている。

↓こちらが確認のweb pageです。
Thoughts on the Riemann Hypothesis
http://www.umcs.maine.edu/~chaitin/riemann.html

なお、来年3月にACMから

"20 Years of the ACM SIGPLAN Conference on Programming Language Design
and Implementation (1979-1999): A Selection"

なるものが出るそうで、Chaitinもそこに懐古記事を載せるとのこと。

再帰下降構文解析を用いて数式を解析する場合の結合規則について。
4*4%3
この式では乗算を先にするのとモジュロ演算を先にするのとでは結果が違いますよね。
左からだと1、右からだと4です。
ttp://member.nifty.ne.jp/nakamula/recurs.htm
にあるような実装をした場合、結合規則は右から左になるようですが、
左から右の結合規則はどうやって実装すればよいのでしょうか?

>>935
もともと左から右に見えるが、気のせいか？
まあどちらでもいいが、結合を逆にするには、例えばcalc.htmのterm()の場合、
factor(val2)ではなくterm(val2)を呼んでやればいい。

>>935
ループになっているのを再帰呼びだしに変えればいい。
細かいところは省略するが

void term(int *valp) {
　int val, val2;

　factor(&val);
　if (sym == '*' || sym == '/') {
　　op = sym;
　　getsym();
　　term(&val2);
　　switch (op) {
　　case '*': val *= val2; break;
　　case '/': val /= val2; break;
　　}
　}
　*valp = val;
}

こんな感じでは(チェックはしてないよ)。

実は元の版も、再帰で書いたものをtail-recursion最適化をほどこしてループ
に展開しているわけ。

>>937
失礼、元の版は再帰だけでは書けないね。
LLパーシングだから、left-recursionはright-recursionに直さなくては
いけない。

最近パーサから離れていたのですっかり忘れてた。

>>935
ttp://member.nifty.ne.jp/nakamula/recurs.htm
のソースにある#include #include #includeってのは、どんなＣコンパイラも通らんだろ？
何でこうなってる？
#include <stdio.h> #include <stdlib.h> #include <string.h>に直さんといかんだろう？

>>936-937
ごめんなさい。張るリンク間違えてました。
ttp://www.is.akita-u.ac.jp/~sig/lecture/java/variable.html
構文木の作成方向は左から右へ作成するけど実行する時は
木の葉の部分から始めるので右から左になるって事でしょうか。

で、肝心の結合規則のについてですが、
右辺を下請けに任せるとそのまま左から右、再起呼び出しで行えば現在の項は保留されて、
先に右側を解決しにかかるので最終的に右から左になるという事でいいんでしょうか?

>>940
これもどう見ても左結合なのだが。
で、結合規則だが、BNFで表記すると、

左結合は
　term ::= primary
　　　　 | term OP primary

左再帰があるので、除去すると
　term ::= primary { OP primary }

右結合は
　term ::= primary
　　　　 | primary OP term

となるので、これをそのままプログラムすればいい。
ということで、

> 右辺を下請けに任せるとそのまま左から右、再起呼び出しで行えば現在の項は保留されて、
> 先に右側を解決しにかかるので最終的に右から左になるという事でいいんでしょうか?

は合ってると言えば合っている。理解できているかどうかは知らんが。

spirit使えねー。
同じ場所に対して何度もアクションが呼び出されたりする。

>>941
BNF表記で表せればプログラムにするのは難しくないみたいですね。
自分は文法規則をBNFを使って組み立てる所の理解が不足してるみたいです。
ちゃんとした書籍でも買って勉強してみます。
結合についてはなんとなくですが理解できました。
ご丁寧にどもありがとう!

ちょっとコンパイラとは程遠いのですが、
数式を評価するプログラムを作っています。
(a + 2)*3 + (b + 4)*5 + 6　⇒　a*3 + b*5 + 32
のように複雑な式を演算が少なくなるよう最適化(？)する方法ってありますか？

>>944
"symbolic algebra" simplify algorithm あたりでぐぐっても、
あまりいいのは出てこないね。

>>944
その例だけなら、パターンマッチで

(any + const_1) * const_2
-> any*const_1 + const_1*const_2

というような変形を行い、定数項を集めればできる。
実際、多くのコンパイラでは配列参照 a[i+1] に対するコード
*(a + (i+1) *4) を *(a+4 + i*4) のように変形している。

しかしどんな式に対しても最小の演算回数を保証するアルゴリズムとなると難
しい。結局、いろいろな変形ルールを用意しておくしかないのでは？

たとえば、x^10は素直にやると9回の掛け算が必要だが
x2 = x*x
x4 = x2*x2
x8 = x4*x4
answer = x2*x8
とすれば4回ですむ。この掛け算回数を最小にする手順を生成するアルゴリズムを
考えるだけでもけっこう大変である。

>>944
ドラゴンブック下巻の最適化を一通り読むことをお勧めする。
ためになるよ。

>>944
自分はツリーにして定数を出来るだけ刈っていくだけならしてるけど、
定数項を出来るだけ集めるようにするとなると、
964さんの方法で分配法則で展開するしか無いですね。

(a+3)*b -> そのまま
(a+3)*4 -> 4a + 12 に展開

>>948
すまそ、
(a+3)*4 と　4*a+12 だと全然最適化されてないっすね。

でも

(a + 2)*3 + (b + 4)*5 + 6 だと 乗算2回、加算3回、変数2個、即値5個
a*3 + b*5 + 32 だと 乗算2回、加算2回、変数2個、即値3個

なので、そこまで最適化をすることに
意味がないような気がしますが、どうでしょう?

>>946
x86の話で恐縮ですが、
定数のかけ算のばあい、昔は符号付きシフトを交えたり、
LEAをつかったりしたのと似てますね。

>>942
> 同じ場所に対して何度もアクションが呼び出されたりする。
そんなことないけど…？

switch文の嵐にしても良いよね？

>>945-949
遅くなりましたがレスくれた方々どうもありがとうございます。
このスレを一通り目を通しましたがあまり触れられていないので聞いてみました。
定番と呼べるアルゴリズムは無いようですね。
逆に言ったらここがコンパイラの売りとも言うことなんでしょうか。
パターンマッチの段階で展開してしまうというのは思いつきませんでした。
たとえ展開できても最適化できるとも限らないところも難問ですねぇ。
思っていいた以上に奥が深かそう・・・

>>949
加算が一つ減るなら十分やる価値あります。

> x86の話で恐縮ですが、定数のかけ算のばあい、昔は符号付きシフトを交えたり、
定数の乗算をシフトと加算に展開するのはRISCプロセッサでもやってますね。
だいたい、初期のSPARCやHPのRISCには乗算命令なかったし。後になって追加
されたけど、それでも10倍程度ならたぶんシフトと加算の方が速いんじゃないかな？

>>952
最適化の地獄の世界へようこそ(笑
あなたはいずれ、NP完全問題とは何かを肌で感じることになるでしょう。

LL(1)の文法で書かれたソースを解析するプログラムを作っているのですが、
右結合の演算子をどのようにすればいいかわかりません。
つまり　a^b^c　が　a^(b^c)　と解析されるようなプログラムです。
現在、
<項1>:= <項2> {( '+' | '-' )<項2>}
<項2>:= <因子> {( '*' | '/' )<因子>}
<因子>:=<数値>| '(' <項1> ')'
のような感じで定義を行っています。
これに、'*','/'よりも順位の高い右結合の演算子はどのように定義すればいいでしょうか。
よろしくお願いします。

>>954
>>941 をみるといいかと

<項2>:= <項3> {( '*' | '/' )<項3>}
<項3>:= <因子> { '^' <因子>}

こうやっちゃっといて、構文木を作るときに右結合に
してしまうこともできたと思ったけど。

>>955-956
ありがとうございました。
最初941見てよくわからなかったので質問したのですが、941をよく読んだらわかりました。
一応結果を書いておきます。
static void term1() {
String s;
term2();
while (token.equals("+") || token.equals("-")) {
s = token;
token = nextToken();
term2();
System.out.print(s);
}
}
static void term2() {
String s;
term3();
while (token.equals("*") || token.equals("/")) {
s = token;
token = nextToken();
term3();
System.out.print(s);
}
}

static void term3() {
　factor();
　if (token.equals("^")) {
　　token = nextToken();
　　term3();
　　System.out.print("^");
　}
}
static void factor() {
　if (token.equals("(")) {
　　token = nextToken();
　　term1();
　　if (token.equals(")")) {
　　　token = nextToken();
　　} else {
　　　System.out.println("\nERROR");
　　}
　} else {
　　System.out.print("[" + token + "]");
　　token = nextToken();
　}
}
です。
皆さんありがとうございました。（まちがってないよねぇ？）

>>926
特定のマシンのアセンブラじゃなくて
JVM（Java仮想マシン）向けに作って移植の手間軽減＞ウマー
（.NETでもいいけど。）

JVM向けアセンブラならjasminがあるけど、

テンプレスレに書いたのですが、ひょっとしたらこっちのほうが詳しい人がいるかなと思ったので
知っている人がいたらレス下さい。

http://pc2.2ch.net/test/read.cgi/tech/1066493064/104

>>961
要するに控えめなマルチポストということですか？

>>962
同一データにリンクしているのでクロスポストと呼んで欲しいな(笑

それはともかく、大分なれてきたので簡単なスクリプトエンジンを作ってみたのですが、boost::spiritってなかなか興味深いね。
テンプレートジェネリックプログラミング＋テンプレートメタプログラミングの組み合わせという超絶変態ぶりですが、
それを使うとここまで書けるのか・・・・
これでワーニングをなんとかしてエラーメッセージをジェネレートできれば yacc lex いらんぞ。
次辺り C# にもテンプレが付くそうですが、リフレクションと組み合わせたらどこまでやれるのか興味深いです。

そろそろ次スレのテンプレを考えましょう。

>>1 は

yaccやlexの使い方やら言語仕様やらの話題。

前スレ
1 http://pc.2ch.net/tech/kako/981/981672957.html
2 http://pc2.2ch.net/test/read.cgi/tech/1021136715/

リンク >>2-6

でいいと思うのだけど。

UNIX板の
yacc & lex
http://pc.2ch.net/test/read.cgi/unix/1031801314/
もリンクしといたほうがいいのかな？

>>1-6のリンク切れはチェックせんと。

あとは↓とか、yacc/lex以外のコンパイラ・コンパイラ等は？
http://www.catnet.ne.jp/t-press/javacc.html

あと、ざっとこのスレ眺めてキーを拾ったから、適宜取捨選択してくれぃ。
>>23-27, JavaCC, boost::spirit, ttp://catalog.compilertools.net
>>487, >>494, ttp://www.linux.or.jp/JF/JFdocs/Lex-YACC-HOWTO.html

個人的な趣向を言えば、テンプレにBNF/EBNFの略説があると◎。

¬＜＞＜∪∪
ttp://ne.cs.uec.ac.jp/~koto/notavacc/

とかも

C++のパーザ（コンパイラじゃなくてよいので）を作った人がいたら教えて欲しいんだけど、
Cのパーザを作るのと比べてどのくらい大変なものでしょうか？
当人比？倍っていう感じで。

今、Cのパーザを作っててこれはなんとかできそうなんだけど、
C++って言われたらどうしようかと思って。

>>968
javaccのrepositoryで見かけたので教えておく。
作ったことはないけど、c++のパーザはcのパーザの約２倍くらいの分量になってた。
ttp://www.cobase.cs.ucla.edu/pub/javacc/

boost::spirit をいれるなら、この辺りにもリンクを入れておくといいかも
http://spirit.sourceforge.net/
マニュアル日本語化プロジェクト http://boost.cppll.jp/HEAD/libs/spirit/index.html

さて、そろそろ次スレ立てる？

21st Century Compilers

Alfred V. Aho, Columbia University
Ravi Sethi, AT&T Bell Laboratories
Jeffrey D. Ullman, Stanford University
Monica Lam, California State University at Sacramento


ISBN: 0-321-13143-6
Publisher: Addison-Wesley
Copyright: 2004
Format: Cloth; 700 pp
Status: Not Yet Published; Estimated Availability: 02/13/2004


http://www.aw-bc.com/catalog/academic/product/0,4096,0321131436,00.html

>>972
をを。
さっそく注文しました。amazon.co.jpでは11/30発売予定となってますね。

Monica Lamはよく論文で名前みかけるけど、ついにドラゴンの仲間入りですか。
この方、中国系みたいですね。

>>973
http://suif.stanford.edu/~lam/
女の人みたい。

まぁ、Monicaなら女性だろう。

>>972
ｷﾀ━━━( ´∀`)･ω･) ﾟДﾟ)･∀･)￣ｰ￣)´_ゝ`)-_-)=ﾟωﾟ)ﾉ━━━!!!!
早速予約しますた。

ペーパーバック版とハードカバー版があるみたいだが。PB : ISBN 0321210913 (2003/11/30)HC : ISBN 0321131436 (2003/10/10)単なる装丁の違いなんだろうか？

しまった、ペーパーバックを注文してしまった。キャンセルせねば。
ありがとう、おかげで気付きました>>977

10/10ってことはHCはもう出てるのか。丸善には積んであるのかな？

あぶねぇ。漏れもペーパーバック買うところだった。
つーか、もう出てたのか。全然知らなかったよ。

>>978
オレも買おうと思ってみたら二つあってハテ？って感じだったんだよね。
それよりも977改行コードミスっててスマソ

HCとPBは、まぁ同じと見て良いよね？HCにしとくか。

そろそろ新スレを。