Podcast
Questions and Answers
What is the term for a parser that constructs a rightmost derivation?
What is the term for a parser that constructs a rightmost derivation?
LR Parser
What are the two types of parsing techniques?
What are the two types of parsing techniques?
- Left-to-right parsing
- Right-to-left parsing
- Top-down parsing (correct)
- Bottom-up parsing (correct)
Which of the following is NOT a limitation of a syntax analyzer?
Which of the following is NOT a limitation of a syntax analyzer?
- It cannot determine if a production rule is being used. (correct)
- It cannot determine if a token is initialized before it is being used.
- It cannot determine if an operation performed on a token type is valid or not.
- It cannot determine if a token is valid.
- It cannot determine if a token is declared before it is being used.
Backtracking is a technique that is commonly used in top-down parsing to find the correct derivation.
Backtracking is a technique that is commonly used in top-down parsing to find the correct derivation.
LL(1) parsers are widely used as they can handle both ambiguous and left-recursive grammars efficiently.
LL(1) parsers are widely used as they can handle both ambiguous and left-recursive grammars efficiently.
What are the two key functions used in the construction of a predictive LL(1) parser?
What are the two key functions used in the construction of a predictive LL(1) parser?
What is the purpose of the LR(0) parser?
What is the purpose of the LR(0) parser?
What is the term for a substring that matches a production's right-hand side in a bottom-up parsing process?
What is the term for a substring that matches a production's right-hand side in a bottom-up parsing process?
Flashcards
Formal Grammar
Formal Grammar
A set of rules defining the structure of a language.
Categories of Grammar
Categories of Grammar
Different types of formal grammar systems, each with specific properties.
Ambiguity in CFG
Ambiguity in CFG
A situation where a grammar can generate more than one parse tree for the same input string.
Capabilities of CFG
Capabilities of CFG
Signup and view all the flashcards
Left Recursion
Left Recursion
Signup and view all the flashcards
Left Factoring
Left Factoring
Signup and view all the flashcards
Non-Deterministic
Non-Deterministic
Signup and view all the flashcards
Deterministic
Deterministic
Signup and view all the flashcards
Top-Down Parsing
Top-Down Parsing
Signup and view all the flashcards
Bottom-Up Parsing
Bottom-Up Parsing
Signup and view all the flashcards
Syntax Analyzer
Syntax Analyzer
Signup and view all the flashcards
Parse Tree
Parse Tree
Signup and view all the flashcards
Terminal Symbol
Terminal Symbol
Signup and view all the flashcards
Non-terminal Symbol
Non-terminal Symbol
Signup and view all the flashcards
Token Stream
Token Stream
Signup and view all the flashcards
Lexical Analyzer
Lexical Analyzer
Signup and view all the flashcards
Parse Tree Leaf
Parse Tree Leaf
Signup and view all the flashcards
Parse Tree Interior Node
Parse Tree Interior Node
Signup and view all the flashcards
In-order Traversal
In-order Traversal
Signup and view all the flashcards
Syntax Error
Syntax Error
Signup and view all the flashcards
Semantic Analyzer
Semantic Analyzer
Signup and view all the flashcards
Study Notes
Compiler Design (21CS3001)
- Unit 3 focuses on formal grammar and its application to syntax analysis.
- Todays agenda includes formal grammar and its application to syntax analysis.
- Lexemes and tokens are used for syntax analysis.
- A parse tree is generated as output from syntax analysis.
Formal Grammar
- Formal grammar consists of non-terminals (variables), terminals (constants), production rules (a→β), and a start symbol.
- Non-terminals are represented by angle brackets, e.g., <Noun>, <Verb>, <Adjective>.
- Terminals are the actual words or symbols in a language, e.g., "Learners," "are," "awesome."
- Production rules specify how non-terminals can be rewritten in terms of other non-terminals or terminals.
- Context Free Grammar (CFG): A type of formal grammar where the production rules can rewrite a nonterminal without any surrounding context.
- Productions are of the format: A → αβ where Α ∈ N, αβ ∈ (N∪T)*
- N is a set of Non-Terminals
- T is a set of Terminals
- S is the Start Symbol
- P is a set of Productions
Types of Grammars
- Type-0/Unrestricted Grammar: α→β (no restrictions)
- Type-1/Context-Sensitive Grammar: αΑβ → αγβ | αΑβ (length of αβ ≤ length of γβ)
- Type-2/Context-Free Grammar: A → α (A ∈ N, α ∈ (N∪T)*)
- Type-3/Regular Grammar: A → aB, A → a (A, B ∈ N, a ∈ T)
- CFGs are useful in describing programming languages.
- Grammars can be designed well for expressions with associativity and precedence.
- CFGS describe nested structures (parenthesis, matching begin-end-iff/then/else)
Parsing Techniques
- A parser analyzes the token stream against the production rules to detect errors.
- Output is a parse tree.
- All leaf nodes are terminals
- All interior nodes are non-terminals
- In-order traversal produces the original input string.
Top-Down Parsing
- Parser starts with the start symbol and tries to expand it using production rules.
- Uses leftmost derivation.
- Can use backtracking.
- Problems include backtracking overhead.
Bottom-Up Parsing
- Parser starts with the given input string and repeatedly reduces substrings to higher-level non-terminals until it reaches the start symbol.
- Uses rightmost derivation in reverse
- Handles both ambiguous and left-recursive grammars
- More powerful than top-down parsing
Shift-Reduce Parsers
- Parsing algorithm that uses shift and reduce actions.
- Shift: pushes a terminal onto the stack.
- Reduce: pops symbols from the stack and replaces them with a non-terminal based on grammar rules.
LL(1) Parsers
- Predictive parser that uses a parsing table to determine the next action.
- The input is scanned from left to right and leftmost derivation is used.
Issues in CFGs
- Ambiguity: Having more than one valid parse tree for the same string.
- Left-recursion: A rule where a non-terminal can produce itself at the start of the rule.
- Eliminating left recursion enables top-down parsers.
- Replacing a→ Aa' with a→ a'α helps eliminate the ambiguity.
- Left Factoring: Simplifying grammar rules that have common initial prefixes in multiple productions
- Simplifies decision making in parsing.
Formal Grammars - First() and Follow() Functions
- FIRST(X): Set of all terminals that can begin a string derived from X.
- FOLLOW(X): Set of all terminals that can follow X in a string derived from the start symbol.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
