次のようなBNFで定義された文法を考える。
<p> ::= <q> | <q> '#' <p>
<q> ::= <r> | <q> '@' <r>
<r> ::= 'x' | 'y' | '(' <p> ')'
ここで、< > で囲まれたものは非終端記号、' ' で囲まれたものは終端記号とし、# と @ は二項演算子である。また、括弧 ( と ) は、通常の数式での利用と同じように、二項演算子に対するオペランドを明示するために用いるものとする。さらに、開始記号を<p>とする。このとき、次の記述のうち、最も適切なものを選べ。
① この文法は曖昧である。
② 二項演算子 # と @ は、ともに左結合である。
③ @ より # の方が演算子の優先順位が高い。
④ y # (x @ y # x) の括弧は冗長であり、なくても意味は変わらない。
⑤ この文法は正規文法である。
④
① 曖昧なく定義されており、問題ない。
② 二項演算子 # は、<q> '#' <p> により、x # y # z は x # (y # z) となり、右結合である。
二項演算子 @ は、<q> '@' <r> により、x @ y @ z は (x @ y) @ z となり、左結合である。
③ 二項演算子 @ の方が優先順位が高い。
④ 正しい。二項演算子 @ の方が優先順位が高く右結合、二項演算子 # は左結合であるため、
y # x @ y # x
= y # (x @ y) # x
= y # ((x @ y) # x) である。
一方、y # (x @ y # x) = y # ((x @ y) # x) である。
⑤ 正規文法は文字列の生成規則を定義するものである。
x # y や x @ y を <p> や <q>として認識できないため、定義できない。
| Ⅳ－４ | 目次 | Ⅳ－６ |