31-10-2012, 04:35 PM
Syntax Analyzer
Syntax.ppt (Size: 153.5 KB / Downloads: 230)
Syntax Analyzer creates the syntactic structure of the given source program.
This syntactic structure is mostly a parse tree.
Syntax Analyzer is also known as parser.
The syntax of a programming is described by a context-free grammar (CFG). We will use BNF (Backus-Naur Form) notation in the description of CFGs.
The syntax analyzer (parser) checks whether a given source program satisfies the rules implied by a context-free grammar or not.
If it satisfies, the parser creates the parse tree of that program.
Otherwise the parser gives the error messages.
A context-free grammar
gives a precise syntactic specification of a programming language.
the design of the grammar is an initial phase of the design of a compiler.
a grammar can be directly converted into a parser by some tools.
Parser
We categorize the parsers into two groups:
Top-Down Parser
the parse tree is created top to bottom, starting from the root.
Bottom-Up Parser
the parse is created bottom to top; starting from the leaves
Both top-down and bottom-up parsers scan the input from left to right (one symbol at a time).
Efficient top-down and bottom-up parsers can be implemented only for sub-classes of context-free grammars.
LL for top-down parsing
LR for bottom-up parsing
Context-Free Grammars
Inherently recursive structures of a programming language are defined by a context-free grammar.
In a context-free grammar, we have:
A finite set of terminals (in our case, this will be the set of tokens)
A finite set of non-terminals (syntactic-variables)
A finite set of productions rules in the following form
A where A is a non-terminal and
is a string of terminals and non-terminals (including the empty string)
A start symbol (one of the non-terminal symbol)
Left Recursion
Top-down parsing techniques cannot handle left-recursive grammars.
So, we have to convert our left-recursive grammar into an equivalent grammar which is not left-recursive.
The left-recursion may appear in a single step of the derivation (immediate left-recursion), or may appear in more than one step of the derivation.