Podcast
Questions and Answers
What are the abstractions being defined in a BNF description called?
What are the abstractions being defined in a BNF description called?
In a BNF grammar, what are the lexemes and tokens of the rules called?
In a BNF grammar, what are the lexemes and tokens of the rules called?
What is used to describe lists of syntactic elements in programming languages?
What is used to describe lists of syntactic elements in programming languages?
When is a rule considered recursive in a BNF grammar?
When is a rule considered recursive in a BNF grammar?
Signup and view all the answers
What is the sequence of rule applications called in a grammar?
What is the sequence of rule applications called in a grammar?
Signup and view all the answers
What is the name given to the special nonterminal symbol at the beginning of the derivation process?
What is the name given to the special nonterminal symbol at the beginning of the derivation process?
Signup and view all the answers
What is the difference between syntax and semantics in programming languages?
What is the difference between syntax and semantics in programming languages?
Signup and view all the answers
Which of the following is an example of a lexeme in a programming language?
Which of the following is an example of a lexeme in a programming language?
Signup and view all the answers
What is the function of a token in programming languages?
What is the function of a token in programming languages?
Signup and view all the answers
Which grammar class describes the forms of tokens in programming languages?
Which grammar class describes the forms of tokens in programming languages?
Signup and view all the answers
What is Backus-Naur Form (BNF) commonly used for in programming language development?
What is Backus-Naur Form (BNF) commonly used for in programming language development?
Signup and view all the answers
Why is a metalanguage essential in describing programming language syntax?
Why is a metalanguage essential in describing programming language syntax?
Signup and view all the answers
What is the purpose of using semantic rules in a grammar?
What is the purpose of using semantic rules in a grammar?
Signup and view all the answers
In the given text, what does left recursion specify?
In the given text, what does left recursion specify?
Signup and view all the answers
What is the purpose of extended Backus–Naur Form (EBNF)?
What is the purpose of extended Backus–Naur Form (EBNF)?
Signup and view all the answers
How does right recursion differ from left recursion in grammar rules?
How does right recursion differ from left recursion in grammar rules?
Signup and view all the answers
What is a characteristic of a grammar rule that is right recursive?
What is a characteristic of a grammar rule that is right recursive?
Signup and view all the answers
Which feature is NOT a part of EBNF extensions?
Which feature is NOT a part of EBNF extensions?
Signup and view all the answers
Study Notes
BNF (Backus-Naur Form)
- A notation for describing syntax, developed by John Backus and Peter Naur in the mid-1950s
- Uses abstraction for syntactic structures
- Left-hand side (LHS) - the abstraction being defined
- Right-hand side (RHS) - the definition of the LHS
- Rule (or production) - a mixture of tokens, lexemes, and references to other abstractions
Abstractions and Symbols
- Nonterminal symbols or nonterminals - the abstractions in a BNF description or grammar
- Terminal symbols or terminals - the lexemes and tokens of the rules
Recursion
- Used to describe lists of syntactic elements in programming languages
- A rule is recursive if its LHS appears in its RHS
Grammar
- A collection of rules that describe the syntax of programming languages
- Sentences of the language are generated through a sequence of applications of the rules, beginning with the start symbol
- This sequence of rule applications is called a derivation
Derivation
- Each of the strings in the derivation is called a sentential form
- In leftmost derivation, the replaced nonterminal is always the leftmost nonterminal in the sentential form
- In rightmost derivation, the replaced nonterminal is always the rightmost nonterminal in the sentential form
Parse Tree
- When an expression includes two operators that have the same precedence, a semantic rule is required to specify which should have precedence
- The rule is named associativity
- Left recursion specifies left associativity, while right recursion specifies right associativity
Extended BNF (EBNF)
- Extended versions of BNF that increase the readability and writability of BNF
- Three EBNF extensions:
- Optional parts of an RHS are placed in brackets
Syntax and Semantics
- Syntax - the form of the expressions, statements, and program units of a programming language
- Semantics - the meaning of the expressions, statements, and program units of a programming language
Lexemes and Tokens
- Lexemes - include the numeric literals, operators, and special words of a programming language
- Token - a category of the lexemes of a language
Language Recognizer and Generator
- Language recognizer - reads input strings of the language and decides whether the strings belong to the language
- Language generator - creates sentences of a language
Formal Methods of Describing Syntax
- Grammar - describes the syntax of programming languages; a collection of rules
- Noam Chomsky - described four classes of generative devices or grammars that define four classes of language
- Two of these grammar classes are regular and context-free grammars
- Regular grammars - describe the forms of the tokens of the programming languages
- Context-free grammars - describe the syntax of whole programming languages
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Learn about the basics of BNF (Backus-Naur Form) notation, including the definitions of Left-hand side (LHS), Right-hand side (RHS), and Rules. Explore how nonterminal symbols and terminal symbols are used in BNF descriptions. Discover how recursion is applied to describe syntax in BNF.
