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

「入れる」は状態スタックにプッシュするってことね。多くのLR構文解析系はスタックを使って状態記号を保存するので。
LR構文解析は状態記号が入ったスタックのトップの状態と入力記号列の最初の終端記号からだけで次に行うべき動作を決定する。
その動作が移動なら入力から一つ記号を取り出し構文解析表から次に移る状態を引いて状態スタックにプッシュする。
還元なら生成規則に従って状態スタックから特定の数だけ状態をポップして、
その時の状態スタックのトップの状態と還元された非終端文字で決まる状態をプッシュする。
この時にだけ還元された記号が使われるが後から使ったりしないので特に保存する必要はない。

>>952
だとするととてもありがたいのですが、それほんとに信じてもいいんですよね？
LR構文解析機を作ったことがあったうえで言ってるんですよね？

>>953
感謝の言葉もなしに>>952になんて失礼なことを言ってるんだ、こいつはｗ

ちょっと読み返すと失礼にあたる書き方に見えてきました。
どうもすいません。
>>953をちょっと補足します。
コンパイラIの286ページ図4.39を参考にします。
ここでI0からI1へ遷移するためには非終端記号Sの入力が必要なのではないか？
と考えたわけです。
逆に終端記号のみから次の遷移先を決定できる項集合について考えると、
循環する文法記号がある場合、永遠に展開し続けねばならず、終端記号のみからなる
gotoグラフの作成は不可能ではないかと考えたのです。
これを可能にするには、goto表の入力となる非終端記号を何に置き換えればいいのでしょう？

よろしくお願いします。

相談に来ておいて相手に文句たれる奴っているよね。
なんで相談する気になったのかいつ見ても不思議

>>954さんも>>952さんの考えを裏付けるってことですか？
私はドラゴンブックを見て考えていたので、最近の事情は知らないのです。
よろしくお願いします。

>>957
裏づけがほしいんだったら、相応の対価を払って専門家に会って聞くべき

構文解析系が入力記号列と状態スタックから構成されている場合、
状態スタックには最初に初期状態０がプッシュされている。
構文解析動作は、入力記号列の先頭の記号と状態スタックのトップ状態を見て、
対応する状態遷移表の項目からその動作を決定する。
移動なら、入力記号列の先頭記号を消費し、指定の状態を状態スタックにプッシュ。
還元なら、指定の生成規則の右辺の記号数だけ状態スタックからポップし、
　　　　　その時の状態スタックのトップ状態と生成規則の左辺とで決まる状態をプッシュ。
受理なら、正しく構文解析が完了。それ以外はエラー。
構文解析系はこれだけで動作する。還元された非終端記号はそれ以降の動作に出てくることはない。
例えば、数と＋を終端記号、式を非終端記号として、
(1) 式 ::= 式 ＋ 数
(2) 式 ::= 数
のような生成規則に対して、＋は左結合的とすると、
状態０：入力記号が数なら移動し状態１、還元されたものが式なら状態２
状態１：有無を言わせず生成規則(2)によって還元する
状態２：入力記号が＋なら移動し状態３、入力が終端に達していたら受理
状態３：入力記号が数なら移動し状態４
状態４：有無を言わせず生成規則(1)によって還元する
のような状態遷移表が作られる。
状態スタック：０｜入力記号列：数＋数＋数　（０と数で状態１移動）
０，１｜＋数＋数　（１と＋で生成規則(2)による還元、状態を1個ポップし０と式なので状態２をプッシュ）
０，２｜＋数＋数　（２と＋で状態３移動）
０，２，３｜数＋数　（３と数で状態４移動）
０，２，３，４｜＋数　（４と＋で生成規則(1)による還元、状態を3個ポップし０と式なので状態２をプッシュ）
０，２｜＋数　（２と＋で状態３移動）
０，２，３｜数　（３と数で状態４移動）
０，２，３，４｜　（４と終端で生成規則(1)による還元）
０，２｜　（２と終端で受理）
で、受理される。

>>959
どうもありがとうございます。
よくわかりました。
お礼に私に出来ることはありますか？

>>955
「コンパイラIの286ページ図4.39を参考に」できないからその内容はよく分からないけれど、
LR項の集合族間の状態遷移図とLR構文解析系の状態遷移表による動作とは別物。
LR構文解析系の状態遷移表を構成するための理論的裏づけがLR項の集合族間の状態遷移というだけであって、
実際に構文解析を行うに当たって非終端記号を入力記号として記録する必要はない。
もちろん、次の状態を決定するために、ある１動作の範囲内で非終端記号は必要になるが、それだけ。
そして、その必要な非終端記号は還元時に定まるもので入力として記憶するものではない。

>>960
別にないよｗ
構文解析関係は理論だけでは取り付き難いから、
小さな系でもいいから実際に動作を手で追いかけながら見ていくと理解が進む。

LISPやれば構文とかどうでもよくなる

推敲せずに書いたらちょっと不要なことまで書いてしまった。
>>959の「＋は左結合的とする」必要はなかった。
生成規則の定義だけで結合性を指定しなくても衝突は起きない。

>>963
構文解析とかガキのやることだよな。
その先を見ろよ。

おれのちんこなめろよ

構文解析は今もホットだぜ。

>>947
オントロジーｗｗｗｗｗｗ

未だにオントロジーやってるのってEUの
外基地研究者ぐらいじゃねーの？

オントロジーなんて日本でもアメリカでも中国でもどこでもやってるぞい

阪大でやってたような

オントロジーいらないって言ってる輩は、
「いいもん、別にCだけで何でも作れるから今のままで苦労してないもん！」
みたいな事を平然と言ってのける人種だけ
「もっとOSとかネットとかグリッドとかやってみたいから何かいいのないかな」
っていってる奴は死んでいいけどオントロジーはおもしろいです

（　ﾟдﾟ）ﾎﾟｶｰﾝ

ちょっとした処理系を作ろうと思ってるんだけど、yacc勉強したほうがいい？
それとも、自前で実装するほうがいい？

ソースを公開したい場合は、
lex はライブラリを必要とするので
lex のインストールを相手に強要することになってしまう。

この点が問題にならないのであれば、yacc/lex というか、
今なら bison/flex あたりを勉強するのが楽だと思う。

> lex はライブラリを必要とするので

ええ？どの環境？

そもそもライブラリ無かろうが lex のソースをコンパイルするのに lex が要るんじゃないか？

lex が　flexのエイリアスだったりすることをいってるじゃないか？

ソースを公開したい場合は、
〜 はコンパイラを必要とするので
〜 のインストールを相手に強要することになってしまう。

ユーザならともかくコンパイルする人間にそこまで気を使ってどうするよ

コンパイラ１つあればコンパイルできる、って方が楽だ

>それとも、自前で実装するほうがいい？

自前で実装すればコンパイラ１つあればコンパイルできるという状況になる。
そっちの方がいいと思うなら自前で実装した方が良い。

ソースを公開したい場合は、
ソースはダウンロードを必要とするので
ソースのダウンロードを相手に強要することになってしまう。

バイナリを公開したい場合は(以下略

>>977
cに変換したの入れとけばいいし。

>>978
libflのこと言ってるんだろうね。
BSDライセンスだから、一緒にソースを配布すればいいんだけど。

ここ2,3日ttp://piumarta.com/software/peg/のPEG/LEGっての弄ってるけど
エラー出にくくてBNF系より楽でなんか気に入った
Windows用にビルドしたので一応UP
ttp://www.csync.net/service/file/view.cgi?id=1232894452

気づいたら980越えてるな。
テンプレ修正要求とかあったら出してちょ。

...電通大の（渡邊先生のところかな）compilers鯖が403のままだ。
検索したら最終講義という話題が2005年にあったようなので、
引退されたから鯖止めたのか、だとすると復帰はないかな。

あそこは研究室にグローバルIP振って各自管理だから、
引退されたなら、ゼミを引き継いだ教授ゼミのサーバにあるかも。

次スレ立てるまでに情報探すの無理そうだな。
http://compilers.cs.uec.ac.jp/ はウェブアーカイブを示しとくか。
http://web.archive.org/web/*/compilers.cs.uec.ac.jp/

21st Century Compilers はISBNが変わったらしい
http://www.amazon.co.jp/dp/0321210913

>>295
アプリケーションハンガリアンを言語レベルでサポートするということかな。

ttp://local.joelonsoftware.com/mediawiki/index.php/間違ったコードは間違って見えるようにする

タイプセーフな言語の好き嫌いと同様に好みは分かれそうだけど、
好む人たちもいると思う。
私は、制限できること自体は便利そうだと思うけど、
元の型が分からないのは困る。
(Cのtypedefは無い方がいいと思っている)

うぉ、>>297までしか見えていない状態だったので、
超カメレスしてしまった。。

>>974
使っているうちに欲しい機能は増えていくから、
最初からパーサジェネレータを使った方がいいと思う。
再帰下降だと左再帰の扱いが面倒だし。
yaccやbisonは古臭くて扱いにくいので、他のも見てみては。
ソースコードのきれいさで言えば、個人的にはCaperが好み。

テンプレにPEGとPackrat parsingの話題ほしいかな。
まとまってるのはウィキペディアの解析表現文法とか。
http://ja.wikipedia.org/wiki/%E8%A7%A3%E6%9E%90%E8%A1%A8%E7%8F%BE%E6%96%87%E6%B3%95

さっき見たら昨日の>>988が壊れてたのでSJIS対応外してうｐし直し
ttp://www.csync.net/service/file/view.cgi?id=1232978313
そのうち本家にパッチ送るけど..

>>976
最近は違うのか？

flexをC++モードで使うとライブラリが必要ないのでオヌヌメだったりする．．．．ってか
10年以上前の情報だけどね。

>>974
実装したい言語のタイプによるんじゃないかなぁ。Lispっぽければパーサジェネレータいらない。

>>972
オントロジーは面白いです、確かに。しかし、オントロジー研究者が約束した果実は
今までもたらされていないし、これからももたらされることはないでしょう。

>>1000にあたり意見を述べさせていただきます。
次スレは必要ないと思います。

このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。