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

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

[前50を表示]
150:デフォルトの名無しさん
02/07/29 04:09
字句解析をする際に予約語と予約語でない名前とを区別するにはどうするべきなんでしょうか？
つづりを切り出し照合せよなどと本には書いてあったのですが、意味がよく分かりません。
ハッシュ法を使って何とかするのでしょうか？

151:デフォルトの名無しさん
02/07/29 05:24
>>150
とりあえず単語切り出すところまではできてるとして、後は

static const char *keywords[] = {
　　"if", "else", "while", ..., NULL
};

int is_keyword(const char *s)
{
　　int i;
　　for (i = 0; keywords[i] != NULL; ++i)
　　　　if (strcmp(s, keywords[i]) == 0)
　　　　　　return 1;
　　return 0;
}

とか。キーワード数が増えたら、ベタな線形検索やめてハッシュや二分木を
使った方が良いかもしれんが、たかだか数十程度なら気にしなくて良い。

152:ろうひ男爵
02/07/29 09:44
>>150
c言語+asmのマクロを展開するプログラムを作って、
当初は普通の検索(線形検索)で90秒かかった処理が、
ハッシュ(チェイン法)を使って15秒になったよ。
でも、そのときの登録語数が3万単語位なので、
cコンパイラ部分だけで使うくらいの語数(変数合わせて千単語ぐらい)だと、
それほど性能の差は無いと思うよ。
ちなみに、2本木の方が実装は難しいかも。

153:デフォルトの名無しさん
02/07/29 10:36
gperfつかっとけ

154:デフォルトの名無しさん
02/07/29 12:13
2本木ってなに?

155:ろうひ男爵
02/07/29 12:22
すまん、２分木の事。
あと、90秒かかったのが5秒になったの間違えです。

156:デフォルトの名無しさん
02/07/30 01:44
２本木なんて初めて聞いたよ

157:ろうひ男爵
02/07/30 04:41
>>156
すまんのう

158:デフォルトの名無しさん
02/07/30 04:48
>>157
ろうひ男爵、いいかんじのひとだね。

159:デフォルトの名無しさん
02/07/30 23:38
後学のため自前でスクリプトコンパイラを作ってみようと思い、
再起下降構文解析とかBNFとかLAL(1)等の解説されているページをみてまわっています。
a -> a b
b -> c
c -> X
このような一直線な処理は簡単にできる気がするのですが、
a -> a b|c
b -> X
c -> Y
のようにorが入るとたちまちパニックです。
上記の場合bの処理でfalseが帰った場合、
取得したトークンをスタック等に積んでおいて、
cでそのスタックを参照するというような仕組みになるんでしょうか？
それとももっとエレガントな仕組みがあるのでしょうか？
実は全くトンチンカンな事いっちゃってるんでしょうか？
つべこべ言わずYaccで仕組み覚えろモルァ!でしょうか？

160:デフォルトの名無しさん
02/07/30 23:56
>>159
まだコードやアルゴリズムを考える段階にないと思われ。

URLﾘﾝｸ(cspt1.ict.ru.ac.za)

ここにコンパイラ作りの基礎を書いた本一冊文のドキュメントがある。
LL文法の範囲内しか扱ってないけれど最初に手を着けるにはこれぐらいでいい。

161:棄教者 ◆witdLTi2
02/07/31 08:42
>>159
Yaccを使いこなせるようになった方が手っ取り早いです。
yacc/lex プログラムジェネレータ on UNIX
五月女健治著
テクノプレス
ISBN4-924998-14-1

162:デフォルトの名無しさん
02/07/31 13:58
>>159
自前で作らなきゃいやなの？

163:159
02/07/31 14:39
>>160
もっと基礎や概念みにつけるべきということですね。
英語はかなり苦手ですが、いい機会なので昼休み等に読んでいこうと思います。

>>161
昨日Yacc/Lex関係の本を探してみたのですが、
Flaxの本しかありませんでした（買いませんでした）
教えていただいた本を探してみようと思います。
（そういえばネットで買えるとこがありましたよね）

>>162
仕事には全く関係ないというか、完全に興味本位です。
あとオブジェクト指向を勉強してたとき感じたのですが、
自分の知らない技術理解すると、今までやってきたことを
違った視点で見れたりするじゃないですか。
そういうのも狙ってます。
（再起下降構文解析とかみててビビビときましたね）

164:デフォルトの名無しさん
02/07/31 14:48
>>161
LL の方が

　エラー回復が楽
　先読みするトークン数を容易に増やせる

って利点もあるから、俺は両方やることを推奨したい。ま、お勉強としては
手書きのパーサーも悪くないっしょ。

165:デフォルトの名無しさん
02/07/31 20:00
下の文法のパーサをつくれたらLALR(2)パーサジェネレータを名乗っていいですか？

//term
a
b
c
//non-term
START:
　E;
E:
　C a a|
　D a b;
C:
　A;
D:
　B;
A:
　a;
B:
　a;

166:デフォルトの名無しさん
02/07/31 20:03
>>165
実際にLR表作ってみたら？

167:デフォルトの名無しさん
02/07/31 20:07
>>166
できてるっぽいんですが、goto表をここに貼ってみればいいですか？

168:デフォルトの名無しさん
02/07/31 21:22
貼っていい？

169:デフォルトの名無しさん
02/08/02 00:48
イっていい？

170:高速化
02/08/07 02:49
インテルのコンパイラでコンパイルするだけで高速化しました。
無料体験版があります。
URLﾘﾝｸ(www.xlsoft.com)

171:デフォルトの名無しさん
02/08/07 03:02
ハッシュはどこら辺を参考にすればいいんでしょうかねぇ。

172:デフォルトの名無しさん
02/08/15 00:22
『コンパイラ構成法』を読みながらlex/yaccを勉強しているのですが、
URLﾘﾝｸ(216.239.51.100)
でダウンロード出来るであろうソースコードが相手先サーバーが動いていないか何かで、ダウンロード出来ません。

正誤表はグーグルキャッシュでゲットできたのですが。

ソースコードお持ちの方、どこかのアップローダに上げていただけませんか？

173:棄教者 ◆witdLTi2
02/08/15 15:30
>>172
いま、鯖が㌧㌦みたいですね。
このまえはぼくもﾀﾞｳｿできたので。
しばらくしたらもう一度渡来してみたらどうよ。

この本は親切で分かりやすい本です。おすすめです。
わからないところや面白い本はドラゴンブックで補充するとさらに良いでしょう。

174:ろうひ男爵
02/08/17 05:29
>>171
'0'-'9' を 0-9
'@' を 10
'A'-'Z' を 11-36
'_' を 37
'a'-'z' を 38-63
それ以外を 0
にする文字変換テーブルを作り(chartbl[256])、
ハッシュ表(hashtbl[256])を256だとすると、

hashtbl[chartbl['最初の文字']+chartbl['真ん中の文字']+hashtbk['最後から2番目の文字']+chartbl['最後の文字']]
でハッシュ値が収得できるよ。

175:デフォルトの名無しさん
02/08/27 16:01
インタープリターの勉強したいんですが、どこかに参考コードとか、
いい本ありませんか？

176:ろうひ男爵
02/08/27 16:38
どういった用途に使います?>>175
中間言語に落として、ゲームやツールに組み込む単純なスクリプト言語なら、
LL(1)が良いと思います。
それ以上に簡単な物の方がよいのでしたら、
構文解析もほとんど考えなくても良い言語にしたら簡単なんじゃないのでしょうか?
使用用途にもよりますが、以下ぐらいなら簡単に作れるのではないでしょうか?

命令を組み込みの物だけにする、
関数を使えなくする、構造化も出来なくする(手続き言語の古いMS-BASICみたいにする)
変数は$マークから始まるとか、特殊記号にする
算術計算式などを、別扱いにするか、専用の命令を作り、ADDとかにしする。
それでも、バックパッチぐらいは必要ですけど。

LLなら、そこまで難しくはないけど、
yaccとlexを使い、LALRって方法でも簡単に出来ますよ。

177:デフォルトの名無しさん
02/08/27 16:53
>>176
用途というか、PerlやＨＳＰを使ってるうちに、どうやってコンパイラや
スクリプトが動くんだろうと思って、すごく簡単なものでもいいから作れたら
勉強がてらやるのもおもしろいかなーと漠然と思ったんです。

コンパイラに関してはぜんぜん知らなかったので、すこしＷＥＢを見て
LL(k),LR(k)について勉強しましたが、言ってる事は理解できても
それをどうやってコードにしようと悩んでしまって。なにかコードがあれば
みながら勉強することができるのですが・・・言語はＪＡＶＡかＣかＰＥＲＬか、ＶＢ
くらいしか使えないので、どれかでやろうと思っています。

何かインタープリター系の本でコードが載っていて、いい本かなにかありますか？
お願いします。ちなみにＵＮＩＸ系使えないのでＹＡＣＣとかできません・・・

178: ◆JAPH9PWA
02/08/27 17:42
Macは知らないけど、Windowsならyaccあるよ
URLﾘﾝｸ(hp.vector.co.jp)

179:デフォルトの名無しさん
02/08/27 17:49
JavaCCで、構文と構文の隙間を埋めるような
柔軟な構文を定義する方法を教えてください。
Perlでいうところの (.*?) みたいなものが欲しいんです。お願いします。

180:デフォルトの名無しさん
02/08/27 18:07
URLﾘﾝｸ(www.tokumaru.org)

ここのコンパイラソースコードは参考にはならない？

181:ろうひ男爵
02/08/27 18:37
>>177
でしたら、
コンパイラ構成法原田賢一共立出版株式会社 ISBN: 4320029224 6,500円
が一番分かりやすいのですが、yaccとlexが必要です。

コンパイラの仕組み情報科学こんせぷつ〈8〉朝倉書店 ; ISBN: 4254127081
も物量的に少ないので読みやすいですが、消化不良のところが出てきます。
しかし、1日から一週間で読めると思います。

あと、インタープリタとコンパイラの違いは大きくないので、
ここのスレッドに色々質問すると良いかもしれません。

どちらにしろ、コンパイラ関連の本は難解な物が多く、
いろいろなアルゴリズムを理解していることが前提となったりするので、
軽くアルゴリズムの本を読んでおいた方がためになりますよ。

アルゴリズムを１冊ですますには、以下の本が良いと思います。
定本Ｃプログラマのためのアルゴリズムとデータ構造近藤嘉雪技術評論社

簡単なアルゴリズムの本は
C言語アルゴリズム+徹底入門柏原正三技術評論社
が読みやすいです。

182:デフォルトの名無しさん
02/08/27 18:40
金出す前にこれでも読んどけ。

URLﾘﾝｸ(www.hayalab.cs.ritsumei.ac.jp)

183:Aoki
02/08/27 19:12
実行速度が速いSmalltalkを実装するための技法をいろいろ教えて下さい。

184:デフォルトの名無しさん
02/08/27 20:03
>>179
JavaCCは少し使ったことがあるんで、答えられるようなら答えますけど、
Perlは知らないんで、質問の意図がわからないです。

185:179
02/08/27 20:28
<ALL:~[]> /* Perlの(.*)相当だと思うのですが… */
void this () : {} {
　　( "{" this() "}" )+ )|(s = getAll() { println(s) } )
}
が、期待通りの動作をしてくれません。
左の構文を優先させたいのです。お願いします。

186:179
02/08/27 20:35
具体的には、(asdf()asdf((asdf)asdf))
みたいなのをパーズしたいと思ってます。
asdfの部分は、それが構文そのものを含む時以外は、
全ての文字を処理したいのです。

187:デフォルトの名無しさん
02/08/27 20:46
<ALL:~[]*>
すみませんこっちでした。

188:184
02/08/27 21:43
まだようわからんけど、{asdf{}asdf{{asdf}asdf}}が無理やりパースできるようにしてみた。
解釈が間違えてたらごめん。

TOKEN :
{
　 <ALL: (~["{","}"])+>
}

void Input() : {} {
　foo()
}

void foo() : {
　String s;
} {
　　( LOOKAHEAD(2) "{" ( foo() )* "}" )+
　| (s = getAll() { System.out.println(s); } )
}

String getAll() : {
Token t;
} {
　t = <ALL>
　{ return t.image; }
}

189:179
02/08/27 21:58
ありがとうございます。参考にします。

190:デフォルトの名無しさん
02/08/28 05:15
パスカルやＣはLL?LR?どっちを使ってるの？最近のはやいコンパイラは
みんなLRかな？

191:デフォルトの名無しさん
02/08/28 09:24
最近のflexはスレッドセーフなCコードを吐くようになったのか。
%option reentrant

192:デフォルトの名無しさん
02/08/28 10:06
>>182のリンクはいいリンクだ

193:デフォルトの名無しさん
02/08/28 10:13
>>190
パスカルはLL(1)じゃないの？

194:デフォルトの名無しさん
02/08/28 10:58
PascalはLL(1)でもパースできるように設計されているだけであって、
コンパイラがどうしているかは別。

195:棄教者 ◆witdLTi2
02/08/28 13:04
>>182のリンク先にあるコンパイラのソースコードの解説、
これってWEBを使って吐き出されたのかなぁ。

スレとは関係ないのでsage
そういえば TeX とか WEB とか Knuth なスレってあったっけ?

196:デフォルトの名無しさん
02/08/28 13:41
Texスレはなぜかビジネスソフト板で見たような気がする。
Knuthスレはないんじゃないかな？

>>182のリンク先にある
URLﾘﾝｸ(www.hayalab.cs.ritsumei.ac.jp)
の元のコードってどこにあるの？ないぞ

197:デフォルトの名無しさん
02/08/28 16:32
knuthが作ったＷＥＢ言語って何？気になるんだけど

198:デフォルトの名無しさん
02/08/28 22:53
>>197
Knuthが提唱した文芸的プログラミングの実装、かな？
ドキュメントの中にソースコードを埋め込む形を取ることで、ソースとドキュメントの
間の不整合や、ドキュメント無きコーディングを避けるっていうものらしい。
コンパイルのためにはドキュメントの中からソースを抜き出してコンパイラに渡す
プログラムが必要になる。
で、Knuth自身が作った、TeXドキュメントからPascalプログラムを抜き出してコンパイルする
システムがWEBシステムの筈。

詳しくは
URLﾘﾝｸ(www.google.com)
でも見れ。

199:デフォルトの名無しさん
02/08/28 22:54
>>195
TeX総合スレ@数学板
ｽﾚﾘﾝｸ(math板)

200:棄教者 ◆witdLTi2
02/09/02 13:04
>>111
原田本を今読んでいるところですが、気になった箇所があるので皆さんにお伺いします。
p.164下から11行目
> $p_m$ にアドレス $m+n$ の領域を割り付ける.
とあるのは
> $v_m$ にアドレス $m+n$ の領域を割り付ける.
ではないでしょうか。
ちなみに正誤表
URLﾘﾝｸ(www.hara.cs.keio.ac.jp)
で確認したところ、掲載されていませんでした。
いきなり原田先生にメールして自分が間違っていたら恥ずかしいので、
2CHのハッカーの皆さんに確認してからメールをしようと思います。

201:棄教者 ◆witdLTi2
02/09/02 13:04
ﾃﾕｰｶ200get

202:棄教者 ◆witdLTi2
02/09/02 16:12
>>182
p.15 の BNF の説明
> Backus Nauer Form 　Backus Nauer Form (BNF) では、....
って the Jargon File には
Backus-Naur Form / Backus Normal Form って書いてあるんですけど。。。
Nauer って who?

203:デフォルトの名無しさん
02/09/02 16:33
ドイツ語綴り->Nauer
英語綴り->Naur
だったと思う。

204:棄教者 ◆witdLTi2
02/09/02 17:15
グーグルすると
backus naur form で日本語限定だと213件, 言語非限定だと約20700件ヒット。
backus nauer form で日本語限定だと9件, 言語非限定だと253件ヒット。
おまけに「スペリング修正候補 backus <b>naur</b> form」として修正を勧告される。

205:棄教者 ◆witdLTi2
02/09/02 17:16
×backus naur form で日本語限定だと213件
○backus naur form で日本語限定だと215件

206:デフォルトの名無しさん
02/09/03 21:12
インタープリタの仮想機械に興味を持ち、調べています。

調べてみた JVM、CRI、Python はいずれもスタックマシンのようでしたが、レ
ジスタマシンと比較して何かメリットがあるのでしょうか。

207:デフォルトの名無しさん
02/09/03 22:29
Forthハッカーの伝統。
というのは半分冗談だけど、中間コードが簡単/短くできるからじゃないんですか。
コンパイラも作りやすいし。

208:デフォルトの名無しさん
02/09/04 00:53
詳しくは知らんけど、インタープリタの仮想機械では、
レジスタのアクセスがメモリをアクセスするのと同じ。
パイプラインとかハードウェアで実装する場合の利点が
いかせられないからだと思う。

209:
02/09/04 02:05
>>206
仮想マシンで最もコストが高いのが、コードのフェッチとデコード。
スタックマシンなら、コードも短いしオペランドも要らない。

210:デフォルトの名無しさん
02/09/04 11:34
>>207-209
ありがとうございました。

まとめると、ネイティブコードまでコンパイルするのでなければ、レジスタマ
シンでも結局はメモリへのアクセスを行うことになるので、スタックマシンに
対する利点はなく、むしろコードが短くなる分だけスタックマシンの方が速度
的に有利、というところですかね。

211:ろうひ男爵
02/09/04 12:20
>>210
たしかに、
ネイティブコードへ最適化する場合、レジスタマシンの方が有利ですよね。
広域レジスタとローカルレジスタを割り当てたりした方が最適化しやすいですからね。

一方、インタプリタの場合、おっしゃるとおり
レジスタマシンと言っても結局メモリアクセスされるので、
スタックマシンに対するメリットはないですね。
それだったら、簡単に設計でき、
なおかつコードが短くなるスタックマシンの方が有利でしょう。

自分的には出力されたコードがレジスタマシンの方が読みやすいので、
レジスタマシンを使ってます。(インタプリタですが)

212:デフォルトの名無しさん
02/09/04 14:39
つーかJITコンパイル等でチューニングを詰めていくと
結局どっちも速度的に大差ないという話。

213:デフォルトの名無しさん
02/09/04 21:04
スタックの一部をレジスタにマップする最適化は比較的簡単だから
ネイティブコードでも結構速くなる。
ネイティブコードのみをがりがりチューニングしたければ、中間コードは
３つ組や４つ組がわかりやすいかも。

214:デフォルトの名無しさん
02/09/05 10:00
インタープリタの初歩なら、石田晴久訳のUNIXプログラミング環境の
後半のhocを一通りやってみるのが近道じゃないかな。

215:デフォルトの名無しさん
02/09/05 14:22
スタックマシンでのコンパイルがよくわからない～

216:デフォルトの名無しさん
02/09/06 01:30
ちとスレ違いですが、JITの勉強にお勧めの良書教えてくれませんか？

217:デフォルトの名無しさん
02/09/06 02:16
>>216
詳しくはないけど、良書どうこういうより、
JITについて書かれている本を探すの自体が大変だと思う。
一応、参考URLを貼り付けておく。
shuJIT
URLﾘﾝｸ(www.shudo.net)

218:デフォルトの名無しさん
02/09/07 15:01
コンパイラの理論と実現ではC--という小さなCの処理系を作ってるけど
それのソースコードがわけわからんとです。
構文木の構造体が
struct TREE{
int val;
struct TREE *left;
struct TREE *right;
}
で、
maketree(int a,TREE *b,TREE *c)という関数で構文木を作るんですが、
あるところでmaketree関数のパラメータのbにint型を渡してるんです。
型が合わないからエラーがでると思うのですが、なにか僕が大きな間違いをしてるんでしょうか

219:デフォルトの名無しさん
02/09/07 19:27
>>218
sizeof(int) == sizeof(void*) を仮定していて、
int の即値を格納しようとしているとか?

220:218
02/09/08 11:15
>>219
構文木関係の部分だけ抜き出してコンパイルしてみると、
BCCではエラーがでました(TREE *型にint型は渡せない。と言っておられました）、
clは警告文だけでした。それにちゃんと動きました。
うーむ、やはり即値を渡しているのか。。。

221:デフォルトの名無しさん
02/09/09 17:06
>>218
宣言してない関数の戻り値をそのまま渡してるとか？
それかNULL代わりに0渡してるんじゃない？

こんなんだったらどっちでも昔の名残だね。

222:218
02/09/09 21:26
>>221
なにしろANSIで定められる前のCなので古めかしいところは多いです
たとえば、
func(a,b){
int a;
int b;
}
とか。。。
それと、bには字句解析で得たリテラルを渡してるようです
(TREE *)にキャストしてやることで問題は回避できました。

223:デフォルトの名無しさん
02/09/11 23:39
>>222
それを書くなら、こうだろう。

func(a, b)
　　int a;
　　int b;
{
　　...
}

> それと、bには字句解析で得たリテラルを渡してるようです
正攻法としては union 使うように書き換えちゃえ、かな。

224:デフォルトの名無しさん
02/09/21 12:17
LALR(K)パーサジェネレータのお勧めってありますか？
googleでlalr(k)てしたところいくつか見つかったのですが。

225:デフォルトの名無しさん
02/09/21 13:28
>>224
yacc以外でってこと？
といっても他はyaccの他言語用ぐらいしかしらないけど。

226:デフォルトの名無しさん
02/09/21 14:09
>>225
いやそうでなく k >= 2　という意味でお願いします。

227:デフォルトの名無しさん
02/09/22 19:47
URLﾘﾝｸ(www.cminusminus.org)
これはよいです。

228:デフォルトの名無しさん
02/09/25 09:46
>>227
面白そうですね
簡単に説明してもらえませんか？

229:
02/09/25 10:05
>>228
自分で読む気はないのか？

230:デフォルトの名無しさん
02/09/25 11:26
Cより低級な、簡単なアセンブラとしてのC--ってことでは？

231:デフォルトの名無しさん
02/09/25 21:44
氷魚さんの作ったやつ？

232:デフォルトの名無しさん
02/09/25 22:01
>>231
だれそれ？電波固定？

233:デフォルトの名無しさん
02/09/25 22:09
コンパイラとかじゃなく、ファイルを読む道具としてyacc&lexを
使っているのですが、入力した数値で要素数が定義されてるよう
な場合どうしたらよいでしょうか?

要素数 - 要素...
4 4 4 2 2
5 0 1 0 2 3
2 0 3

という形式です。

int_array
: /* empty */
| integer
| int_array integer
;

では、全部一気に読んでしまうので・・・。(低レベルでスマン・・・。)

234:デフォルトの名無しさん
02/09/26 03:13
>>233
int_array
: /* empty */
| one integer
| two integer integer
| three integer integer integer
(略)
;
とするとか…

イヤスギ

235:デフォルトの名無しさん
02/09/26 03:43
int_list: /* カラ */
| integer
| int_list integer
;
int_array: integer int_list
;

ダメか？

236:棄教者 ◆KIKYO7cg
02/09/26 08:48
-----------------yacc------------
%token NUM
%%
lines : /* empty */
| line lines
;
line : index elements '\n' ;
index : number ;
elements : /* empty */
| number elements
;
number : NUM ;
%%
------------------lex-------------
[0-9]+ { yylval = atoi( yytext ); return NUM; }
[ \t] { /* 空白は捨てる */ }

でどうよ。

237:233
02/09/27 01:01
レス下さった方々ありがとうございます。

>>234
ちょっと無理です・・・。^^;

>>235
最初の要素は良いのですが残りはすべてint_list integerに一致して
しまうようです。

>>236
233の例では行けると思いますが、実はこの形式を出力するツールは
一つではなくて、それらの間で改行の位置というのは統一されていな
いのです。というわけで、できれば改行フリーでなんとかしたいと
思ってるのですが・・・。

うーん、そもそも読み込んだ値を利用したり、繰り返しの回数を制限
するのはyaccで定義できる構文の概念を逸脱しているんでしょうか・
・・。今回はyaccの使用はやめてlexだけに留めるべきかもしれませ
んね。(その辺ご存知の方いましたら後学のため教えていただきたい
です。)

238:デフォルトの名無しさん
02/09/27 01:04
>>237
atoiでいいじゃん。
「何回繰り返す」とかはセマンティクスの部類に入るから、
yacc使うのはお門違い。

239:デフォルトの名無しさん
02/09/27 01:09
>>237
ドラゴンブックにはそういうの（個数の検査とか）は構文では解決でけん
と書いてあった気がします。

240:デフォルトの名無しさん
02/09/27 01:19
>>233
正攻法は単に数値のリストとして、リストに含まれる文字コードチェックに
利用を限ってしまうのがいいんじゃないかな？
考えてみるのは面白そうだけど、
仕事となると、むきになってやっても費用対効果がなさそうだし・・・

241:デフォルトの名無しさん
02/09/27 22:01
ギコBasic新しく作り直してみた

URLﾘﾝｸ(page.freett.com)

242:241
02/10/01 09:30
まだギコBasicのスレが残ってるのに気づかなかった・・・ｽﾏｿ

243:デフォルトの名無しさん
02/10/17 18:25
ANTLRの使い方を日本語で解説してあるウェブページありませんか？

244:デフォルトの名無しさん
02/10/19 07:54
ガイツュシ

245:デフォルトの名無しさん
02/10/19 21:12
STLスレから出張。
これ　URLﾘﾝｸ(spirit.sourceforge.net)　どうなん？

246:デフォルトの名無しさん
02/10/19 23:06
>>245
すげー。びびった。久々に驚嘆したハックだ。

247:デフォルトの名無しさん
02/11/05 22:08
ふふ

248:デフォルトの名無しさん
02/11/07 02:31
以下のような構文を作ります。データを定義しているフォーマットです。xmlとかcvsみたいな物です。
ここから木の様に情報を取り出したいと思ったのですが、上手くパーサを作れません。
tokenizerは簡単に出来るのですが、どうすれば良いですか。rubyでやってます。

object hoge
　caption='hogehoge'
　val=0
　object fuga
　　caption='fugafuga'
　　object aaa
　　　caption='aaa'
　　end
　　object bbb
　　　caption='bbb'
　　end
　　object ccc
　　　caption='ccc'
　　end
　end
end

249:ねこま
02/11/07 02:39
インデントレベルだけで解釈できれば簡単そう

250:デフォルトの名無しさん
02/11/07 02:46
トラバースと逆の手順。
各ノードは子供と親のリンクを持つ。

＜でノードを生成、現在処理中のノードへの参照を
親への参照として新規ノードへ設定。
その後で親に子として新規ノードへの参照を設定。
処理中のノードの参照として新規ノードを指させる。

＞でシングルタグか開始タグか終了タグかを判断し
親に戻るかどうかを決める。
戻る時には処理中のノードの参照として
親を指させる。

こっちにドキュメントを置いてます。
サンプルソースはC++。
ソース玉は整理してないんで乱雑にメモテキストとか
テストデータが散らかっててちょっと気が引ける。
URLﾘﾝｸ(sourceforge.jp)
こういうドキュメントが欲しいとか
掲示板に投げておけばそのうち対処するかも。

251:デフォルトの名無しさん
02/11/07 02:55
>>248
rubyじゃできないな。

252:デフォルトの名無しさん
02/11/07 03:22
手抜き実装で考え方だけ。言語も適当。

loop
　　token　w = Tokenizer.next();

　　if w == 'object' then
　　　　currNode := currNode.pushNewNode( Tokenizer.next());
　　　　continue;
　　end if

　　if w == 'end' then
　　　　currNode := currNode.parent();
　　　　if currNode is null then break;
　　　　continue;
　　end if

　　Tokenizer.skip();
　　currNode.pushNamedValue( w, Tokenizer.next());
end loop

Node というクラスはツリーのノードを表す。
各ノードは子ノードとして、object か namedValue を持つことができる。
pushNewNode は object 子ノードとして追加して、その新規子ノードを返す。
引数はノードの名前を表す。
pushNamedValue は namedValue 子ノードとして追加する。戻り値はなし。
第一引数は値の名前、第二引数は値の中身。

253:デフォルトの名無しさん
02/11/07 04:33
今ちょっと色々調べてたんですけど、色々とヒント有り難うございます。
一週間前にはかけらすらないような事趣味でやり始めて分かったんですが構造を持つ
ファイルフォーマットってコンパイラ作成のような視点が必要なんですね。
さすがにインデントでは無理だってすぐ分かりましたが、xmlに近いことは
気づきませんでした。そう言えばxmlと似てますね。

内部データ構造を持つファイルフォーマットのパーサーの解説の一般的なドキュメント
希望>250

254:デフォルトの名無しさん
02/11/07 07:52
schemeで書くとこんな感じなんだが

(define (hoge-read s)
　(let loop ((x s) (stack '()))
　　(if (pair? x)
　　　(case (car x)
　　　　((object)
　　　　　(loop (cddr x) (cons (list (cadr x) (car x)) stack)))
　　　　((end)
　　　　　(if (null? stack)
　　　　　　(error "Syntax-error - Corresponding 'object' is required :"
　　　　　　　s))
　　　　　(if (pair? (cdr stack))
　　　　　　(loop (cdr x)
　　　　　　　(cons
　　　　　　　　(cons (reverse (car stack)) (cadr stack))
　　　　　　　　(cddr stack)))
　　　　　　(loop (cdr x) (reverse (car stack)))))
　　　　(else
　　　　　(loop (cdddr x)
　　　　　　(cons
　　　　　　　(cons (list (car x) (caddr x)) (car stack))
　　　　　　　(cdr stack)))))
　　　(if (and (pair? stack) (pair? (car stack)))
　　　　(error "Syntax-error - 'end' is required :" s)
　　　　stack))))

255:デフォルトの名無しさん
02/11/07 07:52
;テスト
(define hoge-read-test-data '(
object hoge
　caption = "hogehoge"
　val = 0
　object fuga
　　caption = "fugafuga"
　　object aaa
　　　caption = "aaa"
　　end
　　object bbb
　　　caption = "bbb"
　　end
　　object ccc
　　　caption = "ccc"
　　end
　end
end
))

(hoge-read read-tag-test-data)
=>
(object
　hoge
　(caption "hogehoge")
　(val 0)
　(object
　　fuga
　　(caption "fugafuga")
　　(object aaa (caption "aaa"))
　　(object bbb (caption "bbb"))
　　(object ccc (caption "ccc"))))

256:デフォルトの名無しさん
02/11/07 08:20
(中身的に変んないけど)Cに変換すると
scmobj_t hoge_read(scmobj_t s) {
　scmobj_t x = s;
　scmobj_t stack = nil;
　tail_recursive_loop:
　if (pairp(x)) {
　　if (car(x) == make_symbol("object")) {
　　　stack = cons(list2(cadr(x),car(x)),stack);
　　　x = cddr(x);
　　　goto tail_recursive_loop;
　　} else if (car(x) == make_symbol("end")) {
　　　if (nullp(stack))
　　　　return error("Syntax-error - Corresponding 'object' is required :",s);
　　　if (pairp(cdr(stack))) {
　　　　x = cdr(x);
　　　　stack = cons(cons(reverse(car(stack)),cadr(stack)),cddr(stack));
　　　　goto tail_recursive_loop;
　　　} else {
　　　　x = cdr(x);
　　　　stack = reverse(car(stack));
　　　　goto tail_recursive_loop;
　　　}
　　} else {
　　　stack = cons(cons(list2(car(x),caddr(x)),car(stack)),cdr(stack));
　　　x = cdddr(x);
　　　goto tail_recursive_loop;
　　}
　} else if (pairp(stack) && pairp(car(stack)))
　　return error("Syntax-error - 'end' is required :",s);
　return stack;
}

257:デフォルトの名無しさん
02/11/14 06:59
>>245
Expression Templateをはじめ各種のテンプレート・メタ・プログラミングは
知ってたけどPaser Generatorにまで行きつくとは。　
　カ　コ　イ　イ　！　！
テンプレートらしく解析対象の列の要素型がパラメタ指定できるのもカコイイ！
（char, w_charに始まってユーザー作成のクラスまで）
字句解析器も含んでるしね。

当方Java（正確にはバイトコード）のPartial Evaluationを実装中なのだが、
Javaに演算子多重定義が導入されていれば、
合わせ技で同じようなことが狙えたのになァ。惜しい。
（メソッド呼び出し式で書けば良いわけだが、カッコ良さが大いに減る。）

258:デフォルトの名無しさん
02/11/17 16:17
>>257
でも、あんまり真剣な用途には使えないよね。

実行時にパーザ生成するんだったら、文字列で文法与えても良いな。

259:祐一ゴン
02/11/17 19:39
やぁ、ぼく押金さん(*´∀｀*)ノ
中学の時からポカリの粉を麻薬と思って鼻から吸ってたけどヽ(`Д´)ﾉｳﾜｧｧﾝ!!全然トリップできないや！最近初めてその事実を知ったよ
今部屋をﾃﾗﾌｫｰﾐﾝｸﾞしたら鼠の干からびた死体が出てきたよ、あまり旨くなかったよ

260:デフォルトの名無しさん
02/11/18 04:16
パスカルとベーシックってどっちが作りやすいですか？

261:：－）
02/11/18 07:12
pascal→delfy
ベーシック→HSP

HSPはタダの開発環境です。デルフィは１０万円くらい？

262:デフォルトの名無しさん
02/11/18 11:55
たとえば、関数呼び出し
a(b(c(d())));
ってのをなんらかの中間コードにしてあって、
これを１パスでコード生成できるの？
（最適化はどうでもいい）

a();
のコード生成はできるけど、
a(b());
のようにネストするとできなくなって困ってます。

263:デフォルトの名無しさん
02/11/18 12:01
>>262
ちょっとは考えろ
つーか、お前の言う中間コードって何のためにあるのさ

264:デフォルトの名無しさん
02/11/18 13:15
>>262
> ってのをなんらかの中間コードにしてあって、
> これを１パスでコード生成できるの？

「これ」というのが「中間コード」を指しているのなら、
どのような「中間コード」なのか示してもらわないと。

) を検出したタイミングでコード生成すりゃいいだけの
話なんだけど。

265:デフォルトの名無しさん
02/11/18 17:40
バイトコードバイトコード!

266:デフォルトの名無しさん
02/11/19 00:50
>>261
デルファイじゃないのか？Delphi
嘘教えるなよ

267:デフォルトの名無しさん
02/11/19 01:10
>>261はどうみても無知だろ

268:デフォルトの名無しさん
02/11/19 03:22
>>260はコンパイラ作るならbasicかpascalどっちを作ったほうがいいかって
いってるんだろ。どっちだろう、俺はベーシック知らないからなんとも
いえん。

269:デフォルトの名無しさん
02/11/19 03:26
コンパイラならPascalだろうが、
インタプリタならBasicの方が楽だろう。
昔のBasicインタプリタは4KBくらいだった。

270:デフォルトの名無しさん
02/11/19 03:59
ベーシックインタプリタのコードってないの？

271:デフォルトの名無しさん
02/11/19 05:11
>>271
ほれ
URLﾘﾝｸ(homepage2.nifty.com)

272:デフォルトの名無しさん
02/11/19 11:09
>>260-270
…この21世紀になんでその2択に拘るんだw。

273:257
02/11/19 11:13
>>258
使えないかねぇ…。この辺の技術には期待したいトコロなんだけどなぁ。
私も使ってみたわけではないので大丈夫と言い切れるもんではないんだが。

実行時というか、コンパイル時にテンプレートの展開動作を利用して
パーザが作られるようなんだが。

274:デフォルトの名無しさん
02/11/21 13:10
>>270
ギコBASICは参考にならないですか？

275:デフォルトの名無しさん
02/11/21 14:05
この辺は？
URLﾘﾝｸ(member.nifty.ne.jp)

276:デフォルトの名無しさん
02/12/03 17:38
bisonが吐き出したコードってなんでVC++でコンパイル通らないんだ？
激しく鬱…

bison++/flex++に乗り換えるかのぉ。ドキュメント少なすぎだが・・・

277:デフォルトの名無しさん
02/12/03 18:48
>276
> bisonが吐き出したコードってなんでVC++でコンパイル通らないんだ？
gcc 使え、というお達しかと……。ところで byacc とか kmyacc はどう？

278:276
02/12/04 14:34
正確にはC++ソースとしてコンパイルしようとすると、VC++には入ってない(おそらくPOSIX互換の？)インクルードファイルを要求されてコンパイルできません。
まぁ、別にオブジェクト指向な解析器が作りたいというわけではなく、ただアクション書くのにクラスとか使いたいだけなんだが…

何かいい方法あったらキボンヌ！というか、bison++/flex++の日本語ドキュメントなんか激しくほすぃかも

279:デフォルトの名無しさん
02/12/04 14:47
>278
include 外せばいいんじゃないの？

280:デフォルトの名無しさん
02/12/04 19:38
>279
それだと毎回 *.y からコード生成するたびに書き換えが必要になるから、
ダミーのヘッダファイルをでっち上げるに一票。

っつか、どうしても再入可能にしたいとかで bison の機能が必須でなければ、
bison 以外の yacc 互換処理系を試す方が幸せかも知れんが。

281:278
02/12/05 01:17
>>280
bison以外ならC++ソースとしてビルドできるんですか？

今日はbison++/flex++試しﾏｽﾀ。今度はVC++だとエラー出まくって全然ビルドできない罠。

byaccとkmyacc試してみるかなぁ。

282:デフォルトの名無しさん
02/12/05 08:55
yaccの使い方教えろや

283:bloom
02/12/05 09:10

URLﾘﾝｸ(www.agemasukudasai.com)

284:デフォルトの名無しさん
02/12/05 09:23
coco/r使えよ

285:デフォルトの名無しさん
02/12/05 12:01
coco/rって何か教えろや

286:デフォルトの名無しさん
02/12/05 15:39
うえーんコンパイラフレームワークｷﾎﾞﾝ( ●д●)

287:デフォルトの名無しさん
02/12/05 16:53
>>286
lex + yacc + RTL(gcc)じゃ駄目か？

288:デフォルトの名無しさん
02/12/05 16:56
yaccかbisonについて優しく解説してるサイトはありませんか?
または本でも。

289:デフォルトの名無しさん
02/12/05 18:16
ちょっと聞いていいですか？
このスレ、結構人が訪れているみたいなんだけれど、
実際にコンパイラレベル(変な言い方だけど)のものを作ってる、もしくは作った人っています？
自分はスクリプトぐらいなら、何とかいけそうなんだけれど、
コンパイラまでくるとかなり大変じゃないですか？

290:デフォルトの名無しさん
02/12/05 19:34
仮想的なスタックマシンとかのコンパイラなら
作ってる人は沢山いると思うよ。

291:デフォルトの名無しさん
02/12/05 19:40
>288
オライリーの lex & yacc 本

>289
アセンブラを出力させるなら、そんなに面倒じゃない。実行できるバイナリを出力
しようと思うと、山のような詳細に追われて力尽きる。

292:デフォルトの名無しさん
02/12/05 20:17
インストラクションコードへの変換が面倒だなあ。
テーブル化するのが。

293:デフォルトの名無しさん
02/12/06 07:28
変な聞き方してしまいました。
コンパイラといっても仮想マシンコードに変換するスクリプトコンパイラだってあるし。
ネエィテブなアセンブルや直接、実行形式を吐くコンパイラのことを聞いたつもりでした。

294:ろうひ男爵
02/12/13 20:28
>>289
自分は構造化BASICで186のDOSの.COMを出力する物を作ったよ。
今は暇を見つけて簡易的なC言語コンパイラを作ってるよ

295:デフォルトの名無しさん
02/12/13 20:34
だれか僕のためにCコンパイラのソースみせてください。
Cじゃなくてもパスカルでもベーシックでもいいっす。
(￣人￣)オ・ネ・カ・゛イ♪ヽ(*￣〓￣*)ノ^☆ブチュゥゥ♪

296:デフォルトの名無しさん
02/12/13 20:41
ギャーーーーー

297:デフォルトの名無しさん
02/12/13 20:56
>>295
URLﾘﾝｸ(gcc.gnu.org)

298:デフォルトの名無しさん
02/12/13 21:15
>>295
ほれ

#include <stdio.h>
main()
{
printf("逝ってよし");
}

299:デフォルトの名無しさん
02/12/13 21:33
ｳﾜｧｧｧｧｧｧヽ(`Д´)ﾉｧｧｧｧｧｧﾝ!

300:ろうひ男爵
02/12/14 17:55
>>295
BASICで、

[ラベル:]　if 比較式 goto ラベル
[ラベル:] print "メッセージ"
[ラベル:] 代入式

でよかったら、構文解析もほとんどいらないし簡単じゃない?
改行で行末にして、変数の頭にRをつけてR10とかすれば、
悩むところはないと思うよ。

パスカルだとラベルを読み込むときに細工すればLL(1)だよね、
そんなに難しくないはずだよ。
Cにしろパスカルにしろなにがしらの本を読んだ方が良いんじゃない?

言語はどのレベルの物を作ろうとしてるの?
それと、実行環境はスクリプトで中間言語に落としての実行環境?

301:デフォルトの名無しさん
02/12/14 19:56
>295
どうせ渡されたところで読めない、に 1 票。

言語処理系を作るのが初めてなら、とりあえず「UNIX プログラミング環境」でも
買ってきて hoc の実装追ってみれば？

302:デフォルトの名無しさん
02/12/14 20:38
つーかコンパイラのソースが見たいんならgccなりOpenWatcomなりがあるわけで。
それぐらい自分で探せｳﾞｫｹつー。

303:デフォルトの名無しさん
02/12/14 21:05
bccが一番読みやすいなり

304:デフォルトの名無しさん
02/12/14 21:24
>302
いきなり gcc は厳しすぎ。

10年前だと「アルゴリズム＋データ構造＝プログラム」読めというところだが、
さすがに古いよな…。

305:デフォルトの名無しさん
02/12/14 22:29
URLﾘﾝｸ(www.amazon.co.jp)
はどうよ？　インタープリタだけど。

306:デフォルトの名無しさん
02/12/14 22:31
たけーんだよバカ

307:デフォルトの名無しさん
02/12/15 00:57
専門書の類は、どれもそんなもんだ。諦めれ。

308:デフォルトの名無しさん
02/12/15 07:18
一応タダで読めるけどな。
URLﾘﾝｸ(i.loveruby.net)

309:ろうひ男爵
02/12/20 04:02
Cマガでコンパイラのことをやってますね。
演算子順位法とLL(1)をざらっと、LALRの概説です。
計12ページぐらいだったので、ここにいる方には物足りませんが、
読みやすかったので、人に聞かれた場合にはイイかも。

310:デフォルトの名無しさん
02/12/20 04:16
ｽﾚﾘﾝｸ(lobby板)
これよんでみれ！

311:デフォルトの名無しさん
02/12/20 04:44
えっ、bisonで生成したコードってVC++じゃ、
コンパイルできないのですか？
じゃあ、かわりにVC++で通るyacc互換でお勧めってあります？
仕事でも使うかもしれないので商用OKだとありがたいのですが。

312:デフォルトの名無しさん
02/12/20 04:56
GC(ガベコレ)についてちゃんと勉強してみたいのですが、
何かいい書籍はありますか？今は少しづつですが、gccに含まれている
Boehmのソースで勉強してますがなかなか思うように進みません。

VMにそのようなものが書かれているものがあればそれでもOKです。
よろしくお願いします。

313:デフォルトの名無しさん
02/12/20 06:48
>>312
とりあえず、>>305に紹介されてる本読むとか。

314:デフォルトの名無しさん
02/12/20 09:45
>>309
概説でしかないし、yaccはちょこっとだけしか載ってない。
作るための特集じゃなくて、基礎知識をお勉強するための記事だった。
という印象。

315:デフォルトの名無しさん
02/12/20 09:47
>>311
VCでコンパイルできなかったっけ？
まぁいいや。

URLﾘﾝｸ(www.kohsuke.org)
これなんかどうよ。使った事無いけど。

316:ろうひ男爵
02/12/20 13:09
>>314
さすがにあのページ数だと、1つでも掘り下げるのは難しかったみたいですね。
その中では演算子順位法が分かりやすかったと思います。

317:デフォルトの名無しさん
02/12/20 13:40
>>311
通るよ。

でもbisonで生成したコードにはGNUのテンプレートが含まれるので、商用はま
ずかったと思う。

318:デフォルトの名無しさん
02/12/20 22:12
>>312
書籍じゃないけど。
URLﾘﾝｸ(www.dcs.qmul.ac.uk)

319:デフォルトの名無しさん
02/12/21 01:10
>>317
出力されたコード見れば分るけど 1.24 以降は特例として GPL 適用外になってる。

320:デフォルトの名無しさん
02/12/21 08:09
>>319
あ、変わったんだ。サンクス。

321:デフォルトの名無しさん
02/12/21 18:09
bisonを使った宿題が出ているのですが、
ここでそのことについて質問してもいいでしょうか？

322:デフォルトの名無しさん
02/12/21 23:16
>>321

>yaccやlexの使い方やら言語仕様やらの話題。
だから、宿題丸投げじゃなきゃいいと思うよ。

323:デフォルトの名無しさん
02/12/22 01:11
>>321
　何か本を入手した？（購入するのも、図書館で借りるのも可。）もしまだなら、
　　　書名：UNIX Literacy Series Vol.12　UNIX yaccとlexの使い方
　　　発行所：HBJ出版局
　　　著者：田中正広
　　　ISBN：4-8337-8728-8
を入手して読んでみるといいYO！現在これ読んで某課題と格闘中(^^;
　で、そういった本を読んでから質問するのなら十分OKかと。>>322に同意

324:デフォルトの名無しさん
02/12/22 01:13
スクリプト言語でアセンブラ処理系は作れるのか？

325:デフォルトの名無しさん
02/12/22 01:28
>124
作れるよ

326:デフォルトの名無しさん
02/12/22 11:56
最近、Flex&Bisonをいじり始めました。
まだ、基本概念を勉強中なのですが、Flex&Bisonを使った「C++」用の
チュートリアルや簡単なサンプル実装などないでしょうか？
「C」での実装はいろいろあるんですが、自分はC++で実装したいの困ってます。
C++での解説も申し訳ない程度にはあるんですが、やっぱりサンプルがあると助かります。

327:デフォルトの名無しさん
02/12/22 12:04
スクリプト言語でアセンブラ処理系ってのもいみなさそうだな。
C言語をスクリプト言語として動くように作ったことはあるが。

328:デフォルトの名無しさん
02/12/22 14:09
>>327
意味あるよ

329:デフォルトの名無しさん
02/12/22 14:52
>>328
新規チップの設計用とか？ｗ

330:デフォルトの名無しさん
02/12/22 15:38
>329
ユーザにアセンブラ処理系の機能拡張をさせる場合には、スクリプト言語を
そのまま使えるのは嬉しいかも。自前でマクロ言語作るのって手間だし、マ
クロの設計がダサいとユーザの不満もたまるし（ｗ

ただ、往々にしてバイナリ入出力の扱いって C, C++ の方が楽なんだよね。

331:デフォルトの名無しさん
02/12/22 18:58
Cマガの特集見ました。
よしこれから面白くなるってところで、終わってました。
期待してたのにちょっと悲しい。

332:321
02/12/22 21:22
自己解決しました。
皆さん、ご迷惑をおかけしました。

333:デフォルトの名無しさん
02/12/23 00:22
URLﾘﾝｸ(catalog.compilertools.net)
このあたりはどうかな。

334:デフォルトの名無しさん
03/01/02 18:47
RTLでいいですか？

335:デフォルトの名無しさん
03/01/02 19:45
あははコンパイラを作るのって楽しいなぁ(´∀｀)

336:デフォルトの名無しさん
03/01/02 19:48
YACC link
URLﾘﾝｸ(www2.dewa.or.jp)

337:デフォルトの名無しさん
03/01/04 01:51
>336
チクショー！！
まんまとだまされたぜ。

338:デフォルトの名無しさん
03/01/04 08:38
山形オートキャンパークラブ(´д｀;)

339:中卒
03/01/04 14:37
ナカータ育男の本でわけわからん数式が出てきてるんですがどうにかなりませんか？

340:ろうひ男爵
03/01/04 20:02
>>339
頑張って、勉強するしかないのでは。
もしくは、より簡単な、今月のcマガの特集とか、
コンパイラの仕組み渡邊坦著
とかはどう?

341:デフォルトの名無しさん
03/01/04 20:23
「モナーのコンパイラスレ出張所」ページでも作るか。
AAで語るFSAとか。ネタよろしこ。

次ページ