Introduction to the Top down Parsing :
Parsing
is also known as Syntax Analysis which is a second phase of a compiler
Parsing
recognizes the sentences in a language
The
input to syntax analysis phase is the tokens generated by the lexical analyzer
and generates a parse tree
Parser
Definition: A syntax analyzer is also known as parser. A
parser for a grammar G is a program that takes input as a string s and produces
an output either,
A
parser tree for s, if s is a sentence of G or
An
error message indicating that s is not a sentence of G
Important Points
In reality, no parse tree exists. It exists only as sequence
of actions made by stepping through the tree construction process
It is desirable for some parsers that the grammar must be
unambiguous
Basic issues in Parsing
There are two important issues in parsing
Specification
of syntax
Representation
of input after parsing
Grammars
Why Grammars Now?
- An easy to understand and precise syntactic specification of a language can be specified by grammars, particularly CFG's
- Efficient syntax analyzer can be constructed for a class of grammars, particularly CFG's
- When a language acquires new constructs, it would be easy to incorporate such constructs into the language provided the language was implemented based on a grammatical description
When CFG's are super sets of RE's then why Regular
Expressions in Lexical Analysis?
Lexical rules are quite simple
Regular expressions are more convenient to express lexical
rules
Efficient scanners can be constructed from a regular
expression based description
Why not RE's in Syntax Analysis?
- Regular expressions are not that much powerful as grammars
- They are unable to describe nested constructs like balanced parenthesis, corresponding if-then-else etc.
- For example, there is no regular expression for describing anbn(n≥1) but there exists a CFG
The syntactic structure of language is defined using
grammars.
- A set of strings over an alphabet is specified by grammars (like regular expressions)
- With the help of grammars, it is possible to construct recognizers (like DFA) to determine whether a string is in the language
Different Languages
- Finite Languages
Enumeration
- Regular Languages(RL ⊃ FL)
Regular
Expressions
- Context Free Languages (CFL ⊃ RL)
Context
Free Grammars
