BNF & Syntactical Graphs
Welcome to the comprehensive guide on Backus-Naur Form (BNF) and Syntactical Graphs. These are fundamental tools in computer science for describing the syntax of programming languages, protocols, and formal languages.
What is BNF?
Backus-Naur Form (BNF) is a notation technique for context-free grammars, developed by John Backus and Peter Naur in the 1960s. It's used to describe the syntax of programming languages and other formal languages in a precise, unambiguous way.
Key Components of BNF
- Non-terminals: Abstract syntactic categories (like <expression>)
- Terminals: Actual symbols that appear in the language (like keywords, operators)
- Production rules: Define how non-terminals can be expanded
- Meta-symbols: Special notation used in BNF itself
BNF Notation
<non-terminal> ::= terminal | <another-non-terminal>
::= means "is defined as"
| means "or" (alternative)
< > enclose non-terminals
BNF Examples
Simple Arithmetic Expression
<expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>
<term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor>
<factor> ::= <number> | "(" <expression> ")"
<number> ::= <digit> | <number> <digit>
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Simple Programming Language Statement
<statement> ::= <assignment> | <if-statement> | <while-loop>
<assignment> ::= <identifier> "=" <expression> ";"
<if-statement> ::= "if" "(" <condition> ")" <statement>
<while-loop> ::= "while" "(" <condition> ")" <statement>
Extended BNF (EBNF)
Extended BNF adds additional operators to make grammar more concise and readable:
[ ] Optional (zero or one occurrence)
{ } Repetition (zero or more occurrences)
( ) Grouping
+ One or more occurrences
* Zero or more occurrences
? Zero or one occurrence
EBNF Example
<number> ::= <digit>+
<identifier> ::= <letter> ( <letter> | <digit> )*
<function-call> ::= <identifier> "(" [ <argument-list> ] ")"
What are Syntactical Graphs?
Syntactical graphs, also known as syntax diagrams or railroad diagrams, are a visual representation of a formal grammar. They show the flow of syntax rules graphically, making it easier to understand the structure of a language.
Note: Syntactical graphs represent the same information as BNF but in a visual, flowchart-like format that many find easier to follow and understand.
Components of Syntax Diagrams
- Rectangles: Non-terminal symbols
- Ovals/Circles: Terminal symbols
- Arrows: Show the flow and direction
- Branches: Represent alternatives (like | in BNF)
- Loops: Show repetition
Syntax Diagram Examples
Simple Number
digit
→
(loops back for more digits)
If Statement
if
→
(
→
condition
→
)
→
statement
Expression with Alternatives
term
↓ (alternative paths)
expression
+
term
expression
-
term
BNF vs Syntactical Graphs Comparison
| Aspect |
BNF |
Syntactical Graphs |
| Representation |
Text-based notation |
Visual diagrams |
| Learning Curve |
Requires understanding notation |
More intuitive, easier to follow |
| Space Efficiency |
Compact, takes less space |
Requires more space |
| Tool Support |
Easy to process by parser generators |
Harder to process automatically |
| Readability |
Good for technical documentation |
Excellent for understanding flow |
| Alternatives |
Uses | operator |
Shows as branching paths |
| Repetition |
Recursive rules or EBNF operators |
Visual loops and cycles |
Applications and Uses
Where BNF is Used
- Programming Language Design: Defining syntax for new languages
- Compiler Construction: Parser generation tools
- Protocol Specification: Network protocols, file formats
- Data Format Definition: JSON, XML schemas
- Configuration Files: Syntax validation
Where Syntactical Graphs Excel
- Documentation: User manuals and language references
- Education: Teaching language syntax
- Debugging: Understanding parser behavior
- Language Design Review: Visual inspection of grammar
- IDE Integration: Syntax help and autocomplete
Advanced Concepts
Left Recursion in BNF
// Problematic left recursion
<expression> ::= <expression> "+" <term> | <term>
// Fixed right recursion
<expression> ::= <term> <expression-tail>
<expression-tail> ::= "+" <term> <expression-tail> | ε
Ambiguity in Grammars
Both BNF and syntactical graphs can represent ambiguous grammars where a single input can be parsed in multiple ways. This is typically resolved through:
- Precedence rules
- Associativity rules
- Grammar refactoring
- Parser disambiguation strategies
Conclusion
Both BNF and syntactical graphs are essential tools for anyone working with formal languages, compilers, or language design. BNF provides precision and tool compatibility, while syntactical graphs offer intuitive visual understanding.
Best Practice: Use BNF for formal specifications and tool processing, and syntactical graphs for documentation, education, and design review. They complement each other perfectly in the language design process.