Monday, December 7, 2009

Compiler Construction: Phase One (Backus–Naur Form)

I had a project of compiler construction a few days ago. It is more interesting than I imagined. There would be a language (suppose it is Simple Programming Language). I need to build the BNF,lexical analyzer and the parser. My friend Wasi built the BNF according to the specifications given to us.

Here is the BNF file

"Name"    = 'SPL'
"Version" = '2009'
"Author"  = ''Mir Sajal'
"About"   = 'Simple SPL'
"Case Sensitive" = False
"Start Symbol" =


<Character>::= {letter}
<Digit>::= {digit}
<CharacterOrDigit>::= {alphanumeric}
NewLine ::= {CR}{LF}|{CR}


<Identifier>::= <Character><CharacterOrDigit>*
<Number>::= <Digit>*|<Digit>+"."<Digit>+
<Negative;>::= "-"
<NumberConstant>::= <Negative><Number>|<Number>
<CharacterConstant>::= "'"<Character>"'"
<Constant>::= <NumberConstant>|<CharacterConstant>
<Value<::= <Identifier>|<Constant>|"("<Expression>")"
<Term>::=^lt;Value>|<Value>>"*"<Value>+|<Value>"/"<Value>+
<Expression>::= <Term>|<Term>"+"<Term>+|<Term>"-"<Term>+
<Comparator>::= "=" | "><" | "<" | ">" | "<=" | ">="
<AndOr>::= AND | OR
<Check>::= [<Not>]<Expression><Comparator><Expression>
<Conditional>::= <Check>|<Check><AndOr><Check>+
<Program> ::= <Identifier>";"<Block>"ENDP"<Identifier>"."
<Block>::= [DECLARATIONS<DeclarationBlock>]CODE<StatementList>
<IdentifierList>::= <Identifier>|<Identifier>","<Identifier>+
<DeclarationBlock>::= <IdentifierList> OF TYPE<Type>";"
<Type>::= CHARACTER | INTEGER | REAL
<StatementList>::= <Statement>|<Statement>";"<Statement>+";"
<Statement>::= <Assignment> | <If> | <Do> | <While> | <Write> | <Read>
<Assignment>::= <Expression> "->" <Identifier>
<If>::= IF <Conditional> THEN <StatementList> ["ELSE" <StatementList>] ENDIF
<Do>::= DO<StatementList>WHILE<Conditional>ENDDO
<While>::= WHILE<Conditional>DO<StatementList>ENDWHILE
<For>::= FOR<Identifier>IS<Expression>BY<Expression>TO<Expression>DO<StatementList>ENDFOR
<Write>::= WRITE<OutputList> | Newline
<Read>::= READ<Identifier>
<OutputList>::= <Value> |<Value>","<Value>+

Monday, August 3, 2009

A Sample Process Calling Example

I used gnokii to send sms. So I need to execute the command from my code.

/usr/bin/gnokii --sendsms 8801712273933

So at first, I installed gnokii in my Ubuntu 9.04. Then
I copied the gnokiirc file from /etc to my home folder and renamed it to .gnokiirc
I opened the file and did some change to it. I was using my Siemens SK65 with a data cable.
I did some tweaking to my .gnokiirc file. All # signs indicate comments. I removed hash sign from some lines. Those lines are:


port = /dev/ttyUSB0
model = AT
initlength = default
connection = serial

As my model isn't supported officially by Gnokii so I added a hash sign before the "model = " line.
Then
I run this command in my console.

gnokii --identify


The output is something like this:
GNOKII Version 0.6.26
IMEI : 354784000367194
Manufacturer : SIEMENS
Model : Gipsy Soft Protocolstack
Product name : Gipsy Soft Protocolstack
Revision : 50,"OFFICIAL","2005

Then I wrothe C file sample.c












When I run this file, a new process is opened and gnokii --sendsms command is executed.After sending the SMS the process gonna close. The phone number in the code is the receiver of the message.
For more info, log into www.gnokii.com

Courtesy : Burhan Uddin


Algorithmic Aspects of Shadhinota (English to Bengali Dictionary)



The most crucial part of building a dictionary is to make an efficient searching technology. There are several ways to keep the words ….May be SQL database, XML data or simple text file. I prefered the text files to keep my data. I want to build a simple desktop utility for general users. I don't expect a general user should install a database software in order to use my dictionary. I aint very good at XML stuffs. So one way is open for me, that is to use text files.

But the main problem of using text file is to maintain the efficient algorithm. I used a simple concept for searching the desired words. Here we go now....

At first I used 26 directories for 26 letters of English alphabet. Every directory has some text files...suppose ab.txt, ac.txt,a.txt......etc. Here ab.txt has the words a, absent,abstract.... every words having the prefix of “ab". Now when I enter a word in my dictionary, at first it goes to the corresponding directory according to the first letter and next it goes to the corresponding text file. Now the second problem arises. One word can be used more than one time in a text file. For example:

The pattern of the text file may be like this
Word Meanings

Country Homeland,Motherland,Home..........

…....
…....
…....

Home House, Place of Accomodation ....

My dictionary searches the word and if it finds the word in the file then print the consecutive words and stop printing when it finds new line. But if same word is used more than once the total process get messed. So I need to distinguish the searched words from others. They need to be unique. I simply added a numeric character before every searched word. Now the text file will be like this

Word
Meanings
2Country Homeland,Motherland,Home..........
…....
…....
…....
2Home House, Place of Accomodation ....

Now every searched word has a unique identity. There could be approximate 26*25 files in 26 directories. A tree like hierarchy will be made and searching the words will be done via the traversing the file hierarchy.

Friday, July 31, 2009

Little bit about my Dictionary (Part One)


I made a small English to Bengali dictionary based on Qt4. In this post I gonna describe the environment setup process for it. I was so excited cause it was my first opensource desktop project.

Properties of the project:
Primary language: C++
Primary toolkit: QT4
Primary IDE: CodeBlocks with MinGW,QDevelop
Objective: Open Source cross platform English to Bengali Dictionary.
Setting Up the Environment:
OS: Windows XP
#install codeblocks-8.02mingw.I used C:\Program Files\CodeBlocks path
use gcc as default compiler
#install qt-win-opensource-4.4.3-mingw I used C:\Qt4 path
#install Qdevelop (optional)
Setting up environment variables:
Right click on My Computer and open properties box. Click on the advanced tab and go to
Environment Variable option.On user variable area click on New button and set the following
environment variables.

Variable name: PATH
Variable Values: C:\Qt\4.4.3\bin;C:\Program Files\CodeBlocks\MinGW\bin;
Variable name: QMAKESPEC
Variable Values: win32-g++
Variable name: QTDIR
Variable Values: C:\Qt\4.4.3

You may need to restart windows.
Go to Start menu..Run...cmd
Give the command:

qmake -v
make -v
gcc -v

Go to C:\Program Files\CodeBlocks\mingw\bin and create a batch file named make.bat
file: make.bat
contained text:

@echo off
mingw32-make %*

run that batch file from cmd.
then u will have to type make instead of mingw32-make
***In Windows You must Enable Unicode based Bengali.You can use a Bangla Keyboard Utility
which supports Unicode.***
OS: Linux
Install g++,QT4 with your package manager or from source code.
Compiling Shadhinota:
Command line compilation:
go to source folder from command line and give the following command:

qmake -project
qmake
make

Compiling using Qdevelop:
Open Qdevelop
Click on Project menu
select Open Project and open the *.pro file of Shadhinota's source directory.
Use Build or Rebuild option from Build menu.
Run the executable from the source folder.
Under Windows:
copy the mingwm10.dll,QtCore4.dll,QtCored4.dll,QtGuid4.dll from codeBlock/mingw/bin
and Qt4.4.3/bin directory to your executable's directory for portability.

In the next post I will write about the GUI part of Shadhinota and the algorithm
used in this software.

Thursday, July 9, 2009

using Tomcat in Ubuntu 9.04

I'm debugging my University's result processing software. The total software is written in JSP. I had to install Tomcat6 for this.Then I installed the package libapache2-mod-jk.
I gave the command in the terminal to confirm if the jk module is installed properly.
sudo ls /etc/apache2/mods-enabled/
The output was the following:
alias.conf autoindex.conf jk.load php5.conf
alias.load autoindex.load log_sql.load php5.load
auth_basic.load cgi.load log_sql_mysql.load setenvif.conf
authn_file.load deflate.conf log_sql_ssl.load setenvif.load
authz_default.load deflate.load mime.conf status.conf
authz_groupfile.load dir.conf mime.load status.load
authz_host.load dir.load negotiation.conf
authz_user.load env.load negotiation.load

We can see that jk.load is showed and we assume everything reqired to configure the server is okay.
Then I opened root window by pressing Alt+F2 with gksu nautilus command.I opened /etc/libapache2-mod-jk/workers.properties file and used these lines...

workers.tomcat_home=/usr/share/tomcat6
workers.java_home=/usr/lib/jvm/java-6-openjdk

Then I opened /usr/share/doc/libapache2-mod-jk/httpd_example_apache2.conf
copied the contents and paste it to the ending of /etc/apache2/apache2.conf
Then opened /etc/rc.local and added these two lines:

export JDK_HOME=/usr/lib/jvm/java-6-openjdk
export JAVA_HOME=/usr/lib/jvm/java-6-openjdk


Then I restarted apache2 and tomcat

sudo /etc/init.d/apache2 restart
sudo /usr/share/tomcat6/bin/./shutdown.sh
sudo /usr/share/tomcat6/bin/./startup.sh


Hosting place is /var/lib/tomcat6/webapps/ROOT/

Saturday, July 4, 2009

My first project using SWIG

Problem Summary:

We've a byte array in java which has 10000 elements. We have a shared library built with C , which contains some native functions who take char*,signed or unsigned char * parameters.
Now the task is to pass the byte array into the native functions and get the desired result.


Solution Summary:

We used SWIG to make a bridge between C and Java. There are two major tasks. One is to make the byte array acceptable as a char pointer in native functions and the other thing is to retrieve the array via pinning.

To do the first task I need to use the typemapping feature of SWIG. To do the second task I call the getByteArrayElements method which is a JNI method depends on JRE implementation on the desired platform.

Let we have a C file which contains the native functions and we have a Java file from which we call those functions. Here the sample files are given:


FILE: sample.c



















FILE: Runner.java




Now the task is to pass the byte array into the native functions and get the desired results. So a SWIG input file is needed to do the task. The warapper files will be used to make the bridge between two languages. The main challenge is to make the typemapping in that file. Here is the file I wrote to create the wrappers.


FILE: sample.i





Generating the warapper files:



Warning: This is a platform specific solution. Compilationa may vary from platform to platform. Here I used Ububtu 9.04 with openjdk implementation.

I generated my first required files by this SWIG command:
swig -java sample.i

Now I compiled demo1.cpp file with the following command
gcc -c -fpic sample.c

Then I compiled the wrapper file generarted by SWIG with the help of following
command which can be varied if the JDK header files location is different.
gcc -c -fpic sample_wrap.c -I/usr/lib/jvm/java-6-openjdk/include/ -I/usr/lib/jvm/java-6-openjdk/include/linux


Now its the time to make the library which will be used to access the array by native
methods. I used Linux platform, So the library will be libsample.so. If you are using Windows OS, hen
you should generate libsample.dll file.
gcc -shared sample.o sample_wrap.o -o libsample.so

I should add my directory's address to my System's PATH variable to avoid library
linking error with this command.
export LD_LIBRARY_PATH=.:$LD_LIBRARY_PATH

It's the time to compile the source java file:
javac Runner.java

Showing Output:
To view the output, I used this command.
java Runner

We shall see the output in the console.





Technical Details of sample.i File:




In the first portion of sample.i file we included sample.h file. Otherwise we need to manually declare the prototypes of the native functions.
After that part I include the various.i file of SWIG's library which is needed to do the necessary typemapping from byte datatype to char ponter. Then I declared the first function's (add() function)prototype that doesn't require typemapping.
The second function addIntArray also doesn't require typemapping. So I simply write its prototype. Now we proceed to the third native function testAddByteArray which returns int value and takes char pointer.Here we need to do little coding.
At first we need to rewrite the prototype like this: extern int testAddByteArray(int n,char *BYTE);
Look we use BYTE and INPUTkeyword here. This is must for making the typemaps of byte datatype.
Then I write an in method which describes the parameters and also the way to receive the parameters.
%typemap(in) (int INPUT,char *BYTE) {
$1= JCALL2(GetArrayLength,jenv,$input,0);
$2 = (char *) JCALL2(GetByteArrayElements, jenv, $input, 0);
//Pinning is occured here
}


The local variable $1 receives the array size and $2 receives the byte array by using getByteArrayElements JNI method. If the JRE supports pinning then the array will be retrieved via pinning, that means no copying will be occurred when the array passed to the native functions. The garbage collector must support pinning. In many implementations, pinning is undesirable because it complicates garbage collection algorithms and leads to memory fragmentation. If the garbage collector supports pinning, and the layout of the array is the same as that of a native array of the same type, then no copying is needed. Otherwise, the array is copied to a nonmovable memory block (for example, in the C heap) and the necessary format conversion is performed. A pointer to the copy is returned.


Similarly I've to write code to release memory with this code.
%typemap(argout) char *BYTE {
JCALL3(ReleaseByteArrayElements, jenv, $input, (jbyte *) $1, 0);
//Prevent default freearg typemap from being used
%typemap(freearg) char *BYTE ""

Monday, June 15, 2009

Using JNI method in SWIG's input file

Sometimes we've to use JNI's built in methods in SWIG's input file. Though SWIG's proxy class can do everything possible for JNI,but I prefer to use JNI's method where SWIG gets complicated. For example, I have a byte Array in my java file.If I want to retrieve the array by pinning, we can use getArrayPrimitiveCritical(
) JNI method.Here I gonna give an example that will help you a lot about using JNI's built in method in SWIG.

Let the java file is Runner.java and the code is:


public class Runner {
static {
try {
System.loadLibrary("sample");
}
catch (UnsatisfiedLinkError e) {

System.err.println("Native code library failed to load.\n" + e);
System.exit(1);
}
}



public static void main(String argv[]) {
//declaration of the array
byte array[] = new byte [10000];
for (int i = 0; i <>
array[i] = (byte)((int)i%64);

//call the native method

sample.point_accessPinArray(array);
}
}


Now the input file can be like this(sample.i)

/* File : sample.i */

%module sample
%{
#include "ByteArray.h"
#include "/usr/lib/jvm/java-6-openjdk/include/jni.h"

JNIEXPORT void JNICALL Java_sampleJNI_point_1accessPinArray(JNIEnv *jenv, jclass jcls,jbyteArray array) {

int i;int size;
size = (*jenv)->GetArrayLength(jenv, array);
//pinning process is going to be started from here if your garbage collector supports //pinning.

jbyte* body = (*jenv)->GetPrimitiveArrayCritical(jenv, array, NULL);

(*jenv)->ReleasePrimitiveArrayCritical(jenv, array, body, 0);
}
%}
%native(point_accessPinArray) void *point_accessPinArray(jbyteArray array);



Commands to compile and run:

$swig -java sample.i
$gcc -c -fpic sample_wrap.cxx -I/usr/lib/jvm/java-6-openjdk/include/ -I/usr/lib/jvm/java-6-openjdk/include/linux/
$gcc -shared sample_wrap.o -o libexample.so
$export LD_LIBRARY_PATH=.:$LD_LIBRARY_PATH
$javac Runner.java
$java Runner

Sunday, June 14, 2009

Using SWIG to cooperate Java with C++

Courtesy : SWIG Tutorial

Let the main file where my functions and variables are located is example.cxx
Write that source.

Then create an interface file .let example.i
where the previous module's variables and functions have to be declared.

Sample:


/* example.i */
%module example
%{
/* Put header files here or function declarations like below */
extern type variableName;
extern type functionName(parameters);
%}

extern type variableName;
extern type functionName(parameters);
//end of file



Then create main java file.Let Its name is main.java


//main.java
public class main {
public static void main(String argv[]) {
System.loadLibrary("exampl
e");
System.out.println(example.getvariableName());
System.out.println(example.functionName(parameters));

}
}



commands:
$swig -c++ -java example.i
$g++ -c -fpic example.cxx
$g++ -c -fpic example_wrap.cxx -I/usr/lib/jvm/java-6-sun-1.6.0.06/include/ -I/usr/lib/jvm/java-6-sun-1.6.0.06/include/linux
$g++ -shared example.o example_wrap.o -o libexample.so
$export LD_LIBRARY_PATH=.:$LD_LIBRARY_PATH
$javac main.java
$java main


You can make a shell script to automate the commands.