2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

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

じゃ

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

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

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

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

4 :デフォルトの名無しさん:2010/01/08(金) 23:36:22
もっとまともなパーサーをつくれないのか?もう2010ねんだよwwwww


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

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

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

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

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

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

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

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

11 :デフォルトの名無しさん:2010/01/09(土) 01:06:09
次のような表現Rを考えよう。
・Rは特殊文字"#1,#2,.."(SPEC)と文字列(STR)を要素として含む。
・r,r1,r2がRに含まれるならば、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)

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

20 :デフォルトの名無しさん:2010/01/09(土) 07:53:01
「コンパイラ・スクリプトエンジン」相談室14
http://pc12.2ch.net/test/read.cgi/tech/1258431145/l50

21 :デフォルトの名無しさん:2010/01/09(土) 13:29:12
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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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


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

36 :デフォルトの名無しさん:2010/01/15(金) 16:14:17
>>35
構文廻りはパターンマッチの連続だから、パターンマッチcaseだけじゃなくて、パターンマッチ渡しある方が簡潔になるね。

37 :デフォルトの名無しさん:2010/01/16(土) 00:36:38
関数型からJavaとかに移るとこのへんですごく違和感をおぼえるね

38 :デフォルトの名無しさん:2010/01/16(土) 01:28:52
>>33
つまりLisp最強ってこと?
Lispは今度出るClojure本待ちで勉強しようと思ってる。JVMならJavaから呼べるだろうし
感じとしてはコードを生成→コードを処理、って感じになるのかな

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

39 :デフォルトの名無しさん:2010/01/16(土) 02:19:26
Eclipse環境との親和性を考えると今はJavaCCがいいよ

40 :デフォルトの名無しさん:2010/01/16(土) 23:02:14
どなたかバカな大学生が作るような簡単な構文解析のプログラム作って
ソースをくれませんか??
c言語でお願いします。
記事を辞書を使って解析するようなものがいいです。


41 :デフォルトの名無しさん:2010/01/16(土) 23:44:06
辞書があって出来るのは字句解析だろ

42 :デフォルトの名無しさん:2010/01/17(日) 13:56:59
構文解析をしてみようと思う。
簡単なことだとプログラミング言語の作者とかが言ってるのを読んで
簡単なのだろうと思っていた。
それでググってみるといろいろ情報がある、楽勝だろうと思っていたが、
理解できない。
簡単なはずのことが出来ない自分に腹が立ち、理解できない現状に腹が立つ。

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

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

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

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

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

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


43 :デフォルトの名無しさん:2010/01/17(日) 14:00:40
早い話が、なにをやっても必要な知識は結局同じ。
だから、理解するしかないと思え。

44 :デフォルトの名無しさん:2010/01/17(日) 14:17:39
yacc、かなり簡単だと思うけどなあ。
例によって、計算機作ることから始めたけど、普通にCとか使える奴なら、するする進めると思うけど。

45 :デフォルトの名無しさん:2010/01/17(日) 14:18:49
なんとなく、C++とかperlは適当な構文解析で動いてる印象がある。

46 :デフォルトの名無しさん:2010/01/17(日) 14:24:50
C++が適当って… 怖い物知らずだな。
俺、フル仕様のC++の構文解析なんか、変態過ぎて見たくもないし作りたくもないぞ。

47 :デフォルトの名無しさん:2010/01/17(日) 14:26:00
perlは作者自身が言うように人工言語史上例を見ないぐちゃぐちゃパーサ

48 :デフォルトの名無しさん:2010/01/17(日) 18:31:58
C++ は、C と違ってパーサーのこと考えてないよな。
一番ひどいのは、COBOLらいしけど。

49 :デフォルトの名無しさん:2010/01/17(日) 20:04:53
>>42
薄いのでいいからコンパイラの本を読め
うまく立ち回れば楽ができると考えるのは図々しすぎる

50 :デフォルトの名無しさん:2010/01/17(日) 23:21:58
一生かかってもC++パーサ作れそうにない

51 :デフォルトの名無しさん:2010/01/18(月) 10:40:01
思うんだけど、結局つーるつかってもたいした時間削減にならん
とくにまともなソフトに組み込む場合

52 :デフォルトの名無しさん:2010/01/18(月) 10:55:30
手書きでLRはかなり難しいでしょ。

53 :デフォルトの名無しさん:2010/01/19(火) 00:19:23
一回作れば後はかなり再利用できる。
ま、それを突き詰めればツールなのだろうが

54 :デフォルトの名無しさん:2010/01/19(火) 02:49:26
最近は手書きのパーサーが増えてきた感じ

55 :デフォルトの名無しさん:2010/01/19(火) 05:54:02
Javaパーサってどこかで公開されてる?
自作するとなると相当難しいよね


56 :デフォルトの名無しさん:2010/01/19(火) 06:31:29
>>55
javaCCにも入ってるし、そもそもjavacがオープンソース。

57 :デフォルトの名無しさん:2010/02/02(火) 21:46:49
素人でScalaやってるんだが,パーサコンビネータでちまちましたのを作って組み合わせていくのがちょっと楽しい.
ボトムアップでパーサコンビネータっぽいのってなんかないの?

58 :デフォルトの名無しさん:2010/02/07(日) 15:36:51
個人的にはyaccがわりと好き。最初はイマイチわかりにくいと思ったが,他に比べればマシだった。

59 :デフォルトの名無しさん:2010/02/07(日) 20:56:48
yacc/lexは最適解ではないけど落としどころとして良い感じだよね。ドキュメントも多いし。
言語本体との親和性という意味ではRubyのraccが、使いやすいyaccという感じだった。

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

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


60 :デフォルトの名無しさん:2010/02/08(月) 01:23:57
構文解析は手書きでやる事で既に決めたんだけど
字句解析まで手書きしたものか悩んでる。
字句解析は構文解析ほど複雑じゃないから、手書きも可能そうだけど、
手持ちのlexは使えるから、それで十分っぽい気もする。

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


61 :デフォルトの名無しさん:2010/02/08(月) 10:38:54
グローバル変数万歳なところが嫌い

62 :デフォルトの名無しさん:2010/02/08(月) 18:24:10
>>60
もし手書きするのが再帰下降のトップダウンパーサなら
構文解析と字句解析はほぼ同時に行うから
字句解析処理だけ専用に作ったりはしなくない?

63 :デフォルトの名無しさん:2010/02/08(月) 18:34:19
コンテキストによって字句解析の方法を切り替えなければならないしことが多いし、大して楽にならないので手書きが多いような気がする。

64 :デフォルトの名無しさん:2010/02/08(月) 22:27:13
JavaにおいてAAAというトークンがあるとき、
AAAがクラス名であるか否かを判断するのって、
結局前に来てるトークンがclassだとか、
”{”がすぐ後ろに来るとか、Extendsがくっついてるとか、
そういう情報から特定してるんでしょうか?

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

65 :デフォルトの名無しさん:2010/02/09(火) 01:39:12
Javaは普通にclassの後ろに来てるidentifier( [a-zA-Z_]([a-zA-Z0-9_])* だっけ?) がクラス名扱いになるんじゃないの?
よくわからないけど。Javaの文法ってそんなかんじじゃなかったっけ?

66 :デフォルトの名無しさん:2010/02/09(火) 01:52:11
あるトークンがクラス名である、と判断するのは、まず
トークン列がクラス定義(class 名前 ...)だったり
インスタンス生成(new 名前...)だったり
例外送出(throw 名前...)というのを判別するのが先。
その後でマッチした名前がクラス名の役割のものだと分かる。


67 :デフォルトの名無しさん:2010/02/09(火) 02:13:24
クラスって簡単に取れるけど
関数になると少し取りにくくなって
変数になるとさらに取りにくいよな

68 :デフォルトの名無しさん:2010/02/09(火) 02:27:25
・予約語に含まれる型
・宣言されたクラスの型

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

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



70 :デフォルトの名無しさん:2010/02/19(金) 18:01:13
Jparsec って日本語に対応してる?

71 :デフォルトの名無しさん:2010/02/24(水) 22:14:37
してる

72 :デフォルトの名無しさん:2010/02/26(金) 01:42:34
VBだと関数呼び出しなのか配列なのかとか
関数呼び出しなのかラベルなのか変数なのか最後までわかんないな


73 :デフォルトの名無しさん:2010/03/11(木) 11:54:15
よく文字列リテラルの中での改行を
char str[]= "hoge \
fuga\
bar";
みたいに\で区切る言語があるけど
\なんか打たなくても
最近の進歩した解析法で、これは自動認識するようになってたりしないの?

74 :デフォルトの名無しさん:2010/03/11(木) 11:56:11
ああ、\だとくっつけるだけか。まぁ\nとかいちいち書かなくてもよいように出来たりしないのかなっていう疑問です

75 :デフォルトの名無しさん:2010/03/11(木) 15:35:01
ヒアドキュメント

76 :デフォルトの名無しさん:2010/03/11(木) 19:13:31
ヒアドキュメントは構文解析サボってるだけとしか思えない

77 :デフォルトの名無しさん:2010/05/02(日) 09:08:32
str="""
ここをBNFサンドボックスにしていい?
駄目なら他に行きます。
""";


19 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)