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

1 ：デフォルトの名無しさん：2011/01/28(金) 20:33:18 .net

プログラミング言語処理系の開発に興味のある人達のスレッドです。
字句解析・構文解析から，データフロー解析，ループ並列化，データ分散，SSA変換，
CPS変換，レジスタ割付，命令スケジューリング，ソフトウェアパイプライン，
SIMD命令生成，VLIW向けクラスタリング，スクラッチメモリ向け最適化，リンク時最適化，
JIT，動的バイナリ変換等の各種最適化，それにVM，GC，低消費電力化などなど。
意味論に関する話題も歓迎です。

■過去スレ
1 http://pc.2ch.net/tech/kako/981/981672957.html
2 http://pc2.2ch.net/test/read.cgi/tech/1021136715/
3 http://pc5.2ch.net/test/read.cgi/tech/1070089173/
4 http://pc5.2ch.net/test/read.cgi/tech/1100097050/
5 http://pc8.2ch.net/test/read.cgi/tech/1106129164/
6 http://pc8.2ch.net/test/read.cgi/tech/1115335709/
7 http://pc8.2ch.net/test/read.cgi/tech/1129287390/
8 http://pc8.2ch.net/test/read.cgi/tech/1131273918/
9 http://pc8.2ch.net/test/read.cgi/tech/1135082582/
10 http://pc8.2ch.net/test/read.cgi/tech/1146844753/
11 http://pc11.2ch.net/test/read.cgi/tech/1160879890/
12 http://pc11.2ch.net/test/read.cgi/tech/1188688416/
13 http://pc12.2ch.net/test/read.cgi/tech/1233143342/
14 http://hibari.2ch.net/test/read.cgi/tech/1258431145/

939 ：デフォルトの名無しさん：2014/06/04(水) 11:36:58.64 ID:JjkiX3zX.net

各非終端記号を囲むカッコが2つ以上あるとLL文法じゃなくなるな。

940 ：デフォルトの名無しさん：2014/06/04(水) 14:22:25.33 ID:H9m/5fkb.net

具体的にBNFで

941 ：デフォルトの名無しさん：2014/06/05(木) 10:04:10.48 ID:1JqbWMwZ.net

B:=C|(C)
A:=B|(B)
こんな感じ？

942 ：デフォルトの名無しさん：2014/06/05(木) 10:10:07.49 ID:1JqbWMwZ.net

A:=BC
B:=D|(D)
C:=E|(E)
こっちの方が分かりやすいな。

943 ：デフォルトの名無しさん：2014/06/05(木) 10:13:32.16 ID:1JqbWMwZ.net

A:=B|C
B:=D|(D)
C:=E|(E)
違った。

944 ：デフォルトの名無しさん：2014/06/05(木) 17:19:48.25 ID:bOGqmnDA.net

その例なら、

A := BC
BC := '(' DE ')' | DE
DE := D | E

と、くくり出せる。

945 ：デフォルトの名無しさん：2014/06/06(金) 11:15:49.36 ID:y0bQ4ynG.net

なるほど。

946 ：片山博文MZ悪魔崇拝 ◆T6xkBnTXz7B0 ：2014/06/06(金) 16:52:16.19 ID:dyn5MnFB.net

このスレのテンプレにCaperを追加しておくれ。
jonigataさんのパーサジェネレータCaperは充分に実用的になった。

Caper
https://github.com/jonigata/caper

947 ：デフォルトの名無しさん：2014/06/06(金) 20:49:34.19 ID:iMYjirOz.net

>>946
アレは良い物ですな、つかなかなかここまで細かい事できるのに使い方が簡単なのってなかなか無いんだよね。
自分使うだけでアレだけど、MZはpullrequest結構出しててそれもとっても有り難かったです。

948 ：デフォルトの名無しさん：2014/06/06(金) 20:57:54.81 ID:Y8WrhCVM.net

今作ってる言語でCaper組み込む予定だよ。
いいよね、Caper。

949 ：片山博文MZ悪魔崇拝 ◆T6xkBnTXz7B0 ：2014/06/07(土) 19:30:42.70 ID:3R8CEA88.net

実行時に文法を動的に変えることできますか？

950 ：デフォルトの名無しさん：2014/06/07(土) 20:14:40.23 ID:RFWgpx3m.net

主語を明示してください

951 ：片山博文MZ悪魔崇拝 ◆T6xkBnTXz7B0 ：2014/06/07(土) 20:32:42.40 ID:3R8CEA88.net

プログラムが実行時に解析する文法を動的に変えることできますか？

952 ：デフォルトの名無しさん：2014/06/07(土) 20:37:06.36 ID:SxbAzKvi.net

eval

953 ：デフォルトの名無しさん：2014/06/07(土) 20:44:08.32 ID:ZfdboDuT.net

>>951
たとえばオブジェクト指向言語であれば
Gof本のInterpreterパターンで実装することによって
「実行時に解析する文法」を動的に構成できます
関数型言語だとコンビネータやモナドを使った
構文解析器(パーザ)の動的な構成技法があります

954 ：デフォルトの名無しさん：2014/06/07(土) 22:43:46.58 ID:3R8CEA88.net

>>953
わかった
ちょっとjonigataさんに相談してみる

955 ：デフォルトの名無しさん：2014/06/08(日) 16:02:17.85 ID:3LWaPBPW.net

解析実行時に文法を切り替えるっていうと
Boost::Spiritでruleインスタンスを差し替えるのを先に思いついた

956 ：jonigata：2014/06/08(日) 21:20:13.94 ID:/sgfaDLO.net

caper、動的エンジンもともともってるよ。
caperの文法ファイルは動的エンジンで起動時に文法作って読んでる。

957 ：デフォルトの名無しさん：2014/07/12(土) 10:00:10.48 ID:RjnQ2yc8.net

A:=C|BC
B:=B|(B)
C:=C|(C)
これだとくくり出せないし、LL文法じゃないですよね。
カッコが２つ以上あると特殊な場合を除いてLLぶんぽうじゃないですよね

958 ：片山博文MZ悪魔崇拝 ◆T6xkBnTXz7B0 ：2014/07/13(日) 02:56:51.90 ID:rSyi36+2.net

#include "http://example.com/my_library.h"

こんな機能があってもいいと思う。

959 ：デフォルトの名無しさん：2014/07/13(日) 03:18:39.87 ID:EUkLrXER.net

その場合リンカもネット越しにリンクできないと駄目だな

960 ：デフォルトの名無しさん：2014/07/13(日) 03:19:59.56 ID:hh7t9GxI.net

Gogleならやってくれそう

961 ： ◆QZaw55cn4c ：2014/07/13(日) 08:51:38.45 ID:OfL9oG5/.net

>>959
CPP だけの問題なのでは？どうしてリンカが関係するの？論理的に説明してね

962 ：デフォルトの名無しさん：2014/07/13(日) 10:10:10.25 ID:p5bwqgUP.net

ヘッダのインクルードはライブラリを使うためのもの、という固定観念だろう

963 ：デフォルトの名無しさん：2014/07/13(日) 10:11:05.79 ID:fq5Ei1vd.net

そんなどうでもいいことより
958についてどう思う？

964 ：デフォルトの名無しさん：2014/07/13(日) 10:35:33.89 ID:YSmlh2iv.net

1. ヘッダーをネット経由で参照するなら、libもネット経由で参照するだろう
libだけダウンロードしてヘッダーはダウンロードしないのは変だから
２．libファイルをネット越しに参照するなら、リンカもネット越しに対応する必要がある
３．よって、リンカもネット越しに対応しないとだめ

965 ：デフォルトの名無しさん：2014/07/13(日) 11:03:49.99 ID:p5bwqgUP.net

> libだけダウンロードしてヘッダーはダウンロードしないのは変だから

この時点で話が逆になってるし

966 ：デフォルトの名無しさん：2014/07/13(日) 12:32:33.10 ID:fq5Ei1vd.net

A:=C|BC
B:=B|(B)
C:=C|(C)
これはLL文法に出来ないということでよいですか[y/n]

967 ：デフォルトの名無しさん：2014/07/13(日) 12:38:12.73 ID:hh7t9GxI.net

NFSを知らん世代がC使うようになったのか胸熱

968 ：デフォルトの名無しさん：2014/07/13(日) 12:45:23.98 ID:+97kXbwc.net

MZはナウいヤングメンなので、UNIXなんて知りませぬ

969 ：デフォルトの名無しさん：2014/07/13(日) 16:30:35.77 ID:4JQGeYPE.net

aとbはエイリアスだから W

970 ：デフォルトの名無しさん：2014/07/13(日) 18:44:05.22 ID:p5bwqgUP.net

IDで追いかけるなんて、惨めだなw

971 ：デフォルトの名無しさん：2014/07/13(日) 18:57:17.40 ID:4JQGeYPE.net

http://hissi.org/read.php/tech/20140713/cDVid3FnVVA.html

初心者を脱して覚えたてのエイリアス使ってやろうと、
「aとbがエイリアスだったら…」とやっちゃったんだろうな。W

972 ：デフォルトの名無しさん：2014/07/13(日) 20:21:17.96 ID:p5bwqgUP.net

自分が初心者を脱したことがうれしいらしいw

973 ：デフォルトの名無しさん：2014/07/13(日) 21:08:09.17 ID:c9esStKn.net

なんでスレ違いの話題でスレ合ってるのをスルーするわけ？

974 ：デフォルトの名無しさん：2014/07/14(月) 00:06:14.02 ID:IJfuG6Dx.net

>>946
これのJavaを生成してくれるものってないのでしょうか

975 ：デフォルトの名無しさん：2014/07/14(月) 09:01:52.27 ID:0ty9SLgy.net

６月８日から誰も書き込まなくて
やっと７月12日に書き込んだと思ったら
それを急にスレ違いな書き込みで
スルーするっておかしくない？

976 ：デフォルトの名無しさん：2014/07/14(月) 16:07:02.50 ID:85+K9ELL.net

>>975
答えられる人がいないだけだろ

977 ：デフォルトの名無しさん：2014/07/14(月) 20:53:05.31 ID:hsWcAmzQ.net

>>975
しょうがないから説明するが、>>957の文法は無限ループだから何法だろうがパースできないわけで、
答えなんかないわけよ。そういう頭の悪そうな発言をする人がこのスレに来るミステリー。
あなたがおかしなことを書いてしまったのだから、バカにされたり無視されたりするのは当然の
結果なんだが、俺様が一ヶ月ぶりに質問してやったのにスルーするなという、勘違い甚だしい
態度に二度びっくりだよ。

978 ：デフォルトの名無しさん：2014/07/14(月) 22:34:06.61 ID:+HCYiRGv.net

じゃあ最初からそれを書けよ
一切対応せず延々とスレチの話をしてやがって
何が「しょうがないから」だよ

979 ：デフォルトの名無しさん：2014/07/14(月) 23:47:27.27 ID:4Au1+Pyc.net

皆のスルー力が高いからって喚くな

980 ：デフォルトの名無しさん：2014/07/15(火) 14:59:02.41 ID:JZ9KbigV.net

>>977
意味不明。
LL文法ではないかあるかを聞いているのに
「何法でもパースできないから答えが無い」とか的外れな回答をするアホ。
一言LL文法で済む話なのに。
ちなみにプッシュダウンオートマトンでパースできますが、これは
秘密にしておこう。

981 ：デフォルトの名無しさん：2014/07/15(火) 15:11:44.46 ID:JZ9KbigV.net

よくみると>>957は文法をきいているのであって、
解析法を質問しているんじゃないんだよな。
本当に的外れワロスwww
少なくとも文脈自由文法に含まれることは確かだな。

982 ：デフォルトの名無しさん：2014/07/15(火) 22:11:20.95 ID:mz5l6m+l.net

何言ってるのかわからない。
>>957は、解析器の作成に失敗するか、常にパースに失敗する解析器しか生み出さない。
パースが成功することは決してない。パース*できない*。
だから、>>966の「LL文法にできるか」という問いには、
「>>957は意味不明であり、あなたが何をしたいのかわからない」
「あなたがやりたいことがLL文法にできるかは『答えようがない』」
っていうのが正解でしょ。

ちなみに>>957の「カッコが２つ以上あると特殊な場合を除いてLLぶんぽうじゃない」については
「LLで、先読みの上限を超えたら上手く扱えないだろうけれど、カッコのせいじゃないだろ。」
って答えができるが態度悪いやつに説明するのが面倒だから無視しているだけね。

983 ：デフォルトの名無しさん：2014/07/16(水) 09:34:22.88 ID:iVIaM1wP.net

パーサーに>>957を読み込ませて解析できるかってことをきいてるんじゃなくて、
985を変形してLL文法解析器で構文解析できるかをきいているんでしょ。

984 ：デフォルトの名無しさん：2014/07/16(水) 09:39:32.16 ID:iVIaM1wP.net

あと先読み数は関係ない、LL（１）とは書いてないから。
LL(∞）だから扱えないとうのは理由にならない、無限の代わりに十分に大きいN
を使えばいいんだから。

985 ：デフォルトの名無しさん：2014/07/16(水) 09:52:56.89 ID:Dccn/eWm.net

態度を持ち出すとはワロタ
劣勢ですなあ

986 ：デフォルトの名無しさん：2014/07/16(水) 10:06:34.41 ID:iVIaM1wP.net

過疎になると初めに書く勇気が無いくせに
勇気のある一人誰かが書き込むとハイエナのように
群がってそいつの引きづりおろして人の手柄を横取りする
ハイエナばっかだな。
とくに>>946と片山博文MZ悪魔崇拝 ◆T6xkBnTXz7B0（>>958）
どうせこのドチラかの自演だろうけど。
ちなみにおれは通りがかってこのスレを見ただけだがなｗ

987 ：デフォルトの名無しさん：2014/07/16(水) 10:12:05.76 ID:iVIaM1wP.net

訂正:>>946→>>974

988 ：デフォルトの名無しさん：2014/07/17(木) 03:01:43.62 ID:syfeQpO8.net

文脈自由文法が生成する文字列は、
開始記号を有限回書き換えて得られる終端記号の並びだと定義されている
>>957は何回書き換えても非終端記号が残るのに何をどうしろと

どこかにεあたりが抜けているような気はする