Formal Languages, BNF, and Syntax Diagrams

Vocabulary flashcards reviewing core concepts of formal languages, context-free grammars, Backus–Naur Form (BNF) syntax, and syntax diagrams.

Formal language

A set of strings formed from an alphabet according to defined rules that describe which sequences of symbols are syntactically valid.

Context-free language

A language that can be generated by a context-free grammar, using production rules in which a single non-terminal is replaced by a sequence of terminals and/or non-terminals.

Grammar

A set of production rules that defines how valid strings in a language can be generated, describing permitted structure without listing every valid string.

Backus–Naur Form (BNF)

A notation for defining the syntax of a language using production rules, defining non-terminals in terms of terminals and/or other non-terminals.

Production rule

A grammar rule that defines how a non-terminal can be replaced, such as ::= + | -.

Non-terminal

A named grammar element that can be expanded using a production rule, commonly written in angle brackets, such as or .

Terminal

A literal symbol or token that appears in the final string and is not expanded further by the grammar, such as 0, +, (, and keywords.

::= (BNF symbol)

A BNF operator that means 'is defined as' or 'can be replaced by', which separates the non-terminal being defined from its possible replacement(s).

| (BNF symbol)

A BNF operator that means 'or', separating alternative valid replacements in a production rule.

Sequence (in BNF)

A required ordering represented by writing elements next to each other in the required order, such as ::= .

Recursion (in a grammar)

A feature occurring when a production rule refers, directly or indirectly, to the non-terminal it defines, enabling the grammar to describe repeated or nested structures.

Base case (in a grammar)

An alternative in a recursive grammar rule that stops the recursion, allowing repeated expansion to finish and produce a string containing only terminals.

Derivation (in BNF)

The process of starting with a start symbol and repeatedly applying production rules until only terminal symbols remain, forming the generated string.

Syntax diagram

A graphical way of representing language syntax using paths and labelled symbols to show the valid order, alternatives, and repetition of elements.

Alternative path (in a syntax diagram)

A branch representing choices where the input follows one permitted route; symbols on unchosen routes are not required.

Loop / Return path (in a syntax diagram)

A path allowing an element or group of elements to be traversed repeatedly according to arrows and notation keys.

Optional element (in a syntax diagram)

An element with one route that passes through it and an alternative route that bypasses it, allowing it to appear once or be omitted.

$$\{0^n 1^n \mid n \ge 1\}$$

An example of a context-free language that is not regular, featuring equal numbers of 0s followed by 1s (01, 0011, 000111, etc.) generated by ::= 01 | 01.

Matching nested brackets

A context-free pattern of unbounded depth that can be described by a recursive grammar, but cannot be tracked by a finite-state machine due to lacking unbounded memory.

Regular expression vs. BNF

A regular expression describes a regular language, whereas BNF can describe context-free structures using recursion; every regular language is context-free, but not every context-free language is regular.

Syntax

The permitted structure or arrangement of symbols in a language.

Semantics

The meaning or behaviour of a valid statement in a language.

Start symbol

The non-terminal from which a derivation begins, representing the overall construct being described, such as or .

Angle brackets (

The notation used to enclose and mark a non-terminal symbol in BNF.

BNF recursion advantage

The capability of BNF production rules to represent nested or matched structures of arbitrary depth or quantity, which a finite-state machine or regular expression cannot recognise.