Compiler Design

Compiler Design

  

 Compiler

A compiler is a program takes a program written in a source language and translates it into an equivalent program in a target language.
In addition to the development of a compiler, the 
techniques used in compiler design can be applicable to 
many problems in computer science.

Techniques used in a lexical analyzer can be used in text editors, information retrieval system, and pattern recognition programs.

Techniques used in a parser can be used in a query processing system such as SQL.

Many software having a complex front-end may need techniques used in compiler design.

Most of the techniques used in compiler design  can be used in Natural Language Processing (NLP) systems.

-         Major Parts of Compiler

There are two major parts of a compiler:

Analysis and

Synthesis

 

In analysis phase, an intermediate representation is created from

the given source program. 

Lexical Analyzer, Syntax Analyzer and Semantic Analyzer are the parts of this phase.

In synthesis phase, the equivalent target program is created 

from this intermediate representation. 

Intermediate Code Generator, Code Generator, and Code Optimizer are the parts of this phase.

-         Lexical Analyzer

Lexical Analyzer reads the source program character by 

character to produce tokens.

Normally a lexical analyzer doesn’t return a list of tokens at one 

shot; it returns a token when the parser asks a token from it.

A token describes a pattern of characters having same meaning 

in the source program. (such as identifiers, operators, keywords, 

numbers, delimiters and so on).

Ex:      newval := oldval + 12       

tokens:                newval   identifier

                        :=      assignment operator

                        oldval         identifier

                        +        add operator

                        12     a number

                                                             

Puts information about identifiers into the symbol table.

Regular expressions are used to describe tokens (lexical constructs).

-         Syntax Analyzer

A Syntax Analyzer creates the syntactic structure (generally a parse tree) of the given program.

A syntax analyzer is also called as a parser.

A parse tree describes a syntactic structure.

           
            
The syntax of a language is specified by a contextfree 
grammar(CFG).

The rules in a CFG are mostly recursive.

A syntax analyzer checks whether a given program satisfies the rules implied by a CFG or not.

·          
Syntax Analyzer v/s Lexical Analyzer

Both of them do similar things; But the lexical analyzer deals with simple non-recursive constructs of the language.

The syntax analyzer deals with recursive constructs of the language.

The lexical analyzer simplifies the job of the syntax analyzer.

The lexical analyzer recognizes the smallest meaningful units (tokens) in a source program.

The syntax analyzer works on the smallest meaningful units (tokens) in a source program to recognize meaningful structures in our programming language.

visit also : http://techinfomca.wordpress.com