Podcast Beta
Questions and Answers
Who developed the concept of Context-Free Grammars?
What is the primary purpose of Backus-Naur Form (BNF)?
What is the left-hand side (LHS) of a production rule in BNF?
What is the purpose of nonterminal symbols in BNF?
Signup and view all the answers
What is the result of a derivation in BNF?
Signup and view all the answers
What symbol is used to chain multiple RHS in a BNF rule?
Signup and view all the answers
How are syntactic lists described in BNF?
Signup and view all the answers
What is the special nonterminal symbol in a BNF grammar?
Signup and view all the answers
Study Notes
Context-Free Grammars
- Developed by Noam Chomsky, who classified four classes of generative devices or grammars that define four classes of languages
- Context-free grammars are one of the two classes (along with regular grammars) that are useful for describing the syntax of programming languages
Backus-Naur Form (BNF)
- Invented by John Backus to describe the syntax of ALGOL 58
- A natural notation for describing syntax, equivalent to context-free grammars
BNF Fundamentals
- A BNF grammar consists of:
- A start symbol
- A finite set of production rules
- A finite set of terminal symbols
- A finite set of nonterminal symbols
Production Rules
- A production rule has:
- A left-hand side (LHS), which is a single nonterminal
- A right-hand side (RHS), which is a string of terminals and/or nonterminals
Nonterminal Symbols
- Nonterminal symbols are abstractions used to represent classes of syntactic structures
- Also called simply nonterminals
- Nonterminals are often enclosed in angle brackets
Terminal Symbols
- Terminal symbols are lexemes or tokens
Derivation
- A derivation is the repeated application of rules, starting with the start symbol and ending with a sentence (a string of only terminal symbols)
- A sentential form is every string of (nonterminal or terminal) symbols in a derivation
- A sentence is a sentential form that has only terminal symbols
- Leftmost derivation: the leftmost nonterminal in each sentential form is the one that is expanded next
BNF Rules
- An abstraction (or nonterminal symbol) can have more than one RHS, chained using the | symbol
Describing Lists
- Syntactic lists are described using recursion
- Example: a list of identifiers can be described using a recursive rule, where the list can be either an identifier or an identifier followed by a comma and another list
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Learn about Noam Chomsky's context-free grammars and John Backus' Backus-Naur Form, including their development and applications in programming languages.
