Semantic Analyzer

This post is continuation of my previous blog post regarding Compiler construction in which I had discussed "Lexical" and "Syntax" analyzer. In this post, I will discuss the Semantic Analyzer which gave me a really hard time during the semester. It was tougher than the previous 2 phases. For this phase, we were alloted one month (The whole of March).

The job of the Semantic Analyzer is to ensure that the code is semantically correct. In this phase, the compiler associates semantic information to the parse tree built during the Syntax Analysis phase and constructs Symbol Table. A Symbol Table holds information about identifiers in the source code regarding their declaration and location in the code. At this point, the code is syntactically correct and being checked for semantic errors such as type checking, object binding, assignment of local variables before use, etc.

Click here to download Semantic Analyser.zip file. Run JFlex tool over Scanner.txt file to generate a lexer file. Use 'byaccj' tool over CS-540Assignment_3.txt file to generate a parser file. Byaccj is a YACC-compatible parser generator tool that takes an input source file and produces one or more Java files. For detailed information about byaccj and its use, click here. The zip file also contains a README.txt file that contains step-by-step instructions for the user. You will need to download and install "byaccj1.15_win32" before proceeding with the third instruction. The test.txt file is a test file for testing the functionality of the Semantic Analyzer.

Compiler in Java

In my second semester at George Mason University, I took a course "CS-540 Language Processors". In this course, we had to do 4 projects. Guess what were these 4 projects? They were the 4 phases of compiler construction:
1) Lexical Analyzer
2) Syntax Analyzer
3) Semantic Analyzer
4) Code Generator

The compiler was developed for the subset of Tiger language. Tiger language is a small, imperative language with integer and string variables, arrays, records, and nested functions. Its syntax resembles some functional languages.

In this post, I'm going to discuss about the Lexical and Syntax Analyzer. Both of these phases were part of the second project. They were developed using JFlex tool. JFlex is a lexical analyzer generator for Java that is designed to work together with the LALR parser generator CUP by Scott Hudson, and the Java modification of Berkeley Yacc known as BYacc/J by Bob Jamison. For detailed information about JFlex and its specification, click here.

The reason I'm not discussing the first project is that it was a small one whose aim was to facilitate students in getting familiar with JFlex. In order to work with JFlex, one has to provide lexical specification of the language in a format acceptable by JFlex. This specification, as mentioned in the link above, consists of three parts, divided by %%:
a) usercode
b) options and declarations
c) lexical rules.

From this specification JFlex generates a .java file with one class that contains code for the scanner. The class has a constructor that reads standard input and contains a function yylex() that runs the scanner and used by parser to get the next token from the input.

Click here to download my second project which is a text file. Download JFlex and run it over this text file which will generate a .java file. Create a new Java Application project and include the newly created file in it. This file reads input from a file. Therefore, you should provide full path of the test file along with filename as parameter when running this project.

Checkers code

Click here to download the source code for checkers game mentioned in my previous post. It was developed in Visual C#.NET 2005.

The heuristic function is used to get the best possible move for computer at each of its turns. It works as follows:
- For each of the computer's pieces, there are 2 diagonally forward moves available if its a non-king piece and 2 diagonally forward moves and 2 diagonally backward moves are available if its a king piece.
- For each of these available moves, the diagonal distance to the nearest human piece is calculated using the function "EvaluateMove()".
- The diagonal distance value and coordinates of the move with the greatest diagonal distance is stored for the piece which is currently its best move.
- The previous steps are repeated for each of the computer's pieces.
- Finally, the best move of all the pieces are compared and the move with the highest distance is chosen by computer.

Here is the code that carry out these tasks:

public PlayerMove GetBestMove (Player pl)
{
int distance = 0;
int x = pl.X_Coordinate;
int y = pl.Y_Coordinate;
int []x_pos = new int[4];
int []y_pos = new int[4];
bool CanJump, MoveAvailable, HasAtleastOneMove = false;
int DiagDist = 0,MinDist = -10;

PlayerMove move = new PlayerMove();
move.player = pl;

x_pos[0] = x + 1; y_pos[0] = y + 1;
MoveAvailable = CheckMoveAvailability(x_pos [0], y_pos[0]);
CanJump = IsJumpAvailable(x_pos[0], y_pos[0], x_pos[0] + 1, y_pos[0] + 1, pl);

if (MoveAvailable||CanJump)
{
HasAtleastOneMove = true;

if (CanJump)
{
move.player = pl;
move.New_X_Coordinate = x_pos [0] + 1;
move.New_Y_Coordinate = y_pos[0] + 1;
move.CapturedMove = true;
return move ;
}

DiagDist = EvaluateMove(x_pos[0],y_pos[0],x,y);
MinDist = DiagDist;
move.New_X_Coordinate = x_pos [0];
move.New_Y_Coordinate = y_pos[0];
move.Heuristic = MinDist;
move.CapturedMove = false;

}

x_pos[1] = x - 1; y_pos[1] = y + 1;
MoveAvailable = CheckMoveAvailability(x_pos[1], y_pos[1]);
CanJump = IsJumpAvailable(x_pos[1], y_pos[1], x_pos[1] - 1, y_pos[1] + 1, pl);
if (MoveAvailable||CanJump)
{
HasAtleastOneMove = true;

if (CanJump)
{
move.player = pl;
move.New_X_Coordinate = x_pos[1] - 1;
move.New_Y_Coordinate = y_pos[1] + 1;
move.CapturedMove = true;
return move;
}

DiagDist = EvaluateMove(x_pos[1],y_pos[1],x,y);

if (MinDist < DiagDist) // Use of Heuristics
{
MinDist = DiagDist;
move.New_X_Coordinate = x_pos[1];
move.Heuristic = MinDist;
move.New_Y_Coordinate = y_pos[1];
move.CapturedMove = false;
}

}

if (pl.IsKing)
{
x_pos[2] = x + 1; y_pos[2] = y - 1;
MoveAvailable = CheckMoveAvailability(x_pos[2], y_pos[2]);
CanJump = IsJumpAvailable(x_pos[2], y_pos[2], x_pos[2] + 1, y_pos[2] - 1, pl);
if (MoveAvailable||CanJump)
{
HasAtleastOneMove = true;

if (CanJump)
{
move.player = pl;
move.New_X_Coordinate = x_pos[2] + 1;
move.New_Y_Coordinate = y_pos[2] - 1;
move.CapturedMove = true;
return move;
}

DiagDist = EvaluateMove(x_pos[2], y_pos[2], x, y);

if (MinDist < DiagDist)
{
MinDist = DiagDist;
move.New_X_Coordinate = x_pos[2];
move.New_Y_Coordinate = y_pos[2];
move.Heuristic = MinDist;
move.CapturedMove = false;
}

}

x_pos[3] = x - 1; y_pos[3] = y - 1;
MoveAvailable = CheckMoveAvailability(x_pos[3], y_pos[3]);
CanJump = IsJumpAvailable(x_pos[3], y_pos[3], x_pos[3] - 1, y_pos[3] - 1, pl);

if (MoveAvailable||CanJump)
{
HasAtleastOneMove = true;

if (CanJump)
{
move.player = pl;
move.New_X_Coordinate = x_pos[3] - 1;
move.New_Y_Coordinate = y_pos[3] - 1;
move.CapturedMove = true;
return move;
}

DiagDist = EvaluateMove(x_pos[3], y_pos[3], x, y);

if (MinDist < DiagDist)
{
MinDist = DiagDist;
move.New_X_Coordinate = x_pos[3];
move.Heuristic = MinDist;
move.New_Y_Coordinate = y_pos[3];
move.CapturedMove = false;
}

}
}
if (HasAtleastOneMove)
return move;
else
return null;

}


private int EvaluateMove(int x, int y, int Current_X, int Current_Y)
{
int MinDistToOpponent = 0, temp = 0, distance = 0,temp_x, temp_y;
temp_x = x;
temp_y = y;

while (true)
{
if (temp_x + 1 == Current_X && temp_y + 1 == Current_Y)
{
temp = -1;
break;
}

if ((temp_x > 8) || (temp_y > 8))
{
distance = 100;
break;
}

else if (IsCellOccupiedByOpponent(temp_x, temp_y))
{
distance = temp;
break;
}

else
{
temp = temp + 1;
temp_x = temp_x + 1;
temp_y = temp_y + 1;
}
}

temp = 0;
temp_x = x;
temp_y = y;

while (true)
{
if (temp_x - 1 == Current_X && temp_y + 1 == Current_Y)
{
temp = -1;
break;
}


if ((temp_x < 1) || (temp_y > 8)) // No opponents in this path
{
temp = 100;
break;
}

else if (IsCellOccupiedByOpponent(temp_x, temp_y))
{
break;
}

else
{
temp = temp + 1;
temp_x = temp_x - 1;
temp_y = temp_y + 1;
}
}

if (distance > temp && temp != -1)
distance = temp;

temp = 0;
temp_x = x;
temp_y = y;

while (true)
{
if (temp_x + 1 == Current_X && temp_y - 1 == Current_Y)
{
temp = -1;
break;
}

if ((temp_x > 8 ) || (temp_y < 1)) // No opponents in this path
{
temp = 100;
break;
}

else if (IsCellOccupiedByOpponent(temp_x, temp_y))
{
break;
}

else
{
temp = temp + 1;
temp_x = temp_x + 1;
temp_y = temp_y - 1;
}
}

if (distance > temp && temp != -1)
distance = temp;

temp = 0;
temp_x = x;
temp_y = y;

while (true)
{
if (temp_x - 1 == Current_X && temp_y - 1 == Current_Y)
{
temp = -1;
break;
}

if ((temp_x < 1) || (temp_y < 1)) // No opponents in this path
{
temp = 100;
break;
}

else if (IsCellOccupiedByOpponent(temp_x, temp_y))
{
break;
}

else
{
temp = temp + 1;
temp_x = temp_x - 1;
temp_y = temp_y - 1;
}
}

if (distance > temp && temp != -1)
distance = temp;

return distance;
}