Backus-Naur Form (BNF)/syntax diagrams — AQA A-Level Computer Science
Backus-Naur Form (BNF) and syntax diagrams are formal meta-languages used in Computer Science to unambiguously define the syntax of programming languages and data formats. In AQA A-Level Computer Science, students must master reading, writing, and interconverting recursive and non-recursive grammar rules using both notations.
Backus-Naur Form (BNF)/syntax diagrams explained
Backus-Naur Form (BNF) and syntax diagrams are formal metalinguistic notations used to define the syntax of programming languages and formal grammars unambiguously.
Read the full explanation
In BNF, production rules have a non-terminal on the left-hand side enclosed in angle brackets, a definition symbol (::=), and an expression of terminals and non-terminals on the right-hand side, with vertical bars (|) separating alternatives. For example, given the rules: <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 and <number> ::= <digit> | <digit><number>, the string '42' can be derived through the sequence <number> => <digit><number> => 4<number> => 4<digit> => 42. Syntax diagrams represent the same rules graphically using directed paths, with non-terminals in rectangles and terminals in circles or ovals.
Your focus
- Be able to check language syntax by referring to BNF or syntax diagrams and formulate simple production rules.
Which command word is this?
Construct a clear syntax diagram using precise conventions: directional arrows, sharp-cornered rectangles for non-terminals, and circles or rounded ovals for terminals.
Backus-Naur Form (BNF)/syntax diagrams exam tips
Topic Overview
Backus-Naur Form (BNF) and syntax diagrams (also known as railroad diagrams) are formal meta-languages used to define the exact grammar and syntax of programming languages, communication protocols, and file formats. They provide an unambiguous set of rules determining whether a given string of symbols is syntactically valid in a given language.
Within the AQA A-Level specification, these formalisms are central to understanding compiler design and the syntax analysis phase of compilation. Mastering BNF and syntax diagrams allows students to conceptualise context-free grammars, parse tree generation, and recursive language constructs.
Key Concepts
- →Terminal vs Non-Terminal Symbols: Terminal symbols are literal characters or tokens that appear directly in the program code (represented in quotes in BNF and circles/ovals in syntax diagrams). Non-terminals are higher-level syntactic abstractions defined by further rules (enclosed in angle brackets <> in BNF and rectangles in syntax diagrams).
- →BNF Meta-Symbols: The symbol '::=' means 'is defined as', and the vertical bar '|' denotes an alternative (OR).
- →Recursion for Repetition: BNF cannot use loops directly, so repetition is achieved using recursion where a non-terminal rule calls itself (e.g., <number> ::= <digit> | <digit><number>).
- →Syntax Diagrams: Graphical representations where directed arrows dictate valid parsing flow. Branching paths represent alternatives, and backwards loops represent repetition.
Marking Points
- Explains that BNF specifies valid language syntax using production rules.
- Identifies non-terminals enclosed in angle brackets and terminals as literal symbols.
- Interprets ::= as 'is defined as' and | as alternative choices.
- Demonstrates deriving a valid string from given production rules step by step.
- Translates between BNF production rules and equivalent syntax diagrams.
Examiner Tips
- 💡Show each step of a BNF derivation clearly, replacing one non-terminal at a time.
- 💡In syntax diagrams, follow the arrow paths from left to right to test whether a string is valid.
- 💡Always state clear ellipses ('...') when listing digits or letters in exams if permitted, but ensure you include the boundary items (e.g., '0' | '1' | ... | '9').
- 💡When converting from a syntax diagram to BNF, trace all parallel branches first to identify choices ('|'), then identify backward loops to construct recursive non-terminals.
- 💡Remember that whitespace is significant in BNF unless explicitly defined otherwise; do not leave spaces between non-terminals if tokens must be adjacent.
Common Mistakes
- Derives a terminal symbol not defined in the production rules; correct by ensuring all characters exist in the terminal set.
- Confuses terminals and non-terminals; correct by remembering non-terminals require further substitution while terminals do not.
- Omits recursive expansion when deriving multi-character tokens.
- Believing BNF specifies what code does (semantics): BNF defines only structure and valid token ordering (syntax), not variable types, runtime logic, or semantic correctness.
- Confusing zero-or-more with one-or-more repetition: Students frequently write recursive rules that mandate at least one recursive step, making single-element inputs invalid.
- Using regular assignment '=' instead of '::=': In AQA mark schemes, using '=' or '->' instead of the strict BNF meta-symbol '::=' can result in lost marks.
Revision Plan
- 1Day 1-2: Master BNF fundamentals, learning meta-characters (::=, |, <>) and differentiating terminal vs non-terminal symbols.
- 2Day 3-4: Practice writing recursive BNF definitions for common structures like integers, signed floats, and lists.
- 3Day 5-6: Study syntax diagram conventions, practicing conversions from BNF to syntax diagrams and vice versa.
- 4Day 7: Work through past AQA exam questions on BNF validation and parsing traces under timed conditions.
Exam Question Types
- 📋Conversion questions: Translating a BNF definition into a visual syntax diagram or converting a railroad diagram into formal BNF rules.
- 📋Grammar production writing: Writing BNF rules from a written English specification (e.g., valid IP addresses, variable names, or arithmetic formulas).
- 📋Syntax validation questions: Determining whether specific example input strings are valid or invalid according to a provided BNF grammar or syntax diagram, justifying your decision.
Command Word Expectations (AQA)
Construct a clear syntax diagram using precise conventions: directional arrows, sharp-cornered rectangles for non-terminals, and circles or rounded ovals for terminals.
Produce syntactically valid BNF rules using correct meta-symbols ('::=', '|', and angle brackets around non-terminals) that completely satisfy the specification.
Identify why a given string passes or fails the grammar, tracing through specific production rules or branches step-by-step.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: A programming language identifier must start with a lowercase letter ('a'-'z'), optionally followed by any combination of lowercase letters or digits ('0'-'9'). Using Backus-Naur Form (BNF), write production rules to define <identifier>.
- 1.Step 1: Define the terminal sets for lowercase letters and digits. <letter> ::= 'a' | 'b' | ... | 'z' and <digit> ::= '0' | '1' | ... | '9'.
- 2.Step 2: Define a character that can follow the initial letter, which can be either a letter or a digit: <char> ::= <letter> | <digit>.
- 3.Step 3: Define a recursive tail to represent 'any combination of letters or digits' (zero or more): <tail> ::= '' | <char><tail> (or define non-empty sequence and handle optionality). Alternatively, define <identifier> directly: <identifier> ::= <letter> | <identifier><char>.
- 4.Step 4: Verify that the rule guarantees the first character is strictly a letter, followed by zero or more characters.
Question: Consider the BNF rule: <expression> ::= <term> | <expression> '+' <term>. Draw the equivalent syntax diagram flow for <expression>.
- 1.Step 1: Identify that <term> is a non-terminal symbol (drawn in a rectangle) and '+' is a terminal symbol (drawn in a circle/oval).
- 2.Step 2: Identify the base case: the main path runs through a non-terminal box labelled '<term>' directly to the exit.
- 3.Step 3: Identify the recursion: an expression can continue with '+' followed by another <term>. This creates a feedback loop.
- 4.Step 4: Draw the loop: after passing through <term>, an arrow loops back, passing through an oval containing '+' and then re-entering before or through <term>.