PoiNtEr->: December 2010

                             Difference between a dream and an aim. A dream requires soundless sleep, whereas an aim requires sleepless efforts.

Search This Blog

Friday, December 31, 2010

Intermediate code Generation :Compiler Design:

Why Intermediate Representation is important???
Front end translates a program into intermediate representation.Its good to translate in IR because now we can use different back ends to convert the same code in different destination language ,so it give an ease to the construction of different compiler.Thats why every compiler programmer wants its middle phase to be intermediate representation.
hence benefits of IR are
1:Retargeting (as explained above)
2:Now we can use machine independent optimizer to optimize the produced intermediate code as the produced intermediate code is neither in source language form nor in destination language form .

figure showing intermediate code generator
kinds of IR are:
1:syntax tree
2:three address code
3:postfix
Syntax tree:
it depicts the hierarchical structure of source program
Postfix:
it is a lineralised representation of syntax tree
Three addess code:
A three address code is a sequence of statements of general form:
Z=x op y



In some books IR techniques are divided in following category
1:high level representation
2:low level representation
High level Representation is further divided into following:
1:Abstract syntax tree
2:Directed Acyclic Graph
3:P-code
Low level Representation
1:Three Address code
/* I will discuss three address code in detail in next of my posts */

Thursday, December 30, 2010

apache and Php5 in ubuntu

Step 1: install Apache2:

sudo apt-get install apache2

And you get apache2 installed as well. To double check, point your browser to http://localhost, and you should see the Apache2 placeholder page like this.

Step 2: To install support for PHP, do the usual

sudo apt-get install php5 libapache2-mod-php5

To verify that everything installed correctly and php support is enabled, you need to restart apache by doing this

sudo /etc/init.d/apache2 restart

Create a test php file called info.php, using a text editor of your choice (say gedit)

sudo gedit /var/www/info.php

and paste the following content and save the file

<?php

phpinfo();

?>

Now open the following page http://localhost/info.php and you should see something like this

Wednesday, December 29, 2010

BooTsTraPPing (CompilEr)

All this may seem to be skirting around a really nasty issue - how might the first high-level
language have been implemented? In ASSEMBLER? But then how was the assembler for
ASSEMBLER produced?

A full assembler is itself a major piece of software, albeit rather simple when compared with a
compiler for a really high level language, as we shall see. It is, however, quite common to define
one language as a subset of another, so that subset 1 is contained in subset 2 which in turn is
contained in subset 3 and so on, that is:

 

Bootstrapping

 

One might first write an assembler for subset 1 of ASSEMBLER in machine code, perhaps on a
load-and-go basis (more likely one writes in ASSEMBLER, and then hand translates it into
machine code). This subset assembler program might, perhaps, do very little other than convert
mnemonic opcodes into binary form. One might then write an assembler for subset 2 of
ASSEMBLER in subset 1 of ASSEMBLER, and so on.

This process, by which a simple language is used to translate a more complicated program, which
in turn may handle an even more complicated program and so on, is known as bootstrapping, by
analogy with the idea that it might be possible to lift oneself off the ground by tugging at one’s boot-straps.

Tuesday, December 28, 2010

First and Follow (compiler)

The construction of a predictive parser is aided by two functions associated with a grammar G. These

functions, FIRST and FOLLOW, allow us to fill in the entries of a predictive parsing table for G, whenever

possible. Sets of tokens yielded by the FOLLOW function can also be used as synchronizing tokens during

panic-mode error recovery.

just suppose for a sec that you r ll(1) parser and you have n supernatural power of seeing the future of string by one step.

in above statement that supernatural power is nothing but finding follow of given non-terminal to predict the next items....

hope u got the point ...n ya dnt take super natural shit seriously ... ;)

FIRST(α)

If α is any string of grammar symbols, let FIRST(α) be the set of terminals that begin the strings derived

from α. If α ⇒ ε then ε is also in FIRST(α).

To compute FIRST(X) for all grammar symbols X, apply the following rules until no more terminals or ε can

be added to any FIRST set:

1. If X is terminal, then FIRST(X) is {X}.

2.If X → ε is a production, then add ε to FIRST(X).

3.If X is nonterminal and X →Y1 Y2 ... Yk . is a production, then place a in FIRST(X) if for some i, a is in

FIRST(Yi), and ε is in all of FIRST(Y1), ... , FIRST(Yi-1); that is, Y1, ... ,Yi-1 ⇒ ε. If ε is in FIRST(Yj) for

all j = 1, 2, ... , k, then add ε to FIRST(X). For example, everything in FIRST(Y1) is surely in

FIRST(X). If Y1 does not derive ε, then we add nothing more to FIRST(X), but if Y1⇒ ε, then we add

FIRST(Y2) and so on.

Now, we can compute FIRST for any string X1X2 . . . Xn as follows. Add to FIRST(X1X2 ... Xn) all the non-

ε symbols of FIRST(X1). Also add the non-ε symbols of FIRST(X2) if ε is in FIRST(X1), the non-ε symbols

of FIRST(X 3) if ε is in both FIRST(X 1) and FIRST(X2), and so on. Finally, add ε to FIRST(X1X2 ... Xn) if,

for all i, FIRST(X i) contains ε.

FOLLOW(A)

Define FOLLOW(A), for nonterminal A, to be the set of terminals a that can appear immediately to the right

of A in some sentential form, that is, the set of terminals a such that there exists a derivation of the form

S⇒αΑaβ for some α and β. Note that there may, at some time during the derivation, have been symbols

between A and a, but if so, they derived ε and disappeared. If A can be the rightmost symbol in some

sentential form, then $, representing the input right endmarker, is in FOLLOW(A).

To compute FOLLOW(A) for all nonterminals A, apply the following rules until nothing can be added to any

FOLLOW set:

1.Place $ in FOLLOW(S), where S is the start symbol and $ is the input right endmarker.

2.If there is a production A ⇒ αΒβ, then everything in FIRST(β), except for ε, is placed in FOLLOW(B).

3.If there is a production A ⇒ αΒ, or a production A ⇒ αΒβ where FIRST(β) contains ε (i.e., β ⇒ε),

then everything in FOLLOW(A) is in FOLLOW(B).

EXAMPLE

Consider the expression grammar :

E → T E’

E’→ + T E’ | ε

T → F T’

T’→ * F T’ | ε

F → ( E ) | id

Then:

FIRST(E) = FIRST(T) = FIRST(F) = {( , id}

FIRST(E’) = {+, ε}

FIRST(T’) = {*, ε}

FOLLOW(E) = FOLLOW(E’) = {) , $}

FOLLOW(T) = FOLLOW(T’) = {+, ), $}

FOLLOW(F) = {+, *, ), $

/*important point to note ...most of student do mistake while finding follow..please remember if u r finding follow and applying rule2 then that doesnt mean that now you dont have to check for condition 3,check for it also if condition applies then follow its rules also */

/* have any problem then feel free 2 comment*/

Secrets Of C language

I was solving problems some time ago and came to know some good facts about c and c++ and wrote some interesting codes.

1. A C program which can print the file name it is kept in ;) .

#include<stdio.h>

main(){

printf(“the source file name is %s\n”,__FILE__);

}

actually __FILE__ is a macro which stands for the file name the programme is kept in and the compiler does the rest.

2. Usage of assignment suppression operator in scanf – Suppose you have some crap input (the input is provided to you but that is not of any use to your program) then what normally we do is take a dummy variable and scan the input in that variable. Example -

int dummy;

scanf(“%d”,&dummy);

but there is one more method which can save memory and time

what you do is

scanf(“%*d”);

In this method, we provide a character * to the scanf function and by doing that; scanf will scan the input from standard input but it wont assign it to any variable. This is scanned in a buffer of sufficient size and you dont have to worry about that.

3. Printing something with variable width -

Suppose you are to print some formatted output in some program and for that sometime you require to print a variable in a fix width ..

for example if you have to pring an integar in width of 5 or more then you do

printf(“%5d”, var);

now if var is 10 it will append 2 leading spaces to complete the atleast 5 width rule.

now suppose you dont want leading spaces but leading zeroes, then here is another method to write the same -

printf(“%05d”,var);

now if var is 10 it will print 00010 and so on.

Another condition comes if the width in which we want to print the variable is not known at the compile time – suppose you want to print variable with a width which is contained in another variable, then we can use -

printf(“%*d”,x,var);

here x is the width length variable. Whenever we do this * operator .. then it looks for the next integar argument provided in the arguments and then assumes that it is the width in which the variable is to be printed.

Now if x = 2 then it will b the same as

printf(“%2d”,var); ..

this way we can work with this width thing pretty well.

If any of you guys know some nice facts about c or cpp language, then please post them as comments. Any gud suggestions related to things I posted are also welcome. Have Fun

Saturday, December 25, 2010

Wget Commands(UbUnTu)

it is usually installed in all Linux distros, but if not we can install it.

Debian / Ubuntu

apt-get install wget

Fedora / CentOS

yum install wget

Sabayon

emerge wget

Now lets explore some of its features.

If there is the need to download a single page.

wget http://www.site.com/file.pdf

But if there is the need to download the entire site, use the recursive option.

wget -r http://www.site.com

Now what to do if only certain file types are needed?

Use the -A option

To download only pdf and jpg use.

wget -r -A pdf,jpg http://www.site.com

Well now suppose that there is the need to follow external links, usually wget does not do this, here we can use -H option.

wget -r -H -A pdf,jpg http://www.site.com

This is a little bit dangerous as it could end up downloading a lot much files that the ones needed, so we could limit the sites to follow, we will use -D for this.

wget -r -H -A pdf,jpg -Dfiles.site.com http://www.site.com

By default wget will follow 5 levels when using -r option, we can change this behaviour with the -l option.

wget -r -l 2 http://www.site.com

This way only two levels depth will be followed

Concept of Pointers

click here to download entire pdf

HeRmiTe Spline( For computer Graphics,B.tech C.S)

Hermite spline ( named after ~the French ~

mathematician Charles ~Hermite) is an

interpolating piecewise cubic polynomial with a specified tangent at each control

point.

Unlike the natural cubic splines, Hermite splints can be adjusted locally

because each curve section is only dependent on its endpoint constraints.

If P(L)represents a parametric cubic point function for the curve section be-

tween control points pi and pk, a s shown in Fig. then the boundary

conditions that define this Hermite spline is

with Dpk and Dpk+1,

specifying the values for the parametric derivatives (slope of

the curve) a t control points pk and p k + respectively.

We can write the vector equivalent of above equation for hermite also:

where the x component of P is,

and similarly for the

y and z components

The matrix equivalent of above equation

and the derivative of thin point function can be expressed as

Hermite polynomials can be useful for some digitizing applications where

it may not be too difficult to specify or approximate the curve slopes. But for

most problems in computer graphics, it is more useful to generate spline curves

without requiring input values for curve slopes or other geometric information,

in addition to control-point coordinates. Cardinal splines and Kochanek-Bartels

splines, discussed in the following two sections, are variations on the Hermite

splines that d o not require input values for the curve derivatives at the control

points. Procedures for these splines compute parametric derivatives from the co-

ordinate positions of the control points.

Substituting endpoint values and 1 for parameter u Into the previous two equations, we can express the Hermite boundary conditions

Hermite polynomials can be useful for some digitizing applications where

it may not be too difficult to specify or approximate the curve slopes. But for

most problems in computer graphics, it is more useful to generate spline curves

without requiring input values for curve slopes or other geometric information,

in addition to control-point coordinates. Cardinal splines and Kochanek-Bartels

splines, discussed in the following two sections, are variations on the Hermite

splines that d o not require input values for the curve derivatives at the control

points. Procedures for these splines compute parametric derivatives from the co-

ordinate positions of the control points.

lex program

The following is an example of a lex program that implements a rudimentary scanner for a Pascal-like syntax:

%{

/* Need this for the call to atof() below. */

#include <math.h>

/* Need this for printf(), fopen(), and stdin below. */

#include <stdio.h>

%}

DIGIT [0-9]

ID [a-z][a-z0-9]*

%%

{DIGIT}+ {

printf("An integer: %s (%d)\n", yytext,

atoi(yytext));

}

{DIGIT}+"."{DIGIT}* {

printf("A float: %s (%g)\n", yytext,

atof(yytext));

}

if|then|begin|end|procedure|function {

printf("A keyword: %s\n", yytext);

}

{ID} printf("An identifier: %s\n", yytext);

"+"|"-"|"*"|"/" printf("An operator: %s\n", yytext);

"{"[^}\n]*"}" /* Eat up one-line comments. */

[ \t\n]+ /* Eat up white space. */

. printf("Unrecognized character: %s\n", yytext);

%%

int main(int argc, char *argv[])

{

++argv, --argc; /* Skip over program name. */

if (argc > 0)

yyin = fopen(argv[0], "r");

else

yyin = stdin;

yylex();

}

/*command required to run program on linux is "lex <filename.l>" ,where ".l" is extension of lex file.you can also google flex and download it to run above.*/

/*after running above program you will get a "lex.yy.c" if you are using flex. */

A Newbies guide to Linux



/*Comments are encouraged and motivates author to write more interesting posts*/
Over the years there has been tremendous growth in Desktop Linux , and Linux distributions these days are getting more and more user friendly with all kind of fancy graphical interface . Still the power of Linux or any other UNIX distribution lies in it console and shell commands . Now even though shell is often considered difficult by Linux newbies still it's possible to learn few basic commands , and in this article I'll try to explain basic commonly used console commands .
The general format of Linux command line :
$ command -options target
Where target is target filename or expression
Some Commonly used Linux commands : -
Showing Currently working directory
The command prints the current working directory , for example
$ pwd
/home/vishal
It shows /home/vishal because /home/vishal is the currently working directory .
Listing files in the directory : -
ls -a :- Displays all the files in the directory , by default ls does not show hidden files( hidden files start with (.) )
ls -l :- Displays the detailed listing of the files in the directory , information like Permission , links , owner , group , size , date , name are displayed
ls -S : the -S option displays the file list in a sorted fashion with the biggest sized file displayed first
ls -sS : the -s option displays file size before the filename combined with -S option it displays a sorted list of files currently in directory with the filesize infront of the filename.
ls -Sr : the -r option combined with -S displays the sorted list of files in the current directory with the smallest sized file displayed first.
ls -sSh : the command displays the sorted list of files in the directory with the file size displayed in a more understandable fashion.
ls -F : this command displays the list of files and directory with directories ending with (/) , executable files with (*) , Symbolic links with ( @)
Removing Directories/File : -
rm directory_name/File_name : Removes directory , Files
rm – i filename/directory_name : Removes directory/file with confirmation
rm -rf filename/directory_name : Removes directory and sub-directory recursively , -f stands for Force
rm -r Directory_Name : Removes directory if it is empty
Copying completely one directory to another directory
cp -r source_directory_name destination_directory_name
-r stands for Recursively
Creating Archives :
gzip (GNU Zip)
gzip can be used for compressing a single file , it is not meant for compressing entire directories as other file formats do . The default extension used bu gzip archives is (.gz) .
gzip filename.ext would create a file name filename.gz and replace the existing filename.ext file with filename.ext.gz file which is compressed gzip archive , the gzip command retains the file's attributes the modification,time stamp, access etc.
The compression level of the file can be varied by using options from 1 to 9 while compressing a file
gzip -1 filename.ext would compress the file quicker but with less compression.
gzip -9 filename.ext would compress the file slower but with more compression.
the default compression level is 6.
The filesize of compressed gzip archive would depend on the orignal file format it would do well with a non - archived file such as txt,doc,bmp etc but would fair poorly with JPG , PNG etc which are already compressed by some algorithm.
The gzipped file can be decompressed by using the gzip -d or gunzip command at the command line.
the default file extension used by gzip archives is .gz if you want to use a different file extension it could be done by using the -S option
example : gzip -S .x filename.ext would create a archive by the name of filename.ext.x
tar ( Tape archiver )
The tar program combines a number of files and directory in a single file which then can be compressed using a gzip or bzip2 program to reduce it's file size.
tar -cvf file.tar file1 file2 file3 file4 : This would create a tar archive combining the file1 file2 and file3 into a single file the archive have the same name as the file1 since we have specified the -f option which makes tar use the first option as the filename of the archive , -c tells the tar program to create a archive and -v option displays all the background information on the screen.
tar -cvf file.tar file1.tar file/ : This command would create a archive named file.tar with file1.tar and file subdirectory as the content of the archive .
tar -cvzf file.tar.gz file1 file2 file3 file/ : This command would create a tar file consisiting of the files and directory specified and then the file is compressed using the gzip program, to create a final archive file.tar.gz.
tar -cvjf file.tar.bz2 file1 file2 file3 file/ : This command would create a tar file consisiting of the files and directory specified and then the file is compressed using the bzip2 program, to create a final archive file.tar.bz2
tar -xvf file.tar : This command would extract all the files contained in the tar file file.tar
tar -xvjf file.tar.bz2 : This command would extract all the files contained in the file file.tar.bz2 , it would first call the bzip2 program to extract the file.tar and the call tar to extract the file.tar and it's conetent.
tar -xvzf file.tar.gz : This command would extract all the files contained in the file.tar.gz , it would first call the gzip program to extract the file.tar and then call tar to extract file.tar and it's content.
If you have created the file.tar but want to add some file(s) later it can be done using the following command and using the -rf option .
tar -rf file.tar file(s)
bzip2
The bzip2 is similar to gzip program but compresses file better and more effectively as compared to gzip program . The default extension used by bzip2 program is (.bz2) , the usage of bzip2 is very similar to the gzip program but has some additional options , which are described here .
bzip2 -k filename.ext : This commmand would create a archive of the filename.ext but would also keep a copy of the orignal file unlike gzip which replaces existing file with the the new archive file.
the bzip2 program also has different compression level ranging from 1 -least to 9-maximum . which can be set by using syntax like : bzip2 -1 filename.ext
bzip2 archives can be extracted by using the bzip2 -d option or by using the program bunzip2 .
Displaying file in the console
$ cat file-name(s)
The above command displays the content of file one after the another .
cat v1 v2 v3 > v4 This statement would combine the content of textfile v1,v2,v3 and create a new file v4 having all the content of three files.
cat v4 >> v5 This statement would append v4 file at the end of file v5. To end the statement type (Ctrl + D (EOF))
cat > filename << STOP This statement would create a filenamed filename at the console and accept input from the user for the file , the file is ended(terminated ) on pressing Ctrl + D.
$ more file-name
The above command displays the content of file page-wise , asking user to press a key usually “space bar” when the entire screen is filled to move on to next screen. The command is particularly useful for long files.
$ head File-Name
The above command displays the first few lines of the file .
$ tail file-name
The above command displays the last few lines of the file .
$ wc file-name
The above command would count the lines , words and characters of the file .
Creating Soft-Link/File -Aliases
If you are right now in /home/xyz directory and you issue the following command , it would create a soft-link of the file( file-name ) in the directory /home/xyz
$ ln -s /path/file-name
Searching Commands
$ grep -r “Text” *
The above command would display all the files in the current directory and all it's sub-directory having “Text” by searching recursively .
$ grep -n “Text” filename
The above command search for “Text” in the file-name and displays the line-number where the text was found .
$ grep “file[- ] name “ file
The above command searches for text “file-name” and “file name” in the file and displays it on the screen .
$ find file-name
the above command searches for file-name in directory hierarchy .
Some Other Miscellaneous Commands
$ cal
Commands displays calendar on the screen
$ clear
The command clears the console screen of any text
$ man command
Gives information about command
$ passwd
Above command allows changing of password of logged in user
$ df
Above command displays the free diskspace .
$ who
The command shows the user who are logged into the system .
$ env
Shows environment variables
$ ps
Shows running processes
$ top
The above command shows a dynamic real-time view of running system . It displays system summary information as well as list of task being managed by the linux kernel .

Friday, December 10, 2010

C Graphics Programming in Ubuntu

C Graphics Programming in Ubuntu (how to run c graphics program on ubuntu?? ANswer is here->)

An EasY solution for all those who want to run c graphics program on Ubuntu

libgraph - library providing the TurboC graphics API ( graphics.h) in Linux using SDL.

For using this , you need to follow some simple steps as mentioned below:

First of all, you need to install the dependencies so that all the required compiler tools gets installed.For that you need to run the given command on the terminal:

sudo apt-get install build-essential

Next you need to install some packages. They are: libsdl-image1.2,libsdl-image1.2-dev,guile-1.8 and guile-1.8-dev. For that run the given command at the terminal:

sudo apt-get install libsdl-image1.2 libsdl-image1.2-dev guile-1.8 guile-1.8-dev

Now, download and install libgraph-1.0.2.tar.gz from the link :

http://mirror.veriportal.com/savannah/libgraph/

Download this file in any folder and extract it in the home folder or on the desktop wherever you want.

Open the terminal and navigate to the folder where you have extracted libgraph-1.0.2 with the help of cd command. Install this using the commands given below:

./configure (Return)

sudo make (Return)

sudo make install (Return)

After this you can start your C graphics programming in linux. Now try writing a simple C graphics program by including the header file "graphics.h". You can do the programs as you in TURBO C.

For writing the programs you can use the "gedit" tool in ubuntu. For compiling the programs, navigate to the source program folder and use the following command:

gcc filename.c -lgraph

if u get string conversion error try this:

gcc filename -lgraph -Wno-write-string

if you get this error(/tmp/ccYXvPbQ.o:(.eh_frame+0x12): undefined reference to `__gxx_personality_v0'

collect2: ld returned 1 exit status

)

then try this

gcc filename -lstdc++ -lgraph -Wno-write-strings

For executing the program, use the command ./a.out

The error “./a.out: error while loading shared libraries: libgraph.so.1: cannot open shared object file: No such file or directory” can be solved by

sudo cp /usr/local/lib/libgraph.* /usr/lib

Have any problem feel free to post it here.