BNFの再帰定義で変数名の先頭をどう読むか
基本情報技術者試験 令和元年度秋期 午前 問7 ／ 基礎理論 › 情報に関する理論
過去問にチャレンジ
次のBNFで定義される＜変数名＞に合致するものはどれか。 ＜数字＞::＝ 0｜1｜2｜3｜4｜5｜6｜7｜8｜9 ＜英字＞::＝ A｜B｜C｜D｜E｜F ＜英数字＞::＝＜英字＞｜＜数字＞｜_ ＜変数名＞::＝＜英字＞｜＜変数名＞＜英数字＞
- ア
_B39
- イ
246
- ウ
3E5
- エ
F5_1
会話形式の解説
講師この問題では、変数名の最初の一文字と、その後に続けられる文字を分けて考えましょう。
受験者＜英数字＞には数字と下線もあります。どちらも先頭に使えるのでしょうか。
講師まず、＜変数名＞を一文字だけで成立させるには何を選びますか。
受験者＜英字＞です。先頭はAからFのどれかになります。
講師その通りです。先頭が下線の文字列は、下線の前に成立した変数名がないので、定義に合いません。
受験者先頭が2の数字だけの文字列も、出発点の＜英字＞を満たせませんね。
講師はい。途中にEがある文字列も、最初が3なので同じ理由で合いません。
受験者では、Fで始まる文字列は、Fだけで変数名が成立しますね。
講師成立します。その後の5、下線、1はいずれも＜英数字＞なので、一文字ずつ追加できます。正解はF5_1です。
受験者追加できる文字の種類だけで判断せず、先頭に英字があるかを先に確認するのですね。
講師はい。定義の中に同じ＜変数名＞が現れるため、成立した変数名に文字を繰り返し追加できます。
まとめ
このBNFでは、変数名はAからFの英字一文字から始まります。成立した変数名の末尾には、英字・数字・下線を一文字ずつ追加できます。先頭が下線や数字の候補は条件を満たさず、F5_1が定義に合致します。
解答・解説
正解はエです
この問題のテーマ
BNFの再帰的な定義を読み、変数名として使える文字の並びを判定する問題です。
解き方の考え方
まず、＜変数名＞は＜英字＞だけでも成立するので、先頭はA～Fのいずれかだと分かります。次に、成立した＜変数名＞の末尾へ＜英数字＞を一文字ずつ追加できます。各選択肢の先頭と、それ以降の文字をこの順に確認します。
選択肢ごとの解説
- ×ア _B39アの「_B39」は、最初の文字が「_」です。「_」を追加できるのは、先に変数名が成立している場合なので、先頭には置けません。
- ×イ 246イの「246」は、最初の「2」が数字です。数字だけを並べても、変数名の出発点となる＜英字＞を満たせません。
- ×ウ 3E5ウの「3E5」も、最初の「3」が数字です。途中の「E」は使える英字ですが、先頭の数字を許す定義にはなっていません。
- ○エ F5_1エの「F5_1」は、「F」だけで変数名が成立します。続く「5」「_」「1」はいずれも＜英数字＞に含まれ、一文字ずつ追加できるため、定義に合致します。
POINT
- BNFの「｜」は、並んだ候補のいずれかを選べることを示します。
- 定義の中に同じ＜変数名＞が現れるため、条件に合う文字を繰り返し追加できます。
- 文字列全体を判定するときは、先頭の条件を確認してから後続の条件を確認します。