高校卒業後就職したのですが不況のあおりでリストラされ暇になってしまい仕

質問

高校卒業後就職したのですが不況のあおりでリストラされ暇になってしまい仕事を探す傍ら独学で勉強している者です。

問題集をしているとこのような問題があったのですがいまいち分かりません。

文脈自由文法で書きなさい．
<式> ::= <式> + <項> | <式> - <項> | <項>
<項> ::= <項> * <因子> | <項> / <因子> | <因子>
<因子> ::= -<因子> | <数字> | (<式>)

非常に古い問題集なので解答がついておらず、ネットで色々探したのですが解き方が分かりません。
誰か教えていただけないでしょうか。

回答No.1

sinisorsa · ベストアンサー

文脈自由文法の定義はご存じですか。
G=<N,T,P,S>
ただしNは非終端記号の集合。この問題では、＜＞で括られた記号。たとえば、＜式＞など
Tは終端記号の集合。この問題では、変数がありませんので、数字の０から９、＋、－、＊、／、（、）
　T＝｛0,1,2,3,4,5,6,7,8,9,+,-,*,/,(,)｝
N＝｛<式>、<項>、<因子>,<数字>｝
　Sは開始記号　＝＜式＞
Pは生成規則の集合です。すべての生成規則の左辺が１個の非終端記号となっている
場合、文脈自由文法と言います。
問題にある規則はBNF（バッカス・ナウアー標準形）による表記です。
これを書き直せばよい。
たとえば、<式> ::= <式> + <項> | <式> - <項> | <項>　は
＜式＞→＜式＞＋＜項＞
＜式＞→＜式＞－＜項＞
＜式＞→＜項＞
の３つの生成規則になります。以下はご自分で
問題に書いていない規則も必要になります。
＜数字＞は１文字の数字の意味とすると、
＜数字＞→０、＜数字＞→１、・・・、＜数字＞→９　まで１０個の規則
＜数字＞が複数桁までありうるとすると、もっと複雑になりますが、
この問題ではそこまで想定していないように思います。
もしかすると、BNF形式を生成規則の形式に変えるだけでよいのかもしれません。