Podcast
Questions and Answers
Who developed the concept of Context-Free Grammars?
Who developed the concept of Context-Free Grammars?
What is the primary purpose of Backus-Naur Form (BNF)?
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 left-hand side (LHS) of a production rule in BNF?
What is the purpose of nonterminal symbols 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?
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?
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?
How are syntactic lists described in BNF?
Signup and view all the answers
What is the special nonterminal symbol in a BNF grammar?
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.
