K.Maebashi's BBS

ご自由に書き込んでください。雑談も可。
テスト書き込みの類はテスト用掲示板にどうぞ

[日付順表示] [日付順インデックス] [スレッド順インデックス]


新規投稿 | 開設者ホームページへ戻る | ヘルプ


[1509] 「1回以上の繰り返し」の定義
返信


投稿者:yuya
2010/03/08 09:19:49

Link:
「プログラミング言語を作る」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

と書いてはいけない理由って、何かありますでしょうか?
[ この投稿を含むスレッドを表示] [ この投稿を削除]



[1510] Re:「1回以上の繰り返し」の定義
返信


投稿者:yuya
2010/03/09 10:18:47

Link:
人に聞く前に、実験してみるべきでした。

expression /* 「式」とは… */
        : primary_expression  /* 「一次式」、 */
        | expression ADD expression /* または、「式」 + 「式」 */
        (以下略)

だと、

yacc: 4 shift/reduce conflicts.

となりますね。

どうしてそうなるのかは、まだ自分で説明できません……。
[ この投稿を含むスレッドを表示] [ この投稿を削除]



[1511] Re:「1回以上の繰り返し」の定義
返信


投稿者:(ぱ)こと管理人
2010/03/10 03:09:06

Link:http://kmaebashi.com
>expression /* 「式」とは… */
>        : primary_expression  /* 「一次式」、 */
>        | expression ADD expression /* または、「式」 + 「式」 */
>        (以下略)
>だと、
>yacc: 4 shift/reduce conflicts.
>となりますね。

申しわけありません。これはやはり間違いと判断すべきだと思います。

>どうしてそうなるのかは、まだ自分で説明できません……。

1 - 2 - 3 - 4 - 5

のような式のとき、
-が降ってきた時点でそれまでの分をreduceしないと左結合にならないわけですが、
現状、ここでshift/reduce conflictが起きており、shiftが優先されるため
結合規則が逆順になっています。

この構文規則は、優先順位を気にしなくてよいのなら…という文脈で出てきていた
はずですし、その趣旨は構文規則を簡単にしたかったためなのですが、
結合規則まで気にしないとは書いてないですし、警告が出るのはそれ自体まずいですね。

数日中にWeb上で補足を入れます。ご指摘ありがとうございました。
[ この投稿を含むスレッドを表示] [ この投稿を削除]



[1512] Re:「1回以上の繰り返し」の定義
返信


投稿者:yuya
2010/03/10 14:48:02

Link:
ご回答ありがとうございます。

>-が降ってきた時点でそれまでの分をreduceしないと左結合にならないわけですが、
>現状、ここでshift/reduce conflictが起きており、shiftが優先されるため
>結合規則が逆順になっています。

なるほどー、よく分かりました。もし右結合を明示したければ

expression /* 「式」とは… */
        : primary_expression  /* 「一次式」、 */
        | primary_expression ADD expression /* または、「一次式」 + 「式」 */

と書くべきなわけですね。

そもそも件名に「『一回以上の繰り返し』の定義」なんて書いちゃいましたが、
ただ単にそう定義するだけならレクサのレベルの話であって、
階層的な解析木を築くための構文規則を定めるのがパーサの役割だから、
結合規則によって規則の書き方が変わって当然なのですね。

結果的には誤植(?)がきっかけで非常に勉強になりました。引き続き読み進めていきます。
[ この投稿を含むスレッドを表示] [ この投稿を削除]