Introduction:
Compiler is a program that convert one source code of one language into equivalent another language (called target code). If there is any error in source code then compiler report error. There have six steps that compiler follows to build target code. They are
1. Lexical analyzer (Scan code and find token)
2. Syntax analyzer (verify that tokens follow a grammar. Also called as parser. This step generates parse tree)
3. Semantic analyzer (Checks value of each node in parse tree)
4. Intermediate code generator (Generate three address code)
5. Code optimizer (Optimize more)
6. Code generator (Generate machine code)
1. Lexical analyzer (Scan code and find token)
2. Syntax analyzer (verify that tokens follow a grammar. Also called as parser. This step generates parse tree)
3. Semantic analyzer (Checks value of each node in parse tree)
4. Intermediate code generator (Generate three address code)
5. Code optimizer (Optimize more)
6. Code generator (Generate machine code)
Symbol Table:
When we get any identifier in source code, we need to keep a record of it. A symbol table is a data structure containing a record for each identifier with fields for the attributes of the identifier. When syntax analyzer get an identifier, it is entered into the symbol table.
We can divide the task of compiler into two portion. i) Front end & ii) Back end. Front end depend primarily on the source language and are independent of the target machine. These include lexical, syntax, semantic anlyger and intermediate code generator. On the other hand, back end depend on target machine. These include code optimizer, generator. If the back end is designed carefully, it may not even be necessary to redesign it too much.
We can divide the task of compiler into two portion. i) Front end & ii) Back end. Front end depend primarily on the source language and are independent of the target machine. These include lexical, syntax, semantic anlyger and intermediate code generator. On the other hand, back end depend on target machine. These include code optimizer, generator. If the back end is designed carefully, it may not even be necessary to redesign it too much.
Compiler History:
We need a language to make a compiler and need another compiler to run that code. So there is a great question, "How was the first compiler compiled?" which sounds like "What came first, the chicken or the egg?"
Well, In 1958 Lisp was used as a notation for writing functions. Then they were translated into assembly language and run. Later, S.R. Russell first implement an interpreter.
A compiler is characterized by three languages: the source language S, the target language T, the implementation language L. The following grammer represent the relationship between these language:
Well, In 1958 Lisp was used as a notation for writing functions. Then they were translated into assembly language and run. Later, S.R. Russell first implement an interpreter.
A compiler is characterized by three languages: the source language S, the target language T, the implementation language L. The following grammer represent the relationship between these language:
 |
| Compiler Languages |
How Build Compiler?
This is very difficult to build a real compiler in few days. There only a toy compiler design is discussed. Suppose we will make a compiler of c language that show three address code. Then at first we need to scan the source code. To scan we use Lex. Lex scan source code and find token. At first we declare the pattern that will match with token. Then Lex called bison.
There is a sample code of lex:
/**********************************************/
/******************* One.lex ******************/
/**********************************************/
%{
#include<strings.h>
#include<stdio.h>
#include<math.h>
%}
digit [0-9]
num {digit}+
%%
{digit} { printf(" there is a digit %s .", yytext); }
{num} { printf(" there is a num %s .", yytext); }
. ;
%%
int main (void) {
yylex ();
return 0;
}
int yywrap()
{
return 0;
}
/**********************************************/
/**********************************************/
To run code: flex One.lex
: gcc -o out lex.yy.c
: ./out
/**********************************************/
To get proper action of each token we use bison. Now there may be some variable in source code. So, we need to build a structure of symbol table. It keep track of each variable. We also use a stack to put the results of code.
There is a sample code of Lex, bison that shows calculation of a calculator:
There is a sample code of lex:
/**********************************************/
/******************* One.lex ******************/
/**********************************************/
%{
#include<strings.h>
#include<stdio.h>
#include<math.h>
%}
digit [0-9]
num {digit}+
%%
{digit} { printf(" there is a digit %s .", yytext); }
{num} { printf(" there is a num %s .", yytext); }
. ;
%%
int main (void) {
yylex ();
return 0;
}
int yywrap()
{
return 0;
}
/**********************************************/
/**********************************************/
To run code: flex One.lex
: gcc -o out lex.yy.c
: ./out
/**********************************************/
To get proper action of each token we use bison. Now there may be some variable in source code. So, we need to build a structure of symbol table. It keep track of each variable. We also use a stack to put the results of code.
There is a sample code of Lex, bison that shows calculation of a calculator:
/**********************************************/
/******************* sample.lex ******************/
/**********************************************/
/******************* sample.lex ******************/
/**********************************************/
%{
#include <strings.h>
#include <stdio.h>
#include <stdlib.h>
#include "y.tab.h"
void yyerror(char *);
%}
Digit [0-9]+
%%
[\t ]+ ; /* ignore whitespace */ ;
{Digit} { yylval= atoi(yytext);
return NUM; }
[+] { return PLUS; }
[-] { return MINUS; }
. { printf("Error\n"); }
\n { return *yytext; };
%%
int yywrap()
{
return 0;
}
#include <strings.h>
#include <stdio.h>
#include <stdlib.h>
#include "y.tab.h"
void yyerror(char *);
%}
Digit [0-9]+
%%
[\t ]+ ; /* ignore whitespace */ ;
{Digit} { yylval= atoi(yytext);
return NUM; }
[+] { return PLUS; }
[-] { return MINUS; }
. { printf("Error\n"); }
\n { return *yytext; };
%%
int yywrap()
{
return 0;
}
/**********************************************/
/******************* ver.y ******************/
/**********************************************/
/******************* ver.y ******************/
/**********************************************/
%{
#define YYSTYPE double
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
%}
/* BISON Declarations */
%token NUM
%left MINUS PLUS
/* Grammar follows */
%%
input: /* empty string */
| input line
;
line: '\n'
| exp '\n' { printf ("Result:\t%d\n", $1); }
| error '\n' { yyerrok; }
;
exp:
NUM
| exp PLUS exp { $$ = $1 + $3; }
| exp MINUS exp { $$ = $1 - $3; }
;
%%
main ()
{
yyparse ();
}
yyerror (char *s)
{
printf ("Error:Ashis:: %s\n", s);
}
/**********************************************/
/**********************************************/
To run code:
#define YYSTYPE double
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
%}
/* BISON Declarations */
%token NUM
%left MINUS PLUS
/* Grammar follows */
%%
input: /* empty string */
| input line
;
line: '\n'
| exp '\n' { printf ("Result:\t%d\n", $1); }
| error '\n' { yyerrok; }
;
exp:
NUM
| exp PLUS exp { $$ = $1 + $3; }
| exp MINUS exp { $$ = $1 - $3; }
;
%%
main ()
{
yyparse ();
}
yyerror (char *s)
{
printf ("Error:Ashis:: %s\n", s);
}
/**********************************************/
/**********************************************/
To run code:
>> bison -dy ver.y
>> flex sample.lex
>> gcc -o out y.tab.c lex.yy.c -lm
>> ./out
/**********************************************/
Therefore, read the pdf and go at the links that given below to make a simple compiler or to know more.
>> flex sample.lex
>> gcc -o out y.tab.c lex.yy.c -lm
>> ./out
/**********************************************/
Therefore, read the pdf and go at the links that given below to make a simple compiler or to know more.
References:
- Compilers Principles, Techniques and Tools by Aho, Ravi Sethi, D. Ullman
- Compiler.pdf
- Toy compiler link
- Compiler.pdf
- Toy compiler link
মন্তব্যসমূহ
একটি মন্তব্য পোস্ট করুন