「コンパイラ・スクリプトエンジン」相談室16 (649ﾚｽ)
上下前次1-新
121(2): 2014/12/06(土)17:17 ID:djm9MkQZ(1) AAS
演算子の優先順位はどうしてんの？
122: 2014/12/06(土)17:30 ID:5oGFUyw+(1/2) AAS
べつに区切り文字が = だろうが : だろうが ::= だろうが BNF は BNF だ
123(1): 117 2014/12/06(土)23:05 ID:BPhK2Nlg(1/3) AAS
>>120
>みんなBNFとかやってるのか
JavaCCの場合字句解析でトークン列に分解してくれて、
>>117にあるようにそのトークンの並びを書いて構文解析の定義をします。
なのでBNF記法とは違った書き方になります。
>>121
>演算子の優先順位はどうしてんの？
いい説明文が思い浮かばないので、
まずは例として1+2*3/4-5という式を構文木にしたものを以下にアップします。
外部ﾘﾝｸ:fast-uploader.com
こんなかんじのまとまりです。
演算子：/ 左辺：3(enzan5) 右辺：4(enzan5) → ?(enzan4)
演算子：* 左辺：2(enzan5) 右辺：?(enzan4) → ?(enzan4)
演算子：- 左辺：?(enzan4) 右辺：5(enzan5) → ?(enzan4)
演算子：+ 左辺：1(enzan5) 右辺：?(enzan4) →?(enzan3)
124: 117 2014/12/06(土)23:06 ID:BPhK2Nlg(2/3) AAS
とりあえずenzan3の定義の先頭にマイナスの記号があるかもしれないという意味合いで
以下のようなコードに変えてみました。
void enzan3() :
{}
{
[<HIKU>]enzan4() //★
((<TASU>|<HIKU>)enzan4())*
}
void enzan4() :
{}
{
enzan5()
((<KAKERU>|<WARU>)enzan5()
}
void enzan5() :
{}
{
<MOZI>|<SUUZI>|"(" enzan3() ")"
}
<>：トークン |：左右のどちらかの構文(||やOr演算子のようなもの) []：省略可能構文
125: 117 2014/12/06(土)23:07 ID:BPhK2Nlg(3/3) AAS
すると、以下のような警告が出ました。
Warning: Choice conflict in (...)* construct at line 608, column 9.
Expansion nested within construct and expansion following construct
have common prefixes, one of which is: <HIKU>
Consider using a lookahead of 2 or more for nested expansion.
内容は選択の突出(Choice conflict)と言うもので、
私が作った構文の定義があいまいのようで
608行目(ここでは★を付けた行)の定義が他の定義とかぶっているらしく、
先頭に出てくる<HIKU>トークンが共通点らしいです。
そもそもの考え方が間違っているかもしれませんが、
それを抜きにしてもまずなぜこのような警告が出ているかわかりません。
一体なぜ出ているかわかる人いれば教えてださい。
126: 2014/12/06(土)23:08 ID:q7blqefO(1) AAS
>>120
java（というよりC）のforは()の内部に;が出てくるのが
>>119
javaccの書き方と大差ないみたいよ
127(1): 2014/12/06(土)23:27 ID:5oGFUyw+(2/2) AAS
この文脈でconflictは「衝突」と言う。
そのメッセージの通り、複数の定義で共通してるトークンがあるから、どっちの定義のほうだとして
解釈していいかわからないからエラーになる。
そのメッセージでは「Consider using a lookahead of 2 or more for nested expansion.」2個あるいはそれ以上の
先読みを使うことを検討してみろ、と言っているが、それに従ったところでうまくいくかどうかは
わからんけどね。
128(2): 2014/12/07(日)01:31 ID:bfkTF4nN(1/3) AAS
>>123
>>121は重要なヒント
-(1+2)とか、1+(-2)とかにその定義で対応できる？
たとえば★の行をenzan5に移してみるなり、演算子の優先順位を変えてやりなおすとか
それとは関係ないけど、3*2/4って直感的には( (3 * 2) / 4 )になりそうだけどその構文木だと右から左なのね
129: 2014/12/07(日)01:36 ID:bfkTF4nN(2/3) AAS
>>128
勘違いしたわすれて
130(1): 117 2014/12/07(日)21:58 ID:OacxF8nB(1) AAS
>>127
選択の衝突でしたね。
間違えて覚えました；
かぶってるらしいからLOOKAHEADで先読みをしなくてはならないのはわかるのですが、
そのコードでどのパターンとどのパターンでかぶってるのかがわからなくて。
>>128
>-(1+2)とか、1+(-2)とかにその定義で対応できる？
1+(-2)のパターンは意識していましたが、-(1+2)のパターンは忘れてました。
きちんと考えなおしてきます。
131: 2014/12/07(日)22:37 ID:bfkTF4nN(3/3) AAS
>>130
試しに四則演算のみ行う言語をjavaccで作ってみたけど単行演算子程度ならLookAheadいらないよ
132(1): 117 2014/12/08(月)00:25 ID:yQ2quuvD(1/3) AAS
いろいろ考えているうちに構文規則がおかしなことになってきました；
とりあえず負の数やかっこを含む数式の構文木を一通り考えてみたつもりなんですけど、
以下のような感じであっているでしょうか？
外部ﾘﾝｸ:fast-uploader.com
また、他に欠けているパターンはないでしょうか？
133(1): 2014/12/08(月)18:02 ID:3czqE9B9(1) AAS
>>132
単項演算子はどこに行ったんだ
134: 117 2014/12/08(月)21:29 ID:yQ2quuvD(2/3) AAS
>>133
あれは構文木と言うより抽象構文木というか内部構造と言うかそんなかんじのものですね；
負の数をどう計算するか考えてたらその式や数字に-1をかければいいかなと思って作ってました。
今度はきちんと抽象じゃない構文木を考えます。 はい。
135: 117 2014/12/08(月)23:27 ID:yQ2quuvD(3/3) AAS
とりあえず自分がわかっている範囲で -(1+2)*4 の解析木を作ってみました。
外部ﾘﾝｸ:fast-uploader.com
enzan番号という名前はやめてみました。
空欄部分は下位置調節のためや何を入れたらいいかわからない部分です。
136(1): 117 2014/12/09(火)21:43 ID:KYZ3f1RL(1/3) AAS
構文規則作ってみましたが、選択の衝突が消えません。
tasuhikuのkakewaruをkakewaru2に変えると消えます。
kakewaruで呼んでるminusの[<HIKU>]がtasuhikuの<HIKU>と競合しているのかと思いましたが、
なぜなのかわかりません。
どこが間違っているでしょうか？
警告なのでとりあえず無視してjavacコンパイルして解析＆実行させてみると、以下の式はきちんと実行できました。
1+2+3
-9-3
1+2*3/4-5
7+(-2)
-6*2
-(1+2)*4
(-1+2)*4
-1+2*4
4-(-2/5)
-(-(-39))/13
一応ある程度のパターンを網羅していると思います。
Warning: Choice conflict in (...)* construct at line 608, column 9.
Expansion nested within construct and expansion following construct
have common prefixes, one of which is: <HIKU>
Consider using a lookahead of 2 or more for nested expansion.
137: 117 2014/12/09(火)21:44 ID:KYZ3f1RL(2/3) AAS
void tasuhiku():
{}
{
kakewaru() //608行目
((<TASU>|<HIKU>)kakewaru2())*
}
void kakewaru():
{}
{
minus()
((<KAKERU>|<WARU>)sikikakko())*
}
void kakewaru2():
{}
{
sikikakko()
((<KAKERU>|<WARU>)sikikakko())*
}
138: 117 2014/12/09(火)21:45 ID:KYZ3f1RL(3/3) AAS
void minus():
{}
{
[<HIKU>]sikikakko()
}
void sikikakko():
{}
{
("(" tasuhiku() ")"
|atai())
}
void atai():
{}
{
<SUUZI>
}
139(1): 2014/12/10(水)06:22 ID:ICK0nNNi(1) AAS
荒らされてるなぁ・・・
140(1): 2014/12/10(水)14:14 ID:lFxVBhH5(1/5) AAS
>>136
文法作るのはものすごく難しいんだよ。
同じ文書を受理する複数の文法が存在し、複数の間で優劣がある。
しかも、優劣を機械的に評価することが難しい。
「こいつを使えば簡単にできる」というようなソフトウェア紹介を見かけると
思うけど、そんな魔法の杖みたいなソフトは無いから。
そういうこと言ってる人は、付属してきたサンプルを動かして簡単といってるだけ。
信じちゃだめだ。
構文解析器の生成系を自分で作れるようにならないと文法を作れないと思っていい。
少なくともその程度の理解は必要。
まずドラゴンブックを買ったらどうかと思うんだが。
141(1): 2014/12/10(水)14:18 ID:lFxVBhH5(2/5) AAS
まずドラゴンブックを買う。
実際に作ってみる。
この作ったものは実用にはならないよ。
テーブルが大きすぎるからね。
それでも作ることが重要。
その後に、市中に出回る生成系を使ってみたらどうだろう。
俺はこの順番が良いと思うよ。
中身の動作を知らないと使えないって、ツールとしては下等だけど、
今はまだその程度の世界なんだよ。
142(1): 117 2014/12/10(水)16:50 ID:pQyEQrGQ(1/3) AAS
>>139
私のことだったら荒らそうと言うつもりは全くありません。
でも荒らしに見えてしまっていたならすいません。
>>140-141
ドラゴンブックってこれのことですかね？
外部ﾘﾝｸ:www.amazon.co.jp
(私にとって)安くないですし今そこから勉強している余裕はないので・・・。
すいません。
よそでパーサジェネレータ使った方がいいとか言われて、
Javaが好きなどの理由でJavaCCを使うようになりました。
なんにせよ周りに作ったことある人とかいないので、
外部ﾘﾝｸ[html]:www.sbcr.jp
とか
外部ﾘﾝｸ:item.rakuten.co.jp
とか片手に独学でやってます。
143(2): 2014/12/10(水)17:17 ID:lFxVBhH5(3/5) AAS
>>142
そこが勘違いなんだよ。
JavaCCを使うにはJavaCCを作れる程度の知識が必要。
だからドラゴンブックが必須。
ドラゴンブックは決して読みやすい書籍ではないよ。
どうとでもとれる表現がいくつもある。
読み解きながら理解する必要があるので、結局生成系を自分で一つ書き上げる必要がある。
「JavaCCを使えば知識がなくてもこんなに簡単」的なことを書く人は
実はJavaCCを使っていないんだよ。
そこに騙されてはいけない。
文法を作るには深い理解が必要なんだよ。
簡単にできる方法はない。
144(1): 2014/12/10(水)18:27 ID:eXNtCHKb(1/2) AAS
誰か別の人にやってもらえばいいんだよ。クラウドソーシングとかあるじゃん。
145(1): 2014/12/10(水)21:11 ID:Lctd7lUm(1/2) AAS
荒らされてるんじゃなくて話題がなさすぎるから一人が専有してるように見えるだけだろ？
146(1): 117 2014/12/10(水)21:46 ID:pQyEQrGQ(2/3) AAS
>>143
>「JavaCCを使えば知識がなくてもこんなに簡単」的なことを書く人は
そこまで言われたことはないです。
一番最初は文字列を自分で解析するところからやろうとしてましたけど、
パーサジェネレータを知ってからわたしにとってはそっちの方が楽だと感じています。
ここで質問したこと以外でも詰まったりもしましたけども、
もし構文解析ツールを1から作っていたらきっとここまでたどり着くまでにもっと詰まっていると思います。
>>144
すいません。
実はこれ卒業研究なので・・・。
自分で作ってみたい→卒研のテーマに悪くないよね？
な感じで決めてしまったテーマです。
>>145
連投とかしすぎましたかね・・・；
147(1): 2014/12/10(水)21:57 ID:dcz7kjCK(1) AAS
指導教授に聞けば。
148(1): 2014/12/10(水)22:28 ID:ZSLSh1LL(1) AAS
www
卒研なら自分で考えいw
149(1): 2014/12/10(水)22:32 ID:eXNtCHKb(2/2) AAS
>>146
まさか卒業研究の本体がなんの新規性もない構文解析なわけじゃないだろう。
それが本質的な部分じゃなければ人に手伝ってもらうのもありだよ。
もし、構文解析そのものが君の卒業研究なら……
楽してでっち上げるという考えは即座に捨てて、143のいうようにちゃんと勉強して理解しな。
150(1): 2014/12/10(水)22:55 ID:Lctd7lUm(2/2) AAS
卒研かよ
フォローして損した
上下前次1-新書関写板覧索設栞歴
あと 499 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.013s