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


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.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment