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?
Which of the following is NOT a limitation of a syntax analyzer?
Which of the following is NOT a limitation of a syntax analyzer?
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.
Signup and view all the answers
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.
Signup and view all the answers
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?
Signup and view all the answers
What is the purpose of the LR(0) parser?
What is the purpose of the LR(0) parser?
Signup and view all the answers
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?
Signup and view all the answers
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.
