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

1 名前：デフォルトの名無しさん mailto:sage [2009/01/28(水) 20:49:02 ] プログラミング言語処理系の開発に興味のある人達のスレッドです。 字句解析・構文解析から，データフロー解析，ループ並列化，データ分散，SSA変換， CPS変換，レジスタ割付，命令スケジューリング，ソフトウェアパイプライン， SIMD命令生成，VLIW向けクラスタリング，スクラッチメモリ向け最適化，リンク時最適化， JIT，動的バイナリ変換等の各種最適化，それにVM，GC，低消費電力化などなど。 意味論に関する話題も歓迎です。 過去スレ 1 pc.2ch.net/tech/kako/981/981672957.html 2 pc2.2ch.net/test/read.cgi/tech/1021136715/ 3 pc5.2ch.net/test/read.cgi/tech/1070089173/ 4 pc5.2ch.net/test/read.cgi/tech/1100097050/ 5 pc8.2ch.net/test/read.cgi/tech/1106129164/ 6 pc8.2ch.net/test/read.cgi/tech/1115335709/ 7 pc8.2ch.net/test/read.cgi/tech/1129287390/ 8 pc8.2ch.net/test/read.cgi/tech/1131273918/ 9 pc8.2ch.net/test/read.cgi/tech/1135082582/ 10 pc8.2ch.net/test/read.cgi/tech/1146844753/ 11 pc11.2ch.net/test/read.cgi/tech/1160879890/ 12 pc11.2ch.net/test/read.cgi/tech/1188688416/ 関連リンクは多分 >>2-10 あたり 236 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 09:59:40 ] >>234 それは偏見。 組み込みLinux開発ではgdbくらい使いこなせないとお話になりません。 237 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 17:28:59 ] >>236 それは偏見。 組み込みLinux開発ではgdb使ってるようではお話になりません。 238 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 17:31:41 ] gdbは使いこなせるけど使ってないケースもあるわけで 239 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 17:35:33 ] printfの方が高機能なわけで 240 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 17:56:46 ] Caper良さそうなのですが字句解析(Lexar)には 何を使うのがいいでしょうか？ おすすめを教えてください。 241 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 18:34:20 ] Caper良さそうなのですが字句解析(Lexar)には 何を使うのがいいでしょうか？ おすすめを教えてください。 242 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 18:53:24 ] 手書きでOK 243 名前：デフォルトの名無しさん [2009/07/08(水) 19:48:27 ] 手書きでいいと思う 文字列→数値のパースみたいなランタイムの処理に流用しやすいし 244 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 23:21:38 ] 本気で速度気にするならflex出力を手修正とかがいいんじゃないか 245 名前：デフォルトの名無しさん [2009/07/09(木) 01:22:53 ] アセンブリから機械語にどうやって変換しているんですか？ 246 名前：デフォルトの名無しさん mailto:sage [2009/07/09(木) 01:54:23 ] まずOPコードを暗記するんだ 相対アドレスも数をこなせば暗算できるようになる 247 名前：デフォルトの名無しさん mailto:sage [2009/07/09(木) 09:40:02 ] >>245 アセンブラを使う。 gccに-vオプションつけてみな。 248 名前：デフォルトの名無しさん [2009/07/09(木) 09:50:38 ] >>241 Caperはgcc+Perlで開発されているので字句解析にはPerlを使うと馴染みやすい。 Linuxには必要なものがすべて揃っている。 249 名前：デフォルトの名無しさん [2009/07/09(木) 10:10:50 ] >>247 あなたの作っているコンパイラに対してアセンブラは自前ですか？ 250 名前：デフォルトの名無しさん mailto:sage [2009/07/09(木) 10:16:58 ] 母国語でおｋ 251 名前：デフォルトの名無しさん mailto:sage [2009/07/09(木) 16:11:15 ] アセンブラどころかリンカもローダも自作したが 最初は使えるものを使って、徐々に置き換えていけばいいんじゃない 252 名前：デフォルトの名無しさん mailto:sage [2009/07/21(火) 23:01:50 ] Richard Bornatのコンパイラの本でお勧めですか？ 253 名前：デフォルトの名無しさん mailto:sage [2009/07/21(火) 23:26:02 ] 日本語でおｋ 254 名前：デフォルトの名無しさん mailto:sage [2009/07/24(金) 21:58:11 ] やさしいコンパイラ（デコイ本）はやめたほうがいい ふつうの方は神本確定の出来だった 255 名前：デフォルトの名無しさん mailto:sage [2009/07/25(土) 00:56:59 ] やさしいコンパイラ貶して ふつうの方宣伝してる人は まったく具体的な指摘がないんだよな 256 名前：デフォルトの名無しさん mailto:sage [2009/07/25(土) 01:09:34 ] と、ここぞとばかりに架空の傾向を持ち出すわけですね。 257 名前：デフォルトの名無しさん [2009/07/25(土) 09:32:51 ] ふつうのコンパイラ良書なんでしょうか 学生なのでちょっと資金余裕がなくて 258 名前：デフォルトの名無しさん mailto:sage [2009/07/25(土) 09:38:48 ] 研究室で買ってもらえばいい。あるいは図書館。 259 名前：デフォルトの名無しさん [2009/07/26(日) 02:01:07 ] mingw-jpの使い方まったくわからないので どなたか教えてもらいたいのですが 260 名前：デフォルトの名無しさん mailto:sage [2009/07/26(日) 17:17:33 ] 言語ワークベンチは究極的には完全にプログラミング方法を変えるかもしれない www.infoq.com/jp/news/2009/05/Language-Workbench 261 名前：デフォルトの名無しさん mailto:sage [2009/07/26(日) 17:40:02 ] >>260 なんかスタイルシートが効いてなくて生々しいレイアウトになってない？ 262 名前：デフォルトの名無しさん mailto:sage [2009/07/26(日) 17:57:19 ] >>261 今見たが、特に問題ないぞ。 263 名前：デフォルトの名無しさん mailto:sage [2009/07/27(月) 11:25:26 ] >>261 うちの環境だとこうなってる IE6　ちゃんと出る FireFox　スタイルシートが効かない Google Chrome　スタイルシートが効かない上に画像も表示されない 264 名前：263 mailto:sage [2009/07/27(月) 11:30:13 ] 今見たら直ってました。 265 名前：261 mailto:sage [2009/07/27(月) 12:19:46 ] うーん。うちのFirefoxだと変わらずだな。 エラーコンソールになんか出てるけど、それが原因を示してるのかわからん... 266 名前：デフォルトの名無しさん mailto:sage [2009/07/27(月) 13:05:55 ] >>265 リロードしたらＯＫになったよ、うちのFX 267 名前：デフォルトの名無しさん mailto:sage [2009/07/27(月) 14:00:29 ] うちもFirefoxだと一度目はスタイルシート読み込まれないな まぁスレには関係ない話題だが 268 名前：デフォルトの名無しさん mailto:sage [2009/07/28(火) 14:39:17 ] >>260 どっちかというと設計よりの話だね。 269 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 04:41:50 ] .NET周りで使えるもの、という条件だが。 ・Lexical analyzer and parser generator 単純だがよくできている。構文木を食わせてソースコードを吐かせるBison式。 最初これで作りかけていたが、パーサーを構築できてもそのパーサーが予定の挙動をしない場合、デバッグの方法が困難。 （テーブルに分解されてしまうため、ソースが追いかけられない） パーサーの動作は高速と思われる。 ・Irony パース、構文木構築までをやってくれるコンパイラを動的に構築してくれる。 簡単なGUIのパーサーチェッカーが付いていて、開発がかなり楽 （すごい楽かはもっと楽なものがあるのかどうか知らないので……） 動的に構築する分lapgより遅いかもしれないが、とりあえず自分の目的にはこれで十分なので。 ただ、コンパイル済みコードを吐かすために自分用の構文木を もう一度作り直す羽目になるのは激しくビミョー……。 （別にそのまま構文木を消化していったっていいわけだが。 　まあ少なくともテキスト形式で出力するにはあの構文木のオブジェクト構造は向いてないな） 270 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 04:55:36 ] 修正と補足。 「構文木を食わせて〜」は、「BNF定義を食わせて〜」が正しい。 lapgもIronyもどちらもEBNFではなくBNF式。（Wikipediaで調べた限りでは） ただしどちらもパースに正規表現が使える。 lapgは非Ascii文字の正規表現パースがどうも挙動が怪しい……。 Ironyはホワイトスペースの除去以外にも非構文要素を取り除けるチャンスがあるので小回りが効くようだ。 (といったところも気に入っている) 271 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 13:51:44 ] JetBrains Meta Programming System これが最強他は全て旧世代の糞技術 272 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 14:25:38 ] >>271 どんなものか説明してみれ 273 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 14:32:14 ] .NET向けの旧来のスタイルのものとしてはGPPG/GPLEXが定番 GPPGはIronRubyにも使われてる 274 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 15:05:06 ] ドラゴンブック買ってきたぞ！さあ読むぞ！ 275 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 16:48:45 ] >>273 なるほど……。 現在はMPPG/MPLEXと名前が変わってるようだけどね。 どうせいずれVisual Studioの胸を借りる（SDKを使ってオレ様IDEを作る）予定なので、 はじめからこちらで構文解析を実装しておいた方が 構文の強調、InteliSenceなどで使い回しが利くかもしれない。 結構進んでてあとはエラー周りくらいだったんだが、破棄してしまうかなぁ……。 276 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 16:55:06 ] MPPG/MPLEXはまた別物だよ(MSがVisual Studio SDK用にカスタマイズしたもの?) 本家はttp://plas.fit.qut.edu.au/gppg/Default.aspxで開発継続中でドキュメントも充実してる 277 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 17:30:29 ] >>276 HPみてみたら、GPPG is closely related to the “Managed Package Parser Generator” application って書いてるね。 今仕様を決めているスクリプトは文法がPythonに似ているので IronPythonがどうなってるか調べてみたら、こっちはパーサーを自前で書いてる……？ （ソースコード中に直接コメントでBNFが書いてある） 278 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 17:42:08 ] ともあれ、BNF定義の中に直接コード片が埋め込めるGPPG/MPPGの仕様は興味深いね。 ただそれだけに、PDFドキュメントだけじゃなくて実際に動くサンプルプロジェクトが欲しいところだなぁ。 どっかにお手ごろなのが落ちてないかな。 279 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 18:06:36 ] >>276のサイトにあるパッケージには電卓のサンプルが付いてる。 言語なら ttp://www.iunknown.com/2007/11/lolcode-on-dlr.html これなんか手ごろで面白い。あとは大規模だけどIronSchemeやIronRubyくらいかな。 280 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 18:20:30 ] >>278 > ともあれ、BNF定義の中に直接コード片が埋め込めるGPPG/MPPGの仕様は興味深いね。 >>276のサイトも見ないで聞くがyaccなんかのアクションとは違うもの？ 281 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 18:41:28 ] 同じです 言語定義が処理系を実装する言語に依存しないというのは，むしろ流行りの売り文句です 282 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 18:47:36 ] >>281 > 同じです じゃあ>>278は何が興味深いんだろうか？ > 言語定義が処理系を実装する言語に依存しないというのは，むしろ流行りの売り文句です JavaでいうとSableCC的なやつかな JavaCC+JJTree、ANTLRでもできるが 283 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 19:06:25 ] > GPGP is a generator for LALR(1) parsers. It accepts a > “YACC/BISON-like” input specification and produces a C# output > file. The parsers that it produces are thread-safe, with all parser > state held within the parser instance. プログラミング言語非依存でもないよ。 284 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 19:09:44 ] >>280,281 278だが、その点で言えば、269で挙げたLexical analyzer and parser generatorはC++/Java/C#形式で吐き出せるよ。 だがこちらとしては、実装言語の非依存性などどうでもよい。 パーサーを実装しやすい仕様になっていればそれでいいわけ。 実装しやすさという観点で言えば、BNF式ごとにコードが埋め込めるGPPGは小回りが利きそうだし、 コンパイラやエラー処理があらかじめ一通り実装された状態で使えるIronyよさげ、というわけで。 285 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 19:14:10 ] >>284 話の流れが見えてなくてすまないが、要は昔ながらのコンパイラ・コンパイラが 欲しくてGPPGがそうだってだけ？ 仕様が興味深いというから何か目新しいネタがあるのかと期待しちゃったんだが 286 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 19:16:39 ] ANTLRみたいなのって，C#にも対応してるよと謳ってるのが多いけど ランタイムの実装が糞すぎて使い物にならないのが多いんだよね 287 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 19:28:14 ] >>286 学者風情が作った糞ライブラリに 期待するなよｗ自作しろ 288 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 19:37:36 ] >>284>>286>>287 ノイズレスはやめてくれ 289 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 19:47:26 ] >>285 他のやつらとこのスレの趣旨的にはどうか分からないが、 オレとしては自分で仕様を決めたスクリプトを他の形式にコンパイルするのに 必要十分な環境をそろえられればいい。 GPPG(MPPG)はスレの流れからするとyaccに仕様が近いようだが、（いわゆる昔ながらのコンパイラ・コンパイラ） 別にそれにこだわりはない。 むしろIronyによる作りやすさを評価してるくらいだ。 ともあれ、構文木を作った後が大変なんだがな……。 290 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 21:50:56 ] 確かに、はじめてyaccを知ったときは大変興味深かった。 >289はGPPG？で今その感動を味わっているわけだ。 291 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 21:55:08 ] >>289 あんなバグフィックスも含めて、 ちゃんとメインテナンスされてるどうかわからんツールよく使えるな。 近況はブログにでも書いてて欲しい。 292 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 22:02:23 ] >>291 リリース版しか見てないだろ。 Subversionのリポジトリみたら今月に至るまでコミットされつづけてるぞ。 というか、作者に連絡して修正パッチを投げてさっき返事が来たところだ。 codeplexにおけるプロジェクトratingsも★5つだし、どこが気に入らないのか知らないが、 まあオレが使いこなせれば済むことだからいいや。 293 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 22:27:30 ] yaccを知らずに僕らは生まれた〜 lexを知らずに僕らは育った〜 294 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 10:06:57 ] PEG世代の歌か？ 295 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 00:01:46 ] 夏休みなんで C++でPEGかpackratのパーサ作ってみたいのですが 何を参考に作るのが面白いでしょうか？ 296 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 00:13:52 ] ポリエチレングリコール？ いやいや・・ 297 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 00:23:12 ] >>295 PEGは新しい概念で古い言語向けにはあまり実装されて無いんじゃね？ Haskell、Pythonあたりを使うことをお勧めする。 298 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 11:42:07 ] ttp://pdos.csail.mit.edu/~baford/packrat/ Packrat の総本山に、C++ 実装へのリンクがいくつかあるよね。 299 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 12:00:32 ] PEGって使いやすいの？ CFGに比べた利点・欠点とか こういうのが書きやすいとか書きづらいとかありますか。 300 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 12:29:13 ] 原理的には、バックトラックのあるトップダウンパーザの受け入れる文法そのもの なので、CFGに比べて、原理を理解してしまえば直感的。 利点とも欠点ともとれるけど、レキシカルアナライザと統合される。 ナイーブな（メモ化なし）実装だと、指数的に時間がかかり、かつ無駄が多い。 301 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 12:41:16 ] C#の処理系ってことでIronMetaを眺めてみたが、こりゃあ異次元行ってるな。 ぱっと見ただけじゃさっぱりわからんぞ……。 302 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 12:56:06 ] ? これ別にC#をパースしてるわけじゃないと思うよ yaccみたいにテキスト的に処理してるだけだろ 303 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 12:58:29 ] >>302 まあそうなんだけど、C#自体の文法と似通っていて、 どこまでがC#の文法なのかが非常にわかりにくい。 どう見ても構文の宣言とラムダ式の定義が混じって見える。 304 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 01:55:34 ] >>303 そもそもそういう人が処理系なんて書けるの? 305 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 07:32:04 ] >>304 んんー、昨日いっぱいまでで、Irony使って大体書き上げてしまったぞ。 単独ファイルのコンパイルは文法の厳密化とか以外は大体こんなもの。 あとはエラー出力を整理してGUIくっつけて複数ファイルのコンパイルに対応したらおしまい。 ソースコード吐き出し式よりライブラリ式の方がオレには使いやすいようだ。 306 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 10:55:30 ] C#って文法は単純でも中身は超複雑だぞw 307 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 12:43:57 ] 中身w 308 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 16:08:03 ] PEGのパーザジェネレータ作るのはかなり簡単だよ。LL(1)やLALR(1)のパーザジェネレータ 作るのと比べてもかなり簡単。LLやLR系だと文法に対するグローバルな解析が必要になるけど PEGはそういうのしなくていいし。パーザジェネレータじゃなくてパーザコンビネータならもっと簡単に書ける 無名関数に相当する機能がある言語だったら、大体100行程度で基本的な機能を持ったものを作れる 309 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 16:14:10 ] PEGの利点： ・原理的にyaccとかのLALR(1)より強力なので、yaccでハンドリングするのが難しい文法も簡単に扱える(ことがある) ・レクサとパーザが統合されてるので、Rubyの"#{exp}"みたいな式埋め込み文字列みたいな文法も簡単に扱える 　・Rubyとかではトリッキーな事をしてこの問題を回避している ・アルゴリズムが簡単なので挙動を理解しやすい＝文法をデバッグしやすい（かも） PEGの欠点： ・ナイーブな実装では最悪の場合指数関数時間（だけど、実用上最悪ケースはそんなに起きないと思う） ・メモ化(Packrat)しても、定数係数でLLやLRとかの非バックトラック型のパーザよりは遅い ・Packratだと、状態付きパーザを扱うのが難しい(シンボル表を参照しながらパーズする場合など) ・レクサとパーザが統合されてるので、空白とかの処理がやや面倒 310 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 16:14:12 ] それはPackratパーザ？ それともバックトラック？ 311 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 16:15:27 ] >>310 Packratも基本的には、単にナイーブなPEGパーザをメモ化するだけなので、多少手間が増えるくらいで、実装は難しくは無い 312 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 16:28:07 ] とりあえずLISP系でスマートに実装してみて！ ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 313 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 16:43:41 ] >>312 OK. 1時間くらい待っててくれ 314 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 16:50:54 ] なんかPEG/Packrat詳しい人がいるみたいなので質問させてくれ。 手元のPEGのサンプルは四則計算を解釈していて、いきなりインタプリタとして動くようになっている。 いきなり動かすんじゃなくて構文木構築の段階で動作をとめることはできるんだろうか？ それから途中まで解析した文脈を情報として続く解釈で再利用できるだろうか？ 例えばPythonの文法を考えてもらうとして、 # ***ここから*** if [Expr]: 　　[Sentence] 　　[Sentence] [Sentence] # ***ここまで*** Pythonでは構文の範囲は字下げで表現しているので、 if文の範囲を調べるのに字下げの数を数えないといけない。 どうやって解釈させたらいいのかわからなくて戸惑っているところなんだが。 315 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 17:21:20 ] そのサンプルは、構文木を作ってから四則演算を実行してるんじゃなくて、 いきなり構文を解析しながら四則演算をしてるんじゃなかろうかという気がするが。 オフサイドルールとかはPEGの鬼門だということかと。 確か原論文では、それを理由にHaskellはムズいとして、Javaのパーザを 実装していた。 多分さがせば解決方法が出てる論文もあるだろうと思うのだけど。 パーザを状態付きにする方法は原論文にある。 316 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 17:56:21 ] >>309 > 定数係数で この言葉遣いはちょっと変なのでは? >>314 字下げ処理はレキサの仕事と割りきってしまえばそれほど難しくはないでしょ。 先読みして{と}に相当するものに変換できるから。 317 名前：313 mailto:sage [2009/08/04(火) 18:20:40 ] (use srfi-9) (define-record-type result 　(make-result x y) result? (x value) (y next)) (define (app parser f) 　(lambda(in) 　　(define r (parser in)) 　　(if r (make-result (f (value r)) (next r)) #f))) (define (term str) (lambda(in) (if (equal? (string-scan in str ' index) 0) (make-result str (substring in (string-length str) (string-length in))) #f))) (define (/: x y) (lambda(in) (or (x in) (y in)))) (define (^: x y) 　(lambda(in) 　　(define r1 (x in)) 　　(if r1 　　　(let ((r2 (y (next r1)))) 　　　　(if r2 (make-result (cons (value r1) (value r2)) (next r2)) #f)) 　　　#f))) (define (seq p . parsers) (fold (lambda(x y) (^: y x)) p parsers)) (define (rep0 parser) 　(lambda(in) 　　(let loop ((rest in) (rs '())) 　　　(define r (parser rest)) 　　　(if r (loop (next r) (cons (value r) rs)) (make-result (reverse rs) rest))))) (define (rep1 parser) (^: parser (rep0 parser))) (define (? parser) (/: parser (app (term "") (lambda(v) '())))) (define (& parser) (! (! parser))) (define (! parser) (lambda(in) (if (parser in) #f (make-result '() in)))) (define-syntax rule 　(syntax-rules() ((_ name body) (define name (lambda(in) (body in)))))) 318 名前：313 mailto:sage [2009/08/04(火) 18:25:10 ] なんとか１レスの範囲に収めたが、そのせいもあって、読みづらくなってる。その辺は読む側 の環境で適当になんとかしてくれ。あと、Gaucheのライブラリ関数string-scan使ったので、Gauche でしか動かんと思う。string-indexとかに置き換えれば、他のSchemeでもたぶん動くと思われ。 Schemeは普段使わないんで、Scheme使いの人からするとアレなコードかもしれんが、そのへんは勘弁。 使い方は以下のような感じ。文脈自由文法では表現できない、A^n B^n C^nの文法。 (rule S (seq (& (^: A (! (term "b")))) (rep1 (term "a")) B (! (term "c")))) (rule A (seq (term "a") (? A) (term "b"))) (rule B (seq (term "b") (? B) (term "c"))) (display (S "aaabbbccc")) 319 名前：313 mailto:sage [2009/08/04(火) 18:28:52 ] Pythonのインデントルールみたいなのは、レキサがインデント処理する事が前提だから、PEG/Packrat で処理する場合でも、レキサを別に用意した方が書きやすいと思う。レキサがあったらPEGじゃないというわけ じゃないので別に構わないはず(基本単位が文字の代わりにトークンになるだけ)。 320 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 19:26:20 ] >313 うお、本当にできてる！ たしかにこれはクロージャ使えない言語では無理だ こういう風になったけど合ってますか？ gosh> (display (S "aaabbbccc")) #<result 0pbb1788>#<undef> gosh> (define res (S "aaabbbccc")) res gosh> (result? res) #t gosh> (value res) (((() #0="a" #0# #0#) (#1="b" (#1# (#1#) . #2="c") . #2#) . #2#)) gosh> (next res) "" 321 名前：313 mailto:sage [2009/08/04(火) 19:34:21 ] >>320 たぶんそれであってる。まあ、これだけだと構文エラー時のエラーメッセージ 表示とかどうしようも無いし、実用的にしようと思うと、色々付け足す必要があるけど、 コアの部分はこれくらい簡単だということで。 322 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 23:05:50 ] みんな論文みながら作ってるの？ どうやってpackrat実装すればいいかよくわからん 323 名前：デフォルトの名無しさん mailto:sage [2009/08/04(火) 23:21:12 ] 21世紀…人類はいまだに左再帰問題を克服できずにいた 324 名前：313 mailto:sage [2009/08/05(水) 00:55:09 ] >>322 一応、自分が作ったときは論文参考にしたけど、基本的にナイーブなPEGパーザ＋メモ化に過ぎ無いから それさえわかっていれば、自力で実装することもできると想う。ヒントとして、上で書いたSchemeによる パーザコンビネータで、各非終端記号の解析結果をメモ化するにはどうすればいいか考えてみて。 Rats!とか高度な最適化してる奴はまあソース読むしかないと思うけど。 325 名前：デフォルトの名無しさん mailto:sage [2009/08/05(水) 01:16:54 ] 左再帰の論文もあったような。 326 名前：デフォルトの名無しさん mailto:sage [2009/08/05(水) 02:07:47 ] これのことかな。 Packrat Parsers Can Support Left Recursion (PEPM 2008) Alessandro Warth, James R. Douglass, and Todd Millstein www.tinlizzie.org/~awarth/papers/pepm08.pdf 327 名前：デフォルトの名無しさん mailto:sage [2009/08/08(土) 18:40:53 ] COBOLインタープリタを作ろうと思ったが挫折。 制定されているキーワードの数が尋常じゃない。 商用COBOLコンパイラを作っているメーカーの人はマジ天才。 328 名前：デフォルトの名無しさん mailto:sage [2009/08/08(土) 19:51:58 ] 何でそんなものを作ろうと思ったんだｗ 329 名前：デフォルトの名無しさん mailto:sage [2009/08/09(日) 03:42:55 ] COBOLかっこいいじゃん。大文字で。 Cを使える人はいっぱいいるけど、COBOLはそうはいない。 だからこっそり開発して職場のヒーローになろうと思ってね。 でも道は遠かった・・・使うのと作るのとは別物なのだ。 330 名前：デフォルトの名無しさん mailto:sage [2009/08/09(日) 09:26:31 ] >>327 > 制定されているキーワードの数が尋常じゃない。 何のためにパーサジェネレータがあるんだか まあ、BNF 打ち込むだけで疲労困憊ってのはあるかもしれんが… 331 名前：デフォルトの名無しさん mailto:sage [2009/08/09(日) 09:32:18 ] 大文字使いたいだけならマクロでも使えばいいじゃん 332 名前：デフォルトの名無しさん mailto:sage [2009/08/09(日) 10:31:58 ] >>330 やっぱ疲労困憊ら？(静岡弁で) 333 名前：デフォルトの名無しさん mailto:sage [2009/08/09(日) 11:53:19 ] >COBOL ほとんどは命令の名前なんだから、Identificationのレベルで区切って、 命令の判別はあとの段階にまわした方が簡単になるんじゃない？ あとはまあ、フリーソフトのCOBOLの処理系なんて昔ならともかく今ならいくつもあるんだし、作らないという手も。 334 名前：デフォルトの名無しさん mailto:sage [2009/08/12(水) 15:03:20 ] ゲームのNPCとかにスクリプトを使いたいんだけど 参考になるサイト教えて、lexとかyaccとか難しいのはいらない 335 名前：デフォルトの名無しさん mailto:sage [2009/08/12(水) 15:32:59 ] >>334 とっつきは悪いかもしれないけど、yacc&lexを使った方が 結局は落だと思うよ。 336 名前：デフォルトの名無しさん mailto:sage [2009/08/12(水) 16:35:21 ] >>334 オープンソースのスクリプトの処理系を組み込んだ方が普通は楽。 オレはそれにシナリオ記述用の独自形式のスクリプトと２種類用意しているが。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef