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

プログラミング言語処理系の開発に興味のある人達のスレッドです。

字句解析・構文解析から，データフロー解析，ループ並列化，データ分散，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/
関連リンクは多分 >>2-10 あたり

Wikiのまとめページ
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
　初心者向けの優しい解説本。

乙

ごめ。21st Century Compilers差し替えるの忘れてたので次にはよろ

・Compilers: Principles, Techniques, and Tools(Alfred V. Aho, Sethi, Ravi Sethi, Jeffrey D. Ullman, Monica Lam)
　http://www.amazon.co.jp/gp/product/0321486811

>>8
それドラゴンブックと違うの？

改訂版だろ？

早く訳されたやつでないかな(・∀・）

Ahoをアホつって通じるかな

C++用パーサジェネレータ作ってみた
暇な人いじってみて
http://tinyurl.com/yefoxa

動かなかったらごめん

なんじゃ
また構文解析か

>>11
スロバキア語でAhojって通じるかな

>>12
あのね、今時そういうの流行らないの。
だいたい、同じようなものがいくらでも存在するのに、なんでそういうの作ろうと思ったわけ？
新規性がないんだよね。
いや、悪いとは言わないよ。
でも、これからのコンパイラ作りというのは、COINSやGCCのような
コンパイラインフラストラクチャ(COINSの用語を借りるなら)を利用して
最小限の労力で必要な部分だけを作るというように変わりつつあるのに、
君は今時そんなことをやってるんだねぇ。

>>15
いいよねぇ、ｹﾁだけつける楽な人生で

>>16
>>16

>>16
だってほら、何かしようとする子って「やる気」がある子でしょ？
そういう子は先につぶしておかないと後々やっかいなんですよ。

私が既存のどれを試したかはドキュメントにも書いた( http://tinyurl.com/yzxbdl )。
新規性がないということも書いたよ。
コンパイラの開発者ではなく、職業プログラマが、道具として、
小さいパーサを必要なところで自由に使えるものを、
というコンセプトで作ったものです。
自分はコンパイラにも使うつもりだけど。

私だって何も制約がなければocamlyacc使うよ。
ocamlであるということ以外、特に不満ないし。
既存のパーサジェネレータと格闘したことあれば
わかってもらえると思うんだけどなあ。勘違いかな。

COINSにパーサジェネレータあるの？　どこ？
web見るとJavaCC使ってるようだけど……

caper作ってから発見した(見落としてた)のは以下の二つ。
後者はJavaだけど。

glrParser( 全然知らなかった )
notavaCC ( javaに興味がなかった＆名前がJavaCCに似てたんで無意識にスルーしてしまっていた )

自分が何かを為す分のエネルギーを全部他人の足を引っ張ることに使って
何が悪いのさ。

>>19
あれ？もう一度みたんだけど、最初読んだとき、>>15が書かれる前だけど、と微妙に内容が変わってないか？

>>19
あんたが考えているようなものはすでにいろんな人がいろんな実装を作っていて、新しいものを作っても大抵は他の人がやってる事なんだよ、残念だけど。
20年以上も前なら人気があった分野だけど、今は>>15が言うように変わってきている。

微妙に変わってるけど、ほとんど見た目とかリンクだけだと思うよ。
svnのdiffみる？

nScript改造した方が早かったのにね

>>15
少しは他人の仕事も認めてみてはどうだ？
昔、自分でやってみて失敗したから腹いせなのかねぇ

認めるって12を？
この程度だと、高校の部活で作ったレベルだと思うけど。
はっきり言って何一つ面白くない。

レベル表現に中高が出てくるレスはどういうわけか説得力が無い

引くに引けないから逆撫でに終始してます、みたいな

高校生乙。
俺の勝ちだな。

>>28
一言多かったようだが、その態度は止めとけ。
その一言が、お前が認められない原因なのかもな。

作ってない奴よりは上だろうな
出来るけどやらないだけとかいう奴は論外

しかし面白くないという意見には100％同意

>>29
他人のふりして説教か。
つくづく負け犬というのは、まっとうな言論でまったく勝ち目がなくなってからが
「本腰の入れ所」なんだな。
消えろ、ゴミ。

>>31
本人のふりして煽りか。
つくづく負け犬というのは、まっとうな言論でまったく勝ち目がなくなってからが
「本腰の入れ所」なんだな。
消えろ、ゴミ。

そんなことより鮫の話しようぜ

>>33
鮫ってなあに？

http://nanashi.info/img/mirror/1123177027649.jpg

>>30
面白くないなら面白いlこと書いてよ

前スレのx86の命令表とかwikiにまとめてあるとうれしいなぁと
思いました。

>>31-32 ゴミですが消えてくないんですけど？

それっぽっちの日本語も正しく書けないとは、
本当にゴミだな。

>>39
日本語にそれっぽちもあれっぽちもあるんですか？

ここではクラスとしての日本語とインスタンスとしての日本語を
区別する必要があって、39は前者、40は後者なわけだ。
40のスクリプトエンジンは、意味解析に難があるな。

>>40
文章もソースコードも、量が多いほど「きちんと成立させる」のは難しくなる。
逆に、たかが一行の内容の無いレスさえまともに書けないなんてのは論外。

こんなこと（量について言っているということ）さえ説明されなきゃわからないとは、
本当に頭が悪いんだな。

>>42
数行に渡る説明よりも、一行の方が分かり易いが？

>>43
唐突に関係ない新しい切り口を持ち出して、さも反論のように書かないように。

なんで急に書く話が読む話にすり替わるんだろう

って書こうとしたら、当事者の反応の方が早かった。

>>37
http://freshmeat.net/projects/ia-32-instrdb/

キチガイはそろそろほっとくか・・
まあまあ楽しかったけどな。

お前ら釣られすぎw

いや、どうせならVB用のパーサジェネレータ作ってくれれば良かったのに、、、

もうどうでもよさそうな話終わった？

>>49

VBって処理系無料？
無料だったら、exampleのhello0.hppをVBで記述したらどのようになるか
書いてみてくれれば、作れるかも。
無論人柱やってくれるなら、だけど。

>>50
せっかくがんばって作ったのに、みんなに叩かれてかわいそう・・；；
私は味方だからね・・

漏れもダウンロード済み。

動かなかったらごめんね

>>50
http://go.microsoft.com/fwlink/?LinkId=51405&clcid=0x411

インスコはした

VB、10年くらい前にやった気はするがまったく覚えてないんで、
どのような出力をしたらよいか
(hello0.hppに相当するものはどのようになってほしいか)と
わかりやすい入門サイトかなんかきぼんぬ

それくれれば
週末にでもやってみる

VBか。俺は今よりもVB6（以前）の方が好きだったな。
できればそっちを作ってくれんか＞12

そんな違うの？

まあhello0.hpp相当のものをくれたほうをやるよ
処理系タダならね

COINSってライセンスに制約あるの？
なんかちょっと動かすごとに１００円とか取られるイメージがある。

残念。タダじゃない。もう発売&生産停止の状態。
だが一部のファンの間で未だに根強い人気があるから、オークションとかで
激しく高値で取り扱われていたりする。

俺はたしかに好きだったが、離れてからだいぶ経つから「久々にものづくりに
勤しんでみますか」程度のノリで。パーサから構築するのはさすがに骨が折れるから
どうしようと思っていたらたまたまこのスレを見掛けたもので。

そんなわけだから、まあ無理なら自分で組み上げてみるよ。サンクス^^

XMLSchemaのパーサ作りたいでつ
でもでもEBNFとかなんもないでつよどうやってつくれば
いいんでつかだれか助けてぉ？

MLRISC とか C-- とかはもうアクティブじゃないのかね。

　　x inW w2
------------------
x inW w1 UNION w2

こんなふうに文法分数みたいに定義してあるのたまに見るけど
これってどうやって解釈すればいいの？分母のルールを割るの？

>>62
えっと、これは数理論理学ではよくある書き方なんだけど、
上の式(or 命題 or 述語)が成り立つならば下も成り立つ
という意味。
二重線にすると、上から下が成り立つ、かつ、下から上も成り立つ（要するに同値）。

>>12
頑張れ
ドキュメントも良くかけてる

フラスコに精液を溜めようと思って、実際に半分ぐらいまで溜めたんですが、
使うときにフラスコからだそうと思ったら出なくなりました。
どうやって出したら良いでしょう？

おうthx

>>65
割れば？

自作自演乙

>>65
>使うとき

詳細(ry

いま、誰も知らないマニアックな言語のデータ構造を
Cの構造体に修正するツール作成したいのですが、

ある言語体系のルールから
別の言語体系のルールに変換するような内容の論文とか
資料とかって知りませんか？

意訳: パーサが書けない僕でもなんか処理できちゃう魔法知りませんか

パーサーの先読みが１つがデフォルトなのは知ってますが、
少なすぎませんかね？

例えばLR(k)をLALR(1)にするとかってことか？
つか先読み1つより大きくすると別の問題しょいこむだけだぜ

>>71
大体複雑なのが出来るだけだから、複雑になるリスクとの兼ね合い。

>>72,73
よく言われることだと思うけど、それほど複雑にならない気もする。

例えば、LALR(99)なんてのは論外としても
LALR(2)ぐらいならメリットの方が多いのではないかな？

ならそれでいいじゃないか？
つべこべ議論する事じゃないと思うが？

お前こそつべこべいうなよ

すまなかった。

この2や99ではない、1ってのがミソなんだな。

>>78
"Zero-One-Infinity Rule" だね

シフトを続ければ、１も９９も同じ

>>71
Packrat Parsingでは、無限長先読みができますよ、と

>>81
HaskellのPersecとかだね？

バナナ気持ちいいよバナナ

>>82
Parsecは確かに無限先読みが使えるけど、Packrat Parsingとは違うもの
Parsecは基本的にはLL(1) + Syntactic Predicate(Parsecで言うtryのこと)
Packrat Parsingのアルゴリズムは、基本的には再帰下降型Backtracking Parserで、
(入力開始位置、非終端記号)のペアに対して、一度計算したSemantic Valueを再計算
しないように記憶しておくことで入力文字数に対して線形オーダの計算量でできるように
効率化したもの

>>84
空間計算量はO(n^2)になりそうな気がするけどどう?

なんか、凄くレベルが高いなこのすれ。
俺的にはyaccの書き方に四苦八苦していて、gawkとかのお手本を勉強してたんだけど、
shift/reduce が沢山でていてちょっと安心した。
普通 shift/reduce や reduce/reduce って０に持って行くものだと思ってたけど、
現実は違うのかな？

>>86
慣れだよ。

yacc(happy)使うくらいならParsec使いたいな

>>85
非終端記号の個数mと入力文字数nに対して、空間計算量はO(mn)。で、
非終端記号の数は通常一定なので、大体O(n)と考えて良いと思う。
ただ、それでも莫大なメモリを消費することには変わりないので、
巨大なXMLファイルなどを解析するのは向いてない。
Java用のPackrat Parser GeneratorでRats!というのがあるので、
興味があれば使ってみれば良いかも。

ちなみに俺はyaccのようなbottom up parserの挙動はイメージしづらいんで、
あんまし好きじゃない。自分では、JavaCCのようなLL(k)
Parser Generatorをもっぱら使ってる。

>>86

reduce/reduce は0にしないとだめなんじゃないか?

True AWK の結果（↓）
awkgram.y: conflicts: 43 shift/reduce, 85 reduce/reduce

コンパイラってどうやって作るの？

まず、HSPを卒業して他の言語を覚えることから始めないとダメだ。

　　　 　　　　　,-､　　　　　　　　　　　　,.-､
　　　　　　　 ./:::::＼　　　　　　　　　 ／::::::ヽ
　　　　　　　/::::::::::::;ゝ--──-- ､._/::::::::::::::|
　　　　　　 /,.-‐''"´ 　　　　　　　　 ＼:::::::::::|
　　　　　／　 　　　　　　　　　　　　　　ヽ､::::|
　　　　/　　　　　　　　　　　　　　　　　　　ヽ|
　　 　 l.　　 　　　　　　　　 　 　 　 　 　 　　 l
　　　 .|　　　 ●　　　　　　　　　　　　 　 　 　|
　 　 　l　　, , ,　　　　　　　　　　　●　　　　　l
　　　　` ､　　　　　　(__人__丿　　　　､､､ 　 /　>>1 糞スレ
　　　　　　`ｰ ､__　　　　　　　 　　 　　　 ／
　　　　　　　　　/`'''ｰ‐‐──‐‐‐┬'''""´
　　　　　　　　./　　　　　　　　___　l　__
　　　　　　 　 l　　 ./　　　　／　 |／　|
　　　　　　 　 `ｰ-<　　　　/　　./　　./
　　　　　　　　　　　`ｰ‐--{___／ゝ､,ノ

>>93
HSPでかけないアルゴリズムってあるの？

>>95
ランレングス

冗談でしょう

>>95
普段使ってないので言語仕様確認してみたけど、構造体定義や配列のネストが無い
みたいなんでコンパイラ内の中間構文木の処理なんかが相当苦労しそうな気がする。

何かでDLL作成して、それ以外をHSPで作成すれば問題ない。



・・・・HSPってDLL読み込めるの？
使ったこと無いからわかんない。
（調べてない。）

HSPを使う意味ね〜

>>86
本職で書いている訳では無いので、言語設計の文法は出来るだけシンプルなものにする方向
でしか書いてないけど、自分の場合はreduce/reduceは無効になっている構文が発生するので
無くす方向で、shift/reduceもログチェックして意図した通りの動作になっているか確認してる。

C++とか複雑過ぎるパーサ書く場合は知らない、awkは省略規則による例外文法が多いのかも
しれないけど類似のJavaScript程度の言語なら殆どshift/reduce無しで書ける筈だと思う。
(if文とtry文、オブジェクトリテラル構文で発生している程度

>>91

True awk ってえと bwkのとこにあるやつ?
とりあえず gawkの gawkgram.y をbisonに食わせたら

conflicts: 31 shift/reduce

だった。reduce/rdeuce conflict はこの状態だとないんだよね?

ところで、話は変わるんだが、C/C++用のParser Generator
でLALRじゃなくてLL(k) Parser吐くタイプで良いの無いかな？
ANTLRはなかなか良さげなんだけど、生成したパーザが
ランタイムを必要とするのが、ちょっとイマイチ

つSpirit
ttp://boost.cppll.jp/HEAD/libs/spirit/

蛇オナニーって気持ちいいって聞いたんですけど、やったことある人いませんか？

>>101
それだと reduce/reduce は無いことになるが、
そんなにも有るものなのか？ shift/reduce conflict

>>105
該当ソースは見てないけど、省略表記が可能なルールを並べるとshift/reduceに
なるんで、awkみたいな構文糖的な文法の曖昧さが多いパーサだとその辺が引っか
かってるんじゃないかって気がする。

>>91
恐ろしいな、これも慣れなのか？

──────────────────　　　＿＿＿＿＿＿＿＿
──---ｧ--──--､＿＿＿,,. イ＿＿＿＿＿＿　─────　　＿＿＿
　　　　'´　　　　 　 　 ＼　　 　 /　　　　　　　　　　　　　　　　　　　 ＿
　　　　　　　　　　　　　　ヽ　　/----　　二二二 　 　　 　 　─
　　　　　　　　　　 　 　 　 '.　/　　￣￣　＿＿＿　　　　　　　　　￣￣
｀ヽ./　 　　　　　　　　　　　ｉ/────　　　＿＿　　-　　──
　　|　 　○　　　 　　　 ○l　　　 _,,ｨi⌒ヽ　　　　二　＿＿　二　　￣
　　ヽ　　 　 ＿＿＿ 　　 /r‐-r''´ ﾉ.ｌ　　|⌒ヽ　　　　 　　　　　　　　---
　 ／｀ヽ､　 　　　　　 ＿厶'⌒_l 　 { :|　　l　　 |_　￣￣￣　 　　　──　＿
／　　　　　　　＜￣´　　　,,＿ゝ､_ﾉｽ,,_,ノ､_,,ノ》｀!＿＿＿　　　　　　＿＿
　　　　　　　　 　 ＼　';:,:　　　　　　　　　　　:.ﾐ_ﾉ 　 ＿＿　
⌒⌒ヽ　　 　 　 ｀';:;,＼　　　　　　　　　　　　　ﾍ.＿＿＿ 　 　 　　 ￣￣
　､　　）￣}￣￣￣￣￣ヾ　　　　　　　　　　　　|←>>94　＿＿ ＿　　　
､_人_,ﾉ⌒)}─┐ 　 　.,,;:':;}#;;'　　　　　　　　　ノ──　 ＿＿ 　 　　─
　　＿,,ノ´　　└───;ｲ;ﾟ;'　　　　　　　　j/　　　　　　　　　　─
r‐'´　　　　 　 　 　 ..:;::','/；;　　　　　　　　　ヽ、￣　───　- 　 　＿

いまどきのプログラム言語の作り方 (単行本)
http://www.amazon.co.jp/exec/obidos/ASIN/4839919232/

がなかなかいい感じでした。
諸本に挫折した俺には、わかりやすかった。
Javaで、コードも読みやすいし。
もっとこんな本が出てほしい

ふーん、俺もいまだにコンパイラ本の読破に挫折し続けているから
読んでみるかなあ


なお、コンパイラ本を読破はしたことないが
コンパイラを作って事はある
読むより書くほうが簡単みたいな希ガス

設計に向いてないじゃないか。
コンパイラじゃなくてツールとかGUIとか作ってた方が今後のためだろうに。

>>109
そのタイトルを見ただけで不安を覚えるのは、俺だけじゃないはずだ。

いまどきのアセンブラプログラミングのことか・・・

処理系について、もうちょっとちゃんとした勉強をしようと思ったときの導入本としてはコンピュータサイエンス入門とかお勧めだけどなぁ。

yacc 使い始めたところなんですが、エラー処理がさっぱりわかりません。
再帰下降法のときは手書きだったしエラー処理はわかりやすかったんですが、
yacc使うと、なんというか、エラーが発生したときにどの生成文法のどの箇所でエラーが発生したのかわかりません。
例えば
while-statement : 'while' '(' expression ')' '{' statements '}'
;
という文法があったとして、
while x > 0 { .... } 　なら「'('が期待されてるけど見つからないよ」
while (x > 0) ... 　なら「'{' が期待されてるけど見つからないよ」
ということをしゃんと出力したいんですけど、参考になるページとかありましたらお願いします。

しゃん‐と
副
正しく整ったさま。きちんと。「つづら帽子を―着て」(狂言歌謡)
確定的であるさま。たしかに。浄、薩摩歌「―嫁入つて退ければよいものを」
姿勢・気力などがしっかりしているさま。「背筋を―伸ばす」「年に似ず―している」
【岩波書店 広辞苑第五版】

しゃきーーーん！

yaccから先の話しよーぜ

ANTRL age

ちょっと前にドラゴンブック買ったら米国で>>8
ちょっと前にホップクロフトのオートマトン2nd.Ed.買ったら米国で3rd.Ed.
　　　　　　　　　　　　 (´Å｀)

lemon秀逸なデザインだがGPLだから用途が限られる。
caperに期待したいとこ。

caperって有名なの？

いまどきのプログラム言語の作り方 (単行本)
今から読んでレビューしてみる

>>１２１
ぐぐっても関係ないものばかり出て来る

http://www.hwaci.com/sw/lemon/lemon.html
http://www.chibutsu.org/faf/translated/LemonPG/LemonParserGenerator.html

プッシュ型まんせー

公開したばっかだよ

>>125
ざっとみてけど A＝B＋C と書けること以外、何が良いのかさっぱり分からんな

ソース見るかぎりpublic domainだけど……
ttp://www.sqlite.org/cvstrac/getfile/sqlite/tool/lemon.c

As a public service, Hwaci makes the following software available for free in source-code
form. Most of the software here is covered by the GNU Public License.

Lemonは例外でGPLではないのかな。

>129
それってソースどこ？

lemonを含むSQLite自体がpublic domainだから、lemonもpublic domainの
扱いになっているみたいだけど……
fleshmeatのライセンスが間違っているような気がする。

>>130

本人のサイトでしょ。
http://www.hwaci.com/sw/index.html

ジェネレーターはソースを吐くから、
普通のソフトとはライセンス問題の事情が違うなぁ。

>131
それだったら、lemon自体の説明には
 Both the source code to lemon itself and the code that lemon generates
 are in the public domain.
と記載されているから、public domainと考えていいんじゃない？
fleshmeatのは間違いと言うことで。

public domain だと copyright が守れ無い可能性があるのでは？

それは問題無い。

ttp://d.hatena.ne.jp/higepon/searchdiary?word=%2a%5bScheme%5d
チッ。イイ気になりやがって。

>>37
それ欲しがってたの俺ですけど、例のマニュアルに載ってる分は完成しました。
86系ってインテルだけじゃないし、インテルにしても種類があるので
それだけじゃぜんぜん足りないんだけど、まぁとりあえず出来たってことで。

　　　　　　　　,-､　　　　　　　　　　　　,.-､
　　　　　　　 ./:::::＼　　　　　　　　　 ／::::::ヽ
　　　　　　　/::::::::::::;ゝ--──-- ､._/::::::::::::::|
　　　　　　 /,.-‐''"´ 　　　　　　　　 ＼:::::::::::|
　　　　　／　 　　　　　　　　　　　　　　ヽ､::::|
　　　　/　　　　　　　　　　　　　　　　　　　ヽ|
　　 　 l.　　 　　　　　　　　 　 　 　 　 　 　　 l
　　　 .|　　　 ●　　　　　　　　　　　　 　 　 　|
　 　 　l　　, , ,　　　　　　　　　　　●　　　　　l
　　　　` ､　　　　　　(__人__丿　　　　､､､ 　 /　>>1 糞スレ
　　　　　　`ｰ ､__　　　　　　　 　　 　　　 ／
　　　　　　　　　/`'''ｰ‐‐──‐‐‐┬'''""´
　　　　　　　　./　　　　　　　　___　l　__
　　　　　　 　 l　　 ./　　　　／　 |／　|
　　　　　　 　 `ｰ-<　　　　/　　./　　./
　　　　　　　　　　　`ｰ‐--{___／ゝ､,ノ

>>12が煽られてる意味がまったくわからん。
>>12乙。
こういうの欲しかった。

>>138
自演乙

レモンだけど、bisonもライセンスの制約が全くないと思われるが、
はて？

coinsってライセンスの記述がサイトに無いけど、制限無しなの？

bisonて、bison本体はGPLじゃないの？lemonは本体もpublic domain

>>１４２
その通りだけど、 bison自体をいじるのでなければGPLの縛りはない。

まだ作ったばっかでバグとかあると思うから
そのつもりでﾖﾛﾋﾟｸ

細かい仕様に関する突っ込み等も歓迎

12の自演がキモいレベルにきている件について突っ込みたい

EBNFとかABNFとか自分で記述して矛盾がないか確かめたいんですけど
やっぱLispとか関数言語叩いて、自分でBNFを処理するプログラムを書く以外
方法ないでしょうかね？なんか、ぽちぽちっと定義して実行とかできないですかね？

>>146
矛盾っていうのが何を指しているのかがよくわからんが
構文規則がLL(1)に収まっているかとか、LALR(1)に収まっているかとか
を確かめたいだけなら、JavaCCなりANTLRなりyaccなりに文法定義ファイル
を処理させて、conflictが起きないか確かめればいいだけだと思うが
それでは駄目？

>>145
嫉妬心ｲｸﾅｲ

>>147
それすらも免土井のは染んだほうがいいですよねｗ
がんばってかきますｗ

どなたか>>115お願いします。

> yacc 使い始めたところなんですが、エラー処理がさっぱりわかりません。
> 再帰下降法のときは手書きだったしエラー処理はわかりやすかったんですが、
> yacc使うと、なんというか、エラーが発生したときにどの生成文法のどの箇所でエラーが発生したのかわかりません。
> 例えば
> while-statement : 'while' '(' expression ')' '{' statements '}'
> ;
> という文法があったとして、
> while x > 0 { .... } 　なら「'('が期待されてるけど見つからないよ」
> while (x > 0) ... 　なら「'{' が期待されてるけど見つからないよ」
> ということをしゃんと出力したいんですけど、参考になるページとかありましたらお願いします。

>>150
bison なら、verbose オプションをつけてパーサーを生成すれば
それでOKですよ。普通にyyerror()で目的の出力が得られます。

クロージャを実現する簡単なスタックマシンの例のソースとか
ないでしょうか？

>152
スタックマシン上でクロージャを作る必要性ががさっぱりわからないのですが。

SECDマシンのことじゃまいか？
Palm向けだけどLispMeのソースが読みやすいとおもた

ほんとーはHendersonさんの『関数型プログラミング』がおぬぬめなんだけど絶版なのよね・・・

tinyschemeもSECD machineじゃないかな。
"SECD Machine" でぐぐれば解説は出てくるよ。

C++で実装したBasicのインタプリタってどっかにない？

その要求でぐぐったらすぐに出てきたぞ。質問する前に自分で探せ。

>>156
ゴミだなコイツはｗ

>>156
「IOCCC Basic Interpreter」でぐぐると短いソースが見つかるお（ ＾ω＾）

>>157
探しても見つけられなかったから訊いたんだよ

>>159
サンクス
別のものだけど、それで検索したらいいのが見つかったよ

相当探し物が下手なんだな。

つまり　めがね〜めがね〜ってやつだな？

...

>>159 も罪作りなヤシだ（藁

ってよく読んだら160が見つけたのは25 linesじゃないのか
ちっ

>>159

すげープルグラムだな。
読む気なくすよ。

BNF集があるといいのにな。

>166
ほれ
ttp://www8.atwiki.jp/e9g92z/

>>167
ん？これなんか関係あるのか？

>>167
それは、資産100億のB・N・F氏（わら

【スクリプトをちょっと紹介させてください】
アドベンチャーゲーム用スクリプトシステム「ＭＩＣｏスクリプト」を開発しました。
軽いこと＆商用ゲームでの使用可能な高性能を目指して設計しており
複雑な演出も簡単に作れるシステムです。
詳しい紹介は公開サイトにありますので、よろしければ使ってみてください。

公開サイト
http://mico.x0.com

うんこ

>>170
途中でハングした

こんどはフリーズした…これでマジ商用目指してんの？
サンプルのレベルでこんな簡単にぽろぽろ止まるようじゃ
販売されて一般のPCに入ったらとんでもないことになるぞ

ノートンが反応した

Not Found で落とせない……

>>175
リンク先のURLが
http://mico.x0.com/files\MICo100c.zip
になってるから\を/に直してやれ…

まぁ、これはどう見ても
出来を知った赤の他人が「紹介」を称して晒してるんだろうな。

WIN専用ということで、捨てw

Win専用じゃないのってあったっけ？

>>170
商用利用(に限らずだけど)してもらうには開発環境が貧弱な気がする・・・
スクリプトのデバッグ方法ってあるのかな？

>>179
一応、吉里吉里が動かなかったっけ？
前にソース眺めたときにLinux用のソースを見た覚えが

そういや、すごく前の話 >15 >22 を見てて思ったんだけど、
・LALR(1)
・C++コードを吐き出す
　- パーザーをオブジェクトとして扱える
　- namespaceで閉じている
　- マクロを使わない
・フリーな実装
て、>12以外にあったっけ？
LL(∞)ならboost::spiritなんだろうけど。

>>170
WinXPマシン(2.53GHzのPentium4、1GBのメインRAM、128MBのVRAM)で
サンプルスクリプトを起動させてみたが、商用ゲームで使用可能な性能を
目指すなら、最低限これの倍以上は軽快に動いてほしい。
そうでないとユーザーとしてはマジでやってられん。

>>181
（確か）吉里吉里３はLinuxでも動くように開発されてるよ。

吉里吉里は良く出来てる。
動作がもう少し軽ければもっといいのにな。

>>182
本題からはずれるんだが、LL(∞)って用語は一般的なのか？
LL(*)というアルゴリズム(無限長先読みだけど、先読み文法が
正規言語に限定される)は前に調べたことがあるけど、
LL(∞)というのは、今まであまり聞いたこと無いもんで。

>>184
吉里吉里って非JITの仮想マシンしか搭載してないくせに結構速かったような

(ここにベンチがある)
ttp://gamdev.org/w/pukiwiki.php?%5B%5B%A5%CE%A5%D9%A5%EB%A5%C4%A1%BC%A5%EB%C1%AA%B9%CD%5D%5D

Applying a function pairwise to all data of two trees.
Variable combine:
forall (A: Set), (option A -> option A -> option A) -> t A -> t A -> t A.
Hypothesis gcombine:
forall (A: Set) (f: option A -> option A -> option A)
(m1 m2: t A) (i: elt),
f None None = None ->
get i (combine f m1 m2) = f (get i m1) (get i m2).
Hypothesis combine_commut:
forall (A: Set) (f g: option A -> option A -> option A),
(forall (i j: option A), f i j = g j i) ->
forall (m1 m2: t A),
combine f m1 m2 = combine g m2 m1.

これってどの関数型言語？

そういえば、志古志古１０００というのが無かったっけ？

>>187 Coq?

「スモールコンパイラの製作で学ぶプログラムのしくみ」を
買ってしまった。
なんだこの本の内容？買って損した。
First(),Follow()の説明に自分でウソ書いてて気づいてなんだな。
ま、理解できてないまま本出すの勝手だけど、ウソ書いて
混乱させんじゃねーよ。全く。

Follow(S)に $ を加えるのはいいだが、
この著者は 終わりといいう意味の $ を '$'と混同してるんだ。
こっちが理解してやるのに疲れる。
誤記多いし。勘弁してよ〜。

その様子じゃ、理解出来てないまま非難してるのはお前だなぁ｡

>>191

その通りだ。スマン。。

素直でよろしい。
これはとても大切。

パパ乙

コンパイラの本って少ないな。

>>190
説明しろ

りんごタソの本か？
なかなか良かったぞ。

>>197
あそこの調子はどうですか？

ぬめってます

>>154
>>155
凄く遅いレスになりましたが、サンクスです。
地道に勉強してみます。

たまらんなw

ここに知ったかぶりをしている人は何人いるでしょうか？

ハァハァ

その名もSECDR-schemeというのがあったはずだが。

caper作った人まだみてる？

たまにみてるよ
最近仕事忙しくてcaperいじってないけど

お仕事で使おうとして上司に
「caperだよね」
「自動生成だよね？」
って釘指されてﾜﾗﾀです

まじで仕事に使うの
チャレンジャーすぎｗ

設定ファイルの定数に数式入れたいだけだからね。
文字で書かれた簡単な数式をdoubleで計算とかそういうライブラリあるかと思ったら
yaccやらbisonやらのサンプルばっかりで以外と見つからなくてさ。

ぶつくさいいながら再帰下降パーサ書くくらいならとおもって使わせてもらいました。

ohそれはすばらしい

バグや気に喰わない使用があったら教えてね

このスレでCoinsの話題って禁句？

>>211
推奨だよ

log読んでたら>58 >148がスルーされてたから、駄目なのかなと
特に話題はないんだけど

58と148の関連性が全くﾜｶﾗﾝ

このスレでLISPの話題って禁句？

>>215
高度粘着性のキチガイを召喚する可能性が高いのでやめといたほうがいい

スレちがい。
実装の話ならOK。

いや実装の話でも止めてくれ

お前の事情なんざ知るか。
イヤならもっと面白い話題を振って乗っ取ってみろや。

実装の話は、そもそもついてこれるヤツがろくにいないだろ
Lispに限らずな、コンパイラ作れるヤツがろくにいねえ

ごめん、間違った。148じゃなくて>141

>>215
やめとけ、そのうちRuby坊も出て来るから。

>>220
いや、実装の話の方が実は簡単なんだよ。

その簡単な話よりさらに簡単な話しか
殆どのヤツはついて来れねえんじゃねえの？

あとまあ、どこぞの誰かの作ってる糞言語の
実装の詳細なんぞ興味がないから、
ついていけても、食いつかねえってのもあるが

シグウィンというコンパイラを手に入れたのですが、ソケットヘッダがあるのに使えないのです。どなたかわかる人いませんか？また他に使い易い、コンパイラあったら教えてください。

その簡単な話よりさらに簡単な話しか
殆どのヤツはついて来れねえんじゃねえの？

あとまあ、どこぞの誰かの作ってる糞言語の
実装の詳細なんぞ興味がないから、
ついていけても、食いつかねえってのもあるが

シグウィンというコンパイラを手に入れたのですが、ソケットヘッダがあるのに使えないのです。どなたかわかる人いませんか？また他に使い易い、コンパイラあったら教えてください。

ここはコンパイラの実装等をお話するスレで使い方のスレではないですお

データフロー解析のソースコード付き簡単説明が欲しいです。

HendersonのSECDマシンの、DUM,RAP,ATOMがまだわかりません。
http://www.yuasa.kuis.kyoto-u.ac.jp/~nobu/study/palm/chap6.html
これの、6.4がわからん。くそう、わからんぞー。
頭悪いんだなぁ。
SECD Maniaとかのソースは古くてごちゃごちゃしすぎてる気がするし。。。
なかなか、時間もないけど、能力もないので嫌になってきました。

>>230
それ、LispMeの論文の超適当かつ端折りまくりの日本語訳だろ。
SECD machineでぐぐるとそいつが上位でマッチするというのは害悪のような気がする。

その論文はoriginal SECD machineとLispMeの差分について述べてるんであって、
original SECD machine の仕様も押さえながら読まなきゃ理解できんぞ。
特にLDF (クロージャを作る操作) がそこには書いてないんだから。

ちょっとスレ違いかもしれないけど質問です。

今、プロトタイプベース（移譲中心）の俺言語を作っているんですけど、
ダイアモンド継承の処理の方法に悩んでいます。

ダイアモンド継承についての良さげな文献とかありません？

>>232
C++のD&Eを見れば、なんか参考になることが書いてあるかも。

>233
見ました。良い本だよね。D&E

「vtblを間接参照する」までは載ってたけど、流石に同一仮想ベースクラスを
効率的に検索する実装までは載っていませんでした。

プロトタイプだと、下手すると変数を参照するたんびに移譲先を探さなきゃ
いけないので、このあたりの処理は悩ましいですよね……

>>234
じゃ、そこらのC++コンパイラでvtblをどのように扱ってるか解析するのが近道かもね。
以前、ダイアモンド継承してるオブジェクトのデータ構造を調べたらなんかへんちくりんな構造してたけど。

プロトタイプベースでダイアモンド継承というのが理解できない。
プロトタイプベースってことは分裂+突然変異でオブジェクトができるんじゃないの?

二つをくっつければいいんだよ

>>232
うーむ。日本語でSECDマシンのいい解説があるといいのだけどなぁ。
ほかの英語の論文をちまちま訳しながら、勉強してるところです。

>236
ダイアモンド継承と言ったのはちょっとまずかったかな？
実際にはちょっと違います。

俺言語では、こんな感じで
A <= B
a|　　a|
α<= β
参照aを持つオブジェクトAに委譲するオブジェクトBがある時、
Bからaを参照する場合は、参照先αをそのまま使わずに、αに委譲した
プロキシβを作成してそれを参照するようにしています。

で、何が問題かというと、Aに同じオブジェクトを参照する参照が2つある場合、
A <=== B
a|b　　a|　|b
α<=　β　|
　　<===　β'
こんな感じでBの参照aと参照bが別のプロキシになってしまいます。
C++のダイアモンド継承の問題もこんな感じだよね？
 

SECDてこれ？
ttp://en.wikipedia.org/wiki/SECD_machine
面白そうですな。ちょっと読んでみるよ。

CodeZine：JavaScriptでつくるSchemeインタプリタの基礎の基礎（lisp）
http://codezine.jp/a/article/aid/739.aspx


JavaScriptでLispｗｗｗｗｗｗｗｗｗ

>説明の簡略化のため、マクロ、末尾再帰の最適化、継続などの実装は省きます。

それSchemeじゃねぇwwwwwwwww
普通にLispて言やいいじゃん

JavaScriptってほとんどschemeやん

(ﾟДﾟ )ﾊｧ?

scheme with C's clothing?

>>240
遅レスですが、それです。

HendersonのSECDマシンの実装は出来てるっぽいのだけど、
DUMとRAPの使い方がわかってるような、わかってないような。
JavaScriptだと、
function plus(a){ return a + 1; }(10);
が
(LDC (10) LDF (LD (1 . 1) LDC 1 SUB RTN) AP STOP)
となる。と言った感じの、まともに動くサンプルをつくりたいんだけど。

>>246
どうしてそこでSECDの本来のターゲットであるSchemeで考えないのか
とっても不思議なんだけど。
DUMとRAPの用途は、letrec。

そこまで自分のわかってないことがわかったなら、あとは
LispMeのソースを眺めてどういう風に使われるか見れば一発でしょ。

コンパイラとかSECDのコアとかなら、Palm依存のコードを除いて
手元のPCで実行できるようにするのもさして難しくはない。
動かさなきゃ理解できないようなものでもないが。

SECDマニアのHendersonのプログラムをコンパイルして弄ってみたのだけど
((letrec a (a lambda (b) b)) 1)
が
(LDC (1) DUM LDC NIL LDF (LD (0.0) RTN) CONS LDF (LD (0.0) RTN) RAP AP STOP)
ということでいいのかしら？とりあえず、思ったとおりに動いているのだけど。
letrec用途であることはわかるのだけど、自分で作って動かすとなると動かなくて。

coins verup

coins使ってる人っている？

いません

今時Javaって・・気が触れたとしか思えん

>>252
あなたなら、今なら何が、コンパイラを作るのにいいと思いますか？

Ruby か Haskell だろ

そーか? HaskellはともかくRubyは……
作り始めはいいかも知らんが、だんだんチェックが欲しくなってくるから
型がルーズな言語はしんどいよ。

C++
boostあれば色んなことできるようになるし。

http://hp.vector.co.jp/authors/VA000092/jokes/strup.html

>>256
お前は４年前の俺か

4年の間にどんなカルト宗教に洗脳されちゃったんだろう

適当になれた言語で一応動くものを作ったあと、自己記述化

しかし、処理系作るなんておまいらすごいですね。
自分も何れは、自分で設計したスクリプト言語のインタプリターでも作りたいと思ってるんだけど。

ところで、知ってる言語が、C/C++, VB, PHP, Ruby, BASIC なんだけど
インタプリター実装に使う言語としては、この中だとどう考えても、C/C++ になるよね？
あと、こういうのって、ある程度汎用的に使える様な構文解析エンジンみたいなのはフリーで良いのが公開されてる？
それとも、Boostとかの正規表現ライブラリとか使って、自分で解析エンジンとかも製作するの？

bison, flex

ほほうー これでparserクラスとか作るわけかー
いつか作ろう。

いまからbison+flexを覚えるくらいなら最初からantlrに取り組んだ方がいいと思う。
いろんな言語向けのコード生成できるし。

C++でお勧めありますか？ 今はspiritでシコシコやってます。
まあ、Forthチックだから大したの要らないんだけど。

>>265
spiritを使う気になる環境ｳﾗﾔﾏｼｽ

>>265
antlrじゃダメなの？処理系自体もC++で書いてあることが要件なのかな。
大袈裟なのが必要ないならcaperでいいんじゃない？

>>250
ソース拾ってきて、眺めて終了してしまってます。。。
もっと、面白い記事がネット上にあればなぁ、思います。

>>265
時間の無駄だからやめたほうがいいよ

>>265
FORTHチックじゃ構文が分かち書きで切った部分が直接命令に還元されるって事かい？
なら構文解析コード使う事自体に意味がないだろう？

むしろできあがったコードの中身をJITでネイティブに落とすとかそっちの話の方がメインじゃないのかい？

来月のPOPLってどうよ？

GCCってもっと速くならないの？

GCCの何を速くしてほしいの？

coinsは遅くなったらしい。

中田先生がファビョってるようにしか見えない
もっと落ち着いてメールして欲しい
公の場なんだから

たしかにメールの勢いはひどいが
INFOがうざいのも事実。

あけおめ

COINSのMLどうなった？
スレッドがぐちゃぐちゃで読む気がしないんだけど

COINSのMLってどうやったら読めるのですか？

COINS使いたいのですが、ヘッダのGCC拡張エラーになります
ヘッダを入れかえるのは、パッケージ管理しているのでやりたくありません
どう対処するのが一般的ですか？


# FreeBSDでは問題無く動いてます

超能力者募集中か？>>280

>>281
お前には想像力が無いことだけは解った。

想像力で補ってどうするよ。いくつ可能性があると思っているんだよ。
まずは >280 が 『回答者が回答するために必要な情報はなんだろう？』 と想像しろ。
自分の環境を特定しようとしないやつに質問する資格は無いわ。

>>283
過剰反応。
子供か、君は。

>284
お前は誰だよ。ちゃんと名乗れ。
これだからIDの無い板は……。技術系の板でID無しって腐ってるよな。

ただ正論言っているだけだよ。 現実世界と違って >280 に気を使う必要無いしな。
早い話、>280は質問の仕方を覚えないと技術系としてはやっていけないよということで。

>>285
鬱憤晴らしで初心者いびりがしたいだけだろう？

>>286
SOREDA

環境もワカラン、どのコンパイラつかってるのかもワカランでどうしろっての？

莫迦？

>>288
解らんことがあれば聞け。
ただそれだけだろ。
お前は普段の仕事で、解らんことがあるのでこの仕事はできません、なんて言うつもりか？

>286
そりゃそうだ。こんなマヌケじゃなぁ……

>288
おまっ、それマジで言ってんの？？？？？

「相手が根気良く確認してくれるのはなぜか？」ということ考えたことある？
確認する側にメリットがあるからじゃないか。
仕事なら『業務を遂行する＝自分の業績に繋がる』というメリットがあるけど
こんな匿名掲示板で根気良く確認しても何のメリットもねぇだろ。
逆に、質問する側は『疑問点を解消する』というメリットがある。
ある意味一方的な関係だ。

だから、こういうところでは回答者に積極的に協力しないとシカトされてお仕舞いなんだよ。
そんなに手取り足取り確認したけりゃCOINSのサポートに頼め。

COINS コンパイラ・インフラストラクチャ協会も無償奉仕みたいだから、>280みたいな
質問の仕方だと、「何いってんの、お前」というのをやんわりと言われるかもしれんがな。

仕事のような熱心さで、２８０の質問に答えてくれる人、
募集中というところかｗ

libc の header に gcc 拡張が使われていて
coins が gcc 拡張を理解できないからエラーになるんだろ？

いいじゃん glibc なんか捨てて *BSD 使えば

むしろsolarsiのでばんですよ

>>279
中の人に頼み込む。

自分の質問の馬鹿さを指摘されたあと見せる無駄なエネルギーの半分でいいから、
元の質問文の練り込みに使えばいいのにな。

くっ、スルー力が足りないっ

>>296
スラドにお帰りください

>>297
omochiの日記読んでしまって鬱

中田先生の本、ちゃんとした日本語でわかりやすいね。
しかし数学家のせいか、変な数式化するやつには参るな
A = {P,S}とか{a} = 　a |aa | aaa....とか

慣れれば普通だよ

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

中田先生の本はアレだな。理論の説明はいいんだけど、その理論を実際どういうときに使うのかもう少し詳しく書いてくれればもっとわかりやすくなるな。
できれば１つ１つの理論とＣ言語のコードを対にして書いてほしい。

コンパイラの構成と最適化を読んでいて再帰的下向き構文解析のところまで読んだのですが、
構文解析と字句解析の区別がよくわからないのです。

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

Wikipediaさんに聞くと良いと思うよ。
字句解析：入力を字句（プログラムの最小単位）に分割する
http://ja.wikipedia.org/wiki/%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90
構文解析：字句同士の関係を解析するhttp://ja.wikipedia.org/wiki/%E5%AD%97%E5%8F%A5%E8%A7%A3%E6%9E%90

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


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

>>303
字句解析しないということは、文字単位で構文解析することになるけど、
f 一文字を読んで、予約語の for なのか、ただの識別子なのか判断つかないのが下向き構文解析だとちょっと困る。

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

C++みたいに、文脈情報が無いと字句解析できない場合はわけない方がいいのかも。
最近流行？ のcombinator parserも基本はわけないよね。

Lispなら（ｒｙ

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

packrat parserって下降型のparserだっけ？
左再帰は大丈夫？

後戻りできるようなものを作ろうとすると、
字句解析と構文解析が分かれていたら非常にやりにくい。

ループ以外の左再帰って使う機会あるの？

>>309
左再帰はNG。そういうのは繰り返し(*)を使って書くのが定石。
右結合の演算子の場合は、右再帰で書くけど。

21世紀にもなったというのに、左再帰を人手で展開せなあかんのか…
あれ、文法が汚くなるから嫌いなんだよな

e ::= e + e | n

が

e ::= n (+ e)*

になるのはつらい。

>>313
まあ、その辺はトレードオフということで
ちなみに、俺はトップダウンparsing的な発想がデフォだから
左再帰を人手で展開するというよりも、展開系がまず先に
思い浮かぶ

>>301
自己レス。同じ疑問をもった人へ。
いまどきのプログラム言語の作り方
http://www.amazon.co.jp/%E3%81%84%E3%81%BE%E3%81%A9%E3%81%8D%E3%81%AE%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E8%A8%80%E8%AA%9E%E3%81%AE%E4%BD%9C%E3%82%8A%E6%96%B9-randy/dp/4839919232/ref=pd_sim_b_4/
がいいと思う。
字句解析と構文解析がわかればどういうもんか一発で理解できると思う。

つ ttp://www.hpcs.is.tsukuba.ac.jp/~msato/lecture-note/comp2005/index.html
　　ttp://kmaebashi.com/programmer/devlang/yacclex.html
　　>2-3
まずはこんなところじゃね？
 

>>316
いや、自分にはこの↓説明がいかんかったです。

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

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

>>317
理論抜きでもｲｲから、他のちっこいスクリプトをまねして、
とにかく一回でも、実装してみれば、
ああーんそうか、って納得できるんだけどね・・・。

パーサコンビネータの論文ありますか？

最適化って、結局はグラフの操作がメインになるんだけど、
あれは、ややこしいねぇ・・・

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

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

>>320
最適化って例えばどんなやつ？
それによって変わるような気がするけど。

>>321
"ほにゃららほにゃらら elimination" とか、
データフロー解析に絡む
あの一連のやつ。

>>322
フローグラフ上のデータフロー解析なら
自分で実装するのがたぶん一番楽。

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


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

フローグラフ解析かぁ。
coins.flowあたりみればいいのかと思ったけど、さっぱりわからないです。
超簡単なソースどっかにないかなぁ。

>>324
coins.backend.ana.LiveVariableBitMap
とか結構簡単だと思われる。

>>323
手で書くのが難しいレベルの最適化って論理式で書けるの？
実行時間は？

>>326
データフロー方程式を解くのと同程度のことなら書けるらしい。
それ以上だとたぶん無理。

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

へー
おもしろそうだね

>>325
おおー、理解できる予感！！

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

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

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

俺スクリプトがようやっと文字列結合まで回るようになった……

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

>>330
つ　諦めろ

>>330
http://www.squeak.org/Download
http://www.cincomsmalltalk.com/userblogs/cincom/blogView?content=smalltalk

squeakね。クラスはこんな感じか。
ttp://squeak.qp.land.to/wiki/index.php?%E3%82%AF%E3%83%A9%E3%82%B9%E8%A7%A3%E8%AA%AC

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

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

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

>334
「自由自在〜」持ってたので、それを参考にブラウズしてみました。
……すごい数ですな。GUI系を飛ばして眺めてみます。

質問です。

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

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

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

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

有名な問題なのでぐぐれ。

>>303
その疑問はもっともだと思う。

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

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

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

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

無理してやればできるんでないの？

symbol ::= alphabet alpabet_or_digits

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

大まかに言うと字句解析は正則言語（⊆文脈自由言語）の解析、構文解析は文脈自由言語の解析なんだから、字句解析の部分も構文解析でできるに決まってるでしょ。

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

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

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

>>341

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

A | C

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

なるほど。サンクス。
Cのparserでも書いてみるかな。

再帰下降構文解析をするときに、
深いところで起きたエラーを戻り値で次々と伝えて行くやりかたは
かっこ悪いですよね?

例外はどうでっしゃろ？

>>345
投げられない言語もあるからなぁ。

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

ギャグで言ってます

人間bison!
まさかコレが「件」って奴？

>>345
if( !is_ident(context) ){
　throw syntax_error("hoge hoge");
}

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

再帰だとスタックを使い過ぎてオーバーフローしないだろうかと
不安だった、そういう時期が僕にもありました

Rubyのインタプリタはスタックオーバーフローで死んだりする……

どんだけスタック食いつぶすスクリプト書いたんだｗｗｗ

>>352
Mac OS Xのデフォだと簡単に食いつぶす。
なのでulimitでスタックの制限をunlimitedにしなきゃならん。

>>352
たらいまわしとかだろｗ

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

>>355
……え？

なるる

ちょっと質問良いですか？

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

>>358
Pnutsのような方法以外だと、Lexerに改行を無視する状態と無視しない状態の
２つの状態を持たせて、ParserからLexerの状態を明示的に状態を遷移させる
という方法がある。ただ、それほど楽にはならないと思うけど。

>>358
つまりPnuts式はStatelessなlexerであり、lexerは楽できるけどParserがめんどい。
>>359の方法はlexerがstatefulになって少し面倒くさくなるぶんparserがすこし楽になる。
トレードオフだな。

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

俺言語を造っている変態が減ったんだろ
……俺言語の設計ってけっこう楽しいけど、破綻しないように作るのはしんどいよね。

構造体についての実装方法が載っている良書を教えてもらえませんか？
サンプルソースがあるとベターです

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

別に何を悩むこともないと思うんだが。

磯Cでいいんでない？

それが関数の呼び出しで詰まりまして
ある関数のreturnで構造体を返した場合ですが
呼び出し前に返値用のスタックを確保しておいて
そこにreturnのときにコピーするようなまどろっこしい方法しか思いつきません。

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

磯Cてなんですか？検索掛けたら考古学関連がでましたが・・・

動的配列のポインタを持っている構造体で無く？
そのものを持っているのですか？

>>366
ＣはISOでも標準化されてる
たしか言語そのものともうちょっとこまごまとしたものがあったはず
http://ja.wikipedia.org/wiki/C%E8%A8%80%E8%AA%9E

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

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

ついでに呼び出し既約
http://ja.wikipedia.org/wiki/%E5%91%BC%E5%87%BA%E8%A6%8F%E7%B4%84

そこらがどう実現すればいいのか解らないのですが
やりたいことは、

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

のような感じです

>磯Ｃ
なるほどISoのことでしたか。
有り難うございます見てみます。

>>370
stringって何者？

>>372
流れからして>>362のスクリプトにあるファーストオブジェクトだと思うが

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

>>370
普通
struct string {
size_t currentBufSize;
　char *pStrBuf;
//なにやらいろいろ定義
};

とかなってないかえ？

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

パーサと文字コードは全く関係ない。
字句解析コードも出力する機能があるタイプなら関係する。

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

rubyのraccは字句解析部分をrubyのパターンマッチで記述しているので日本語もいけそう。
構文解析やその他の部分で機能が十分かどうかは不明。

raccでHTML用のテンプレートエンジンを作ったけど、特に問題なしです。

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

>>375
日本語はparserでなくlexerの方の問題では？

lexのもんだいだよな・・・

ttp://www.mainichi-msn.co.jp/shakai/fu/news/20070321k0000e060005000c.html
訃報：Ｊ・バッカスさん８２歳＝コンピューター言語開発者

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

正規表現を状態遷移図に変換するツールalamo。
現在WIN32バイナリのみリリース、
まだシフトJISのみ入力可能。

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

http://capslockabcjp.kitunebi.com/alamo-a.zip

※動作条件としてhttp://www.graphviz.org/が必要

>>381
うお、マジか。ご冥福をお祈りします。

「可愛そうなジョージ、病気になる前まではソートルーチンもちゃんと動いていたのに・・・」

>>384
これなんだっけ!?すげーみたことあるんだけど・・・・

http://news21.2ch.net/test/read.cgi/scienceplus/1174456881/
【訃報】ジョン・バッカス氏　FORTRANを開発

>>384
本物のプログラマおつ

lemonがWindows上ではlemapar.cがカレントにないと動かないので、
調べてみるとlemonのpathsearchという関数がバグっている。
6行程度の修正で直る。

http://capslockabcjp.kitunebi.com/lemon-patch.txt

かわいそうなのはジョージじゃなくてソートルーチンなんだろ。

ジョージかわいいよジョージ

どうしてもMOTHERを連想する

ＭをとったらＯＴＨＥＲ、他人です。

other単体では他人になりません。

another

bother

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

ANTLR

なぜLuaを使わないかの理由が知りたい。

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

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

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

BNFのコンフリクトを解決しやすいツールって何かないですか？

つ-vオプション

つ熟練者の直感

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

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

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

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

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

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

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

もう前任者のはいったん捨てた方がいいかもシレン
ちゃんとしたドキュメントがあるなら別だが

>>406
レオもそう思う

>>403
>でマシン語にしたものを実際のゲーム側で読み込んで使っていました。

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

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

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

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

ちなみにLuaのVMはJITを搭載しているから、他のスクリプト言語と比べてバフォーマンスはだいぶ高い。

>>404-409
返答ありがとうございます。参考になります。

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

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

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

訂正：言語使用　→　言語仕様

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

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

ちうか速度面で劣化があっちゃまずいのならインタープリタじゃアレなんじゃね？
前任者さん版のスクリプトのおぼろげな仕様聞く感じ

>>414
まあ、マシン速度も昔に比べれば比較にならないくらい向上してるし、
どうしても速度的に問題があるなら、、その部分だけゲームエンジン本体に
直接機能追加すればいいから、そんなに問題になることはないんじゃないかな？

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

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

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

>>409
LuaJITってLuaの大本にマージされたの？

>>410
>前任者のスクリプトがCライクな仕様で、社内メンバーがそれに慣れているので

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

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

>>413
>Squirrel
これ知らんかった。Luaもいいけど、これもよさげだね。さんくす。

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

んなこたーねえｗ

>>419
そのスクリプトの仕様を見てみないと
なんとも言えないと思うが？

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

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

ていうか話聞いてるとSystem4.0が思い浮かんでしょうがない

自動でマルチスレッド化、グリッド化
できるコンパイラないの？

Intel C++ Comipilerは？

Cライクなスクリプトと言うと、smallというのもあったねぇ。今はPAWNか。
ttp://www.compuphase.com/pawn/pawn.htm
……どんなのか知らんけど……

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

verilogのパーサがほしくて
cygwin + antlrをインストールした後

http://www.eecs.berkeley.edu/~ahurst/research/verilog_grammar.html
からダウンロードしてみました。 flex とbisonは入れていません。

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

Parsing Verilog file...
... successful!

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

>>426
君は何年生？ （どこの大学？ 専門学校？）
それと与えられた宿題の内容も詳しく教えてくれた方が役に立つアドバイスができそう．

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

社会人

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

まぁ、あまりに青臭い煽りにはつい優しくしてあげたくなることもあるｗ

パーサはパースする物。
サンプルはパースするところまで。

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

>>430
えーと、中身を解釈して構造はこうだったよ！と
吐き出してくれるものってないのでしょうか？

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

>>431
おいおい、今朝教えたパーサの知識を
早速こんな所で御開陳か？

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

>>432
すみませんが、もう煽りにレスはしません

いや、煽ってなどいない。

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

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

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

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

フレームの最中申し訳ないが質問に答えてほしい。
今日、電車の中でふと疑問に思った。

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

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

>>436
実行コード中にインタプリタかコンパイラを持っています

>>436
Lispコンパイラとか言うときってスタンドアロンなバイナリファイルを吐くものでないことが多い気がする

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

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

>>437 >>438
レスありがと。

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

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

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

LexerとParserが分離できるかの問題じゃね？

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

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

サイズの問題さえ気しなけりゃ配布ソフトが字句解析器や構文解析器を備えてようが、
それが分離できるかできないかなんて関係なくない？

つーか対話環境ってそんな大きくなるもんかね？

REPLだけが対話環境とは限らんから、Visual Studioみたいな対話環境が
ついてくるのかも知れないじゃんw

商用利用（ゲームとか）を考えると、ソースや開発環境をまるごと載っけてると
勝手に改変版のプログラムを売られる/配られるのが嫌だ。とかいうのはあるかも。

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

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

>>498
サイズの問題がメインなんだよね。まぁ、いじられたくないアプリなら対話環境の機能は殺したいよね。
JIT みたいなインクリメンタルなコンパイル機能に問題があるのかとガクブルしちまった。すまん。

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

＞スタンドアロンなバイナリ作る機能
それはリンカとかローダとか（名前は何でもいいんだけど）
別のプログラムの役割では

極力ランタイムをmsvcrt.dll直にしてnativeに落とせば2KBぐらいから作れる。
VM上で動くのなら10〜20KBぐらいじゃないかな。
eval相当が必要かどうか。

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

これかな？
LSI C 86

こっちかも
libtcc

tccか… あれはいいものだ。

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

>>454
http://java.sun.com/j2se/1.3/ja/docs/ja/api/java/io/StreamTokenizer.html

間違った
http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/api/java/io/StreamTokenizer.html

>>454
字句解析・構文解析・意味解析のそれぞれの意味の違いを知っていますか？

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

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

>>455-456
流石にそこは真っ先にチェックしてます。

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

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

構文解析抜きじゃ、メトリックを計れないでしょ

意味解析という言葉を持ち出している時点でネタ決定

>>461
教科書的には意味解析という言葉はある。

意味解析抜きじゃ、コードの質を計れないでしょ

すげーな
俺は字句解析と構文解析をわける意味も必要も境目も全く理解できんかった
どう考えても構文解析までやらないとわからんトークンってある気がするっつうか
そうでなくとも構文解析しながらのが略

字句解析した方がプログラムとしてまとまりがあってよい。

いや、構文解析までやんねーと字句に分けらんねーって話なんだけど

cモドキでプリプロセッサとcパートとインラインアセンブラを同時に解釈するような
アホコンパイラを作ったときは字句解析と構文解析が交じり合って酷い目にあったな。

こんなん分けていいことないよね

>>466
言ってる意味わかんない＾＾；

いやだからさー
字句解析って構文になってない
つまり前後をみないで文字単体で判断することになるわけじゃん
これやりにくいぜー

という文法を作るとコンパイルが糞遅い言語が出来上がるわけですな。

文字っつうかトークン？

>>470
どんな文法でもトークンに分けられますよ。
だから、大丈夫です。

いやそれがさ
構文解析までしてみないとトークンとしてわけずらいもんがあるわけよ
できるできないの話じゃなくてな

>>474
どの程度までを構文解析って言ってるのか曖昧

あいまいも糞も一回でもやってみりゃわかるでしょ
わからない人とはお話ししませんｗ

いや、字句解析・構文解析ぐらいやったことあるけど、普通に棲み分けできるぞ？

>>474
> 構文解析までしてみないとトークンとしてわけずらいもんがあるわけよ
> できるできないの話じゃなくてな

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

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

こういう曖昧なのとかか？
決め打ちだと思うけど。

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

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

>>480
あ〜そうか、君はちゃんとした教育を受けてないんだ。
我流だね？

>>479
そういうのもそうだな
あとダブルコーテーションの中身が豪勢なのも俺は嫌いだ
あとなんだったかな
なんかもっと個人的に微妙なんだけど凄く嫌なのあったんだけど忘れたｗ
今度メモってくる
誰か解決策知ってるかもしれんし

改行とかタブとか見えないのが構文に影響を与える言語早く廃れてほしい
パイソンとかもう消えていいよ

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

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

>>483
スペースはいいのかね

Cだとint *pで(3/*p)だとコメントのエラーになる。
構文解析の段階で字句まで処理しちゃうと
組み合わせの爆発的増大がおきるからやらんだろ。

構文まで踏み込まないとわからんトークンがあるから
俺は同時にやっちゃったほうがいいと思うけどね

/と*を別々に扱えば良いだけ。

>>484
3---a

>>451-453
どうもありがとうございます
>>451
それちゃいます
>>452-453
それっぽい気もするけどなんか違う気がしました

自分でも探してみましたが見つかりませんでした
どうもお騒がせしました

空気

>>481 >>481

>>481って馬鹿？

構文解析までしないとトークンに分けられないオレオレ言語の文法ってどんなのよ。
変数名に記号でも使えるのか？

>>493
いえ、彼は大天才です。ただ我々のような凡人には馬鹿にしか見えませんが。

>>484 >>481

LL文法に後からルールを追加する方法無いかな……
オートマトンを弄くるしか無いかな？

>>483
Whitespaceおすすめ

ﾎﾙﾎﾙしてﾃﾞﾝﾊﾟ垂れ流しか

>>488
そしたら / * がコメントの開始になるんじゃね？

>>478
>CやJavaレベルなら、構文解析までしなくても字句解析は普通に 
>出来ると思う。 
>
>どんな文法の言語の話？ 
>例文希望。 

C の typedef で定義された型。

これは確かに「文字列」としては切り出せるが、その後
それがただの識別子であるか typedef された型であるかが
分からないと構文解析はできない
（普通この問題は、構文解析して得た情報を
字句解析側にフィードバックすることで対応している筈）。

3/*p　コメント開始
3/ *p 正しい式

>>501
> 筈

脳内ですね

字句解析では、識別子を認識するだけ。
(変数名, 関数名, 構造体/共用体名, typedef名)

狭義の構文解析では、識別子が文法上正しい位置
に出現している事を認識するだけ。

>>503
まあな。
俺は誰かさんとは違って、
世の中の全てのCコンパイラのソースを
読んだ経験がある訳ではないからな。

俺が悪かった。
チラシの裏の落書きだと思って読み飛ばしてくれ。

(int)("foo", stdout)
はキャストで、
(fputs)("foo", stdout)
は関数呼び出しという問題のことでおｋ？
この場合必要なのは意味解析から構文解析へのフィードバックであって、
字句解析は関係ないような。

より正確に言うと、文法上正しい位置に現れた識別子は、
その文法に従って変数名, 関数名, 構造体/共用体名, typedef名, …
のいずれかの属性が付けられる (仮定される)。

例えば
　a = 3;　// aは変数
　b();　　 // bは関数

変数と仮定した識別子の定義と参照に矛盾がないことを
チェックするのは意味解析フェーズの仕事。

　typedef int integer;　// 定義1：integerはtypedefされた型名
　integer a;　　　　　　　// 定義2：a は integer型変数
　a();　　　　　　　　　　　// 参照：a は 関数名のはずだったが
　　　　　　　　　　　　　　// 　　　　定義2と矛盾している→エラー

>>505
見たこともない話をくどくど言うのはビョーキ

>>506
いったい何処に意味解析の入る余地があるのか全然分からない。

もしかして、"int" という文字列を、
字句解析では int キーワードとして
認識しないつもりなのか？

頭悪すぎ。

intは予約語なので、字句解析レベルで認識可能。
(integer)("foo", stdout)　ならば、
字句解析で integerは(関数戻り値の)型と仮定され、
意味解析で integerの型定義を確認する

× 字句解析
○ 意味解析

(integer)("foo", stdout)　ならば、
字句解析で integerは単なる識別子
　(変数名、関数名、typedef名、・・・)と認識され、
構文解析で (関数戻り値の)型と仮定され、
意味解析で integerの型定義を確認する

>>510-511
ミスは見なかった事にしてあげようｗ

>>489
> >>484
> 3---a

うん。だから、それは
「３」「−−」「−」[a」
の４つのトークンに解析されるから文法エラー。

>>512
まぁ、そのほうが身の為だよ。
（相手が自分で訂正したミスを意識し続ける奴って馬鹿にしか見えないから）

>>509
(XXX)("foo", stdout)という形の式を見たときに、XXXが型名(予約語だけでなくtypedef名も含む)か
そうでないかを判断しないとこれ以上構文解析できない、ということを言いたかった。

>>510-511
何を言ってるかさっぱり分からん。
「(関数戻り値の)型」って何？

>>507
いい加減なことを言うな。
Cに関数名と変数名の構文的区別はない。

式 (XXXX)("foo", stdout) の処理方法

字句解析：　XXXXは、(変数名、関数名、構造体/識別子、typedef名
のいずれかを表す)識別子トークンとして認識される。

構文解析： 式 (XXXX)("foo", stdout)は、
(少なくとも)２種類の解釈ができる。

　解釈1. XXXXが関数名の場合
　　 関数XXXXの呼び出しと解釈する。
　　 XXXX("foo", stdout) と等価。
　 　("foo", stdout) は関数の引数と解釈する必要がある。

　解釈2. XXXXが型名の場合
　　 型XXXXへのキャスティングと解釈する。
　　 ("foo", stdout) は式と解釈する必要がある。

意味解析： 識別子XXXXの定義を調べ、
　構文解析フェーズのどの解釈が適切か判断する。

但し実際のCコンパイラは１パスでこれを処理するので、
構文解析フェーズで式(XXXX)("foo", stdout)を処理する前に、
XXXXは関数名もしくは型名として定義済みでなければならない。
(未定義のまま参照された場合、未定義エラーとなる)

頭が悪いから

字句解析時には識別子の種類 (変数名、関数名、構造体/識別子、typedef名) を判断する必要はない。

>>516
おまえの質疑応答はいつも高飛車だな
バカ丸出し

>>500
字句解析では、「コメントの開始」をトークンとして扱わない

ここはひどい揚足鶏スレですねｗ

>>513
何気に勉強になった

>>516
もっとくやしく

>>521
/* 〜 */ をスキップ、かな。

>>523
> /* 〜 */ をスキップ、かな。
そういうのは構文解析の段階でするんじゃないかな

それなんて言語？

Cって、コメントはプリプロセスの段階で取り除かれるんじゃなかったっけ？

>>497
ｗｗｗ

一ヶ月ぶりに覗いたがなんという成長の無いスレか

トークンの座談会の巻

謎の男「やあ伊藤君！」
伊藤君と呼ばれた女の子「そういう君は佐藤君か！」
佐藤君と呼ばれた男「斎藤君はまだ来ないのか？」
斎藤君と呼ばれたネカマ「俺なら既にいるがな！」
後藤君と名乗るネナベ「…俺をシカトするな！」

>>529
不覚にも吹いた。

>>519
そうすると、構文解析で問題が出る。
例えば変数宣言の箇所で、

a b;

という記述があったとしても、
それが構文上正しいかどうかが分からない。
a が typedef 名ならば正しいが、
そうでないならば構文エラーだろ？

まあ、これを（無理やり）構文解析では ok として、
意味解析に押し付けるという主張もあるようだが、
もし本当にそんな設計をしたら、
まあ、多分グダグダになるだろうな。
だってそれじゃ、構文解析って
実質何の仕事もしてない事になってしまうもの。

・・・まるで、どこかの丸投げ SIer みたいな仕事のやり方だよ。

お前は日本語読解力に大きな問題がある事が判った。

>>531
「構文」エラーを判定するのは「構文」解析の仕事だと思うのだが？

>>533
>「構文」エラーを判定するのは「構文」解析の仕事だと思うのだが？ 
もちろん、そのとおり。

・・・で、一体何処に突っ込んでいるの？

おこちゃまむけせつめい

（１）ていぎぶのしょり１
　　"typedef int a;"
字句解析くん：　　予約語(typedef)、組込み型(int)、識別子(a) ";" ｷﾀー
構文解析さん：　　typedef文ｷﾀﾜｧ・・・組込み型(int)、型識別子(a) って感じ？
意味解析先生：　 型テーブルに登録しときますね。

　　型識別子｜型
　　--------+-------------
　　a　　　　　｜int

（２）ていぎぶのしょり２
　　　a b;
字句解析くん：　　識別子(a)、識別子(b)、";" ｷﾀー
構文解析さん：　 変数宣言みたいな感じぃ？
　　　　　　　　　　　でも 型(a)って定義されてるのかしら
(意味解析先生：　型テーブルを見ればいいのに・・・)
構文解析さん：　 型テーブルに型(a)って書いてあるわね
　　　　　　　　　　　じゃあ答は 型(a)、識別子(b) ね。
意味解析先生：　(よしよし) 変数テーブルに登録しときますね。

　　変数識別子｜型
　　-----------+-------------
　　b　　　　　　　｜a

低レベルな人間の自作自演はいつまでたっても話が解決しないので、ﾁｮｰ笑える

そもそも「意味解析」って、入力データが
"構文的に完全に正しい" という事が判明した「後」の話だろ？

まず、そこら辺の常識、知ってるのか？

糖質か。スルー

意味解析持ち出したアフォに話を合わせといたら、
ついにアフォが自分の掘った穴にはまったなｗ

変数テーブルや型テーブルの管理は、
構文解析の仕事だよ
yaccで言うと、BNFを構成するの
それぞれの構文要素にアクションとして記述する

管理っつか、登録と参照ね

>>539
> 変数テーブルや型テーブルの管理は、
> 構文解析の仕事だよ

「ふつうは」それらは意味解析の仕事だよ
Cなどの言語では構文の都合上本来は意味解析でやるべき
仕事を構文解析でやらざるを得なくなってるだけ
そりゃもちろんyaccのアクションにそれらの仕事を押し込む
ことはできるけど、言語が複雑になればなるほど
そういうことするとメンテナンス性が下がる

それと、亀レスだが構文解析レベルでなければ処理しづらいトークンの
例としては、上でも誰かが挙げてた文字列リテラルの中に式を埋め込める
構文(Rubyの#{...}など)で十分だろう。この場合、字句解析器は埋め込み式の
ネスト構造を認識しなければならないので、字句解析と構文解析を完全に
分離するとうまく対処できない(字句解析では一般的に、正規表現を使って
トークンを表現するため)

字句くん：構ちゃんがいつも相談してもらってる先生って、ホントは構ちゃんの一人二役でしょ？
　ホンモノの意味先生は忙しいから、そんな雑務に付き合うわけないし

構文さん：当たりでーす てへへ

>>539
>変数テーブルや型テーブルの管理は、 
>構文解析の仕事だよ 
>yaccで言うと、BNFを構成するの 
>それぞれの構文要素にアクションとして記述する 

アクションとして記述する部分は構文解析の範疇じゃないだろ？
構文解析と言えば、

・構文的に正しいか否かを判別すること
    yacc で言えば、{ } 内の処理が全くない状態で
    parsing できるか否かを判別すること。

・正しい場合、それがどの構文形式かを一意に特定すること
    >>517
    >構文解析： 式 (XXXX)("foo", stdout)は、 
    >(少なくとも)２種類の解釈ができる。 
    こんなのダメダメ。実質、reduce/reduce conflict だろうが。

だろ？

>>441
ありゃ。スミスさんが来た予感。

> こんなのダメダメ。実質、reduce/reduce conflict だろうが。

それでは正しい解説をどうぞ。
↓

>>534
字句解析に対して構文解析の仕事を要求しているように読解できたんでな。
まあ、漏れの読解力不足かもしらん

> こんなのダメダメ。実質、reduce/reduce conflict だろうが。

それでは正しい解説をどうぞ。
↓

>>537
C言語の場合は実質 >>517, >>535だろ。
それが気に入らないなら、
C言語使うのヤメるか、

　　　　自分でコンパイラ書けばいい。

毎度毎度のお話だが。

>>541
言語内のミニ言語(埋め込みSQL、Cのプリプロ、printfフォーマット等)なら
別の言語エンジンで解析するのがデフォだろ
eval絡みのリテラルなら、言語エンジンを再帰的に適用するとか。

>>547
もしかして、ダメダメだってことが
"本当に" 分かってないの？

BNF による ANSI C の定義なんて、ネット上に
いくらでも転がっているのに？

あのさぁ、素人向け解説にいちいちマジ突っ込みするのって、
それなんて名前の火病？

このスレの惨状、レベルの低さを見てから、
ちゃんと回答を丁寧に示せ。お前の義務だ

> こんなのダメダメ。実質、reduce/reduce conflict だろうが。

それでは正しい解説をどうぞ。
↓

>>550
話もろくにかみ合わない糖質相手にマジんなんな

>>548
>C言語の場合は実質 >>517, >>535だろ。 

じゃあ、
http://www.bookshelf.jp/texi/bison/bison-ja_10.html
とか読む限りでは、GCC なんて異端児だな。

火病だ（ﾌﾟｹﾞﾗ

「gccでは二種類のトークン 識別子 と typedef型名 を扱っており、
　字句解析と構文解析が連携して動作する」

きちっと言えばこれだけの話だろ。
ところでスレの話の本筋は意味解析がうんたらかたらになっちゃっている。
じゃあまず話の筋がおかしいって指摘したらどう？

物事を丁寧に説明できない人種には
あまり関わりたくはないなあ

reduce/reduce conflictを避けたら、
lexical tie-inが必要になっちゃいましたぁ

>>555
こんな時間帯にここに常駐してる人間に
そんなクオリティを求めるのはムリだ

>555
>きちっと言えばこれだけの話だろ。 

それは >>555 の思い込みに過ぎない。
俺が言いたいのは「これが一般的な処理方法だ」という事。

あーうるせー
俺のいない間にスレ進み過ぎだろ
全部読むのに苦労したぜ

結局さ、字句解析と構文解析なんてわざわざ分けるだけ面倒なだけでしょ

俺が週末に趣味で作ってるスクリプト言語が完成するまで
反論は一切許さない
このスレにくるたび最良の方法が目移りしてなかなか作業が進まない罠

年内に公開はもう無理だと思うｗ

> それは >>555 の思い込みに過ぎない。
> 俺が言いたいのは「これが一般的な処理方法だ」という事。

「一般的」・・・これまた脳内でしょ
なんでいつもハッタリかますの？

字句くん： 構ちゃん、俺と結合しようぜ

構文さん： （結婚前はダメ
　　　　　　　　　・・・でも身体が反応しちゃうの)

字句くん： あ”なんか身体に入ってきた・・・♂かよ！

>>548
>eval絡みのリテラル

具体的な例が思い付きません ><
先生、教えて下さい ><

>>560
ググってページ示すのがやっとで
内容理解できない人だからしようがないｗ

キーワード：ダメダメ
発言者：　　ダメダメ業務コンサル

>>560
まあな。 
俺は誰かさんとは違って、 
世の中の全てのCコンパイラのソースを 
読んだ経験がある訳ではないからな。 

俺が悪かった。 
チラシの裏の落書きだと思って読み飛ばしてくれ。 

結局LISPが最強ってことか。

キーワード：ダメダメ
発言者：　　ダメダメ業務コンサル
発言：　　　 まあな。
俺は誰かさんとは違って、
世の中の全てのCコンパイラのソースを
読んだ経験がある訳ではないからな。

俺が悪かった。
チラシの裏の落書きだと思って読み飛ばしてくれ。

Web石碑に登録完了しました

>>567
で、結局、意味解析に任せるのが
「正統派だ」ということでいいのか？

>>548
541だが、俺が例に出した式を埋め込める文字列リテラルというのは、
そのミニ言語がその言語自身なわけで、もう１つ言語エンジンを作るのは
無駄でしょ。しかも、その埋め込まれた式が構文的に間違っていたら
構文解析エラーを出す必要があるから、言語エンジンを再帰的に適用する
なんて方法でもダメ

で、実際はどうするかというと、状態付きLexerにして、ParserからLexerの状態を切り替えるか、
そもそもLexerとParserを分ける必要が無い構文解析アルゴリズム(Packrat Parsingなど)を
使うわけだ

>>568
宗教選択じゃねぇんだから、目的考えて自分で解決しろ。
スミスっぽい方が >>569に来てるから、相談したらどうよ。

>>569
> 構文解析エラーを出す必要があるから、言語エンジンを再帰的に適用する
> なんて方法でもダメ

ダメな理由をｋｗｓｋ

Packrat Parsingで効率良いパーサ書けますって言いたいだけじゃないか、とｗ

Packrat Parsing: Simple, Powerful, Lazy, Linear Time. Bryan Ford. ICFP 2002.
http://pdos.csail.mit.edu/~baford/packrat/icfp02/

で具合はどうよ

> 構文解析エラーを出す必要がある
から
> 言語エンジンを再帰的に適用する
なんて方法もダメ

前段と後段がつながらないね。
エスケープ文字の問題？

エスケープ文字を処理済みの式を
構文チェック・モードの言語エンジン (≒Lexer+Parser)
で再帰的に処理して、構文解析エラーを出せば済む

左再帰を人手で除去するのがめんどい

>>572
すまん。よく考えてみると、言語エンジンを再帰的に
適用する方法で行ける気がしてきた。ただ、その方法は
煩雑になるんじゃないかなあ(特にParser Generator
を使う場合、面倒そうな気が)。

>>571
> Packrat Parsingで効率良いパーサ書けますって言いたいだけじゃないか、とｗ
まあ、半分くらいはそのような意図が無いでもない

> で具合はどうよ
これはどういう意味？

>>531
遅レスだが。

丸投げするような仕事は、
そもそもSIer内部で誰も興味ない
つまらない仕事だから丸投げ＆ﾋﾟﾝﾊﾈするだけだろう

本筋をちゃんと説明せず
関係ない話でお茶を濁すのは
醜いよ

> > で具合はどうよ
> これはどういう意味？

ｪｪｪｴｴｴエエエ
そこでこっちに投げるか?普通
たとえば
・バックトラックやconflictを避けた素直なパーサを書きやすいか
・処理時間がリニアで高速か
とかそんな話じゃなかったっけ

ちゃんと見てないけど

なんでおまいら今日に限ってこんなにスレ消費が速いんだよｗｗｗｗｗｗｗｗｗｗ

>>576
ああ、そういう意味ね。具合はどうかという言葉の意味を
この場合どう取ったらいいかちとわからんかったもので

で、長文になるけど、Packrat Parsingに対するコメントとしては

・複雑な字句構造を持った言語のパーザは非常に書きやすい
・LL(k)やLR(k)と違って、選択される要素の並び順に意味があるので、
そこは注意する必要がある(A / B / CはA / C / Bとは意味が違う)
・単純な字句構造の言語だとかえって書きづらいことがある(空白文字や
コメントの処理も構文解析レベルで処理する必要があるため。ただ、
これは字句解析後のトークン列をPackrat Parsingで解析すればいい
という話もある)
・処理時間はリニアだけどLL(k)やLR(k)アルゴリズムに比べると低速な
ことが多い。ただ、これはナイーブなPackrat Parsingの話で、Parser Generator
を使うこと前提なら、Parser Generatorに色々な最適化を組み込むことはできる
と思う
・アルゴリズムの特性上、構文規則の書き方で性能がかなり変化する
(選択(/)が上から順番にマッチングを行うようになっているため)

e ::= x | n | e + e | e * e
+, *は左結合で、優先度は* > +

みたいな構文はpackrat parserではどう書けるの？

演算子順位文法かよ
そんなん手書きでもできるだろ

>>531-580
おまんまんらめえーまでよんだ

残りもちゃんと読めよ。読み終わるまで夕食抜きな。

おまえら無駄に加速し過ぎる

>>582
おまんまんらめえー
らめなの！そんな太いの入るわけ無いじゃない！
５００ｋバイトのソースファイルなんて私には無理！
い…いや！ひぃー
（ギチギチ）
あ…あたまがおかしくなっちゃうの…
もう駄目…オーバーフローして…しまう
「」さん…ごめん…げふ

>>579
基本的にはLL(k)の場合と同じく、左再帰を除去して、
優先順位ごとに構文規則を作る必要がある。>>579の例だと
こんな感じ
e ::= a ('+' a)*
a ::= p ('*' p)*
p ::= x | n
Packrat ParsingはParsing Expression Grammar(PEG)ベースの
構文解析アルゴリズムだから厳密には
e <- a ('+' a)*
a <- p ('*' p)*
p <- x / n
のようになるけど(<-とか/はPEGで使われる記法)

>585
なるほど。
parseして抽象構文木を作ろうとした時、元の文法だと自然にできるけど（e + eとか）、
packrat版だとやりづらそうだね。

えええええええ？記法が異なるだけじゃん。

彼女がエッチさせてくれません・・・
みなさん、エッチする前はどういう風に切り出していますか？
アドバイスください

なんだ、頭がおかしい人が来てるだけか

>>589
ねえ、なんでそんなに頭が悪いの？

>>586
そうね。
ただ関数クロージャを使えば上手くやれる

キミの話にはいつも具体性がない。
アフォはアフォなりに、隅っこで小さくなってろ。

どんな解釈してるのやら。
基礎が無い奴って話が特異点だらけで萎えるな

おまえら、アンカーつけろよ。
誰が誰に言ってるのかさっぱりわからん。

ネカマ乙

実際にコードにするときはパーサコンビネータやらパーサジェネレータやらを使う訳で、
そのときに左結合の式を解析するための要素が用意されていればいいのだから、
実際にはそれほど問題じゃないかな？

Parsing Expression Grammars: A Recognition-Based Syntactic Foundation
http://pdos.csail.mit.edu/~baford/packrat/popl04/
http://pdos.csail.mit.edu/~baford/packrat/popl04/peg-popl04.pdf

Abstract

For decades we have been using Chomsky's generative system of
grammars, particularly context-free grammars (CFGs) and regular
expressions (REs), to express the syntax of programming languages and
protocols. The power of generative grammars to express ambiguity is
crucial to their original purpose of modelling natural languages, but
this very power makes it unnecessarily difficult both to express and
to parse machine-oriented languages using CFGs. Parsing Expression
Grammars (PEGs) provide an alternative, recognition-based formal
foundation for describing machine-oriented syntax, which solves the
ambiguity problem by not introducing ambiguity in the first
place. Where CFGs express nondeterministic choice between
alternatives, PEGs instead use prioritized choice. PEGs address
frequently felt expressiveness limitations of CFGs and REs,
simplifying syntax definitions and making it unnecessary to separate
their lexical and hierarchical components. A linear-time parser can be
built for any PEG, avoiding both the complexity and fickleness of LR
parsers and the inefficiency of generalized CFG parsing. While PEGs
provide a rich set of operators for constructing grammars, they are
reducible to two minimal recognition schemas developed around 1970,
TS/TDPL and gTS/GTDPL, which are here proven equivalent in effective
recognition power.

>>597
そんな有名論文をいまさら貼って何がしたいんだ？

なんだよ。
>>585-586のつながりがあまりに不自然だったんで、
なんか変な荒しかと目を疑っちまったよ。
(e + e)＝左再帰除去の話ね。了解

発言は幼く、態度は横柄

こりゃとんだ学生さんだなｗ

基礎がないから、何もかもが特殊な話に見えるのだろう。
見ていて恥ずかしくなる。

たぶんここで聞くのがいいか判らないのですが、

自分で正規表現を実装してみようと思ったのですが、BNFみたいな仕様書はどこに
あるのでしょうか？RFCの何千番台目ぐらいですかね？

底抜けのマヌケだと思った。

NFA　ヌンチャク・ファイティング・アーツ

無形無限流ヌンチャク術を武道スポーツとして、
「誰にでも安全かつスマート」に指導しています。
NFAでは男性、女性、大人、子供と全てが活躍中！
また、NFA精神と無形無限流の技法で、
他流派武器術大会にも積極的に参戦中です！
左動画　無形無限流演武　NFA代表　宏樹

>>604
DFA ドラゴン・ファ……
の方が強そうだぞ

>>602
特に仕様書というのはないと思う。
あるのは、PerlやRubyといった各言語ごとの仕様書。
PHPなんて２種類の正規表現が用意されているし。
RFCもないだろうから、好きなように実装すればいいと思うよ。

以上、自問自答でお送りしました

Internet Engineering Task Forceが正規表現の標準を決めるという発想に度肝を抜かれたｗ

POSIXで一応決まってなかったっけ

公開識別子 ISO/IEC 9945-2:1992//NOTATION POSIX Regular Expression Notation//EN は、 POSIX で規定されている正規表現という記法を表します。この公開識別子は ISO/IEC 10744:1997 で使われています。

The Open Group Base Specifications Issue 6
IEEE Std 1003.1, 2004 Edition
9. Regular Expressions
http://www.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap09.html

ちょっと質問です。
C++で動的にルールを変更できるパーザて存在します？
自分でプッシュダウンオートマトン組むしか無いのかな……

>>612
パーサとコンパイラコンパイラを混同して無いか？

シチュエーションをきちんと説明しないあたり、
また意味ありげに素人妄想口走ってるだけだろ。

>>612
「動的にルールを変更」ってのは具体的にはどうしたいの？
こんなルールからこういうルールに変更したい、とか書いとけば
誰か答えてくれるかも…

>>612がきちんと問題定義するまで、
ヒント与えちゃダメだよ >> All

こいつは問題定義を明確にせずに
議論をかき回す常習犯だからｗ

これくらいエスパーしてやれよ
お前ら役立たずだな

ほら来た半島人

掲示板で乱射事件起こしまくりのチョンｗ

あらら、なんかもめてますね。ごめん。

C++で俺言語作っているんだけど、どうせならForthやLispみたいにソース読み込み時の
挙動についても言語内に取り込んで拡張できるようにしたいなぁ、と考えたのが背景。

Lispのリードマクロとか、Forthみたいなスペース区切り必須にしてもいいけど、文脈自由文法に
対応できたらいいなぁ。でも、自分で動的に変更可能なLexer & parser作るのも大変だなぁ。
有り物でどっかないかな……

ということで質問しました。

個人的には字句解析と構文解析は分離していないと困る。
現実的外人の作ったスケルトンの上での文字コードサポートとか考えるとね。

Forthの例は知らないけど、
Lispのリードマクロはプリプロセッサ程度の事しか
やってないんじゃないかな。

文法を動的に変更できる言語というと、
例えばXSD＆XMLが思い浮かぶけど・・・

セマンティックへの対応付けまで考慮すると
Lispみたいに自己記述可能な言語や、
JavaVMみたくByteCodeでセマンティックを記述可能な言語じゃないと
難しいような気もする。

>>621
それぞれの目的に合った方法を選択すれば良いのだと思う。

上の流れは、単に最近話題になっている
PEG(Parsing Expression Grammer)では
Lexer-Parser分離が不要っていいたかっただけなのだと思う。

Caper作った人待ちかな

lemonの問題点：

ケーパーよろしこ。

・衝突に厳しい
・tokenがunionなんでコンストラクタ/デストラクタが掛けない

動的な変更は、ユーザー定義の中置演算子を導入する等を行う方法と
Dylan,Nemerle等のマクロが有名です。

なんか勘違いしてる雰囲気がする

要するに、動的パーサというよりは
マクロ・プロセッサーが欲しいという事？

動的パーサってことは、要するにマクロ・プロセッサー
ってことなんじゃと思って書いきました。勘違いしてたらゴメン。
というか、動的パーサのいい方法あったら、
マクロプロセッサに使えそうなので俺も知りたいです。

>622
Lispのリードマクロは文字の読み込みもできるので、やろうと思えば色んなことができますな。
ここ以上のことはしらんけど。
ttp://user.ecc.u-tokyo.ac.jp/~t50473/onlispjhtml/readMacros.html
こんなネタもあんのか。
ttp://www.geocities.co.jp/SiliconValley-SanJose/7474/cmuclMemo.html#0013

Forthの場合は、各命令(Word)に、ソース読み込み時に実行するかどうかを設定する
Immediate属性というのがあって、これを活用すると色々なリテラルを設定することができる
ようになるらしいです。
マクロみたいなもんだけど、ForthはWordを基本とする言語だから、これで何でもできるようになる
……らしい

まあ、どっちにしろLexer&Perserは自分で組まなきゃいけないね。


> XSD＆XML
「タグを使った入れ子構造」というルールは変更できたっけ？

>628
いや、動的パーザ。
今はboost::spiritで文法を書いているんだけど、これを俺言語から文法を修正・改造できるようにして、
自己拡張的にしたいと考えてます。

やっぱり自分でオートマトンを書き換えるようにするのかなぁ……

長文どかどか書く奴がろくな事を言った試しがない。

> どっちにしろLexer&Perserは自分で組まなきゃいけないね。

Lispはそれはねぇな

> > XSD＆XML
> 「タグを使った入れ子構造」というルールは変更できたっけ？

タグを使った入れ子構造≒構文解析木
という標準的な解釈で、構文木の文法ルールを変更できるだけだよ。
常識ねぇな

>>630
んーと、「動的パーザ」って一般的な言葉なのかな…？
（無知ですまん）

で、６３０が欲しい機能は動的に制御構造を定義できることでいいのかな？
となると、Lispのリードマクロよりもdefmacroとかのほうに近いような…

Lispの場合、すべてがS式だから、リードマクロやdefmacro等で、
制御構造を定義できるけど（パーザはS式が読み込めればいいだけ
なので単純にできる）、C/C++などの系統の言語だと、制御構造を
動的に定義可能にするのはかなりむずい気がする。

最初から、言語の文法を考えるときに動的に拡張できる文法を
考えながらじゃないと無理なんじゃないかな。

LispにしろForthにしろ、もともとの文法が単純だから
制御構造の拡張なども出来るんだと思う。

> 今はboost::spiritで文法を書いているんだけど

それってしょせん再帰下降文法だろ。
文法ノードを一個一個関数で書いてくだけだ。
ならその関数自体をスクリプトで書いて、
下位の文法要素の呼出組み替えられるようにすれば
文法カスタマイズ完成だな。

大した手間じゃねぇ〜じゃん

>>633
変な勘違いすんな。
なんかやりてぇって言ってるのは>>612だ
よく読めスットコドッコイ。

ほんと半島人はガッついてて大変だな

>>631
ほんと長文書く奴来ると、
途端にレベルが低下するんだよな

>>636
長文書くヤツってようは自分の言いたいことも簡潔に
まとめることができない馬鹿だからねぇ、仕方ないよ。

長文書く奴がどうこう以前に、
このスレは一度たりともレベルが高くなったことがないと思うが。

みんなごめんね☆

何か寂しくなっちゃってしってる事ぜんぶまとめて長文で書き込みしちゃいました。

反省したので明日ボウズにしてきます。

（；＿；）

みんなごめんね☆

何か寂しくなっちゃって自分の内的な願望を書き込んじゃいました。

反省したので明日ボウズにしてきます。

（；＿；）

>>638の節穴っぷりにﾜﾛﾀ

そ、それは、凄く核心的。
いわば、コンパイラ・インタプリタで動的に文法変えられるパーサライブラリですね。
リードマクロ発動を含む基本となる文法を定義してあとはインタプリタは知らせればＯＫ
ってあれば、いいなぁ。

再帰下降でちょちょって書いたパーサなら各文法の関数呼び出し部分を
関数ポインタを介して呼び出すようにしておいて、フックできたら、似たようなことできるかなぁ。

あれの動的文法生成インターフェイス、動的解釈テーブル構築エンジンって
他の言語にも使いまわせないのかねぇｗ

>>635
勘違いでしたか。すまん。

>>612とLispのリードマクロがどうも頭の中で結びつかなくて、
変な妄想がはいったみたい。

>>641
お前はいつこのスレでレベルの高さ感じたんだよ。

いってみろ。そうしたら節穴はお前だってことがはっきりするんで。

>>642
ぉぃぉぃ

きみの目も節穴なのか

>>642は>>630のレスです。
書いてるうちにずいぶんスレが進んでた。orz...

>>646
節穴なんですね。。。どうして？節穴なのでしょうか？

理想：comp.lang.compilers
現実：fj.news.usage

646は口が節穴なので、テキトーな口からでまかせが出るだけです。

とりあえず、俺自身の話はおいといて。
このスレにはパーサジェネレータ自分で書くレベルの人と、
なんかForth自慢やLisp知識自慢で満足しちゃえる程度のレベルの人が
混在している事が判った。

おもしろいよキミ達

すずきぃ、おまえやっぱレベル低いわ

スレのレベルが低いのはここにいる全員の責任だ。
みんな、共に精進していこうじゃないか。

レベルの高い人がタマにしか来なくて、
あとは貧民階級ばっかの気がする。(って変なの１人くらいか)

>>651
名言。いや、判っててネタ振りしてるのかと思ってたよ今まで

>>643
そうだね。とりあえずアレが一番の手がかりだ。
早速なかを確認してみるよ

>>652
禿同

LLパーサのカスタマイズ方法すら判らなかったとは傑作だな。
ソース読めてないんじゃないか、と。

LLはN.Worthのデータ＋アルゴリズム・・・のPL/0で学んで、
その後は惰性で書けるようになるのがデフォだ

・・・ってboost::spiritの中の人もそれっぽい事ゆってたｗ

何でこんな荒れているんかね？騙りも出て来たし。これだからIDの無い板は……
GW前なのに５月病かね？
>632 だから文法を弄りたいんだって。
>634 ちょ、オマ……。オートマトンを書き換えるのと手間変わらないんじゃない？
>658 オートマトン組むLL perser generatorてC++であったっけ？ 具体例は？

>633
>「動的パーザ」って一般的な言葉なのかな…？
いいや。そもそも見たことないから質問している訳で……

>defmacro
defmacroは“ソースはS式”という前提があるけど、ここではそういう制限も無しにしたい、と
いうのが背景にあります。

>LispにしろForthにしろ、もともとの文法が単純だから制御構造の拡張なども出来るんだと思う。
まあね。ただ、俺言語の文法＆挙動定義も俺言語から指定できたらなぁ、と思って。
カスタマイズだけでもできるようになると面白いよね。

>642
そうそう、そんな感じ。
最初はForthみたいな文法だけど、その内（文法を上書きして）CなりRubyなりLispなりに
文法が変わっていく感じで。

>644
>635は荒しだから気にすんな。
Lispのリードマクロ = （S式じゃなくて）ソースを解釈する というイメージですな。

どうせ、ワタシャ貧困層の馬鹿ですよ。うえーん(;_;)

LLにせよLRにせよ、与えられた文法規則からLookaheadを計算することによって
解析アルゴリズムの導出が可能になるわけで、動的に文法が変わったらLookahead計算し直し、
あるいはPackratやSyntactic Predicate等、任意長の先読みができるように最初からしておくとかしか無いわな。

>>660って、もしかしてblogにASTの事書いてた人かな。

>662
簡単にするんだったら
・受理状態じゃないと文法書き換え不可
・その時のLookaheadはステ
あたりかな？

>663 違う、違う。誰と間違えているのか知らないけど、おいらじゃないよ。

あやしい…

>>660 >>662
お、なんか核心突けそうな人が来たー


>>660
>>634否定して、>>642持ち上げるって事は、
「Forthライクになんとかしたい」って結論で固まってるのかな。
意図が判らない。

あと、>>612を読んで
caperの「動的文法生成インターフェイス、動的解釈テーブル構築エンジン」
ってのを改造できればいいのかな？と考えた。

なんか意図がつかみにくいスレだな

(プッシュダウン)オートマトンだから
Forthマンセーって所か。

LALRパーサならプッシュダウンオートマトン使ってなかったっけ？
(すげぇ不安になってきた・・・)

>662
……良く考えたら、そんな簡単な話じゃないな。
少なくとも、最上位のルールが受理状態でないとダメですな──うわ、かなり限定的だなぁ
Lookaheadを捨てるだけでも何とかなりそうな気がするけど、どういう挙動になるか判らない……

>>660
騙るつもりはなかったんだが、
スレ番読み間違えたようだ
その件はスマン。他には騙りなどしていないよーん

>>668
PDA（Push-down automaton）はただの概念上の、入力テープ上を逆戻りできなくて、テープを書き換えることもできないけど、スタックのついたチューリング機械。
LLはPDAのLeftmost derivationの順方向を、LRはPDAのRightmost derivationの逆方向をそれぞれシミュレートするアルゴリズム。
LALRはLRの改良版。

>>669
文法を途中で書き換えるっていうんじゃ、その度に構文解析表なりなんなりをまるごと構築しなおさないと。
少なくともPDAってのは静的な生成規則に基づいた機械だから、別の方法を使うなら、もはやPDAではないものになるんじゃないかと。
つーか、受理状態のときのみどうのこうのってのは、あんま意味がわからんが、いわゆるトップレベルでのみ文法操作が可能ってこと？

これって一種のリフレクションとも言えるよね。
オブジェクトレベル（解釈されるもの）であるソース文字列がメタレベル（解釈するもの）であるパーサの
解釈の仕方を動的に変更するという点で。
こういうシステムを作るときは、オブジェクトとメタの切り分けと、メタへのインタフェースをきっちり定義しないと
ドツボにはまるだけ。
問題は、まだ構文木にもなっていない解析前の文字列が、パーサを変更できるほどの表現力を持てるかどうかだ。

うん、それは判ってる(はず(汗))

あなたが仰るとおり、>>669が何故PDAに拘るのか、
それがよく判らないだけだ(はず(汗))

うーん、言語処理系に対するイメージってのは
人それぞれなんだなぁ。もっと人の発言を大切にしなきゃ(荒しは除外)

>>672
リードマクロ関数の書き換え程度の小さな文法変更ならともかく、
大規模な文法変更ってのは、あんま段階的にやるような類の話じゃないんじゃないかな。
カエルの変態じゃあるまいし。

コンパイラの世代みたいな感じで、
最初は核(つーか初期値)となるパーサで文法変更関数読んで、
構文木かVMコード内部に溜め込んで、
その関数実行したらどーんと文法変わるという
サナギ方式が使いやすいとｵﾓﾀ

>>671
> PDA（Push-down automaton）はただの概念上の、入力テープ上を逆戻りできなくて、
> テープを書き換えることもできないけど、スタックのついたチューリング機械。

逆戻りも書き換えもできるだろ。

>667 >>634否定して、>>642持ち上げるって事は、
いや、否定してないよ。LLぐらいはサポートしたいから、最後の手段としては考えているけど……

>caperの「動的文法生成インターフェイス、動的解釈テーブル構築エンジン」

今から作るとしたら、caperをベースにするのが分かり易そうですな。
caperカスタマイズしてPDA吐き出すようにして、ルール変わるたんびに再構築
といった感じかな……さすがに遅そう……
それとも複数文法持てるようにして、切り替え命令で文法を切り替えるようにするとか。
>674の指摘している方法もいいね。

>671 その度に構文解析表なりなんなりをまるごと構築しなおさないと。
やっぱりそうだよな……既にあるオートマトンにくっ付けるだけじゃダメそうだよね……
>もはやPDAではないもの
PDAを元にオートマトンを書き換えるのならば、それはもうTMだよね。
ちなみに、PDAはTMじゃ無いよ。TM相当は2スタックマシンね。

>受理状態のときのみどうのこう
受理していない場合は受理しない可能性が残っているから、受理していない情報を元に
オートマトンを組み換えるのは不味いよね。
決定性PDAなら単にエラーになるだけだけど、非決定性PDAだと他の受理状態の可能性が
あるからね（バックトレースが発生して書き換え自体がキャンセルされる）

>672
>ドツボにはまるだけ
それはそうだね。ただ、趣味の俺言語なんで、馬鹿みたいな柔軟性を用意してみようかと……

>パーサを変更できるほどの表現力を持てるかどうかだ。
ここはForthみたいにImmediate属性を導入するという手もあるね。
そもそもコアの部分はソースを読み込む前に使用可能になっているから、そこから
組み上げていくのが良さそう。

>675 逆戻りも書き換えもできるだろ。
できないよ。できるとしたらTMか2スタックマシンのどっちかだね。

じゃ、そろそろ寝ます
ﾉｼ

>>675
堂々と嘘つくでねぇ。
思わず本棚から言語理論の本引っ張り出してきちまったよ。

あいすんませんね

後でチェックし直しときます

動的な文法とやらを文脈依存文法で定義してみたらどうだろう？とか言ってみたりして

と思ったけど、構文解析がPSPACE完全になっちまうか
なんか制限つけたら軽くなるのかな？

なんかGW中の勉強にとLLパーサ(BNF?)自前で作りたいんだけど
何かいい課題になる題材ないでしょうか？

>>682
ttp://www.kmonos.net/alang/d/lex.html

LISP最強

Lispパーサなんか作ってもたいした勉強にならんだろ

スレのレベルが急速に低下しました・・・

「このスレは一度たりともレベルが高くなったことがない」
とか思ってる人が暴れてるだけだろ
スルーしておけ

人の所為にすんなボケｗ

しょうがないよ、現実を歪めてまで
お前のせいではないと主張する理由が無いものｗ

↑全部こいつの妄想か。

孤軍奮闘ｗ

なんかしらんけど、俺が言いたかったのはこういうことでした。
var exp = function() {
var m;
if(m=str.match(/^[0-9]+/)) {
str = str.substring(m[0].length);
return m[0];
}
throw "error";
};
parse("1+2");
で１が戻るようなもので
var fact = exp;
exp = function() {
var c = fact(); var m;
while(m = str.match(/^\+/)|| m =str.match(/^\-/)) {
str = str.substring(m[0].length);
c = [m[0],c,fact()];
}
return c;
};
alert(parse("1+2"));
で、["+",1,2]がかえるように出来るというかんじ。
http://f38.aaa.livedoor.jp/~sakurai/cexp/aaa.html
実際動くのはこんな感じ。

何を言いたいの君は？
相変わらず話題とずれてるな

再帰下降パーサがやっと理解できました、
と言うだけの話なら「よく頑張りましたね」って
ポジティブな方向に持ってけるんだけど、


おまえの場合スレ荒しまわって「このスレレベル低い」
までほざいた挙句に、いけしゃーしゃーと初心者発言開始するから
嫌われるんだよ。
いい加減にしとけクズ

目の前の人間と仮想敵をごっちゃにして
わけのわからない呪文みたいな罵倒する奴増えたなぁ。

まあいいんじゃない？そんな仮想敵にムキにならなくても

このスレの現実は
匿名なら何やってもいいと思っている身元バレバレの性格破綻者も居れば、
このスレのお陰で再帰下降パーサ書けるようになった>>626も居るって事。

メデタシメデタシ

なんだ。桜井さんが来てたのか。

「このスレはレベルが低い」って言ってる人は、
本音としては「お前らレベル高すぎるから、もっと優しくしてくれ」と泣き言を言っているだけだろう。

素直にそう言えばいくらでも対処してくれる人が居るだろうに、
いちいち相手を高飛車に叩いて初心者質問を繰り返すから敬遠されるわけだが

どっちかというと、スレのレベルが低くなったとか言うアホが問題。

ねぇMatz、信仰者にもいろいろなタイプが居るんだね。

なんでmatzが出てきたの？

国内でも最高レベルの技術的知名度を持つ信仰者と
人間として最低レベルの信仰者が同じスレに存在する不思議さ

それが２ちゃんねる

モデレーターがいて肩書き出す、そういう場でなくて
2ちゃんでなければならぬ理由は
直接民主制への夢を棄てるべきではないから。
2ちゃんでなければ意味がない。

そういう話は別の板でやってくれ。
お前の話はいつもズレズレなんだ

>>703
はっきり言っておまえ統合失調症だろ。
お前の会話や文章の支離滅裂さは
見ていて頭が痛くなる

>680
それLBAじゃないと解釈できない……つうか万能TM作っているようなもんじゃない？
そもそも有効な記法てあったっけ？

>>693
再帰下降の出来上がったパーサを拡張するのに、
こういう風にやったらいいんでないってことの具体例を書いたのだけど。

>>694
ん？「このスレレベル低い」なんていったことないですよ。
凄いレベル高い人達が多くて、いつも怒られてると思ってたんですけど。

ほんとは、caperみたいなものが作れたらいいなぁ思ってるけど
作れないしわからないので、理解できる範囲で書いたのだけども。

匿名掲示板は知らないこと聞くにはありがいですが。
でも、それ以外は辛いことが多いですねぇ。
俺は、躁鬱病で統合失調障かも知れないとこまでいってしまってたり、
統合失調症で苦しんでる人もしってるから、辛い。
まぁ、２ｃｈ用語だから、ジョークなんだろうけど。
ちょうどいい、匿名でないコンパイラのこと話せる掲示板ってないのかなぁと
思う今日この頃ですよ。

この違和感はいったい何なんだろう。
例えるなら……そう、一人だけ全然違うこと喋ってるみたいな。

荒らしているのが一人だけというのがよくわかった

やったね！

>707
再帰の関数をクロージャかオブジェクトにしてプラガプルにするのが王道じゃない？
突き詰めるとboost::spiritのオブジェクト版になると思うけど……

要するに、彼はようやく再帰下降パーサとは何か理解できたって事だ

>>711
すでに、そういう概念あるんですね。
プラガプルって言う概念はググっても出てこないのでよくわからないんですけど。
ちゃんと話についていけるようになりたくて、ドラゴンブックみても、わからん。
鬱出し脳な、今日この頃です。笑

plug ableってことで、挿入可能みたいなかんじですかね。

いいから貴方達はRats!(ttp://www.cs.nyu.edu/rgrimm/xtc/rats.html)を見てから
出直してきたまえ。

またリンク貼るだけのお前か。
何を主張したいのか、簡潔に要約しろ。

とても興味深いね。
ここでやっていたようなお話を
Robert Grimm氏がxtc(eXTensible C)として
研究している、という事か。
Rats!に関してはどうよ？

>>716
「ちゃんと書かれていることはわかるけど、まだ自分には理解できない」
ページを持ってきて、自分もまたそのレベルにあるように見せるのはよくあることです。

初歩的な質問ですみません

文法G=（P,S）
　　　P={S→（L）|a
　　　　　L→L,S|S}

これの終端記号って、”,”も含まれるんですか？

>>719
含まれる

>>720
ありがとうございます。

もう一つ

文法G=(P,S)
P={S→AB
　　A→aAb|b
　　B→bBc|ε　}
の言語はどんなものか。

という問題なんですが、どう答えたらいいんでしょうか･･･問題の意味がよく分かりません

>>722
文字abcがどんな風にならんだ文法か、ってことじゃないかな…
ヒントだしすぎ？

言われてみれば、実に微妙な表現だなぁ……ｗ

ごめんあんまり見てなかった。

動的なルールだけど、
caperは実際に起動時に動的なルール構築を行って
読み込みファイルの文法を定義しているので、
そのソース使いまわせばできるよ。
一応caperとは独立したものとして作ったので、
普通に切り出せると思う(確かlalr.hppとgrammar.hppだけあればよかったような)。
実際の文法定義例はcaper_cpg.[hc]ppのmaker_cpg_parser。

ただ文法定義のインターフェイスが
自分でもよく間違うようなあまりよくないものなので、
ちと工夫しないとまずいかも。

あと内部でSTLバリバリ使ってるので、それも注意。

>>723
つまりこの問題だと
a,b,cがこの順に複数個ずつ並んだ文　って感じでいいんですかね･･･
言語はどんなものってどういう問題なんだ(´・ω・｀)

>>726
> 言語はどんなものってどういう問題なんだ(´・ω・｀)

求められているのは、文法表記からどのような文法になってるのかを
読み取る能力。

この問題だと単に文字abcの並びでしかないが、このabcが
また別の文法ルールだとしたらどうだろう？
そしてその文法ルールには、さらに別の文法ルールが…
ってな感じでどんどん複雑な文法に接するようになると思うけど
今はまだはじめたばかりだろうから、焦らずじっくり取り組むといいと思う。

追記。

最初から、if文や算術演算なんかの文法を教えるよりも
文字の並びという単純なところから教えるほうが
「if文とはなにか」「+-*/の演算の意味」なんかを
教えなくてもいいという利点があるのかな。たぶん。

すでになんらかの言語でプログラムしたことのある人にとっては
かえって意味不明に感じるかも知れないけどね…

>>722
>>726
文字aがn回連続して並ぶというのをa^nと仮に表記するとして、
a^m b^(m + n + 1) c^n (m >= 0, n>= 0)
という条件を満たす言語。a,b,cが順に複数個並んだ文、だけだと条件が
不足してる

packrat parsingってLALR(1)と具体訂にどんな違いがあるの？

>>727
焦らずじっくりだと間に合わなかったりしてｗ

>>730
complexity

“Stop the World”を防ぐコンカレントGCとは？ (1/2) - ＠IT
http://www.atmarkit.co.jp/fjava/rensai4/troublehacks02/troublehacks02_1.html

だいぶ今更な記事だな...

パーサー書くときのコーディングのテクニックが掲載された書籍は存在するのでしょうか。

今年ってコンパイラに関係する本って出版される予定ないんだな...

C/C++のプリプロセッサの構文やマクロ展開アルゴリズムが載ったページや本とかないでしょうか？
あとVCとGCCで使えるマクロの違いが分かるものも探しています。

たとえば、↓のマクロはGCCでは使えて、VCでは使えません。
　#define MSG(format, param...) printf(format, param);
こんなのが分かるものを探しています。

>>737
>C/C++のプリプロセッサの構文やマクロ展開アルゴリズムが載ったページや本とかないでしょうか？
http://gcc.gnu.org/onlinedocs/cpp/
このへん？

>あとVCとGCCで使えるマクロの違いが分かるものも探しています。
処理系固有の拡張は処理系のマニュアルに載っているはず。

それから、スレ違いじゃないか？

Cのプリプロセッサ作りたいなら、このスレでもいいのでは？
コーディングのテクニック載ってる本あったら買うだろうなぁ。

誰かの自作自演が始まると、
ガクッとレベルが低下するな
このスレ

同意

まったくだ

仰る通り

>740はいつも正しいな

>>737
最近プログラミング始めたとかだとその辺
情報足りてないよね…

Cプリプロセッサ・パワー―C言語の秘められた能力を解き放つ(1988年発行)
http://www.pro.or.jp/~fuji/mybooks/cdiag/appendix.b.html
>マクロについて勉強したければ、標準のヘッダーファイルとか、
>ウィンドシステムなどのヘッダーファイルなどに豊富な例があるので、
>そちらを参考にした方が、はるかにためになるでしょう。

というか日本には20年前に出版されたのしかないのね…orz
ソース嫁。もしくはググれ。20年前にはググれなかったわけだし。

プリプロセッサとは - はてなダイアリー
http://d.hatena.ne.jp/keyword/%A5%D7%A5%EA%A5%D7%A5%ED%A5%BB%A5%C3%A5%B5

この辺からマクロっぽいことやってるのを追いかけてみるのも
有効かもね。

alias, エリアス, スクリプト言語とかやってることまんま
マクロっぽい気がする。微妙にスレ稚貝っぽいのでsage。

>>736
書籍の価値って何なんだろうね。出版されるのは入門書ばっかりだよね。
どうでもいいけど。
>速効! Pythonプログラミング バージョン2.5対応
>http://www.shuwasystem.co.jp/cgi-bin/contents.cgi?isbn=978-4-7980-1641-2&cbook=9784798016412

プリプロセッサのプログラミング解説と言えばカーニハンが書いた有名な本があるだろ…

>>746
マクロ カーニハン で 検索
http://d.hatena.ne.jp/Back/20060219
http://www5a.biglobe.ne.jp/~wired/life2000.htm
http://www.coara.or.jp/~tkuri/D/002.htm#D2002-05-05
http://www.pro.or.jp/~fuji/mybooks/cdiag/cdiag.8.3.html

ありが�d。なんか基本中の基本みたいでした
これだからゆとりは orz

言うまでも無い事だが、マクロ・プロセッサーのソースが載っているカーニハンの本と言えば
「ソフトウェア作法」　http://www.amazon.co.jp/gp/search?index=blended&field-keywords=%E3%82%BD%E3%83%95%E3%83%88%E3%82%A6%E3%82%A7%E3%82%A2%E4%BD%9C%E6%B3%95&__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&linkCode=qs
の方だｗ

記述言語＆ターゲット言語はFORTRAN

×マクロプロセッサ
○プリプロセッサ

ｗｗｗ

いろいろと情報ありがとうございます。
C言語の仕様に則したプリプロセッサを作ろうと考えているのですが、
738のPredefined macroとかを見てると完全準拠は難しそうですね・・・
とりあえずたくさんのソースをパースしてみて
１つ１つクリアしていこうかと思います。

>>746
カーニハンの名著って「プログラミング言語C」でしょうか？
同じカーニハンの「プログラミング作法」では関数マクロは使うなみたいなことが
書いてあるらしい(Amazonより)のでプリプロセッサが嫌いなのかと思いました。

>>750
> 同じカーニハンの「プログラミング作法」では関数マクロは使うなみたいなことが
> 書いてあるらしい(Amazonより)のでプリプロセッサが嫌いなのかと思いました。

「プログラミング作法」のほうだと思う。
ただし、「プログラミング作法」に載ってるのはFortran用の
プリプロセッサーの話。
Cのプリプロセッサーではないので注意。

プログラミング作法 第1章「スタイル」関数マクロはなるべく使うな etc
http://www.ascii.co.jp/books/books/detail/4-7561-3649-4.shtml (2000/11)
　↑
プログラム書法 (プログラミング作法の前版 記述言語は Fortran,PL1)
http://d.hatena.ne.jp/asin/4320020855/chikuwadiary-22 (1982/06)
プログラム書法　メモ
http://www.6809.net/tenk/html/prog/syoho_ki.htm
　↑
ソフトウェア作法 使用言語 は RatFor (1981年)
Ratfor - Wikipedia
http://ja.wikipedia.org/wiki/Ratfor

発刊された年順に並べるとsoft作法->prog書法->prog作法

soft作法(Fortran) -> orz
prog書法(Fortran,PL1) -> prog作法(C)

あれっ、soft作法はアップトゥデートされてなwwwww

こんなかんじですた　(調べるのめんどい)

自己フォロー。 boost::spirit v1.8 にstored_parserなんていうのがありました。
正しく求めていたのですな。こんなことができました。ソースコードベタはり

#include <iostream>
#include <conio.h>
#include <boost/spirit.hpp>
#include <boost/spirit/dynamic.hpp>
#include "main.hpp"
using namespace boost::spirit;

template<typename ScannerT>
class TSetToken {
public:
   TSetToken(boost::spirit::stored_rule<ScannerT>& target) : target_(target) {}
   void operator()(const char* begin, const char* end) const {
      target_
         =  target_.copy()
         | str_p(begin, end)
         ;
   };
private:
   boost::spirit::stored_rule<ScannerT>& target_;
};

おっと、誤）stored_parser 正)stored_ruleですな。

struct TProgramGrammar : public grammar<TProgramGrammar> {
   template <typename ScannerT>
   struct definition {
      boost::spirit::stored_rule<ScannerT> program, block;
      definition(TProgramGrammar const& self) {
         program
            =  +block
            ;
         block
            =  '(' >> (+alpha_p)[TSetToken<ScannerT>(block)] >> ')'
            ;
      };
      const stored_rule<ScannerT>& start() const { return program; }
   };
};

int main() {
   {
      TProgramGrammar p;
      std::cout << parse("a", p, space_p).full << std::endl; // false
   } {
      TProgramGrammar p;
      std::cout << parse("(a) a", p, space_p).full << std::endl; // true
   }
   std::cout << "Press any key" << std::endl;
   getchar();
   return 0;
}

>>736
Rubyの青木さんが「ふつうのコンパイラ」という本を昨年から書いているらしいよ
進捗はどうなってるのか知らんが

ドラゴンブックで十分

蛇足ですけど、>>745いい加減にしてくれ
答は>>748-749だよ。このスレって答出しても
知ったかぶった奴が答を曖昧にしがちだな

答が判ってない癖に自作自演する奴が
いつもスレを滅茶苦茶にするのだと思う

答えはわかってるが、素人に説明するのが面倒くさい

結論：プリプロセッサの作成方法が載っているカーニハンが書いた本は「ソフトウェアツール」。

>>737
趣味でCプリプロセッサを書いたことがあるが、規格を読みながらそのまま
実装していけば問題はないと思う。唯一迷うところがあるとすれば、マクロ展開によって
生成されたトークン列をどう扱うかの問題だけど、これは
「後続のトークン列の前に割り込ませる」(つまり入力ストリームに押し戻す)方法が
一番楽だと思う。(むしろ、この方法でないと正しい挙動をさせるのが難しい)

それから、標準準拠を目指すなら、
http://mcpp.sourceforge.net/index-jp.html
mcpp -- a portable C preprocessor
に付属しているテストケースが非常に便利。

> 生成されたトークン列をどう扱うかの問題だけど、これは
> 「後続のトークン列の前に割り込ませる」(つまり入力ストリームに押し戻す)方法が
> 一番楽だと思う。(むしろ、この方法でないと正しい挙動をさせるのが難しい)

要するにそれって、プリプロセッサ処理を、言語本体の構文解析と同時にやるって話に聞こえますね

脳内なんじゃないの

というかマクロの多重展開の話か

>>762
なんでそうなるか良く分からん。単体として動作するプリプロセッサの話をしていたつもりだったんだが。

>>764
そう。特に、
#define A B(
#define B(x) [x]
A 4) /* => [4] */
みたいな変則的なマクロを処理するときに困らない。

俺はマクローリン展開ならできるぞ

NFAとかDNFをちょっと正しいか検証したいときってみんなどうしてますか？

つ 「大量のテスト」
適当なテストサンプルってあったっけ？

はぁ？状態遷移が決定的か非決定的か、なんて
文法見りゃ判るじゃん。

さあ、いつもの早合点くんが来ました

>767
そういや、DFAの間違いだよな >DNF

DFAの間違いなのかBNFの間違いなのか10分ほど悩んだ

オートマトンじゃないじゃない >BNF

BNFといえば逆張り

>>767
Emacs の re-builder とか。
テスト対象（ソースコード等）のバッファで ESC x re-builder RET
正規表現を書き込むと、逐次的にマッチする文字列がハイライトされる。

左隅解析ってなんすか？

boostでxbyakみたいなのありませんかね

状態遷移図をドローするツールって何かよさげなのないですか？

>>778 graphvizに同梱されてるツールの適当なやつでどうよ
もしかして，手描き？

アセンブラ？
環境依存はBoostの範疇外じゃね？

>>779
graphvizにそんなツールがあったのか。毎回めんでーなーふぅ
とか思いつつ、スクリプトでカタカタ書いてたよ。

スクリプトで書けるなら、そのスクリプトを生成するスクリプトを書けばいいじゃんと思った。

>>781 つーか普通のdotの例にこんなのがあった
ttp://www.graphviz.org/Gallery.php
ttp://www.graphviz.org/Gallery/directed/fsm.html

＃ いつの間にgraphviz.orgなんてドメインを取ってたんだろ

そろそろ構文解析専用スレたててもよさげ。

いらない。人いないのにスレ分けてどうするよ。

人はこの板にしては十分いるんじゃないの。

・質問のほとんどは構文解析かそれ以前
・よく荒れる

分離したらスレはもっとまったり穏やかに進むのではないかと思う。
ただいかんせんこのスレの名前が厨房ホイホイのようなものなので
逆にバックエンドを分離した方が幸せになるんじゃない。

>>786
そうは思わない。

＝＝＝　終了　＝＝＝

何が終了したのかわからないが>>787の2ch依存の件であろうか
ならばめでたい

ここに俺の亀頭落ちてなかった？
おかしいなー、昨日買い換えたばっかりなのに・・・

>>788
要するに786が馬鹿すぎるから
この話はもうやめようねってことでしょうね(^_^;

もういっちょう自己フォロー。
boost::spiritって、pull parser化できないんだね……継続使えない……

ということでプルパーザのプロトタイプを作って見ました。
ttp://cvs.sourceforge.jp/cgi-bin/viewcvs.cgi/siki/siki/src/PullParser/PullParser.hpp?view=markup
こんな感じで使います。
ttp://cvs.sourceforge.jp/cgi-bin/viewcvs.cgi/siki/siki/src/test/PullParser/test_PullParser.cpp?view=markup

まだUnionとSequence、string matchしか実装していないけどね。
boost::spiritを参考にもうちょっと練り込もうかな。

>>791
がんばって作らなくていいから設計書あげてくれない？
たぶんそのほうがいいもの湧いてくるよ

>>792
みもふたもないクレクレくんだとおもった

>792
いや……普通にPDA作っているだけだけど……。
イプシロンをバックトラッキングで実装しているので、機械越しに成功／失敗のパラメータを
渡しているけど、大した話じゃないよ。

実質250行ぐらいしかないんだから読め。
しょせんプロトタイプだし、設計書なんて作る方がタルいわ。

ふと思ったんだが、PDA知らないなんてこと無いよな？ >792

自慢じゃないがしらないっすよ

俺GW坊とかいうレベルじゃねーほどDQN出汁

俺にもわかりやすーく教えてくれよなぁなぁ？褒めれば延びる子なんだぜ

段階を踏んでステップアップしてきなはれ

継続の注入は闘魂注入とどう違うんだ？

>796
そうすると >791を理解するのに色々と足りないな。

まずは
ttp://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3
あたりを一通りかね？　その後は「オートマトン 言語理論 計算論 I」を読んでみなはれ
その後にDFA、NFAを組んでみるのも良いかも。

>>791
それくらい解かるもんﾌﾞｩｯｩｩ

カーソル型のAPIでパースしたいから継続使って状態をオブジェクト化するって
ことだよね？SAXのパーサとかそんな感じだよね。

>800
いや、boost::spiritだとパーザが継続待っている状態に夏ちまうんだけど、それだと俺言語の継続を
実装する上で色々と都合が悪いんだよね。なんで、プルパーザ化してステップ実行するようにしています。

SAXってイベント駆動じゃなかったっけ？ StAXつうのがプルパーザみたい。

>>786
>・質問のほとんどは構文解析かそれ以前
ツリー作った後なんてほとんど問題なんておきないじゃん

C++の構文解析がむずかしいでぅ

>>803
具体的にどんな構文でつまってるのか書いてみたら？

生垣FSMって普通のFSMとどのように違うのですか？

あのー継続をCかC++で実装してみたいのですがぁ
参向になるソースなど知りませんでしょうか？

ttp://www.google.com/codesearch?hl=ja&q=show:PvXHA4oqtzo:Rm5ilgV7xog:AJXFALhq-6o&sa=N&ct=rd&cs_p=http://svn.gna.org/daily/etoile-snapshot.tar.gz&cs_f=etoile/Etoile/Languages/Io/IoVM/base/Coro.c
継続じゃないけど、Io のコルーチンの実装。

>806
つ Schemeの実装におけるスタックフレーム(Draft)
ttp://www.shiro.dreamhost.com/scheme/stack-j.html
ヒントにはなると思う。

>>806
libcont

Scheme: A Interpreter for Extended Lambda Calculus
ttp://www.brics.dk/~hosc/local/HOSC-11-4-pp405-439.pdf

Cでの実装じゃないけど
単純なんで理解しやすいんじゃないかな

>>809
libcontなんか変なasmで書かれていてキモイのですが...

おまいら化粧水何使ってる？

愛液

エストのコンディショニングローションIII。
十分潤って、自分の肌には合ってるみたい。

誤爆でした

ム板に女が居るということか？

居て悪いか

Continuation based C： C言語とアセンブラの中間に位置するプログラム言語。
C 言語との互換性を持つ　1pathのtiny compilerです。
現在は、i386, PowerPC, MIPS, ARM 用の出力を出します。
科学技術振興機構「機能と構成」のプロジェクトの一部でした。

http://sourceforge.jp/projects/cbc/

>>818
「スタック不要になるけど、GCが必須」という説明に吹いた覚えがある

>>818
中に人に聞こえないぐらいの距離(50m)ぐらいで
デラワロスって指さして笑ったことある。

まいど。
結局、状態のコピーに対応するため>791を作り直しました。
……どうも車輪の再発明している気がしてならんな。
どっかに途中経過をコピー可能／オートマトンを再構築可能なプルパーザ無いのかしらん……

つ「手書きパーサ」

やってられっか〜〜〜　>822
第一俺言語から弄れないだろ……

>>823
あんたに、何か新しいソフトウェアを作る資質は無い。

自分に使いやすい車輪は自分で作るしかないべさ
都合のいい車輪がそうそう転がってるわけがない

一方>827はホバークラフトを作った

え、オレ？(´д｀;)

じゃあ俺ファイアースティングレイね。

わたし歩く

質疑応答が自作自演ぽく自己完結しちゃうから
一体何をやりたくて悩んでいるのか謎。

バックトラックが必要な文法を
再帰下降パーサで無理矢理処理しようとするから
継続が必要とか無茶な話になってるのとちゃうか？

継続ベースのスクリプト言語で、
文法を動的に変更可能にしたい
　↓
pull parserが必要

って事か？

その通り。 >831
他になんか良い実現方法ある？

一体何をしたくてboost::spiritをいじっているのか、
なんでpull parserが必要と結論したのか、
全く以って意味不明。

パーサの状態を記録/復元可能にしたいなら、
再帰下降ではなく、状態管理可能な状態遷移マシンを用意して
その上で入力、遷移状態、出力を記録してけばいいだけだろ。

>>833
同意、
いずれにせよ、自動的なエラーリカバリーを入れないのであれば
ここで大騒ぎするほどのプログラムでもないと思うけどね。

>833
欲しいのは>821で、理由は>831ですな。
boost::spiritはセマンティックアクションを実行するときにパーザが継続を待っている状態に
なっちゃうので、パース俺言語の処理を中心にしようとすると何かと不便です。
＃場合によってはパース途中で強制的に終了することもあるけれど、spiritでは対応できません

>状態管理可能な状態遷移マシンを〜〜
そういうプルパーザのコンパイラコンパイラライブラリあるなら是非とも紹介してクレクレ。
>791みたいなクソ面倒臭いのを作り込まなくて済むんだったら助かるよ。

うお、編集ミスった……失礼。
×パース　 　 　 俺言語の処理を中心にしようとすると何かと不便です。
○パースではなく俺言語の処理を中心にしようとすると何かと不便です。

とりあえず説明する気がないのはよく判ったから
スルーさせてもらうわ。

ええええ？？そんなに判らん？ >831あたりは判っていそうだけどな。
継続とかの概念が判っていればすぐ理解できそうな気がするけど……

スルーもいいけど、せっかくだからなんかパーザ作成ライブラリを紹介してくれよ。

相手したら後付の条件が山ほど出てきそうだな

ん？ライブラリの条件？
>791みたいなやつで、もっと実績とか機能とかがあるやつだけど。
＃設計がマトモなら言う事ない。
・パース途中の経過をコピー可能
・パース途中で文法を変更可能
　（オートマトンのグラフを変更するとか）
・プルパーザ
・C or C++
ですな。

>>840
そこまでわかってて見つからないなら無いってこった。

自分でパーサ組め、って結論

>841-842
結局そこか！ ギャース！！

「ふつうのコンパイラ」が出るらしいですね。
Javaで、C似な言語をつくるんだそうで、対象プラットフォームは、Linuxの予定らしい


俺みたいな万年初心者でも、コンパイラが作れるようになるんだろうか

>>844
普通にコードが書けるならドラゴン本とか読むだけで十分事足りるハズだよ。
もしも量が多くて読むのが苦痛って話ならどの本読んでもあんまり変わらない。

まじめな話どうして万年初心者などと言う単語を使うのかさっぱりわからん。

レビューでもやさしいと言われている「プログラミング言語処理系」を読んでも
難解すぎてわからんすぎて、それ以来分厚いコンパイラ本を買えないのです・・・

Amazon.co.jp： プログラミング言語処理系: 本: 佐々 政孝
http://www.amazon.co.jp/dp/4000103458

>>846
難解な理由はどこにある？
語彙か？

>>847
なんつーか、理論ばっかだったという記憶
むかーし高校時分に読んで、放り投げた覚えがある
そんな俺には、コンパイラ制作は夢なんです。

昔あきらめたことでも、今やろうとするとできるってことって良くあるよね

１つ１つ手順を追って、理詰めでやるんだ。

>>848
理論抜きでやりたいならbit臨時増刊1978/2 マイクロコンピュータのプログラミング
http://www.pro.or.jp/~fuji/computerbooks/pasocom/micro1978.bit.html
にマイクロPLANコンパイラの記事があるからそれを読むといい。

たった４ｋワードの空間しか扱えない16ビット仮想マシンだが結構な事ができる。

ただし理論無くして自分で考えて前進することは無理があるって事だけは肝に銘じておくといい。

理論知らずに、直感的にMLコンパイラ作ってた大学時代
なぜ俺は作れたのか

>>852
車輪の再発明しながら進んだか、理屈を学習しながら進んだんだろ。
どっちもゴールは一緒だが達成感は前者の方がありそうだな、再発明だってしらなければ楽しくてしょうがないだろうし。

知っても値打ちはほとんどなかった罠

ぶっひゃあ

理論を知るのはいいことだろうけど実際には役に立たないからな。
日進月歩の技術革新の前には、覚えるより買うほうが早い。

そうだな。　買った方がいいんだろ。　だから労働者も消費物。　買われる奴隷なんだろな

勉強用にForthて良いと思うんだけど、どうかね？

考えるより作るほうが早く終わる、そんな言語

Forthは字句解析も構文解析も簡単すぎて、ある意味、勉強にならない。
でもVM系の言語つくるなら、多少はその面で役に立つ。
つぎはLispをつくって抽象構文木のいじり方を覚える。
と、言語の階層を昇っていけば、いつか、自分の言語を作れるようになるかもしれないし、
ならないかもしれない。
この方法の落とし穴は、多くの人が「Lisp最強じゃね？」
と、気付いて自分の言語をつくるのをやめてしまう点にある。

Lisp最強って否定はしないけど、
個人的にはLispで大規模なものは作りたくない^^

MLのアセンブラだからな
「LISP最強」は「アセンブラ最強」って言ってるのと同じだ

アセンブラ最強！

バックトラックありの再帰降下パーサは指数時間かかるけど、実用にならないほど遅い？
普通の文法なら、実際のところそれほど深いバックトラックはされない気がするんだけど。

GCC4も手書きの再帰下降パーサだそうだし、もんだいないんじゃない？

普通の文法でも、バックトラックをまったく気にしないで書いて、
バックトラックしまくりになると、やっぱりめちゃくちゃ遅くなるよ。

適当にバックトラックがなるべく起こらないようにすると瞬時に終わるようになった。

よし、ちょっくらForth83のインタプリタ作ってくる。

関係ない話題で申し訳ないけど、今日好きな子の名前を下の名前で呼んで良い許可が出た
明日から下の名前で呼ぶことになるけど、口を開くたびにドキドキしそう
なんかアドバイスください

あらかじめしゃべる言葉をコンパイルしておけ

何かがNGワードにひっかかってるな
どーでもいいけど

>>864
よっぽど変な文法にしない限り、実用にならない程遅いってことは無い
http://home.swipnet.se/redz/roman/pubs.htm
にある
Parsing Expression Grammar as a primitive recursive-descent parser with backtracking
という論文では、実際にバックトラックありのただの再帰下降構文解析でJava 5のパーザを
書いてみたら、実用的な速度(おおむね線形時間)になったという事が紹介されている

Java5の構文の振舞いが元々良いから速い、と読めたけど
変な文法が具体的になんなのか知りたい

>>866
必要な所だけバックトラックするなら十分実用的なんだね。thx.

>>871
これって lexer も含めてパーザに突っ込んでるの？
単純な再帰降下パーザがそんな力業に耐えられるとは知らんかった。

ただ、正しい入力が与えられたときにほぼ線形時間なのは、個人的には
当たり前だと思うんだよな。
バックトラックが問題になるのって、構文解析に失敗するような入力が
来たときだと思うので、その辺が気になる。

PEGはstatelessなのが残念。
状態（文脈依存情報、Cの場合ならsymbol table）を持てるparser combinatorって
ないかな。

解析結果と状態のペアをmemoizeして、次に呼び出された時に状態が新しくなっていたら再解析する、
みたいなやり方をすればstatefulにできるかな。
当然必要な再計算コストは避けられないし、メモリ使用量が輪をかけて増えるがな。

PEG っつーのは BNF に ! と & が増えた奴、と思っていいの？

BNFの | に相当する / の順番に意味がある点も違う。例えば、BNFにおいて、
A ::= B | C; は A::= C | B;
は同じ意味だが、PEGにおいて
A = B / C; は A = C / B;
は異なる。

PEGて、/のお陰で再帰下降で素直に組めるな。
結局 >791もPEGになった。再帰下降じゃなくてスタックだけど。

>873
>バックトラックが問題になるのって、構文解析に失敗するような入力が
そこは文法次第だと思う。そのあたりは従来型正規表現エンジンなんかと同じですな。
逆に、正しい入力が与えられてもバックトラックがたくさん発生して遅くなることもあるしね。

>874
ちょっと興味があったので、>791に状態による分岐・加工を実装してみました。
Procedureというのがそれで、次に判定する条件を決定するenterと、実行したあとの結果を加工するleaveという
メソッドを持ったオブジェクトを使って、パース中に何でもできるようにしています。

使い方は
ttp://cvs.sourceforge.jp/cgi-bin/viewcvs.cgi/siki/siki/src/test/PullParser/test_PullParser.cpp?view=markupのtestProcedureを見てちょうだい。

ここの人って、もしかしてこういうのに興味ある人なの？
http://d.hatena.ne.jp/squeaker/20061031/p2
http://d.hatena.ne.jp/sumim/20070306/p1

ちょこっと。
おいらはそれをForth + プロトタイプ でやろうとしている。
ただ、構文解析 --> 実行のところの意味が上手く整理できないんだよな……
ForthみたいにImmediatelyeを導入するのもスマートじゃないし。

うお、typoった。 Immediatelye --> Immediate

>>880
smalltalkみたいなpepsiがあって、shemeみたいなcokeがある、と。
cokeは文法が定義できるのが特徴？
pepsiがC言語関数が呼べるsmalltalk?

CodeZine：MASMとなでしこによるオリジナルコンパイラの制作 1（MASM, コンパイラ, アセンブリ, なでしこ）
http://codezine.jp/a/article/aid/505.aspx

CodeZine：MASMとなでしこによるオリジナルコンパイラの制作 2（コンパイラ）
http://codezine.jp/a/article/aid/686.aspx

CodeZine：MASMとなでしこによるオリジナルコンパイラの制作 3（MASM, コンパイラ, なでしこ）
http://codezine.jp/a/article/aid/766.aspx

CodeZine：MASMとなでしこによるオリジナルコンパイラの制作 4（コンパイラ, なでしこ）
http://codezine.jp/a/article/aid/996.aspx

なでしこで、コンパイラ製作ってすげーなｗ

中学生とか嘘くせえけど

暇と情熱と勢いでなんとかしちゃう中学生ってたまにいるよ
BASICでcoffを吐くクロスコンパイラ作っちゃった中学生だっている
俺の弟のことだけど

まぁどうでもいいか

>なでしこ以外にも、他の言語を心得ており、HTMLがなでしこの次に得意であり、Perlが第３位（かも）。ベクターにも多彩な作品を残している。

しかし、ここはモロ中学生でほほえましいな。

他の言語を心得ていると豪語して、それがHTMLってのは衝撃的発言。
「ベクターにも多彩な作品を残している。」他人事かよ！

>作文がど苦手

だめじゃんw

ﾜﾛﾀ
微笑ましくてよいな

おちんちんおっきした　ショタの才能あるのかな

>>886
学生って暇と勢いはあるからな。

全員まとめてこいよ。　ボコボコにしてやんよ。

　∧＿∧
　(　･ω･)＝つ≡つ
　(っ　≡つ＝つ
　./　　　) ﾊﾞﾊﾞﾊﾞﾊﾞ
　( /￣∪

>>892
坊主、もうちょっと上からたたいてくれんか、最近肩がこっていかんのじゃ

>>893
チ○コアタック！
　∧＿∧
　(　･ω･)
　(　 　　 ） ﾊﾞﾊﾞﾊﾞﾊﾞ
　./　　＝つ≡つ
　( /￣∪

おや、こんなところにウィニーが

>>894
上からゆうとるやろうがｗ

C言語を学び始めようと思ってるんですが
Vistaで動作するコンパイラって何かありますか？

ＶＣ２００５ＥＸＰＲＥＳＳＩＯＮ

ちょっと聞きたいのですが
生垣オートマトンってどのようなオートマトンを指すのでしょうか？
性質がいまいちどのようなものを意味するのか理解できません。

生け垣オートマトンだとRelax系の論文とか文章あたればいいんじゃないのか？
Relaxなら日本発だから日本語の文献あるじゃろ？

とりあえずはここか？
ttp://www.xml.gr.jp/relax/hedge_nice_ja.html

ざっと読んで、
生垣オートマトン　≒　（XML文書のような）生垣を文法構造含めてパースするオートマトン
のような気がした。

「文法構造」じゃ無いな……「文書構造」だな。

コンパイラが吐くコードってコンパイラや言語ごとに特徴が出るのかなあ・・・

まったく一緒だったら怖いわ

すべてS式になります

<チラ裏>
なんというか色んな人が俺言語作ってるから、他人と被らない名称を考えるだけでも一苦労だなぁ……
</チラ裏>