Syntax Analysis
There are two types of parsers.
[Link]-Down parsers
[Link]-up Parsers
If a compiler had to process only correct programs, its design
and implementation would be simplied greatly. However, a
compiler is expected to assist the programmer in locating and
tracking down errors that inevitably creep into programs,
despite the programmer's best e
orts. Strikingly, few languages have been designed with error
handling in mind, even though errors are so common place.
Parser and Types of Parsers
A parser for the given grammar G is a program which constructs the
parse tree for the given input string ‘w’ if input string is accepted by the grammar
otherwise parser calls error handler to display appropriate error messages.
There are two types of parsers.
[Link]-Up Parsers : These kinds of parsers constructs the parse tree for the
given input string starting from the leaves and working upwards to the root, at the
end if root of the parse tree is with starting symbol of the grammar then the string
will be accepted by that grammar.
[Link] – Down Parsers : These kinds of parsers constructs the parse tree for the given
input string starting from the root and working downwards to the leaves, at the end if
leaves of the parse tree is with symbols from the given input string then the string will
be accepted by that grammar.
4.2 Context-Free Grammars
Grammars helpful to systematically describe the syntax of programming
language constructs like expressions and statements. Using a syntactic variable stmt
to denote statements and variable expr to denote expressions, the production
stmt -> if ( expr ) stmt else stmt
specifies the structure of this form of conditional statement. Other productions
then define precisely what an expr is and what else a stmt can be.
In formal language theory, a context-free language (CFL) is a language generated by
a context-free grammar (CFG). Context-free languages have many applications in
programming languages, in particular, most arithmetic expressions are generated by
context-free grammars.
Conversion from ambiguous to unambiguous Grammar
Consider the following Grammar G
E E+E / E * E / (E) / id
After Re-writing
EE+T/T
TT*F/F
F (E) / id Now construct parse tree for w = id + id * id
Consider the following grammar G
E -> E+T / T
T -> T*F / F
F -> (E) / id
Grammar after elimination of left recursion is
Left Factored Grammar
