FIT2014 Lecture Notes - Lecture 12: Context-Free Grammar, Lr Parser, Parse Tree
28 Jun 2018
School
Department
Course
Professor
Lecture 12 Parsing.
Suppose you have a context free grammer (e.g. S aX) and a string of letter, Parsing is the task of
determining whether the string
- is a word in the language and if it is
- finding a parse tree for it
How do we find a parse tree for a given input?
A parser for a grammar is a program.
- Input is a string. It decides whether the input can be generated by a grammar
- Then it find a parse tree of a derivation for the input .
Two types of Parsers
- Top down parsers
- Bottom up parsers
Top down parsers
The parsers scans the input Left to right one token at a time. If the parsers can determine which rule to use,
then it is called a predictive parser and it is deterministic.
However if it needs to guess which rule: , It is a non-deterministic and will need to employ backtracking
Recursive Descent Parsers
- It associates a function with each non terminal of the grammar.
- Write these function so that they mirror the grammar.
Difficulties with top down parser:
- Left Recursive Grammars i.e A ⇒ … ⇒ Aw
- Error Handling
- Backtracking
o Allocating/Deallocating resources
o Undoing actions
