パーサーとか構文解析とかその他もろもろ

最近仕事でチョいとしたパーサーを何度も作るはめになりました。
パーサー技術、実装、ちょっとした技、そのたいろいろ教えてください。

じゃ

ちなみにJavaで書いてるのでJavaでのパーサーの話題お願いします。
とりあえず
ANTLR,JavaCCとかを使い始めていますが、まったくもってイライラします

もっといいのないですか？

そもそも、
Ｌ　⇒　Ｒ a | R b
R ⇒　(c | b)*

がコンフリクトするとかいわれてまじいらついてます

もっとまともなパーサーをつくれないのか？もう２０１０ねんだよｗｗｗｗｗ

HaskellでParsec使ってみ
マジ簡単だから

あるいはScalaとかな。
noopがたぶんScalaで構文解析の部分書いていたと思う。

>>5 さんきゅう、とりあえずぐぐってみた
で、だ、
Haskellってのおぼえないとつかえないんじゃないの？
それをおぼえるのと、Yaccおぼえるのと、どっちが簡単なのかがもんだい。

まあ、おぼえたあと、どっちがイラつかないかも問題だけど。

>>6 サンキュウ noopってなに？

だいたい、パーサーを作る時って、別にインタプリタやコンパイラを作るとかじゃないんだよ、
たんに文字列受け取ってJavaプログラムで操作できるＡＳＴにできればいいだけ、
後はこっちで書くから、、ってかんじ

そういう用途むけのパーサーツールがあってもいいとおもうんですけどーー

>>6 noopって言語があるんだ！

次のような表現Rを考えよう。
・Rは特殊文字"#1,#2,.."(SPEC)と文字列(STR)を要素として含む。
・r,r1,r2がＲに含まれるならば、r1+r2, r1;r2, (r), (r)*, (r)? もRに含まれる
・文字列としての#,+,;,*,?を表現するためエスケープ文字"\"を導入
　
・例："123dff" -> STR(123ddf)
: "\\ddf" -> STR(\ddf)
: "#134;dd" -> SPEC(134);STR(dd)
: "\#134dd" -> STR(#134dd)
: "\#134;dd" -> STR(#134);STR(134)
; (3+g)+\+ -> (STR(3)+STR(g))+STR(+)
; \(3+h;#5 -> STR((3)+STR(h);SPEC(5)

こういうのを作りたいんですが、あ、あくまでＡＳＴをとれればいいんですが、
こういうのちょいちょいっとつくれるのないんですかねー

JavaならANTLRが一押し

そうなんだよね。結局、ボトムアップ型のパーサーだとちょっと文法複雑になると、
Shift-Reduceコンフリクトを取り除くが大変になるんだよ。そう、悟った俺は
トップダウン型のパーサーの方が楽って事に気づいた。で、現状のパーサーは
どれもLL(∞)で、トークンを何個も先読みできるし。だいたいの言語は何個も先読み
しなきゃいけない部分なんてそんなたくさんあるわけじゃないし、問題なし。

>>3 はボトムアップだとconflictはおきないし、先読みトークンの回数も決まらない

こういう文法は（直観的なものから）書き換える必要があるけど、LL(k)で処理可能
結論としては、なれればLL(k)がいい。

C++パーサーむずい

>>1
パーザや構文解析処理が必要になった場合、その実現方法には
yaccなどのコンパイラコンパイラを使う方法もあるが、他には
「再帰下降構文解析」という古典的なアルゴリズムがある。

・http://ja.wikipedia.org/wiki/再帰下降構文解析

このWikipediaの解説ではC言語が用いられているが、
Javaへの書き換えは容易なはず。もし>>1がこの記事を理解できて、
それに興味を持ったのなら、残念ながら既に絶版になっているが
以下の書籍を古本や図書館などで入手・閲覧でするのがお勧め。

・「翻訳系構成法序論」 ニコラス・ヴィルト著 近代科学社

策員を含めて133ページの薄っぺらな本だけど、PL/0と呼ばれる
小さな手続き型言語の処理系の再帰下降による作成方法が
詳細に解説されている。記述言語はModula-2というPascal系言語だが、
こちらもJavaへの書き換えは容易なはず。

>>16
>>1が使い始めているjavacc,antlrがそもそも再帰下降構文解析を実装しているんじゃないの？
　（バックアップ回数が制限されてるから正確には制限された再帰下降構文解析だけど）

制限があるの無いのとでは大違い

今 Flex でゲームシナリオを解析して XML 化、XSL で XHTML 表示して遊んでるんで、このスレ助かるわ。

Boost::Spirit って、Flex を置換出来るモノじゃないの？

<HOGE>とか、YY_START、yy_push_state()、とかの代替となるような関数・手法が見つからなくて、
あと変態黒魔術に死にそうになったんで、素直に Flex 使ってるけど。

「コンパイラ・スクリプトエンジン」相談室14
http://pc12.2ch.net/test/read.cgi/tech/1258431145/l50

wikipediaからのリンク失敗する男の人って

http://ja.wikipedia.org/wiki/%E5%86%8D%E5%B8%B0%E4%B8%8B%E9%99%8D%E6%A7%8B%E6%96%87%E8%A7%A3%E6%9E%90

てか >>20 のスレでやれよ。
ここまでレス付いちゃうと即死では dat 落ちしないかな。
重複で削除依頼するか。

>>19
spiritはやめたほうが良い。
理由は単純にビルドが重いから。

>>20 コンパイラ スクリプトエンジンとはべつものだろ、ばかかおまえらｗｗｗｗｗｗ

とりあえずパーサを書くには
1.パーサジェネレータなり自分で書くなりして、コードを抽象構文木に変換する
2.その抽象構文木を処理したりバイトコードに変換する
という行程を踏めばいいのはわかった。

で、どこにも聞けないんで聞くんだが…
抽象構文木？AST？ってなに？データ型なの？

データ型として定義もできる。
とにかくコードを特定の言語で処理できる抽象構文木にさえできれば
後はその言語でその抽象構文木を操作するプログラムを書けばいいだけ

antlrがもっともお勧め、LRパーサーはもはや遺物

最近はやってるなANTLR
LALR(1)とLL(k)って実用性としてはどう違うんだ
PerlとかC++はLALR(1)でパースできないと聞いたが

このスレはパーサーとか構文解析のスレです

抽象構文木をどう扱うかの話はスレ違いですので、>>20 のスレでやってください

いやです。ASTの話題はパーサーの中心的な話題です

関数型言語だとパーサって作りやすいんだよね？
なんか、このページ
http://diaspar.jp/node/236
に手入力でASTを作成して処理ってコードがいくつかあるけれど、
これの見た目でLispみたいな、Scalaのとこだと
Add(Number(5), Sub(Number(7), Number(9)))
が抽象構文木ってことでいいんだろうか…

>>31　そうですぼくもそれが抽象構文木だと思ってます。

でですよ、自分で勝手に決めた文法から、こういう抽象構文木をぱぱって作ってくれるパーサー
をあっという間に作ってくれるパーサージェネレーターがほしいんですよ。

yacc/lexとか、javaCCとかまじいらつくんで、もっといいのないんですか？

たんにASTと作りたいだけなのに、どんだけ頭つかわして、コードかかせてんだよ！ってかんじですねｗ

>>31
だってLispは抽象構文木をそのままプログラミング言語に
したものだし

>>31
関数型言語は、型名（クラス名）、コンストラクタ名、印字表現名が一致しているのが伝統的で、後者二つにはディホォールト実装がある。だからプロトタイプ実装に強い。

ただ、デバッガサポート、エラー処理やろうとすると、ディフォールト実装のままではどうにもならない。

>>31
パターンマッチ最強だなw

>>35
構文廻りはパターンマッチの連続だから、パターンマッチcaseだけじゃなくて、パターンマッチ渡しある方が簡潔になるね。

関数型からJavaとかに移るとこのへんですごく違和感をおぼえるね

>>33
つまりLisp最強ってこと？
Lispは今度出るClojure本待ちで勉強しようと思ってる。JVMならJavaから呼べるだろうし
感じとしてはコードを生成→コードを処理、って感じになるのかな

Antlrはもうちょっと日本語の資料があればなぁと思う
Javaのパーサ生成器はJparsec
ttp://jparsec.codehaus.org/
ってのを見つけてるけど日本語の資料が皆無（ブログで書いてくれてる人も旧バージョン）で
サンプルコードも計算機しかないし使いこなせる気がしない…

Eclipse環境との親和性を考えると今はJavaCCがいいよ

どなたかバカな大学生が作るような簡単な構文解析のプログラム作って
ソースをくれませんか？？
ｃ言語でお願いします。
記事を辞書を使って解析するようなものがいいです。

辞書があって出来るのは字句解析だろ

構文解析をしてみようと思う。
簡単なことだとプログラミング言語の作者とかが言ってるのを読んで
簡単なのだろうと思っていた。
それでググってみるといろいろ情報がある、楽勝だろうと思っていたが、
理解できない。
簡単なはずのことが出来ない自分に腹が立ち、理解できない現状に腹が立つ。

それで、ライブラリがあればと思ってyaccとか何とかをつかってみる。
すると今度はその使い方が難しい。
なぜかというと、そのライブラリが別パラダイムの別な言語だからと気がつく。

理想は例から構文解析ツールが出来るようなものなのだ。でも現実にはない。
xmlschemaの定義がGUIで出来るものがあるように、
GUIで組み立てられるツールがあればいいのかもしれないけどない。
というか、xmlschemaが難しい。難しいけど認めたくない。

感覚的に理解しやすいのはおそらく、再帰下降法だ。
四則演算なら理解できた。

ただ、Javaで思った文法を直書きすると永遠と長く書かないといけないことに気がつく。
めんどくさい。

パーサジェネレータは難しい。直書きはめんどくさい。

関数型言語とやらがよいらしい。
ocamlを勉強する。結局構文解析はyaccをつかうことになる。
haskellを勉強する。parsecとやらがいいらしい。
パーサコンビネータとかなんかが、結局yaccとかといっしょだ。わけわからん。

早い話が、なにをやっても必要な知識は結局同じ。
だから、理解するしかないと思え。

yacc、かなり簡単だと思うけどなあ。
例によって、計算機作ることから始めたけど、普通にCとか使える奴なら、するする進めると思うけど。

なんとなく、C++とかperlは適当な構文解析で動いてる印象がある。

C++が適当って…　怖い物知らずだな。
俺、フル仕様のC++の構文解析なんか、変態過ぎて見たくもないし作りたくもないぞ。

perlは作者自身が言うように人工言語史上例を見ないぐちゃぐちゃパーサ

C++ は、C と違ってパーサーのこと考えてないよな。
一番ひどいのは、COBOLらいしけど。

>>42
薄いのでいいからコンパイラの本を読め
うまく立ち回れば楽ができると考えるのは図々しすぎる

一生かかってもC++パーサ作れそうにない

思うんだけど、結局つーるつかってもたいした時間削減にならん
とくにまともなソフトに組み込む場合

手書きでLRはかなり難しいでしょ。

一回作れば後はかなり再利用できる。
ま、それを突き詰めればツールなのだろうが

最近は手書きのパーサーが増えてきた感じ

Javaパーサってどこかで公開されてる？
自作するとなると相当難しいよね

>>55
javaCCにも入ってるし、そもそもjavacがオープンソース。

素人でScalaやってるんだが，パーサコンビネータでちまちましたのを作って組み合わせていくのがちょっと楽しい．
ボトムアップでパーサコンビネータっぽいのってなんかないの？

個人的にはyaccがわりと好き。最初はイマイチわかりにくいと思ったが，他に比べればマシだった。

yacc/lexは最適解ではないけど落としどころとして良い感じだよね。ドキュメントも多いし。
言語本体との親和性という意味ではRubyのraccが、使いやすいyaccという感じだった。

HaskellのParsecは、構文解析はすごくわかりやすく書けるけど、字句解析がなんか微妙。
ドキュメントやサンプルが少なくて理解できてないだけかもしれんが。

ParsecとかBNFCとか見てると、今後は構文解析の定義を自分で一から書くんじゃなくて、
ライブラリが提供するテンプレート（JavaタイプとかHaskellタイプとか）をカスタマイズする
方向に発展していくのかなとも思う。

構文解析は手書きでやる事で既に決めたんだけど
字句解析まで手書きしたものか悩んでる。
字句解析は構文解析ほど複雑じゃないから、手書きも可能そうだけど、
手持ちのlexは使えるから、それで十分っぽい気もする。

もし字句解析を手書きした人がいたら、
どういうメリットから手書きを選んだのか参考に教えて欲しいな。

グローバル変数万歳なところが嫌い

>>60
もし手書きするのが再帰下降のトップダウンパーサなら
構文解析と字句解析はほぼ同時に行うから
字句解析処理だけ専用に作ったりはしなくない？

コンテキストによって字句解析の方法を切り替えなければならないしことが多いし、大して楽にならないので手書きが多いような気がする。

JavaにおいてAAAというトークンがあるとき、
AAAがクラス名であるか否かを判断するのって、
結局前に来てるトークンがclassだとか、
”{”がすぐ後ろに来るとか、Extendsがくっついてるとか、
そういう情報から特定してるんでしょうか？

何かもっと効率的に判断するための方法があるんでしょうか。

Javaは普通にclassの後ろに来てるidentifier(　[a-zA-Z_]([a-zA-Z0-9_])*　だっけ?)　がクラス名扱いになるんじゃないの？
よくわからないけど。Javaの文法ってそんなかんじじゃなかったっけ？

あるトークンがクラス名である、と判断するのは、まず
トークン列がクラス定義(class 名前 ...)だったり
インスタンス生成(new 名前...)だったり
例外送出(throw 名前...)というのを判別するのが先。
その後でマッチした名前がクラス名の役割のものだと分かる。

クラスって簡単に取れるけど
関数になると少し取りにくくなって
変数になるとさらに取りにくいよな

・予約語に含まれる型
・宣言されたクラスの型

の後ろに来るidentiferが変数名かな？
ぱっと考えただけだから例外あると思うが。

回答感謝、マルチレスで。
>>61 同意せざるをえない。今回はクラスに押し込める予定。
>>62 そんな高尚なブツは作れないです。
　　　　キーワードの前後関係から文を解釈する原始的なものなので。
>>63 確かに。lexのスタート状態で何とかなるかな、程度に考えてる。

Jparsec って日本語に対応してる？

してる

VBだと関数呼び出しなのか配列なのかとか
関数呼び出しなのかラベルなのか変数なのか最後までわかんないな

よく文字列リテラルの中での改行を
char str[]= "hoge \
fuga\
bar";
みたいに\で区切る言語があるけど
\なんか打たなくても
最近の進歩した解析法で、これは自動認識するようになってたりしないの？

ああ、\だとくっつけるだけか。まぁ\nとかいちいち書かなくてもよいように出来たりしないのかなっていう疑問です

ヒアドキュメント

ヒアドキュメントは構文解析サボってるだけとしか思えない

str="""
ここをBNFサンドボックスにしていい？
駄目なら他に行きます。
""";

アホの日本語訳誤植多いね。

エイホのどの本？

「コンパイラ」なら普通「ドラゴンブック」と呼ぶ。

ドラゴンブックということで・・・・・

出版社によっては連絡すると正誤表のコピーを送ってくれる。
メール書くか電話してみ？

英語のｐｄｆみながらやってるんで・・・

EBNFについてISO/IEC 14977:1996(E)を調べてたんだが
文字セットが7-bit character set (ISO/IEC 646:1991 International Reference Version)
なんという時代遅れ

この辺のメタ構文言語ってそれぞれが勝手に微妙に変えて作るし
W3Cしかり、GOのページにも別種が載ってるし、
RFCはABNFだっけ。最近はPEGもあるし

PEG以外で一個覚えるとしたらどれがいいんだ

別に覚える必要などなかろう

そんなこと言ってるから・・
とりあえずEBNF自身をパース出来るEBNFパーサを作ったけど
文字はすべて1文字ずつ|で区切って記述。
これでUnicode文字を表現するのは悪夢
??で独自拡張するのも微妙だし
Unicodeぐらいは組み込みで使えるやつはないのだろうか

今度はABNFについて調べる作業がはじまるお

日記なら自分のブログにお書き下さい。

オートマトンの遷移関数表の入力記号が２５５種類以上（１万くらい）ある場合
どんなデータ構造にしたらいいですか？

1万エントリぐらいの振り分けってことだったら、関数ポインタの配列を使うかなぁ

マジレスすると255はアスキーコードで一万くらいといったのはユニコードですよ（笑）
ユニコードの実質使う文字数が１万個くらいかなーとおもっただけで
正確には１００個くらいかもしれません。

何を言ってるんだ

過疎ってるのにレス速いことに絶句

Unicode は U+10FFFF までだから100万文字くらいあるぞ

100万bitの配列をもつのはいかにも非効率だから、
Unicodeコードポイントのレンジを表現できるデータ構造をつくって
intersectionやunionの演算をできるようにしておくのかねえ

ドラゴンブックの解答ってないの？

ドラゴンブックは２冊よみとおしたけど、からだにあわん。もっとげんだいてきなのないの？

タイガーブック

　　　　　　 　 　 ＿_
　 　 　 　 , ‐' ´　　　｀`‐、 　 　 　 　 　 　 ／￣:三}
.　　 　 ／,. -─‐- ､.　　 ヽ　　　　　　　　/　　 ,.＝j
　＿,.:_'＿＿＿＿＿_ヽ、　.!　　　　 　 .／ 　 _,ﾉ
　 `‐、{　へ　　'ﾞ⌒　`!~ヽ. !　　　　 ／{.　　/
　　　 ｀!　しﾟ　 （　ﾟj　`v‐冫　　　, '::::::::ヽ､/ 　　　　そんなことよりyaccしようぜ！
.　　　 {.l 　 '⌒　 　 　 ﾞ 6',!　　 / :::::::::::::::/ __
. 　 　 〈　　< ´￣,ﾌ　 .ﾉｰ'_ , ‐'´::::::::::::::;/ （_ノ)‐-､
.　 　 　 ヽ.、 ` ‐", ‐´‐:ラ ':::::::::::::::: ;∠.　　 ヽ_}　 ﾞヽ
　 　 　 　 ,.r｀ "´　　／:::::::::::::::::::ィ´　　｀ゝ　 !、　　/
　　　　　/ 　 　 　 / :::::::::::::::: ; '´　　　/´＼　/ 　 r'＼
.　　　　 i　　　　　 ! ::::::::::::::／ 墨　|　.!::::::::／ヽ､.._!ヽ.　ヽ､
　　　　 {　　　　　 {:::::::::::;:ｲ　/　　 ‖ｉ:::::::/:::::::::::::/　 ＼
.　 　 　 ヽ 　 　 　 ヽ,.ｧ‐'´ /ヽ 二 ,/`ヽ、::::::::: ／

>>94
ttp://www.amazon.co.jp/dp/4797337958/

jparsec2にさわって見たけど情報がなさ過ぎるぜ

こんなルールがあって、
Aのパース結果の型をどうするかって時
A = *( B | C )

オブジェクト指向だとBとCの共通の基底クラスを作って
その配列を結果とする、よりも良い解ってありますかね

通常のBNF形式の文法を
PEGパーサでパースする際にパースされないパスを教えてくれるようなツールってないかな
["+"] / "-" って文法はPEGのパーサだと"-"にマッチしないから

ここって最適化の話もOK？
Dominance frontier で分からないことがあるんだが。

「コンパイラ・スクリプトエンジン」相談室14
http://hibari.2ch.net/test/read.cgi/tech/1258431145/

こちらへどうぞ

>>102
ありがとう

xtextは？これはつかえるの？

カ　オ　ス　ラ　ウ　ン　ジ　ゆ　る　せ　な　ぁ　い　ー

EclipseつかってるならXText最強だな

いまのじだいはDSLだろ

静的コード解析のスレはないんだね。

このすれだろ

その他もろもろ∋静的解析