K.Maebashi's BBS

「プログラミング言語を作る」p43～p44にかけてのソースに、 expression /* 「式」とは… */ : primary_expression /* 「一次式」、 */ | expression ADD expression /* または、「式」 + 「式」 */ （以下略） とあるのを見て、はたと疑問に思いました。 これって、 expression /* 「式」とは… */ : primary_expression /* 「一次式」、 */ | expression ADD primary_expression /* または、「式」 + 「一次式」 */ （以下略） としなくてもよいのでしょうか？ 他のソースではそうなっているので、反射的に「あっ、間違いだ！」と思ってしまったのですが、 よく考えると、これでもいいような気がします。 一般に、「hoge は piyo の1回以上の繰り返しである」という定義を、 hoge : piyo | hoge piyo と書かずに hoge : piyo | hoge hoge と書いてはいけない理由って、何かありますでしょうか？

人に聞く前に、実験してみるべきでした。 expression /* 「式」とは… */ : primary_expression /* 「一次式」、 */ | expression ADD expression /* または、「式」 + 「式」 */ （以下略） だと、 yacc: 4 shift/reduce conflicts. となりますね。 どうしてそうなるのかは、まだ自分で説明できません……。

>expression /* 「式」とは… */ > : primary_expression /* 「一次式」、 */ > | expression ADD expression /* または、「式」 + 「式」 */ > （以下略） >だと、 >yacc: 4 shift/reduce conflicts. >となりますね。 申しわけありません。これはやはり間違いと判断すべきだと思います。 >どうしてそうなるのかは、まだ自分で説明できません……。 1 - 2 - 3 - 4 - 5 のような式のとき、 -が降ってきた時点でそれまでの分をreduceしないと左結合にならないわけですが、 現状、ここでshift/reduce conflictが起きており、shiftが優先されるため 結合規則が逆順になっています。 この構文規則は、優先順位を気にしなくてよいのなら…という文脈で出てきていた はずですし、その趣旨は構文規則を簡単にしたかったためなのですが、 結合規則まで気にしないとは書いてないですし、警告が出るのはそれ自体まずいですね。 数日中にWeb上で補足を入れます。ご指摘ありがとうございました。

ご回答ありがとうございます。 >-が降ってきた時点でそれまでの分をreduceしないと左結合にならないわけですが、 >現状、ここでshift/reduce conflictが起きており、shiftが優先されるため >結合規則が逆順になっています。 なるほどー、よく分かりました。もし右結合を明示したければ expression /* 「式」とは… */ : primary_expression /* 「一次式」、 */ | primary_expression ADD expression /* または、「一次式」 + 「式」 */ と書くべきなわけですね。 そもそも件名に「『一回以上の繰り返し』の定義」なんて書いちゃいましたが、 ただ単にそう定義するだけならレクサのレベルの話であって、 階層的な解析木を築くための構文規則を定めるのがパーサの役割だから、 結合規則によって規則の書き方が変わって当然なのですね。 結果的には誤植（？）がきっかけで非常に勉強になりました。引き続き読み進めていきます。