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

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

1:デフォルトの名無しさん
10/01/08 23:32:50
最近仕事でチョいとしたパーサーを何度も作るはめになりました。
パーサー技術、実装、ちょっとした技、そのたいろいろ教えてください。

じゃ

2:デフォルトの名無しさん
10/01/08 23:34:10
ちなみにJavaで書いてるのでJavaでのパーサーの話題お願いします。
とりあえず
ANTLR,JavaCCとかを使い始めていますが、まったくもってイライラします

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

3:デフォルトの名無しさん
10/01/08 23:35:30
そもそも、
Ｌ　⇒　Ｒ a | R b
R ⇒　(c | b)*

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

4:デフォルトの名無しさん
10/01/08 23:36:22
もっとまともなパーサーをつくれないのか？もう２０１０ねんだよｗｗｗｗｗ

5:デフォルトの名無しさん
10/01/08 23:49:28
HaskellでParsec使ってみ
マジ簡単だから

6:デフォルトの名無しさん
10/01/09 00:23:54
あるいはScalaとかな。
noopがたぶんScalaで構文解析の部分書いていたと思う。

7:デフォルトの名無しさん
10/01/09 00:25:46
>>5 さんきゅう、とりあえずぐぐってみた
で、だ、
Haskellってのおぼえないとつかえないんじゃないの？
それをおぼえるのと、Yaccおぼえるのと、どっちが簡単なのかがもんだい。

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

8:デフォルトの名無しさん
10/01/09 00:26:56
>>6 サンキュウ noopってなに？

9:デフォルトの名無しさん
10/01/09 00:30:02
だいたい、パーサーを作る時って、別にインタプリタやコンパイラを作るとかじゃないんだよ、
たんに文字列受け取ってJavaプログラムで操作できるＡＳＴにできればいいだけ、
後はこっちで書くから、、ってかんじ

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

10:デフォルトの名無しさん
10/01/09 00:31:14
>>6 noopって言語があるんだ！

11:デフォルトの名無しさん
10/01/09 01:06:09
次のような表現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)

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

12:デフォルトの名無しさん
10/01/09 01:15:04
JavaならANTLRが一押し

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

14:デフォルトの名無しさん
10/01/09 01:34:48
>>3 はボトムアップだとconflictはおきないし、先読みトークンの回数も決まらない

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

15:デフォルトの名無しさん
10/01/09 02:16:42
C++パーサーむずい

16:デフォルトの名無しさん
10/01/09 02:33:14
>>1
パーザや構文解析処理が必要になった場合、その実現方法には
yaccなどのコンパイラコンパイラを使う方法もあるが、他には
「再帰下降構文解析」という古典的なアルゴリズムがある。

・URLﾘﾝｸ(ja.wikipedia.org)再帰下降構文解析

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

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

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

17:デフォルトの名無しさん
10/01/09 02:57:46
>>16
>>1が使い始めているjavacc,antlrがそもそも再帰下降構文解析を実装しているんじゃないの？
　（バックアップ回数が制限されてるから正確には制限された再帰下降構文解析だけど）

18:デフォルトの名無しさん
10/01/09 03:06:21
制限があるの無いのとでは大違い

19:デフォルトの名無しさん
10/01/09 03:25:37
今 Flex でゲームシナリオを解析して XML 化、XSL で XHTML 表示して遊んでるんで、このスレ助かるわ。

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

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

20:デフォルトの名無しさん
10/01/09 07:53:01
「コンパイラ・スクリプトエンジン」相談室14
ｽﾚﾘﾝｸ(tech板)l50

21:デフォルトの名無しさん
10/01/09 13:29:12
wikipediaからのリンク失敗する男の人って

Wikipedia項目ﾘﾝｸ

22:デフォルトの名無しさん
10/01/09 13:38:14
てか >>20 のスレでやれよ。
ここまでレス付いちゃうと即死では dat 落ちしないかな。
重複で削除依頼するか。

23:デフォルトの名無しさん
10/01/09 18:44:30
>>19
spiritはやめたほうが良い。
理由は単純にビルドが重いから。

24:デフォルトの名無しさん
10/01/11 18:48:25
>>20 コンパイラスクリプトエンジンとはべつものだろ、ばかかおまえらｗｗｗｗｗｗ

25:デフォルトの名無しさん
10/01/11 22:32:05
とりあえずパーサを書くには
1.パーサジェネレータなり自分で書くなりして、コードを抽象構文木に変換する
2.その抽象構文木を処理したりバイトコードに変換する
という行程を踏めばいいのはわかった。

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

26:デフォルトの名無しさん
10/01/12 10:07:48
データ型として定義もできる。
とにかくコードを特定の言語で処理できる抽象構文木にさえできれば
後はその言語でその抽象構文木を操作するプログラムを書けばいいだけ

27:デフォルトの名無しさん
10/01/13 01:04:52
antlrがもっともお勧め、LRパーサーはもはや遺物

28:デフォルトの名無しさん
10/01/13 12:02:12
最近はやってるなANTLR
LALR(1)とLL(k)って実用性としてはどう違うんだ
PerlとかC++はLALR(1)でパースできないと聞いたが

29:デフォルトの名無しさん
10/01/13 16:47:20
このスレはパーサーとか構文解析のスレです

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

30:デフォルトの名無しさん
10/01/14 08:15:10
いやです。ASTの話題はパーサーの中心的な話題です

31:デフォルトの名無しさん
10/01/14 12:58:44
関数型言語だとパーサって作りやすいんだよね？
なんか、このページ
URLﾘﾝｸ(diaspar.jp)
に手入力でASTを作成して処理ってコードがいくつかあるけれど、
これの見た目でLispみたいな、Scalaのとこだと
Add(Number(5), Sub(Number(7), Number(9)))
が抽象構文木ってことでいいんだろうか…

32:デフォルトの名無しさん
10/01/14 22:19:43
>>31　そうですぼくもそれが抽象構文木だと思ってます。

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

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

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

33:デフォルトの名無しさん
10/01/15 00:15:21
>>31
だってLispは抽象構文木をそのままプログラミング言語に
したものだし

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

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

35:デフォルトの名無しさん
10/01/15 08:32:14
>>31
パターンマッチ最強だなw