
出典:公益社団法人 日本技術士会「技術士第一次試験 過去問題」
BNF(バッカス・ナウア記法)で与えられた文法(名詞句、助詞句、形容詞句)に従った名詞句「明るい色の新しい本」の構文木(導出木)が何通りあるかを求める問題(文法の曖昧性)。
曖昧な文法に対する、1つの文の構文木の数を数える問題。
① 構文木の数え方: 文全体(形・名・助・形・名)に当てはまる規則を1つずつ試し、中身がさらに規則どおりに分けられるか確かめる
② 当てはまるのは<形容詞句>名(「明るい色の新しい」+本)、形<形容詞句>名(明るい+「色の新しい」+本)、<助詞句>形 名(「明るい色の」+新しい+本)の3通り。<助詞句>名 と 形 名 は形が合わない
③ 3通り(③)
文は、形容詞(明るい)、名詞(色)、助詞(の)、形容詞(新しい)、名詞(本)の並びである。名詞句の規則のうち、この文全体に適用できるのは次の3通りである。(1)<形容詞句>“名詞”: 形容詞句=「明るい色の新しい」(助詞句「明るい色の」+形容詞「新しい」)+名詞「本」。(2)“形容詞”<形容詞句>“名詞”: 形容詞「明るい」+形容詞句「色の新しい」(助詞句「色の」+形容詞)+名詞「本」。(3)<助詞句>“形容詞”“名詞”: 助詞句「明るい色の」(名詞句「明るい色」+助詞「の」)+形容詞「新しい」+名詞「本」。他の規則(<助詞句>“名詞”、“形容詞”“名詞”)は、末尾や構成が合わず適用できない。したがって構文木は3通りで、③が正しい。
1つの文に対して複数の構文木が存在する文法は曖昧である。BNFの各規則を、文の区間に順に当てはめ、各規則で分割できる構成の数を足し合わせて数える。
キーワード: BNF、構文木、導出木、文法の曖昧性、形式言語、構文解析、情報工学部門