Show description
BNF and Syntactical Graphs - Complete Guide
BNF and Syntactical Graphs - Complete Guide
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.…
BNF and Syntactical Graphs - Complete Guide
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>BNF and Syntactical Graphs - Complete Guide</title>
<style>
* {
margin: 0;
padding: 0;
box-sizing: border-box;
}
body {
background-color: #0a0a0a;
color: #e0e0e0;
font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
line-height: 1.6;
padding: 20px;
}
.container {
max-width: 1200px;
margin: 0 auto;
}
h1 {
color: #ff6b35;
text-align: center;
font-size: 3rem;
margin-bottom: 2rem;
text-shadow: 0 0 10px rgba(255, 107, 53, 0.3);
}
h2 {
color: #4a9eff;
font-size: 2rem;
margin: 3rem 0 1rem 0;
border-bottom: 2px solid #4a9eff;
padding-bottom: 0.5rem;
}
h3 {
color: #ff6b35;
font-size: 1.5rem;
margin: 2rem 0 1rem 0;
}
.intro {
background: linear-gradient(135deg, #1a1a1a, #2a2a2a);
padding: 2rem;
border-radius: 10px;
margin-bottom: 2rem;
border: 1px solid #333;
}
.section {
background-color: #111;
margin: 2rem 0;
padding: 2rem;
border-radius: 10px;
border: 1px solid #333;
}
.code-block {
background-color: #1e1e1e;
color: #f8f8f2;
padding: 1.5rem;
border-radius: 8px;
margin: 1rem 0;
font-family: 'Courier New', monospace;
border-left: 4px solid #ff6b35;
overflow-x: auto;
}
.bnf-rule {
color: #4a9eff;
}
.bnf-terminal {
color: #ff6b35;
}
.bnf-operator {
color: #50fa7b;
}
.syntax-diagram {
background-color: #1a1a1a;
padding: 2rem;
margin: 1rem 0;
border-radius: 8px;
text-align: center;
border: 2px solid #4a9eff;
}
.diagram-element {
display: inline-block;
margin: 0.5rem;
padding: 0.5rem 1rem;
border-radius: 5px;
font-family: monospace;
}
.terminal {
background-color: #ff6b35;
color: #000;
}
.non-terminal {
background-color: #4a9eff;
color: #000;
}
.arrow {
color: #50fa7b;
font-size: 1.5rem;
}
.comparison-table {
width: 100%;
border-collapse: collapse;
margin: 1rem 0;
}
.comparison-table th,
.comparison-table td {
border: 1px solid #333;
padding: 1rem;
text-align: left;
}
.comparison-table th {
background-color: #ff6b35;
color: #000;
font-weight: bold;
}
.comparison-table tr:nth-child(even) {
background-color: #1a1a1a;
}
.highlight {
background-color: #2a2a2a;
padding: 0.2rem 0.5rem;
border-radius: 3px;
color: #ff6b35;
}
.note {
background-color: #1a2332;
border-left: 4px solid #4a9eff;
padding: 1rem;
margin: 1rem 0;
border-radius: 0 5px 5px 0;
}
.example {
background-color: #1a1a1a;
border: 1px solid #333;
border-radius: 5px;
padding: 1rem;
margin: 1rem 0;
}
.railroad-track {
border: 2px solid #4a9eff;
background: linear-gradient(90deg, #1a1a1a 0%, #2a2a2a 50%, #1a1a1a 100%);
padding: 1rem;
margin: 1rem 0;
border-radius: 10px;
position: relative;
}
.railroad-track::before {
content: "→";
position: absolute;
left: 10px;
color: #50fa7b;
font-size: 1.5rem;
}
.railroad-track::after {
content: "→";
position: absolute;
right: 10px;
color: #50fa7b;
font-size: 1.5rem;
}
</style>
</head>
<body>
<div class="container">
<h1>BNF & Syntactical Graphs</h1>
<div class="intro">
<p>Welcome to the comprehensive guide on <span class="highlight">Backus-Naur Form (BNF)</span> and <span class="highlight">Syntactical Graphs</span>. These are fundamental tools in computer science for describing the syntax of programming languages, protocols, and formal languages.</p>
</div>
<div class="section">
<h2>What is BNF?</h2>
<p>Backus-Naur Form (BNF) is a notation technique for <strong>context-free grammars</strong>, 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.</p>
<h3>Key Components of BNF</h3>
<ul style="margin-left: 2rem; margin-top: 1rem;">
<li><strong>Non-terminals:</strong> Abstract syntactic categories (like <expression>)</li>
<li><strong>Terminals:</strong> Actual symbols that appear in the language (like keywords, operators)</li>
<li><strong>Production rules:</strong> Define how non-terminals can be expanded</li>
<li><strong>Meta-symbols:</strong> Special notation used in BNF itself</li>
</ul>
<h3>BNF Notation</h3>
<div class="code-block">
<span class="bnf-rule"><non-terminal></span> <span class="bnf-operator">::=</span> <span class="bnf-terminal">terminal</span> <span class="bnf-operator">|</span> <span class="bnf-rule"><another-non-terminal></span>
<span class="bnf-operator">::=</span> means "is defined as"
<span class="bnf-operator">|</span> means "or" (alternative)
<span class="bnf-operator">< ></span> enclose non-terminals
</div>
</div>
<div class="section">
<h2>BNF Examples</h2>
<h3>Simple Arithmetic Expression</h3>
<div class="code-block">
<span class="bnf-rule"><expression></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><term></span> <span class="bnf-operator">|</span> <span class="bnf-rule"><expression></span> <span class="bnf-terminal">"+"</span> <span class="bnf-rule"><term></span> <span class="bnf-operator">|</span> <span class="bnf-rule"><expression></span> <span class="bnf-terminal">"-"</span> <span class="bnf-rule"><term></span>
<span class="bnf-rule"><term></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><factor></span> <span class="bnf-operator">|</span> <span class="bnf-rule"><term></span> <span class="bnf-terminal">"*"</span> <span class="bnf-rule"><factor></span> <span class="bnf-operator">|</span> <span class="bnf-rule"><term></span> <span class="bnf-terminal">"/"</span> <span class="bnf-rule"><factor></span>
<span class="bnf-rule"><factor></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><number></span> <span class="bnf-operator">|</span> <span class="bnf-terminal">"("</span> <span class="bnf-rule"><expression></span> <span class="bnf-terminal">")"</span>
<span class="bnf-rule"><number></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><digit></span> <span class="bnf-operator">|</span> <span class="bnf-rule"><number></span> <span class="bnf-rule"><digit></span>
<span class="bnf-rule"><digit></span> <span class="bnf-operator">::=</span> <span class="bnf-terminal">"0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"</span>
</div>
<h3>Simple Programming Language Statement</h3>
<div class="code-block">
<span class="bnf-rule"><statement></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><assignment></span> <span class="bnf-operator">|</span> <span class="bnf-rule"><if-statement></span> <span class="bnf-operator">|</span> <span class="bnf-rule"><while-loop></span>
<span class="bnf-rule"><assignment></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><identifier></span> <span class="bnf-terminal">"="</span> <span class="bnf-rule"><expression></span> <span class="bnf-terminal">";"</span>
<span class="bnf-rule"><if-statement></span> <span class="bnf-operator">::=</span> <span class="bnf-terminal">"if"</span> <span class="bnf-terminal">"("</span> <span class="bnf-rule"><condition></span> <span class="bnf-terminal">")"</span> <span class="bnf-rule"><statement></span>
<span class="bnf-rule"><while-loop></span> <span class="bnf-operator">::=</span> <span class="bnf-terminal">"while"</span> <span class="bnf-terminal">"("</span> <span class="bnf-rule"><condition></span> <span class="bnf-terminal">")"</span> <span class="bnf-rule"><statement></span>
</div>
</div>
<div class="section">
<h2>Extended BNF (EBNF)</h2>
<p>Extended BNF adds additional operators to make grammar more concise and readable:</p>
<div class="code-block">
<span class="bnf-operator">[ ]</span> Optional (zero or one occurrence)
<span class="bnf-operator">{ }</span> Repetition (zero or more occurrences)
<span class="bnf-operator">( )</span> Grouping
<span class="bnf-operator">+</span> One or more occurrences
<span class="bnf-operator">*</span> Zero or more occurrences
<span class="bnf-operator">?</span> Zero or one occurrence
</div>
<h3>EBNF Example</h3>
<div class="code-block">
<span class="bnf-rule"><number></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><digit></span><span class="bnf-operator">+</span>
<span class="bnf-rule"><identifier></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><letter></span> <span class="bnf-operator">(</span> <span class="bnf-rule"><letter></span> <span class="bnf-operator">|</span> <span class="bnf-rule"><digit></span> <span class="bnf-operator">)*</span>
<span class="bnf-rule"><function-call></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><identifier></span> <span class="bnf-terminal">"("</span> <span class="bnf-operator">[</span> <span class="bnf-rule"><argument-list></span> <span class="bnf-operator">]</span> <span class="bnf-terminal">")"</span>
</div>
</div>
<div class="section">
<h2>What are Syntactical Graphs?</h2>
<p>Syntactical graphs, also known as <strong>syntax diagrams</strong> or <strong>railroad diagrams</strong>, 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.</p>
<div class="note">
<strong>Note:</strong> Syntactical graphs represent the same information as BNF but in a visual, flowchart-like format that many find easier to follow and understand.
</div>
<h3>Components of Syntax Diagrams</h3>
<ul style="margin-left: 2rem; margin-top: 1rem;">
<li><strong>Rectangles:</strong> Non-terminal symbols</li>
<li><strong>Ovals/Circles:</strong> Terminal symbols</li>
<li><strong>Arrows:</strong> Show the flow and direction</li>
<li><strong>Branches:</strong> Represent alternatives (like | in BNF)</li>
<li><strong>Loops:</strong> Show repetition</li>
</ul>
</div>
<div class="section">
<h2>Syntax Diagram Examples</h2>
<h3>Simple Number</h3>
<div class="railroad-track">
<span class="diagram-element non-terminal">digit</span>
<span class="arrow">→</span>
<span style="font-size: 0.8rem; color: #888;">(loops back for more digits)</span>
</div>
<h3>If Statement</h3>
<div class="railroad-track">
<span class="diagram-element terminal">if</span>
<span class="arrow">→</span>
<span class="diagram-element terminal">(</span>
<span class="arrow">→</span>
<span class="diagram-element non-terminal">condition</span>
<span class="arrow">→</span>
<span class="diagram-element terminal">)</span>
<span class="arrow">→</span>
<span class="diagram-element non-terminal">statement</span>
</div>
<h3>Expression with Alternatives</h3>
<div class="syntax-diagram">
<div style="margin-bottom: 1rem;">
<span class="diagram-element non-terminal">term</span>
</div>
<div>
↓ (alternative paths)
</div>
<div style="margin-top: 1rem;">
<span class="diagram-element non-terminal">expression</span>
<span class="diagram-element terminal">+</span>
<span class="diagram-element non-terminal">term</span>
</div>
<div style="margin-top: 0.5rem;">
<span class="diagram-element non-terminal">expression</span>
<span class="diagram-element terminal">-</span>
<span class="diagram-element non-terminal">term</span>
</div>
</div>
</div>
<div class="section">
<h2>BNF vs Syntactical Graphs Comparison</h2>
<table class="comparison-table">
<thead>
<tr>
<th>Aspect</th>
<th>BNF</th>
<th>Syntactical Graphs</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>Representation</strong></td>
<td>Text-based notation</td>
<td>Visual diagrams</td>
</tr>
<tr>
<td><strong>Learning Curve</strong></td>
<td>Requires understanding notation</td>
<td>More intuitive, easier to follow</td>
</tr>
<tr>
<td><strong>Space Efficiency</strong></td>
<td>Compact, takes less space</td>
<td>Requires more space</td>
</tr>
<tr>
<td><strong>Tool Support</strong></td>
<td>Easy to process by parser generators</td>
<td>Harder to process automatically</td>
</tr>
<tr>
<td><strong>Readability</strong></td>
<td>Good for technical documentation</td>
<td>Excellent for understanding flow</td>
</tr>
<tr>
<td><strong>Alternatives</strong></td>
<td>Uses | operator</td>
<td>Shows as branching paths</td>
</tr>
<tr>
<td><strong>Repetition</strong></td>
<td>Recursive rules or EBNF operators</td>
<td>Visual loops and cycles</td>
</tr>
</tbody>
</table>
</div>
<div class="section">
<h2>Applications and Uses</h2>
<h3>Where BNF is Used</h3>
<div class="example">
<ul style="margin-left: 2rem;">
<li><strong>Programming Language Design:</strong> Defining syntax for new languages</li>
<li><strong>Compiler Construction:</strong> Parser generation tools</li>
<li><strong>Protocol Specification:</strong> Network protocols, file formats</li>
<li><strong>Data Format Definition:</strong> JSON, XML schemas</li>
<li><strong>Configuration Files:</strong> Syntax validation</li>
</ul>
</div>
<h3>Where Syntactical Graphs Excel</h3>
<div class="example">
<ul style="margin-left: 2rem;">
<li><strong>Documentation:</strong> User manuals and language references</li>
<li><strong>Education:</strong> Teaching language syntax</li>
<li><strong>Debugging:</strong> Understanding parser behavior</li>
<li><strong>Language Design Review:</strong> Visual inspection of grammar</li>
<li><strong>IDE Integration:</strong> Syntax help and autocomplete</li>
</ul>
</div>
</div>
<div class="section">
<h2>Advanced Concepts</h2>
<h3>Left Recursion in BNF</h3>
<div class="code-block">
<span style="color: #ff5555;">// Problematic left recursion</span>
<span class="bnf-rule"><expression></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><expression></span> <span class="bnf-terminal">"+"</span> <span class="bnf-rule"><term></span> <span class="bnf-operator">|</span> <span class="bnf-rule"><term></span>
<span style="color: #50fa7b;">// Fixed right recursion</span>
<span class="bnf-rule"><expression></span> <span class="bnf-operator">::=</span> <span class="bnf-rule"><term></span> <span class="bnf-rule"><expression-tail></span>
<span class="bnf-rule"><expression-tail></span> <span class="bnf-operator">::=</span> <span class="bnf-terminal">"+"</span> <span class="bnf-rule"><term></span> <span class="bnf-rule"><expression-tail></span> <span class="bnf-operator">|</span> <span style="color: #6272a4;">ε</span>
</div>
<h3>Ambiguity in Grammars</h3>
<p>Both BNF and syntactical graphs can represent ambiguous grammars where a single input can be parsed in multiple ways. This is typically resolved through:</p>
<ul style="margin-left: 2rem; margin-top: 1rem;">
<li>Precedence rules</li>
<li>Associativity rules</li>
<li>Grammar refactoring</li>
<li>Parser disambiguation strategies</li>
</ul>
</div>
<div class="section">
<h2>Conclusion</h2>
<p>Both BNF and syntactical graphs are essential tools for anyone working with formal languages, compilers, or language design. <strong>BNF provides precision and tool compatibility</strong>, while <strong>syntactical graphs offer intuitive visual understanding</strong>.</p>
<div class="note">
<strong>Best Practice:</strong> 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.
</div>
</div>
</div>
</body>
</html>