1 / 7
BNF, Syntax Diagrams & Context-Free Languages
Learn about Backus-Naur Form (BNF), syntax diagrams, context-free grammars, and how they define programming language syntax.
📚 Learning Steps
💡 Study Tips
- • Read through at your own pace
- • Try the interactive simulators hands-on
- • Study the pseudocode — it appears in exams
- • Quiz yourself before moving on
Step 1: Context-Free Grammars
📖 TheoryA context-free grammar (CFG) is a set of rules for generating strings in a language. They are MORE powerful than regular expressions — they can describe nested/recursive structures like balanced brackets and arithmetic expressions.
A CFG has four parts:
•Terminals — the actual symbols that appear in the output (e.g., letters, digits, +, *)
•Non-terminals — placeholders that get replaced according to rules (e.g., <expression>, <digit>)
•Production rules — rules showing how non-terminals expand into terminals and other non-terminals
•Start symbol — the non-terminal we begin with
Why context-free? The rules apply to a non-terminal regardless of what surrounds it (its 'context'). If A → x is a rule, we can always replace A with x, no matter where A appears.
Context-free grammars are used to define the syntax of programming languages. When you write code, the compiler uses a CFG-based parser to check your syntax.
🎯 Key Points
- •CFGs are more powerful than regular expressions — they handle nesting and recursion
- •Terminals = actual output symbols; non-terminals = placeholders to be expanded
- •Production rules define how non-terminals expand
- •Context-free: rules apply anywhere regardless of surrounding context
- •Used to define programming language syntax
- •Every regular language is also context-free, but not vice versa
0/7 steps completed