左再帰について

質問

次のBNFが左再帰であるかないかを判定し、その根拠を説明せよ。
<A> ::=<B>|<C>|<C>
<B> ::=if<C>then<A>
<C> ::=a|b|c
<D> ::=<A>while<C>

これを簡単でいいので教えてください。

できれば左再帰とは何かも教えてください。

回答No.1

sakusaker7 · ベストアンサー

>これを簡単でいいので教えてください。
>できれば左再帰とは何かも教えてください。

後半だけ。

左再帰というのは、構文定義において
左辺にある非終端記号が右辺の最初の項目に現れるってことです。
#思いっきりざっくり。

たとえば「足し算」という構文を考えたときに

<式> ::= <式> + <数> | <数>
<数> ::= 0|1|2|3|4|5|6|7|8|9

みたいなのがわかりやすい例。
で、左再帰には直接左再帰と間接左再帰があって
上の例は直接左再帰。
間接左再帰はいくつかの規則を辿った末に
再帰が出てくるというもの。

ということで
>次のBNFが左再帰であるかないかを判定し、その根拠を説明せよ。
脳みそ絞って頑張れ :)

http://nicosia.is.s.u-tokyo.ac.jp/pub/staff/hagiya/kougiroku/compiler/ll
Bison 1.28 - 用語集
http://lmj.nagaokaut.ac.jp/gnu_manual/bison-1.28/bison-ja_14.html