Top Down Parsing in Compiler Design

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 aⁿbⁿ(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

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.