字句解析・構文解析から，データフロー解析，ループ並列化，データ分散，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/
http://www6.atwiki.jp/compilerandscriptengine/
★コンパイラ一般
・色々なツールの紹介
http://catalog.compilertools.net/
・コンパイラ関連のリンク集
http://www.ulis.ac.jp/~nakai/rel_web_compilers.shtml
・スクリプティング言語資料室(仮) (リンク集)
http://www.kt.rim.or.jp/~kbk/
・Compiler Construction
http://www.ie.u-ryukyu.ac.jp/~kono/lecture/compiler/
・情報システム工学実験 III コンパイラ・コンパイラ
http://math.cs.kitami-it.ac.jp/~fuchino/proin/experimentIII-2000/jikken.html
・OS/Programming 簡単な C コンパイラ
http://www.csg.is.titech.ac.jp/~chiba/lecture/os/
・正規表現
http://hp.vector.co.jp/authors/VA007799/viviProg/doc_regexp.htm
・コンパイラ研究・開発情報の一集積所
http://compilers.cs.uec.ac.jp/
・Links and Selected Readings
http://www.gnu.org/software/gcc/readings.html
・国産のコンパイラ共通インフラストラクチャCOINS
http://www.coins-project.org/
・Lex and YACC primer/HOWTO （邦訳）
ttp://www.linux.or.jp/JF/JFdocs/Lex-YACC-HOWTO.html
・Turbo Pascal Lex/Yacc
http://www.musikwissenschaft.uni-mainz.de/~ag/tply/tply.html
・Jim Roskind's LALR(1) C++ Grammar
ttp://www.empathy.com/pccts/roskind.html
・Flexと Bisonを同時に使う
http://guppy.eng.kagawa-u.ac.jp/2005/SysProg/both.html
・KITE_ASM (yacc,lex)
http://www.arch.cs.kumamoto-u.ac.jp/project/kite/kiteasm/
・bison用のC++ LALR skeleton
ttp://www.bj-ig.de/software/bison/
・ANTLR（非yaccのパーサジェネレータ）
ttp://www.antlr.org/
・JavaCC(Java Compiler Compiler)
ttps://javacc.dev.java.net/
ttp://village.infoweb.ne.jp/~fwif0083/program/java/javacc/javaccgrm.html
ttp://www.asahi-net.or.jp/~DP8T-ASM/java/tips/JavaCCHelloWorld.html
・CUP, JLex, JFlex
http://www.cs.princeton.edu/~appel/modern/java/ (JLex, CUP)
ttp://www.jflex.de/
・SableCC
ttp://www.sablecc.org/
・¬＜＞＜∪∪ （notavacc）LALR(1)
http://ne.cs.uec.ac.jp/~koto/notavacc/
・boost::spirit（C++のテンプレートでEBNFの構文を模倣）
http://spirit.sourceforge.net/
ttp://boost.cppll.jp/HEAD/libs/spirit/index.html（マニュアル日本語化プロジェクト）
ttp://www.fides.dti.ne.jp/~oka-t/cpplab-boost-spirit.html
・GC FAQ -- draft
http://www.iecc.com/gclist/GC-faq.html
・A garbage collector for C and C++
http://www.hpl.hp.com/personal/Hans_Boehm/gc/
・一般教養としての Garbage Collection
http://www.is.s.u-tokyo.ac.jp/vu/jugyo/processor/process/soft/compilerresume/gc/gc.html
・Garbage Collection : Algorithms for Automatic Dynamic Memory Management
http://www.amazon.com/exec/obidos/ASIN/0471941484/
★処理系,スクリプト
・kikyou.info (吉里吉里というゲームのスクリプト)
http://kikyou.info/
・tiny C コンパイラ (C)
http://www.watalab.cs.uec.ac.jp/tinyCabs.html
・6809用 Micro C コンパイラ
http://www.axe-inc.co.jp/pds/mc09.html
・Portable Object Compiler (Obj-C >> C のトランスレータ？)
http://users.pandora.be/stes/compiler.html
・自作コンパイラの部屋(PL/1, Pascal等)
http://www.tokumaru.org/
・『Rubyソースコード完全解説』サポートページ
http://i.loveruby.net/ja/rhg/
・『やさしい Lisp の作り方』『やさしい Java インタプリタ の作り方』
http://www.okisoft.co.jp/esc/go.html
・MSによるPEフォーマット仕様書(日本語)
http://www.interq.or.jp/chubu/r6/reasm/PE_FORMAT/intro.html
・PLDI http://research.microsoft.com/conferences/pldi06/
コンパイラの研究に関する最新成果を知りたければまずはここ。
・POPL http://www.cs.princeton.edu/~dpw/popl/06/
PLDIよりは理論寄りだが大いに参考になる。
・ICFP http://icfp06.cs.uchicago.edu/
関数型言語に関する学会。とても難しい。
・OOPSLA http://www.oopsla.org/
オブジェクト指向言語に関する学会。最近はやや低調？
・ICCC http://www.st.cs.uni-sb.de/cc/
ヨーロッパ系。派手さはないが堅実。
・コンパイラ 原理・技法・ツール １＆２
http://www.amazon.co.jp/exec/obidos/ASIN/4781905854/
http://www.amazon.co.jp/exec/obidos/ASIN/4781905862/
通称ドラゴンブック。ル。
・コンパイラ構成法 原田 賢一
http://www.amazon.co.jp/exec/obidos/ASIN/4320029224/
http://www.hara.cs.keio.ac.jp/kCompiler/ (ソース、正誤表のダウンロード)
・プログラミング言語処理系 岩波講座 ソフトウェア科学〈5〉 佐々 政孝
http://www.amazon.co.jp/exec/obidos/ASIN/4000103458/
一冊で済ませたい人へ。
・コンパイラの構成と最適化 中田 育男
http://www.amazon.co.jp/exec/obidos/ASIN/4254121393/
最適化がメインだが、構文解析からコード生成までの基本事項も解説されている。
・コンパイラの仕組み 渡邊 坦
http://www.amazon.co.jp/exec/obidos/ASIN/4254127081/
薄い奴(185p)を読みたい人に。
・21st Century Compilers (Alfred V. Aho, Sethi, Ravi Sethi, Jeffrey D. Ullman, Monica Lam)
http://www.amazon.co.jp/exec/obidos/ASIN/0321131436/
まだ出ていない。
・スモールコンパイラの制作で学ぶプログラムのしくみ
http://www.cbook24.com/bm_detail.asp?sku=4774121770
初心者向けの優しい解説本。
http://www.amazon.co.jp/dp/4798114685
・ふつうのコンパイラをつくろう
http://www.amazon.co.jp/dp/4797337958
・プログラミング言語を作る
http://www.amazon.co.jp/dp/4774138959
・やさしいインタープリタの作り方入門
・やさしいコンパイラの作り方入門
http://www.amazon.co.jp/dp/487783219X
http://www.amazon.co.jp/dp/4877832203
スレ立て乙
前スレ終盤で「漢字嫁ねカタカナ表記の方が分かり易くね？」というカキコに対して賛否あった。
で、手元に「翻訳系構成法序論」という1982年刊行の古い本があるけど、
題名で分かるように(w)徹底的に漢字を使う。この本から「さ行」の一部を引用してみる。
元の英単語は、このスレに興味を持つようなヤシなら誰でも知っているものばかり。
お前ら、対応する英単語を即答できるか？(カナでも可とする)
・算体
・算帖
・算程
・算譜
・算法
>・『やさしい Lisp の作り方』『やさしい Java インタプリタ の作り方』
> http://www.okisoft.co.jp/esc/go.html
URL が変更になっていました。
http://www.oki-osk.jp/esc/go.html
すらすら読めるところもあるんだけどたまに引っかかって、文意を解くのに疲れる
いい本だとは思うけどね
・算譜 プログラム
・算法 アルゴリズム
残りはわからん。
算帖 file
算程 process
算譜 program
算法 algorithm
譲り受けた物が手元にあるのですが、最後にピンク色の破線で切り離せるっぽい頁があったみたいなのですが、切り離されていました。
これが何だったのか気になりましてw
素晴らしい。全問正解だ。
>>11
それが(自分を含めて)普通の感覚だと思うよ。
ちなみにこの本では、前スレで誰かが言ってた初出の箇所は「漢字(英単語)」という表記で、
しかも巻末にまとめとして対訳表があるから、漢字だらけでも苦痛に感じられなかった。
力押しでゴリゴリ動かしてるぜー
構文解析分野共通の言語あるいは図解フォーマットみたいなものだから
BNFとか見てるとなんでlexとyaccに分解されちゃうのか時々わかんなくなる（自己記述可能な言語でパーサ書いたあととか特に）
どうしようもなく時間がかかるようになるからでない
ツール的にはむしろyacc(bison)は更に２つに分かれてた方が助かる
状態と遷移表の抽出結果を入力として、表圧縮とソース成形の機能だけ利用したい時があるんだよね
入力内の遷移表にshift/goto/reduce以外の独自操作を定義追記出来る形ならなお良い
BNFが使えるようになれば、言語処理系以外の
一般的なデータ構造の記述(定義)にも応用がきくから、慣れた方がいいと思う。
BNFが難しければ、最初は構文図(Syntax Diagram)でスケッチして、
それをBNFに書き換えるという練習をするのがいいと思われ。
構文図については、たとえば http://www.json.org を参照。
他にもググるといくつも例が見つかるから、自分で調べてね。
言語定義の規模が大きくなるから機能分割しているのではないかと。
より一般的な言い方をすれば、字句解析(下位層)と構文解析(上位層)への階層化。
階層化によって、>>19が指摘した効率化(処理の高速化)という利点も生まれる。
実用的な言語レベルの規模になると、lex/yaccのようなパーサジェネレータを使わずに
実装された例としては、自分の知る限りSmalltalkしかない。(Lisp/Prolog系は別格なので除く)
しかもSmalltalkの構文は二項演算子に優先度が無い等、かなり簡素な定義になっている。
また、自己記述可能な言語としては、自分はPrologのDCG(Definite Clause Grammer)を
使うことが多いけど、定義言語の規模が小さくても意識的にscannerとparserに分割して書いているよ。
gccは手書きだよ
Rubyとかは、その典型例だね。
Rubyは人に優しい言語だから自分は大好きだけど、中の人にはなりたくないw
えええっ！、そうなんだ。知らんかったよ。
よく知らんのだけど、
パーサジェネレータの吐いたコードを下敷きにしてるとかじゃなかったっけ？
エラーメッセージの丁寧さがうんたらかんたら
構文エラーでも、コンパイル続けたいし。
字句解析/構文解析分割については、
字句解析ないと、BNFレベルで字句解析もやることになるから、
予約語や数値リテラルの解析なんかも全部BNFに入ってくる。
嬉しいことなんてないと思うが。
FORTRANとCOBOLに火炎瓶投げられても知らんぞw
ぐぐったらちょうどこの文法がPackrat Parserで受理出来ないって英語版Wikiにかいてあるね
13.4 SSA形式での最適化のアルゴリズム の 13.4.6 定数伝播 内の、
b. 条件文を考慮したアルゴリズム の部分です（第2版ではp.367）。
図13.41 の定数伝播の例(その1)(c) にて、
k3 = φ(k2,k1);
の行を処理した結果が 未→0 となっていますが、この理由が分かりません。
この時点で
k1→1
k2→0
なので、表13.1 により、不定(c≠c') になるのではないでしょうか。
lispのリーダーマクロみたいな仕組みで別言語に化けられる奴とかってないかな？
言語開発フレームワークがある。
Algol 60の例
http://docs.racket-lang.org/algol60/index.html
E -> a
E -> a b
のとき、first(E) in follow(L)なのでしょうか？
Eはepsilonを生成しないのでfollow(L) = phiだと思うのですが...
ドラゴンブックによる解説だと
(1) A -> alpha B betaの時
follow(B) := first(beta)∪follow(B)＼epsilon
(2) A -> alpha B betaでepsilon in first(beta)もしくは A -> alpha Bの時
follow(A) := follow(B)∪follow(A)＼epsilon
なのであっている気がするのですが...
6行目は「のとき、follow(E) in follow(L)なのでしょうか？」が正しいです。
それと、自分で組んだ実装では、follow(L)はfollow(E)を含みませんでした。
タイガーブックにある例とドラゴンブックにある例をパスしましたが、これが気になって先にすすめません。
生成規則の右辺に出てくる終端記号以外に関してはfollow集合は作らなくても大丈夫なんですか？
ところで、LLVM の '条件文を考慮した定数伝播' って実装途中なんですかね。
肝心な部分の処理が足りてない気がします。
毎号付属するモジュールを組み立てていくと、あなたオリジナルのコンパイラが完成します。
創刊号は字句解析器が付いて1200円。
ディアゴスティーニ♪
----
for K の中の各項 B -> γ.δ do begin
J' := closure {[B -> γ.δ, #]}; // (1)
if a を # 以外の記号として、[A -> α.Xβ, a] が J' に含まれている then
goto(I, X) の中の項 A -> αX.β に対して、先読み a が内部生成される;
if [A -> α.Xβ, #] が J' に含まれている then
I の中の B -> γ.δ から goto(I, X) の中の A -> αX.β に先読みを伝播する;
end
----
ここで例えば拡大文法の開始部分 {[S' = .S, #]} で4.12が開始されると
その goto(I, X) の中で {[S' = S., #]} とドットの位置がひとつ右に動かされ、その状態で closure({[S' = S., #]}) と実行されるので
後半部分の closure はドットの位置が最後にあり実行される意味がなく、
それ以上伝達が起こらないと思うんですが実際のアルゴリズムはどうなんでしょうか？
自分で書いたコードでも、上記の通り伝達が S' = S. までしか起こりませんでした。
参考しても(パクっても)GPLに汚染されない、無料なwindows向けのCのソースってない？
http://pcc.ludd.ltu.se/building/
ありがとう。
でもmingw32(gcc)のライブラリが必要っぽいんだけど、
ライブラリだけなら、汚染されないんだっけ？
http://www.mingw.org/license
なるほど、大丈夫なんですね。
w32apiの
> If distributed as a modified package, then a copy of this notice must be included.
の部分は
> This library is distributed in the hope that it will be useful, but WITHOUT WARRANTY OF ANY KIND;
> without even the implied warranties of MERCHANTABILITY or of FITNESS FOR A PARTICULAR PURPOSE.
を通知しなさいってことでOK？
自分なら w32api: のパラグラフ全文を入れると思う
全文入れれば間違いないのは分かるけど、文章の掛かってる部分はどこなのかと…
まぁ、取り合えず、GPLにはならないことは間違いなさそうなので、
もう少し良く考えて、分からなければ、全文にします。
>文章の掛かってる部分
だから w32api: の項目全文でしょ
1. This library... の部分は免責の事しか書いていない（利用制限をしてはいけないという条項が入っていない）
2. This library... の部分だけなら、"the notice below must be included." みたいに書く筈
他人の助言を信じるにせよ信じないにせよ、Use at your own risk.
手元でやるより超高速で出来そうじゃないか？
4/7 予測 http://up3.viploader.net/ippan/src/vlippan198234.jpg
発表はドイツ気象庁 http://www.dwd.de/
どうして止めたんだろう
コメントすら日本語入れるとinternal errorとかいってくれちゃうんだけど、
何か設定なりオプションなり加えれば通るのかしら。
２ちゃんねるってなんなの。シネよ。
エイホは知らんが。
どうも、うまく出来ません。
できれば、エラー復帰もできるとうれしいのですが、そういう話の前に、
エラーをうまく管理できてないので、ちゃんと管理したいんです。
エラーコード表つくって、エラー発生時はエラーコードから、メッセージを取り出せば、
管理は出来そうな気はしてます。
みなさんはどのようにしてますか？
が参考になると思う。オリジナルは、
http://wiki.clean.cs.ru.nl/Documentation
表をずらして保存して圧縮するアルゴリズムの一般的な名前ってなんですか？
何のコメントも無しにリンク張るなよ紛らわしい。
ありがとうございます。参考になります。
>>71 が JavaScriptで書いたPEGのパーサ
>>72 がRubyで書いた、パーサやら、LLVMのなにか
みたいですね。
プログラミング歴はそれなりで、構造化されたものを読むのに
なんとなく再帰下降型のパーサを書くくらいのことはできます
情報科学については学部レベルの知識……かなぁ
仮想マシンの設計や JIT コンパイルとかやってみたいのです
仮想マシンはドラゴンブックでいいかもしれんがJITだとあんまり良い書籍無いような気がする
JITで良い書籍あったら自分も読みたい
#第一版しかもってないからかもしれんけど
具体的なことまで読みたくなると、ドラゴンブックだけでは足りない。
もちろんドラゴンブックだけで書いてしまう人もいる。
JITはインタプリタ、コンパイラ、リンカ、機械語の知識が必要になるので、
いきなりJITを目指さないほうがいいと思う。仮想機械方式にしておけば、
コンパイラからJITへの発展は、ほぼ仮想機械の書き換えで済む。
ｔccにJITを付けるプロジェクトが幾つかあったはずだが、今はもうないようだ。
それから前に会ったとあるコンパイラ屋はドラゴンブックよりタイガーブックと言っていた
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.3985&rep=rep1&type=pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.3303&rep=rep1&type=pdf
タイガーブックのほうが実際的だね。
ドラゴンブックは網羅的概論。
http://www.amazon.co.jp/dp/012088478X/
フロントエンドはドラゴンのほうが詳しいが、
最適化の部分はタイガーのほうが良いとか
JIT がレベル高そうな直感はありました
参考にさせて頂きつつ段階的に勉強したいと思いますです
((((((((( 最近だとLLVMを触ってみるのもいいかもしれんねぇ )))))))))(キリッッッッ！！キリッッッッ！！！！キリッッッ!!キリッッ！ッッッ！
----
(((((( それから前に会ったとあるコンパイラ屋はドラゴンブックよりタイガーブックと言っていた ))))))(←キリッッッ!!キリッッ!キリッ！！！！ッッ
--------------(キリッッ
ゴミは何いってもゴミ
355/113のような文字列を分数として認識させたいと思い、後続コンテキストを使用して
ureal {uinteger}|{numerator}\/{uinteger}
numerator {uinteger}/\/
uinteger [:digit:]+
のように定義を書いてみたのですが、
urealのルール部分でunrecognized ruleというエラーになってしまいます。
（意図しているのは、「スラッシュが続く無符号整数を分母と認識する」というものです）
ルールnumeratorが悪いのか、一時的に
ureal {uinteger}|{uinteger}\/{uinteger}
と置くとエラーは無くなるのですが、正しい書き方とはどのようなものでしょうか。
| と / では | の方が優先度が高かったため、
{uinteger2}|{numerator2}\/{uinteger2}
だと、
({uinteger2}|{numerator2})\/{uinteger2}
として解釈されていたようです。
{uinteger2}|({numerator2}\/{uinteger2})
のように括弧をつけたところエラーがなくなりました。
何度か弄っている間にnumeratorの後ろの /\/ を誤って消してしまっていて
numerator {uinteger}
になっていました。
暑くて半分頭茹ってるし。へるぷ
Lex とFlex では定義の展開の方法が違います。Flex（およびPOSIXのドラフト仕様）は、
定義を展開する時に丸括弧( ) で囲みますが、Lex は囲みません。
このことは、Flex 定義では演算子`^'、`$'、`/'、`<<EOF>>'、および`<start state>'は使うことができない
ということを意味しています。
だって（マニュアル8章）。
-l コマンドオプション使ったら排他的スタート状態を使えなくなるし…。うーあー。
そんなに大事とは思えないのは俺だけ？
つまり1文字先読みだけで解析できればメモリも消費しないし、
入力ファイルを先頭からサーッとなめるだけで終わる。
現代ではぜんぜん大事ではないね。
TOP カテ一覧 スレ一覧 2ch元 削除依頼 ▲
【bzr】Bazaarでバージョン管理 Rev 3 (896)
おまいら最強の麻雀プログラムしてみろよ Part5 (525)
【】configure大嫌い【RMS】 (491)
Jython、Groovy、JRuby - どれが一番効率的？ (253)
HSPプログラムコンテスト２０１１【part 2】 (208)
【Lisp】プログラミング言語 Clojure #2【JVM】 (452)
--log9.info------------------
【甲玉台頭】鹿児島ラグビーPART3【戦国時代】 (865)
なぜラグビーには犯罪者が多いのか？ (157)
東北地区大学ラグビー (237)
【荒尾戦略】熊本県高校ラグビー【佐賀工2本目？】 (236)
ヒーローズカップについて語ろう (426)
★どっちが面白いﾗｸﾞﾋﾞｖｓｱﾒﾌﾄ★ (405)
BBB 日本IBMビッグブルー その4 (139)
【訃報】宿澤広朗氏を悼む (357)
近畿大学付属高校ラグビー部 (175)
★★★愛知県立千種高校【復活！花園へ！】★★★ (172)
NSWワラターズ( ﾟ∀ﾟ)ア八八ノヽノヽノ ＼ / ＼/ ＼ (126)
超常現象応援スレ (767)
新潟県の卓球 (221)
四元奈生美ってキチガイなの？ (923)
スレ立てるほどでもない大会・海外卓球リーグ51 (217)
【松下二世】鈴木啓司総合【イケメンマッチョ】 (258)
--log55.com------------------
【鍋を振って作るナムル】中本出禁YFC村八分ｸﾝﾊﾟゆで太郎61【タコ唐津模様の丼】
【祝！メシコレキュレータークビ】中本出禁YFC村八分ｸﾝﾊﾟゆで太郎63【タクワンとカブのしば漬け】
宮崎県のうどん・そば7杯目
【軟麺】牧のうどん7【中麺】【硬麺】
【広島限定】 ち か ら 【定番食】
【日暮里】一由そば 9杯目【最安転落】
【うどん】 ウエスト 【だけじゃないけど】
【ｸｰﾎﾟﾝﾜｶﾒ少ないと言い掛かり】中本出禁YFC村八分ｸﾝﾊﾟゆで太郎59【女性客に声を掛けられたぁ】
