「コンパイラ・スクリプトエンジン」相談室11

「コンパイラ・スクリプトエンジン」相談室11 at TECH

[前50を表示]
300:デフォルトの名無しさん
07/01/16 22:17:20
慣れれば普通だよ

301:デフォルトの名無しさん
07/01/20 16:58:13
パーサジェネレータとかって勉強するにはどういう本を探せばいいのでしょうか？
いままで自作言語ばっかり書いてきたんですけど、パーサジェネレータってもんがあることを最近知りました。
でも、勉強しようにも難しくてサイトみてもよくわからない状態です。
なにかわかりやすいオススメ書籍とかないでしょうか？

302:デフォルトの名無しさん
07/01/20 22:37:09
中田先生の本はアレだな。理論の説明はいいんだけど、その理論を実際どういうときに使うのかもう少し詳しく書いてくれればもっとわかりやすくなるな。
できれば１つ１つの理論とＣ言語のコードを対にして書いてほしい。

303:デフォルトの名無しさん
07/01/22 23:39:17
コンパイラの構成と最適化を読んでいて再帰的下向き構文解析のところまで読んだのですが、
構文解析と字句解析の区別がよくわからないのです。

再帰的下向き構文解析だと、例えば B -> aAb は
B(){ aを読む; A(); bを読む; } みたいになるのですが、
全ての生成規則を書いていくと
結局は字句解析がいらないことになってしまいませんか？

304:デフォルトの名無しさん
07/01/23 01:33:19
Wikipediaさんに聞くと良いと思うよ。
字句解析：入力を字句（プログラムの最小単位）に分割する
Wikipedia項目ﾘﾝｸ
構文解析：字句同士の関係を解析するWikipedia項目ﾘﾝｸ

乱暴に単純化すると、字句解析は正規文法で扱える範囲を処理して、
構文解析は文脈自由文法で扱う範囲を処理する。

boost::spiritみたいに両者をシームレスに処理するのもあるけど、
普通は分割して扱ったほうが分かり易い。

305:デフォルトの名無しさん
07/01/23 17:37:37
>>303
字句解析しないということは、文字単位で構文解析することになるけど、
f 一文字を読んで、予約語の for なのか、ただの識別子なのか判断つかないのが下向き構文解析だとちょっと困る。

LR構文解析の場合は、字句解析を分けた方がメモリや計算の手間がだいぶ減るような気がする（今の計算機だと大した差ではないけど）。

306:デフォルトの名無しさん
07/01/23 19:06:48
C++みたいに、文脈情報が無いと字句解析できない場合はわけない方がいいのかも。
最近流行？のcombinator parserも基本はわけないよね。

307:デフォルトの名無しさん
07/01/23 19:07:45
Lispなら（ｒｙ

308:デフォルトの名無しさん
07/01/24 20:40:02
>>306
あと、同じく最近流行？のPackrat Parserでも字句解析は分けないね。
個人的には、字句解析というのはあくまでLALRとかLLなどのよくある
構文解析アルゴリズムで処理できるようにするためであって、本質的には
要らないというか有害ですらあると思う。例えば、最近の言語だと文字列
(普通は字句解析で処理される)の中に式(構文解析で処理される)を埋め込む
ことができる言語が普通にあるが、こういうのは字句解析と構文解析が分かれて
いると非常に実現しにくい。

309:デフォルトの名無しさん
07/01/24 20:58:24
packrat parserって下降型のparserだっけ？
左再帰は大丈夫？

310:デフォルトの名無しさん
07/01/24 23:34:14
後戻りできるようなものを作ろうとすると、
字句解析と構文解析が分かれていたら非常にやりにくい。

311:デフォルトの名無しさん
07/01/24 23:56:34
ループ以外の左再帰って使う機会あるの？

312:デフォルトの名無しさん
07/01/25 23:13:20
>>309
左再帰はNG。そういうのは繰り返し(*)を使って書くのが定石。
右結合の演算子の場合は、右再帰で書くけど。

313:デフォルトの名無しさん
07/01/26 08:21:29
21世紀にもなったというのに、左再帰を人手で展開せなあかんのか…
あれ、文法が汚くなるから嫌いなんだよな

e ::= e + e | n

が

e ::= n (+ e)*

になるのはつらい。

314:デフォルトの名無しさん
07/01/26 12:03:23
>>313
まあ、その辺はトレードオフということで
ちなみに、俺はトップダウンparsing的な発想がデフォだから
左再帰を人手で展開するというよりも、展開系がまず先に
思い浮かぶ

315:デフォルトの名無しさん
07/01/26 20:44:33
>>301
自己レス。同じ疑問をもった人へ。
いまどきのプログラム言語の作り方
URLﾘﾝｸ(www.amazon.co.jp)
がいいと思う。
字句解析と構文解析がわかればどういうもんか一発で理解できると思う。

316:デフォルトの名無しさん
07/01/26 23:22:55
つ URLﾘﾝｸ(www.hpcs.is.tsukuba.ac.jp)
　　URLﾘﾝｸ(kmaebashi.com)
　　>2-3
まずはこんなところじゃね？
　

317:デフォルトの名無しさん
07/01/27 02:35:40
>>316
いや、自分にはこの↓説明がいかんかったです。

字句解析
ソースプログラムを、「字句(トークン)」の並びに分割する処理です。
構文解析
トークンの並びから、解析木を構築する処理です。

何度読んでもさっぱりわかりませんでした。
>>315の本はこのわからん部分がわかるのでいいと思いました。
これが他とちょっと違う部分です。

318:デフォルトの名無しさん
07/01/27 02:38:38
>>317
理論抜きでもｲｲから、他のちっこいスクリプトをまねして、
とにかく一回でも、実装してみれば、
ああーんそうか、って納得できるんだけどね・・・。

319:デフォルトの名無しさん
07/01/27 04:17:50
パーサコンビネータの論文ありますか？

320:デフォルトの名無しさん
07/01/27 13:27:52
最適化って、結局はグラフの操作がメインになるんだけど、
あれは、ややこしいねぇ・・・

（プロトタイプ的に）ナイーブな実装をしようとしただけでも、
普通のグラフライブラリなんて殆ど役にたたないし・・・

良いグラフライブラリがあれば、教えてください。

321:デフォルトの名無しさん
07/01/29 02:42:01
>>320
最適化って例えばどんなやつ？
それによって変わるような気がするけど。

322:デフォルトの名無しさん
07/01/30 07:53:13
>>321
"ほにゃららほにゃらら　elimination"　とか、
データフロー解析に絡む
あの一連のやつ。

323:デフォルトの名無しさん
07/01/31 00:31:19
>>322
フローグラフ上のデータフロー解析なら
自分で実装するのがたぶん一番楽。

データフロー方程式を解くシステムは昔からあったと思うけど
なんかいまいち流行ってないし。

最近はCTLモデル検査とかで最適化する人もいるらしい。

324:デフォルトの名無しさん
07/01/31 13:34:45
フローグラフ解析かぁ。
coins.flowあたりみればいいのかと思ったけど、さっぱりわからないです。
超簡単なソースどっかにないかなぁ。

325:デフォルトの名無しさん
07/01/31 16:59:50
>>324
coins.backend.ana.LiveVariableBitMap
とか結構簡単だと思われる。

326:デフォルトの名無しさん
07/02/01 23:47:32
>>323
手で書くのが難しいレベルの最適化って論理式で書けるの？
実行時間は？

327:デフォルトの名無しさん
07/02/02 02:26:28
>>326
データフロー方程式を解くのと同程度のことなら書けるらしい。
それ以上だとたぶん無理。

実行時間はデータフロー方程式解くのと同じくらいかと。

328:デフォルトの名無しさん
07/02/02 18:36:34
へー
おもしろそうだね

329:324
07/02/03 12:44:06
>>325
おおー、理解できる予感！！

「コンパイラの構成と最適化」を見ながらソース読んでみてます。

LiveVariableBitMapのBitMapはBitMapSetのことですよね。
BitMapSetクラスは単なる０か１かが入ってる配列の管理クラスみたいなもんと。
live variable 解析は「12.2.7 変数の生と死の解析」のこと。

この「変数の生と死の解析」の結果を使って「12.2.8 無用命令の削除」等が出来ると。

330:デフォルトの名無しさん
07/02/04 01:03:22
俺スクリプトがようやっと文字列結合まで回るようになった……

誰か、クラス設計とかで参考になりそうな資料ご存知ですか？
……Rubyのクラスを参考にしようかな

331:デフォルトの名無しさん
07/02/04 03:30:00
>>330
つ　諦めろ

332:デフォルトの名無しさん
07/02/04 04:39:42
>>330
URLﾘﾝｸ(www.squeak.org)
URLﾘﾝｸ(www.cincomsmalltalk.com)

333:デフォルトの名無しさん
07/02/04 11:21:15
squeakね。クラスはこんな感じか。
URLﾘﾝｸ(squeak.qp.land.to)

Collectionが充実しとりますな。何でそうなったかの経緯はわからんけど……
マクロ的なものが無かったからかね？

334:デフォルトの名無しさん
07/02/04 11:31:37
>>333
そこのサイト並べ方がよろしくないね。
継承関係がわかるように入れ子で表示するとコレクションがどういう方向でできてるのかよくわかるのに。
smalltalkならクラスブラウザで眺めるだけでいいから必要感じないのかもしれんけど、知らない人が見たらたくさんあってパニック起こすだけじゃないかと思った。

つーわけで330は一度squeakを実行してみるよろし。

335:デフォルトの名無しさん
07/02/04 12:02:38
>334
「自由自在～」持ってたので、それを参考にブラウズしてみました。
……すごい数ですな。GUI系を飛ばして眺めてみます。

336:デフォルトの名無しさん
07/02/06 23:24:01
質問です。

スクリプト言語を作ろうと思って、まずはC++でC言語コンパイラ作ってるんですが、
typedefの処理に困っています。

ソースファイル内の全ての構文解析完了後に、
構文木をたどって意味解析処理の一部としてtypedefの解析をしています。
この方法だと構文解析機がtypedefで定義された型名を使用して変数を宣言しようとしたとき、
typedef定義された型名を型名として認識できません。

解決方法として2つを考えています
・構文解析中にtypedefを検出してtypedef定義テーブルを作成する
・構文解析を2回行う(1回目はtypedefを含めたシンボルの検出、２回目が本当の構文解析？)

皆さんどちらの手法でやっているのでしょうか。
それとも、こんな現象は発生しない？

337:デフォルトの名無しさん
07/02/07 03:04:23
有名な問題なのでぐぐれ。

338:デフォルトの名無しさん
07/02/12 01:34:47
>>303
その疑問はもっともだと思う。

字句解析と構文解析が別れている主な理由は、
yaccを真似たコンパイラ・コンパイラが多いことと、
字句解析には字句解析ならではの問題があるため。
他には、コンパイラの教科書でも字句解析と構文解析が分けられている
ことなんかが挙げられるかもしれない。

一般的に字句解析では、構文解析で使われるLR(k)やLALR(1)よりも
一段制約が多く、より高速に動作する正規表現という文法を使う。
普通こういうことは考えないけど、
正規表現はLALRなどのよく知られている文脈自由文法により常に表現可能で、
(逆は無理な場合がある)
原理的には字句解析を構文解析に組み込むことはできる。

ただし、現実の字句解析が教科書的で単純な方法で行われることは稀で
普通は予約語のマッチを一通り試した後、
どれにもマッチしない場合はそれを識別子として扱うという
バックトラック的な処理が必要になる。
これが普通のLALRなどではできないので、
よく知られたコンパイラ・コンパイラ、yaccやbisonなんかでは
字句解析と構文解析を一緒にやることは無理ではないかと思う。
また、速度的な観点から避けられることもある。

一昔前(yaccが作られたのは1970年代)は、
パソコンの性能が今では考えられないくらい低かったし、
理論の構築も進んでいなかったので
この二つを分けることが絶対に必要だった。
もうこの考え方は古いのかもね。

339:デフォルトの名無しさん
07/02/12 04:57:43
無理してやればできるんでないの？

symbol ::= alphabet alpabet_or_digits

終端でない記号が爆発的に増えてコンパイルできなくなりそ。
遅延評価で空間量を時間量に置き換えてどうたらかな。

340:デフォルトの名無しさん
07/02/12 08:05:49
大まかに言うと字句解析は正則言語（⊆文脈自由言語）の解析、構文解析は文脈自由言語の解析なんだから、字句解析の部分も構文解析でできるに決まってるでしょ。

処理が二つに分かれている理由は、字句解析を有限オートマトン風に処理するアルゴリズムは、既知の構文解析のアルゴリズム（LL等）よりはるかに高速なこと。
それと構文解析木の底辺（＝字句解析前の入力文字列）を字句解析で押し上げれば、構文解析の入力の個数を（定数分の一に過ぎないが）減らせること。
木構造の性質を考えれば、底辺の要素数は、木全体の底辺以外の全要素数より多くなるでしょ（ε生成を除去できることから）。

基本的には理論的な背景がある。

341:デフォルトの名無しさん
07/02/12 16:20:44
正規言語を受理するlexerを、文脈自由言語を受理するparserで置き換えることができる
のは当然だが、これは今の話に余り関係ない。
字句解析-構文解析と処理をわけなかった時の一番の問題は、>338で言われている通り、
バックトラックもしくは予約語の最大長分の先読みが必要になること。
packrat parserはバックトラック演算子があるんだっけ？

342:デフォルトの名無しさん
07/02/12 16:43:34
>>341

packrat parsingではバックトラック演算子があるわけじゃなくて、
デフォルトの動作がバックトラック。つまり、

A | C

という式があった場合、まずAにマッチするかどうかを試して、失敗した場合Cを
試すという動作になる。ただ、これだけだと困る場合があるので、そういうときは
syntactic predicateという無限長の先読み演算子を併用することになる

343:デフォルトの名無しさん
07/02/12 19:05:13
なるほど。サンクス。
Cのparserでも書いてみるかな。

344:デフォルトの名無しさん
07/02/22 21:52:02
再帰下降構文解析をするときに、
深いところで起きたエラーを戻り値で次々と伝えて行くやりかたは
かっこ悪いですよね?

345:デフォルトの名無しさん
07/02/23 23:36:50
例外はどうでっしゃろ？

346:デフォルトの名無しさん
07/02/24 00:18:45
>>345
投げられない言語もあるからなぁ。

347:デフォルトの名無しさん
07/02/24 03:44:41
そこでデータとして定義したステートマシンを各文法ごとに用意して
スタックにそれのステートを積んで行き
本質的には再帰だけどループで実行できて
エラーがあったときはただそのループを止めるだけ
なんてのはどうでしょう

ギャグで言ってます

348:デフォルトの名無しさん
07/02/24 05:59:51
人間bison!
まさかコレが「件」って奴？

349:デフォルトの名無しさん
07/02/24 11:07:55
>>345
if( !is_ident(context) ){
　throw syntax_error("hoge hoge");
}

こんな感じのプログラムが、カッコいいとは到底思えない俺がいる

350:デフォルトの名無しさん
07/02/24 15:00:14
再帰だとスタックを使い過ぎてオーバーフローしないだろうかと
不安だった、そういう時期が僕にもありました

351:デフォルトの名無しさん
07/02/25 05:04:58
Rubyのインタプリタはスタックオーバーフローで死んだりする……

352:デフォルトの名無しさん
07/02/26 08:53:12
どんだけスタック食いつぶすスクリプト書いたんだｗｗｗ

353:デフォルトの名無しさん
07/02/26 19:14:21
>>352
Mac OS Xのデフォだと簡単に食いつぶす。
なのでulimitでスタックの制限をunlimitedにしなきゃならん。

354:デフォルトの名無しさん
07/02/27 20:25:27
>>352
たらいまわしとかだろｗ

355:デフォルトの名無しさん
07/03/02 02:44:15
>>354
スクリプトの実行でスタック食いつぶすなら再帰呼び出しすればいいだけだけど、インタプリタのスタックを食いつぶすってことは、やたら深いネストや式を自力で書くとか（もしくは何らかのプログラムでわざと生成？）しなきゃ無理ですな。

356:デフォルトの名無しさん
07/03/02 02:54:05
>>355
……え？

357:デフォルトの名無しさん
07/03/02 03:00:47
なるる

358:デフォルトの名無しさん
07/03/03 23:21:19
ちょっと質問良いですか？

行末に対してはセミコロンを省略しても良いようにしたいんですけど、
pnuts　がやってるみたいに　『改行入れても良い部分を全部明示的に指定する』　よりもっとスマートな改行な方法あります？
当方　JFlex　と　Jay　を用いております。

359:デフォルトの名無しさん
07/03/04 08:46:19
>>358
Pnutsのような方法以外だと、Lexerに改行を無視する状態と無視しない状態の
２つの状態を持たせて、ParserからLexerの状態を明示的に状態を遷移させる
という方法がある。ただ、それほど楽にはならないと思うけど。

360:デフォルトの名無しさん
07/03/17 12:21:14
>>358
つまりPnuts式はStatelessなlexerであり、lexerは楽できるけどParserがめんどい。
>>359の方法はlexerがstatefulになって少し面倒くさくなるぶんparserがすこし楽になる。
トレードオフだな。

しかし昔に比べて過疎ってるな。

361:デフォルトの名無しさん
07/03/17 23:54:30
俺言語を造っている変態が減ったんだろ
……俺言語の設計ってけっこう楽しいけど、破綻しないように作るのはしんどいよね。

362:デフォルトの名無しさん
07/03/18 15:23:34
構造体についての実装方法が載っている良書を教えてもらえませんか？
サンプルソースがあるとベターです

どうもCのサブセットと言いつつ構造体を省いている本しか持ってないので・・・

363:デフォルトの名無しさん
07/03/18 15:39:23
別に何を悩むこともないと思うんだが。

364:デフォルトの名無しさん
07/03/18 15:48:44
磯Cでいいんでない？

365:デフォルトの名無しさん
07/03/18 15:50:43
それが関数の呼び出しで詰まりまして
ある関数のreturnで構造体を返した場合ですが
呼び出し前に返値用のスタックを確保しておいて
そこにreturnのときにコピーするようなまどろっこしい方法しか思いつきません。

それと、動的配列を有している構造体など
どうしてるのかいなと思いまして

366:デフォルトの名無しさん
07/03/18 15:56:41
磯Cてなんですか？検索掛けたら考古学関連がでましたが・・・

367:デフォルトの名無しさん
07/03/18 16:01:48
動的配列のポインタを持っている構造体で無く？
そのものを持っているのですか？

368:デフォルトの名無しさん
07/03/18 16:04:55
>>366
ＣはISOでも標準化されてる
たしか言語そのものともうちょっとこまごまとしたものがあったはず
Wikipedia項目ﾘﾝｸ

てかアライメントさえ気をつければいいだけなんじゃないか？

>　そこにreturnのときにコピーするようなまどろっこしい方法しか思いつきません。　
それでいいんじゃなかったかと

369:デフォルトの名無しさん
07/03/18 16:05:59
ついでに呼び出し既約
Wikipedia項目ﾘﾝｸ

370:デフォルトの名無しさん
07/03/18 16:10:44
そこらがどう実現すればいいのか解らないのですが
やりたいことは、

struct test
{
　　string s;←これを動的にしたい
　　int i;
}

のような感じです

371:デフォルトの名無しさん
07/03/18 16:12:10
>磯Ｃ
なるほどISoのことでしたか。
有り難うございます見てみます。

372:デフォルトの名無しさん
07/03/18 16:54:50
>>370
stringって何者？

373:デフォルトの名無しさん
07/03/18 17:24:34
>>372
流れからして>>362のスクリプトにあるファーストオブジェクトだと思うが

動的にサイズが変わるんだとiへのオフセットも毎回変わるの？

374:デフォルトの名無しさん
07/03/18 19:11:26
>>370
普通
struct string {
size_t currentBufSize;
　char *pStrBuf;
//なにやらいろいろ定義
};

とかなってないかえ？

375:デフォルトの名無しさん
07/03/20 17:21:18
日本語が扱えないと話にならないコンパイラを作ることになったのですが、
マルチバイト文字の扱いが一番楽なパーサジェネレータはどれですか？
Unicode固定でいいです。
・日本語を含む文字列を普通に解析できる
・文法定義中でも日本語が使える(\uxxxxのような書き方でなく)
SableCCはどちらもいけるようですが、ドキュメントが貧弱なので不安です。
ANTLRは後者が駄目でした。

376:デフォルトの名無しさん
07/03/20 21:59:16
パーサと文字コードは全く関係ない。
字句解析コードも出力する機能があるタイプなら関係する。

たとえば私は今、lemonを使ってるけどトークン番号を渡すだけ。

377:デフォルトの名無しさん
07/03/20 22:34:26
rubyのraccは字句解析部分をrubyのパターンマッチで記述しているので日本語もいけそう。
構文解析やその他の部分で機能が十分かどうかは不明。

378:デフォルトの名無しさん
07/03/20 23:11:19
raccでHTML用のテンプレートエンジンを作ったけど、特に問題なしです。

……まあ、UTF-8のみでOKなら、ダメ文字もバイト切れ目問題も無いから
あんまり気にする必要が無いような気がするけど……

379:デフォルトの名無しさん
07/03/21 04:54:50
>>375
日本語はparserでなくlexerの方の問題では？

380:デフォルトの名無しさん
07/03/21 07:25:13
lexのもんだいだよな・・・

381:デフォルトの名無しさん
07/03/21 09:24:02
URLﾘﾝｸ(www.mainichi-msn.co.jp)
訃報：Ｊ・バッカスさん８２歳＝コンピューター言語開発者

　ジョン・バッカス氏（コンピューター言語の開発者）ＡＰ通信が２０日
伝えたところによると１７日、オレゴン州アシュランドで死去。８２歳。
　デラウェア州ウィルミントン生まれ。米コンピューター大手ＩＢＭで１
９５０年代に、プログラム作業の大幅な効率化に貢献したコンピューター
言語「フォートラン」を開発。コンピューターが扱う言語の文法を定義す
るのに用いる「バッカス・ナウア記法」も開発し、今日でも幅広く使われ
ている。７７年にコンピューター分野のノーベル賞といわれるチューリン
グ賞を受けた。（共同）

382:デフォルトの名無しさん
07/03/21 09:31:15
正規表現を状態遷移図に変換するツールalamo。
現在WIN32バイナリのみリリース、
まだシフトJISのみ入力可能。

使用方法：
標準入力から正規表現を入れると標準出力にdot言語のソースが出力される。
A>alamo < textfile | dot -Tjpg > out.jpg
トンプソンの構成法でなくεを消去した状態のNFA。
出力をファイルに落としてからUTF8に変換すれば漢字も出た。

URLﾘﾝｸ(capslockabcjp.kitunebi.com)

※動作条件としてURLﾘﾝｸ(www.graphviz.org)が必要

383:デフォルトの名無しさん
07/03/21 10:00:12
>>381
うお、マジか。ご冥福をお祈りします。

384:デフォルトの名無しさん
07/03/21 10:41:19
「可愛そうなジョージ、病気になる前まではソートルーチンもちゃんと動いていたのに・・・」

385:デフォルトの名無しさん
07/03/21 14:03:48
>>384
これなんだっけ!?すげーみたことあるんだけど・・・・

386:デフォルトの名無しさん
07/03/21 16:16:51
ｽﾚﾘﾝｸ(scienceplus板)
【訃報】ジョン・バッカス氏　FORTRANを開発

387:デフォルトの名無しさん
07/03/21 17:07:33
>>384
本物のプログラマおつ

388:デフォルトの名無しさん
07/03/21 23:25:45
lemonがWindows上ではlemapar.cがカレントにないと動かないので、
調べてみるとlemonのpathsearchという関数がバグっている。
6行程度の修正で直る。

URLﾘﾝｸ(capslockabcjp.kitunebi.com)

389:デフォルトの名無しさん
07/03/22 13:50:39
かわいそうなのはジョージじゃなくてソートルーチンなんだろ。

390:デフォルトの名無しさん
07/03/22 14:03:45
ジョージかわいいよジョージ

391:デフォルトの名無しさん
07/03/22 18:31:34
どうしてもMOTHERを連想する

392:デフォルトの名無しさん
07/03/24 17:14:38
ＭをとったらＯＴＨＥＲ、他人です。

393:デフォルトの名無しさん
07/03/24 18:15:58
other単体では他人になりません。

394:デフォルトの名無しさん
07/03/26 13:12:56
another

395:デフォルトの名無しさん
07/03/26 14:16:18
bother

396:デフォルトの名無しさん
07/03/28 12:12:32
商用ゲームで使うスクリプトのコンパイラ・エンジンを作ることになったんですが、
そういったプログラムに関してはわからないことが多いので悩んでいます。
組み込み系言語のLuaを使うという選択肢もあるんですが、とりあえず自作する方向で勉強してます。
flex&bisonあたりは使うつもりなのですが、他にも使って便利なツールってあるでしょうか？
初心者はnasmとかalinkみたいなものを使った方がいいんでしょうか。

397:デフォルトの名無しさん
07/03/28 13:20:54
ANTLR

398:デフォルトの名無しさん
07/03/28 14:13:22
なぜLuaを使わないかの理由が知りたい。

399:デフォルトの名無しさん
07/03/28 16:30:15
何故インタプリタ型のLuaとコンパイラ型の言語設計(nasmなどを挙げている事から
の類推)を並べているのか分からないのだけど、コンパイラ作るだけならパーサ
ジェネレータ以外に必要なものは無いし、それ以上の補助ツールも無いと思う。

nativeに落とすのであればWindowsならcoffなどのフォーマット参照、コンソール
なら各ベンダの資料とか、自前でニモニックを変換するのはかなり泥臭い話なんで
可能ならnasmとかを使う方が遥かにお手軽、最適化を自前実装するのでなければ、
期待できるコンパイラの性能にも拠るけどCとかにトランスレートする方が高速な
動作を期待できるかもしれない。

というかゲームの種類と環境でコンパイラなのかVM型のインタプリタとかで良い
のか、デザイナー向け簡易スクリプトなのか汎用言語タイプなのか良く分からない。
単純に上から言われたのならもう少し何が欲しいのか詰めた方が良いんじゃないかと
心配してしまったのだけど。

400:デフォルトの名無しさん
07/03/28 16:55:23
BNFのコンフリクトを解決しやすいツールって何かないですか？

401:デフォルトの名無しさん
07/03/28 20:08:47
つ-vオプション

402:デフォルトの名無しさん
07/03/28 21:28:51
つ熟練者の直感

403:デフォルトの名無しさん
07/03/28 22:08:45
>>399
具体的なことを言えば、
社内のスクリプトのシステムを作っていた前任者が大分前に辞めてしまい、
いい加減作り直さなきゃね、という状況で自分がやることになり、
前任者の作ったものを解析した結果、
yac&lexを使い、自前ツールでアセンブリ言語に変換し、そこから先はnasm+alinkのようなツール（実際は別物）
でマシン語にしたものを実際のゲーム側で読み込んで使っていました。
それで、そういう方向でいろいろ調べているという状況です。
>>398
Luaは存在は知っているのですが、具体的なことはまだ知りません。
上記のような状況なので調べるものとしてLuaの優先順位が今は低いだけで、
一度しっかり調べて検討するつもりです。

404:デフォルトの名無しさん
07/03/28 22:40:22
>>403
>yac&lexを使い、自前ツールでアセンブリ言語に変換し、そこから先はnasm+alinkのようなツール（実際は別物）　
>でマシン語にしたものを実際のゲーム側で読み込んで使っていました。

それは「スクリプトのシステム」ではなく、「コンパイラ」ではないかと・・・

405:デフォルトの名無しさん
07/03/28 22:59:46
難儀ですな、、、
自分がコンパイラ作った時はyaccで文単位で構文木を作ってそれをリストに格納、
ニモニック変換時は各文ごとに構文木を辿ってテンプレートに従ってコード出力、
言語に型システムがある場合はニモニック生成前に構文木を一旦辿って型の文脈
を決定、その後ニモニック生成ってカンジですた。

自分の場合スタック型VMだったんでレジスタ割付の最適化とかは知らない、アキュムレータ
とメモリ間接に限定すれば簡単だけど、アセンブラがシンボル対応ならアドレス解決
は不要かな。

後はリファレンスカウンタまでならNativeでも比較的安易に作れるけどFull GCだと
スタックや変数領域をどう扱うか、スレッドの管理までフレームワークを用意する
形なのである程度事前設計が要ると思う。

まぁ参考になるか分かりませんが、、、

406:デフォルトの名無しさん
07/03/29 00:08:48
もう前任者のはいったん捨てた方がいいかもシレン
ちゃんとしたドキュメントがあるなら別だが

407:デフォルトの名無しさん
07/03/29 01:00:32
>>406
レオもそう思う

408:デフォルトの名無しさん
07/03/29 01:40:53
>>403
>でマシン語にしたものを実際のゲーム側で読み込んで使っていました。

ここまでやってるってことは、普通にインタプリタじゃパフォーマンスが足りないってことかな？

なら、CやＣ＋＋言語へのトランスレータ作ったほうが簡単だし、
工数もかからないんじゃないかな。

俺は商業じゃないけど、EXCEL->C++へのトランスレータ作って使ってる。

場合によってはC++そのままの機能も埋め込めるし、既存言語に足りない機能足すだけだから、
それこそあっという間に完成するぞ。

409:デフォルトの名無しさん
07/03/29 06:38:39
ちなみにLuaのVMはJITを搭載しているから、他のスクリプト言語と比べてバフォーマンスはだいぶ高い。

410:デフォルトの名無しさん
07/03/29 12:01:35
>>404-409
返答ありがとうございます。参考になります。

>>408
最低限のレベルで要求されているのは、メモリや速度の面で問題ないということと、
前任者のスクリプトがCライクな仕様で、社内メンバーがそれに慣れているので
それに合わせなければなりません。

>>409
とりあえず、前任者のものをある程度理解できたのでこれからLuaを勉強しようと思ってます。

411:デフォルトの名無しさん
07/03/29 16:26:26
>>410
作りなおすってことは、前任者の作った言語に不満があるってこと？
どんな不満があるのか（機能が低い、言語使用が貧弱、とか）によっても
作り方が変わってくるんじゃないかと思う。
（トランスレータにするのか、インタープリタで間に合うのかとか…）

412:411
07/03/29 16:27:10
訂正：言語使用　→　言語仕様

413:デフォルトの名無しさん
07/03/29 18:04:54
>>411
いくつか解決しなければいけない問題というのはあります。
トランスレータというほどじゃないですが、それを解決する方向で拡張するという案も確かにあります。
ですが、作った人間がすでに会社にいないので、理想を言えば新しいものを用意することでしょう。
自分が辞めれば結局同じことのループなので、Luaのようなものを使うのが会社にとっては一番いいことなのかもしれません。

LuaはCライクな言語じゃないようなので今はSquirrelを見ています。

414:デフォルトの名無しさん
07/03/29 18:13:32
ちうか速度面で劣化があっちゃまずいのならインタープリタじゃアレなんじゃね？
前任者さん版のスクリプトのおぼろげな仕様聞く感じ

415:デフォルトの名無しさん
07/03/29 18:53:22
>>414
まあ、マシン速度も昔に比べれば比較にならないくらい向上してるし、
どうしても速度的に問題があるなら、、その部分だけゲームエンジン本体に
直接機能追加すればいいから、そんなに問題になることはないんじゃないかな？

自社ツールなら、そこらへんどうとでもなる。

今までＣライクなスクリプトだったなら、Ｃ言語へのトランスレータが簡単でパフォーマンスに
優れていると思うけど、フリーの汎用エンジンなら自社でメンテナンスしなくていいから
将来的な負担を考えると、悪くない選択かもね。

とはいえフリーのスクリプトエンジン使う場合、ライセンスをちゃんと確認しておかないと、
へたすりゃソースコード公開させられる羽目になるぞ。

416:デフォルトの名無しさん
07/03/30 14:36:03
>>409
LuaJITってLuaの大本にマージされたの？

417:デフォルトの名無しさん
07/03/30 14:59:01
>>410
>前任者のスクリプトがCライクな仕様で、社内メンバーがそれに慣れているので

メンバーにCを覚えさせたほうが速いんじゃね？

っていうか、そのスクリプトの「利点」って何なの？

418:デフォルトの名無しさん
07/03/30 15:07:55
>>413
>Squirrel
これ知らんかった。Luaもいいけど、これもよさげだね。さんくす。

419:デフォルトの名無しさん
07/03/30 15:13:21
> メンバーにCを覚えさせたほうが速いんじゃね？

んなこたーねえｗ

420:デフォルトの名無しさん
07/03/30 15:20:24
>>419
そのスクリプトの仕様を見てみないと
なんとも言えないと思うが？

話を聞く限りでは、汗を生成していたんだろ？

実はそれ、ただのCコンパイラ(多少の独自拡張あり)かもよ。

421:デフォルトの名無しさん
07/03/30 16:49:28
ていうか話聞いてるとSystem4.0が思い浮かんでしょうがない

422:デフォルトの名無しさん
07/03/30 18:52:06
自動でマルチスレッド化、グリッド化
できるコンパイラないの？

423:デフォルトの名無しさん
07/03/30 19:00:27
Intel C++ Comipilerは？

424:デフォルトの名無しさん
07/03/30 23:35:18
Cライクなスクリプトと言うと、smallというのもあったねぇ。今はPAWNか。
URLﾘﾝｸ(www.compuphase.com)
……どんなのか知らんけど……

425:デフォルトの名無しさん
07/03/31 13:49:03
>>424
ちょっと使ってみたことがあるが、スクリプトで動的メモリ割当てを使わない場合は
GCを切ることができたり、（再帰がなければ）スタックの最大長をコンパイル時に計算して、
スクリプトのロード時にVMに割当てるメモリを最小限に抑えたり、組込み機器向けにいい感じ。
スクリプトの文法としては、Cライクな手続き的記述に加え、状態遷移、イベント駆動的な
書き方が出来るのも面白い。

426:デフォルトの名無しさん
07/04/01 01:12:36
verilogのパーサがほしくて
cygwin + antlrをインストールした後

URLﾘﾝｸ(www.eecs.berkeley.edu)
からダウンロードしてみました。 flex とbisonは入れていません。

makeしてexeファイルが作れて、adder.vという例題ファイルをexeに食わしてみたのですが、

Parsing Verilog file...
... successful!

というメッセージが出たのですが、ファイルが生成されません。どこかにできているものでしょうか？
ご存知の方いたら教えてください。

427:デフォルトの名無しさん
07/04/01 03:40:32
>>426
君は何年生？（どこの大学？専門学校？）
それと与えられた宿題の内容も詳しく教えてくれた方が役に立つアドバイスができそう．

まずexample.cppをエディタで開いてみるところから始めよう．

428:デフォルトの名無しさん
07/04/01 08:01:20
社会人

一応全部見たが出力先がよく分からんから聞いた。煽りにレスしてしまった・・・

429:デフォルトの名無しさん
07/04/01 09:21:12
まぁ、あまりに青臭い煽りにはつい優しくしてあげたくなることもあるｗ

430:デフォルトの名無しさん
07/04/01 10:11:45
パーサはパースする物。
サンプルはパースするところまで。

VHDLを読んで解釈する、そして文法的には正しく読み込めたと表示。
その中身を変換して出力するのはパーサの仕事じゃない。

431:デフォルトの名無しさん
07/04/01 18:18:39
>>430
えーと、中身を解釈して構造はこうだったよ！と
吐き出してくれるものってないのでしょうか？

構造解析結果まで生成するものがパーサだと思っていたのに・・・

432:デフォルトの名無しさん
07/04/01 18:32:20
>>431
おいおい、今朝教えたパーサの知識を
早速こんな所で御開陳か？

>>430の話は、要するにサンプルコードはパースはするけど、
内部的に生成した構文解析データの出力ルーチンは記述されていない
ってだけの話だろ。

433:デフォルトの名無しさん
07/04/01 20:34:24
>>432
すみませんが、もう煽りにレスはしません

434:デフォルトの名無しさん
07/04/01 20:43:18
いや、煽ってなどいない。

そもそもキミは質問に回答をもらった後で、
回答者に感謝の意を表しているかね？

435:427
07/04/01 20:51:45
>>431
example.cpp（と，そこで使ってるverilogParser.yxx）は
* エラーがあったらyyerrorのassert(false)で異常終了
* なかったら返り値1で終了（←何考えてるんだ？）
ってだけのプログラムなのは読めば分かるだろ？
そもそも出力先を一つもfopenしてないしfstreamも使ってない

内部構造はyydesign->modulesにpush_backされてるから自分で文字列化しる
つまりverilogDesign.cpp内の各クラスにoperator string()を追加するんだよ

とりあえずverilogパーザなんて難しいものでなく逆ポーランド電卓から始めた方がｗ

436:デフォルトの名無しさん
07/04/01 20:52:02
フレームの最中申し訳ないが質問に答えてほしい。
今日、電車の中でふと疑問に思った。

様々なLispやOCamlみたいにevalを持つコンパイラの場合
実行コード中にインタプリタかコンパイラを持っているのですか ?

FAQかも知れませんが教えてください。

437:デフォルトの名無しさん
07/04/01 20:59:53
>>436
実行コード中にインタプリタかコンパイラを持っています

438:デフォルトの名無しさん
07/04/01 21:45:01
>>436
Lispコンパイラとか言うときってスタンドアロンなバイナリファイルを吐くものでないことが多い気がする

対話環境（←コンパイラを含む巨大なプログラム）において関数を定義すると
その関数に対応するネイティブコードをコンパイラがメモリ上に構築してそれを実行，とか
そういうのだと作ったソフトの配布には使いづらい（そうでないものもある）

OcamlのToploopモジュールも，あれocamloptじゃ使えないんじゃないのか？（未確認）

439:436
07/04/01 23:37:28
>>437 >>438
レスありがと。

やっぱ魔法みたいな方法はないんだね。

440:デフォルトの名無しさん
07/04/02 01:49:19
>>438
インクリメンタルなコンパイルのほうが将来性があると聞いて、そっち方面に
手をつけてるんだけど、↓の意味がわからない。コンパイラを含む分、サイズ
が多きくなるけど数メガ程度で、Windows でいったら DLL HELL を避けるため
に C ランタイムとかの DLL を添付程度のもんだとおもってるんだけど、
サイズ以外になにか問題ってある？ Java や Lua の JIT とかも該当しそうだけど

> 対話環境（←コンパイラを含む巨大なプログラム）において関数を定義すると
> その関数に対応するネイティブコードをコンパイラがメモリ上に構築してそれを実行，とか
> そういうのだと作ったソフトの配布には使いづらい（そうでないものもある）

441:デフォルトの名無しさん
07/04/02 02:18:08
LexerとParserが分離できるかの問題じゃね？

xml知ってるならDOMを実装するのにSAXが使われてたりするってのをイメージすると分かりやすいんだが。

字句解析が中のSAXパーサ、構文解析がDOMパーサ全体。
構文ツリーがDocumentノードって感じ。
分離するかしないかの問題でそれと同じだ。

442:デフォルトの名無しさん
07/04/02 02:39:20
サイズの問題さえ気しなけりゃ配布ソフトが字句解析器や構文解析器を備えてようが、
それが分離できるかできないかなんて関係なくない？

443:デフォルトの名無しさん
07/04/02 03:29:52
つーか対話環境ってそんな大きくなるもんかね？

444:デフォルトの名無しさん
07/04/02 07:42:23
REPLだけが対話環境とは限らんから、Visual Studioみたいな対話環境が
ついてくるのかも知れないじゃんw

445:デフォルトの名無しさん
07/04/02 22:37:36
商用利用（ゲームとか）を考えると、ソースや開発環境をまるごと載っけてると
勝手に改変版のプログラムを売られる/配られるのが嫌だ。とかいうのはあるかも。

446:438
07/04/03 00:07:09
>>440
とりあえずサイズの問題だけ考えてた
まぁ今時では気にしなくていいのかな？
こないだ見た例では，abenori氏のTeXインストーラがDLL版Rubyを同梱してたっけな

>>445
特にLispはリフレクション，イントロスペクション周りの機能が多いので
対話環境をそのままくっつけておくと
意図せずに内部を見られ，いじられてしまうことにつながりかねないよね
（それは強みの裏返しだが）

447:デフォルトの名無しさん
07/04/03 01:32:42
>>498
サイズの問題がメインなんだよね。まぁ、いじられたくないアプリなら対話環境の機能は殺したいよね。
JIT みたいなインクリメンタルなコンパイル機能に問題があるのかとガクブルしちまった。すまん。

Lisp 界隈では大抵コンパイラというのはソースをネイティブコードやバイトコードなどの実行形式に変換する
機能のことで、スタンドアロンなバイナリ作る機能とは独立してるみたいだね。うーむ、そーゆうのもアリなんだねぇ…。

448:デフォルトの名無しさん
07/04/03 03:24:05
＞スタンドアロンなバイナリ作る機能
それはリンカとかローダとか（名前は何でもいいんだけど）
別のプログラムの役割では

449:デフォルトの名無しさん
07/04/03 16:58:13
極力ランタイムをmsvcrt.dll直にしてnativeに落とせば2KBぐらいから作れる。
VM上で動くのなら10～20KBぐらいじゃないかな。
eval相当が必要かどうか。

450:デフォルトの名無しさん
07/04/04 00:23:27
ココで聞くべきことではないかもしれないけど
組み込み用(マイコンとかじゃなくLuaなどの方面)のCコンパイラ(スクリプトか？)があったような気がするんだけど
名前が思い出せない
知っている人はいますか？
たしか、機械語を吐けるものだった気がします

451:デフォルトの名無しさん
07/04/04 03:34:16
これかな？
LSI C 86

452:デフォルトの名無しさん
07/04/06 17:00:33
こっちかも
libtcc

453:デフォルトの名無しさん
07/04/06 18:58:21
tccか… あれはいいものだ。

454:デフォルトの名無しさん
07/04/17 16:47:20
訳あって、(メトリクス計算プログラムを作るため)字句解析まで行いたいと思っている者です。
Javaで調べてみたところ、java.io.StreamTokenizerというAPIが自動で構文解析をやってくれるそうなのですが、
このスレ的にはStreamTokenizerの評価はいかがなものでしょうか？
ちなみに、字句解析までのプログラムを（OS云々で面倒なので）Javaで作ろうと考えており、
扱う言語もとりあえずはJavaSE1.4あたりにする予定です。
できれば、StreamTokenizerを詳しく取り扱っている本とかを紹介していただけると助かります。

455:デフォルトの名無しさん
07/04/17 17:13:17
>>454
URLﾘﾝｸ(java.sun.com)

456:デフォルトの名無しさん
07/04/17 17:14:16
間違った
URLﾘﾝｸ(sdc.sun.co.jp)

457:デフォルトの名無しさん
07/04/17 17:18:34
>>454
字句解析・構文解析・意味解析のそれぞれの意味の違いを知っていますか？

458:デフォルトの名無しさん
07/04/17 17:30:49
StreamTokenizerで扱えるトークンは
　・数値
　・ワード (英数字のつらなり、文字列定数、その他の記号)
　・行末、ファイル末検出
　* コメント記号(#等)以降行末まで読み飛ばし
程度。任意のトークンを追加登録する機能はない。
簡単な設定ファイル程度ならともかく
Java言語の字句解析には機能不足だ。

Java言語の構文解析が目的ならば、
パーサ生成プログラムを使うって作るか、
ありもののパーサを探すのが良い。

459:454
07/04/17 18:35:28
>>455-456
流石にそこは真っ先にチェックしてます。

>>457
すみません。字句解析と構文解析を逆に書いてました。
意味解析は今回は必要ないです。

>>458
と、なるとjavaccあたりで行うのが無難でしょうか？

460:デフォルトの名無しさん
07/04/17 18:49:57
構文解析抜きじゃ、メトリックを計れないでしょ

461:デフォルトの名無しさん
07/04/17 18:52:57
意味解析という言葉を持ち出している時点でネタ決定

462:デフォルトの名無しさん
07/04/17 19:10:45
>>461
教科書的には意味解析という言葉はある。

463:デフォルトの名無しさん
07/04/17 19:15:11
意味解析抜きじゃ、コードの質を計れないでしょ

464:デフォルトの名無しさん
07/04/17 21:14:04
すげーな
俺は字句解析と構文解析をわける意味も必要も境目も全く理解できんかった
どう考えても構文解析までやらないとわからんトークンってある気がするっつうか
そうでなくとも構文解析しながらのが略

465:デフォルトの名無しさん
07/04/17 21:22:02
字句解析した方がプログラムとしてまとまりがあってよい。

466:デフォルトの名無しさん
07/04/17 21:24:20
いや、構文解析までやんねーと字句に分けらんねーって話なんだけど

467:デフォルトの名無しさん
07/04/17 21:30:06
cモドキでプリプロセッサとcパートとインラインアセンブラを同時に解釈するような
アホコンパイラを作ったときは字句解析と構文解析が交じり合って酷い目にあったな。

468:デフォルトの名無しさん
07/04/17 21:33:39
こんなん分けていいことないよね

469:デフォルトの名無しさん
07/04/17 21:43:52
>>466
言ってる意味わかんない＾＾；

470:デフォルトの名無しさん
07/04/17 21:50:26
いやだからさー
字句解析って構文になってない
つまり前後をみないで文字単体で判断することになるわけじゃん
これやりにくいぜー

471:デフォルトの名無しさん
07/04/17 21:53:04
という文法を作るとコンパイルが糞遅い言語が出来上がるわけですな。

472:デフォルトの名無しさん
07/04/17 21:57:40
文字っつうかトークン？

473:デフォルトの名無しさん
07/04/17 21:58:15
>>470
どんな文法でもトークンに分けられますよ。
だから、大丈夫です。

474:デフォルトの名無しさん
07/04/17 22:01:56
いやそれがさ
構文解析までしてみないとトークンとしてわけずらいもんがあるわけよ
できるできないの話じゃなくてな

475:デフォルトの名無しさん
07/04/17 22:03:47
>>474
どの程度までを構文解析って言ってるのか曖昧

476:デフォルトの名無しさん
07/04/17 22:08:30
あいまいも糞も一回でもやってみりゃわかるでしょ
わからない人とはお話ししませんｗ

477:デフォルトの名無しさん
07/04/17 22:10:30
いや、字句解析・構文解析ぐらいやったことあるけど、普通に棲み分けできるぞ？

478:デフォルトの名無しさん
07/04/17 22:38:34
>>474
> 構文解析までしてみないとトークンとしてわけずらいもんがあるわけよ
> できるできないの話じゃなくてな

それは多分、言語の文法の問題。
CやJavaレベルなら、構文解析までしなくても字句解析は普通に
出来ると思う。

どんな文法の言語の話？
例文希望。

479:デフォルトの名無しさん
07/04/17 22:50:14
こういう曖昧なのとかか？
決め打ちだと思うけど。

#include <stdio.h>
int main() {
int a = 3;
printf("%d", a---3);
}

480:デフォルトの名無しさん
07/04/17 23:19:51
・ゆるいJavaScriptのような、文の後の改行はセミコロン(の省略)とみなされ、
それ以外ではホワイトスペースとして飛ばされるケース（改行文字のトークン解釈が構文解析の状態に依存）
・文字列リテラル中に、埋め込みテンプレートのような感じでその言語の式が書けるケース（字句構造内に構文構造が存在する）
etc.

481:デフォルトの名無しさん
07/04/17 23:23:12
>>480
あ～そうか、君はちゃんとした教育を受けてないんだ。
我流だね？

482:デフォルトの名無しさん
07/04/17 23:26:10
>>479
そういうのもそうだな
あとダブルコーテーションの中身が豪勢なのも俺は嫌いだ
あとなんだったかな
なんかもっと個人的に微妙なんだけど凄く嫌なのあったんだけど忘れたｗ
今度メモってくる
誰か解決策知ってるかもしれんし

483:デフォルトの名無しさん
07/04/17 23:30:25
改行とかタブとか見えないのが構文に影響を与える言語早く廃れてほしい
パイソンとかもう消えていいよ

484:デフォルトの名無しさん
07/04/17 23:38:42
>>479
a---3　は特に字句解析で困ることはなし。
マイナスが連続した場合の処理だけど、
　１．１つめのマイナスを読み込む。
　２．1文字先読みする。
　３a．２で読んだ文字がマイナスなら演算子--（マイナスふたつ）と判断。
　３b．２で読んだ文字がマイナス以外なら演算子-（マイナスひとつ）と判断。
ってだけで済む。

>>480
眠いから後でよく考えてみるけど、後者の文字列リテラル中に
言語の式が含まれると言っても、その言語の文法すべてを
含めることができるわけじゃない…んだよね？たぶん…

次ページ