Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Day 1-2: Master BNF fundamentals, learning meta-characters (::=, |, <>) and differentiating terminal vs non-terminal symbols.
    2. 2Day 3-4: Practice writing recursive BNF definitions for common structures like integers, signed floats, and lists.
    3. 3Day 5-6: Study syntax diagram conventions, practicing conversions from BNF to syntax diagrams and vice versa.
    4. 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)
    Draw

    Construct a clear syntax diagram using precise conventions: directional arrows, sharp-cornered rectangles for non-terminals, and circles or rounded ovals for terminals.

    Write

    Produce syntactically valid BNF rules using correct meta-symbols ('::=', '|', and angle brackets around non-terminals) that completely satisfy the specification.

    Explain

    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)
    Pitfall: Omitting the base case in recursive BNF definitions, which leads to an infinite sequence requiring at least one recursive expansion.
    ❌ Weak Answer (Loses Marks):A variable name list is defined as: <var_list> ::= <variable> ',' <var_list>
    Example improved answer:<var_list> ::= <variable> | <variable> ',' <var_list>
    Examiner Tip: Always test your recursive BNF rule with both the simplest possible input (base case, e.g., a single item) and multi-item inputs to ensure the rule terminates correctly.
    Pitfall: Mixing up terminal and non-terminal symbols, or using incorrect shapes in syntax diagrams (e.g. using rectangles for terminal literals).
    ❌ Weak Answer (Loses Marks):Drawing a rectangular box around literal characters such as '+' or 'IF' in a syntax diagram.
    Example improved answer:Terminal symbols (literals that cannot be broken down further) must strictly be drawn in circles or rounded boxes (ovals), while non-terminal symbols (syntactic variables defined elsewhere) must be drawn in sharp-cornered rectangles.
    Examiner Tip: Check every shape in your syntax diagram: if it appears in quotes or is a literal character in BNF, it must be enclosed in an oval or circle.
    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. 1.Step 1: Define the terminal sets for lowercase letters and digits. <letter> ::= 'a' | 'b' | ... | 'z' and <digit> ::= '0' | '1' | ... | '9'.
    2. 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. 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. 4.Step 4: Verify that the rule guarantees the first character is strictly a letter, followed by zero or more characters.
    Final Answer: <letter> ::= 'a' | 'b' | 'c' | ... | 'z' <digit> ::= '0' | '1' | '2' | ... | '9' <char> ::= <letter> | <digit> <identifier> ::= <letter> | <identifier><char>

    Question: Consider the BNF rule: <expression> ::= <term> | <expression> '+' <term>. Draw the equivalent syntax diagram flow for <expression>.

    1. 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. 2.Step 2: Identify the base case: the main path runs through a non-terminal box labelled '<term>' directly to the exit.
    3. 3.Step 3: Identify the recursion: an expression can continue with '+' followed by another <term>. This creates a feedback loop.
    4. 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>.
    Final Answer: A main horizontal rail passing through a rectangular box labelled '<term>'. From the exit side of '<term>', a return loop travels back over the top through a circular/oval box containing '+' and re-enters the track before '<term>'.
    Active Recall Memory Test
    What do rectangles and circles/ovals represent in a syntax diagram?
    Key Fact: Rectangles represent non-terminal symbols; circles or ovals represent terminal symbols.
    How is repetition represented in Backus-Naur Form (BNF)?
    Key Fact: Through recursion, where a non-terminal rule includes itself in its own definition.
    What is the difference between a terminal symbol and a non-terminal symbol?
    Key Fact: A terminal symbol is a literal character or token that cannot be broken down further, whereas a non-terminal symbol is a placeholder variable defined by production rules.
    What does the symbol '::=' represent in BNF?
    Key Fact: 'is defined as'.
    Frequently Asked Questions
    Why do we use BNF instead of Regular Expressions in computer science?
    Regular expressions can only define regular languages and cannot handle nested or balanced structures like matched parentheses, nested blocks, or recursive mathematical expressions. BNF defines context-free grammars, making it powerful enough to specify the complete hierarchical syntax of complex programming languages.
    What is the difference between BNF and EBNF?
    Extended Backus-Naur Form (EBNF) is an extension of BNF that introduces shorthand operators for common patterns, such as square brackets for optional items `[...]` and curly braces for repetition `{...}`. Standard BNF requires recursion to express repetition and explicit alternatives to express optional elements.
    Can a syntax diagram have more than one entry or exit point?
    No. A syntax diagram must have exactly one entry point on the left and one exit point on the right. While paths may branch internally to show alternatives or loop back to show repetition, all valid paths must begin at the single entry and lead to the single exit.
    How do you represent an empty string (epsilon) in BNF?
    In AQA A-Level Computer Science, an empty string is typically represented by an empty alternative (e.g., `<optional_sign> ::= '+' | '-' | `), empty quotes `''`, or the Greek letter epsilon (ε). Always check your specific mark scheme context, but empty quotes `''` are the most common.
    Are spaces required between non-terminals in BNF?
    In BNF notation, writing non-terminals next to each other (e.g., `<sign><digit>`) represents concatenation in that exact order. Spaces are used as separators between meta-tokens, but do not imply literal whitespace in the parsed language unless an explicit `<space>` non-terminal is defined.