Parsing – Principles of Compiler Design

Need of a Parser

•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).

•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.

Parser

•Parser  works on a stream of tokens.

  The smallest item is a token.

—We categorize the parsers into two groups:

—

1.Top-Down Parser

—the parse tree is created top to bottom, starting from the root.

2.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

•Used to Systematically describe the Syntax of Programming Language Constructs like Expressions and Statements.

•

•Eg. Syntactic Variable  : stmt

               stmt to denote the statements

•Variable :  expr

       expr to denote the expressions

•

  stmt   ->   if  (expr)  stmt  else  stmt

—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 ® a          where A is a non-terminal and

   a is a string of terminals and non-terminals (including the empty string)

—A start symbol (one of the non-terminal symbol)

—

—Example:

E ®  E + E   |   E – E   |   E * E   |  E / E   |   - E

E ®  ( E )

E ® id