Exam-style question
Try this first
Which BNF rule generates balanced parentheses of arbitrary nesting depth, including the empty string?.
- A.<S> ::= "(" <S> ")" <S> | empty
- B.<S> ::= "(" ")"
- C.<S> ::= "(" <S> ")"
- D.<S> ::= "(" | ")" | empty
Model answer
What a good answer should say
- <S> ::= "(" <S> ")" <S> | empty
Explanation
Why this works
The rule is recursive, allowing a balanced sequence inside parentheses and another balanced sequence after it. The empty alternative provides the stopping case.
This generates strings such as the empty string, "()", "()()", and "(())".
Common mistake
No common mistake is linked to this question yet.