ITPEC FE Morning April 2023 Question 5
Which of the following matches the <variable-name> defined below in BNF?
<number> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> :: = A | B | C | D | E | F
<letter-and-number> :: = <letter> | <number> | _
<variable-name> :: = <letter> | <variable-name><letter-and-number>
Explanation
F5_1 — a variable name must start with a letter A to F, followed by any mix of letters, digits and underscores.
The rule <variable-name> ::= <letter> | <variable-name><letter-and-number> builds a name from left to right. It starts as a single <letter>, and each recursive step appends one <letter-and-number>, which is a letter, a digit or _. So the first character must be one of A to F, and anything from the three groups may follow.
F5_1: F is a <letter>, then 5, _ and 1 are each a <letter-and-number>, so it matches.
Answer (d)
Why not others:
- •(a) _B39 — starts with
_, which may appear only after the first character - •(b) 246 — starts with a digit and contains no letter at all
- •(c) 3E5 — starts with a digit;
Eand5would be fine later in the name
Key rule: In a left-recursive rule of the form X ::= a | X b, the base case fixes the first symbol and the recursive part says what may follow it.
Basic Theory · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.