平成30年度 III-7

解説

この問題で問われていること

二項演算を左右のどちらにも結合できる曖昧な文法で、式の構文木が何通りできるかを数える問題。

解き方

① 優先順位のない文法では、演算子n個の式の構文木の数=括弧の付け方の数(カタラン数: 1個→1、2個→2、3個→5、4個→14)
② x−3+y−5は演算子3個
③ 5通り(②)

正解が正しい理由

文法は、<式>::=<式><演算><式>で、演算の結合順序に制約がない。式x−3+y−5は、4つのオペランドと3つの演算子から成る。このような式の構文木の数は、括弧の付け方の数に等しい。演算子が3つの場合の、括弧の付け方は、カタラン数C3=5通りである。具体的には、((x−3)+y)−5、(x−(3+y))−5、(x−3)+(y−5)、x−((3+y)−5)、x−(3+(y−5))の5通り。したがって②が正しい。

各選択肢について

• ① 4通りでは、構文木の数が足りない。
• ② 演算子3つの括弧付けは、カタラン数C3=5通りで、正しい。これが正答。
• ③ 6通りは、カタラン数とは一致しない。
• ④ 7通りは、カタラン数とは一致しない。
• ⑤ 8通りは、カタラン数とは一致しない。

覚えるべきポイント

n個の二項演算子を含む式の、括弧付け(構文木)の数は、カタラン数C_n(C1=1、C2=2、C3=5、C4=14)。優先順位や結合規則がない曖昧な文法では、すべてが有効な構文木となる。