Compiler Design Laboratory

7. Domain Analysis

In this lab we build symbol table for the analysis and verification of identifiers. Unlike the analysis performed on a procedural language, where the main unit of analysis was the procedure or function and examine global variables, local bodies along with their routines accesses to object-oriented languages we deal with several concepts such as classes the relationship of inheritance, members: attributes and methods, polymorphism, overloading, basic types, user-defined types. It should be noted that in a real object-oriented language we deal with much more concepts such as:

• packages
• classes
• methods
• access modifiers (abstract, concrete, final, static)
• exceptions
• assertions
• synchronization mechanisms
• etc

7.1 The Type System

In order to declare variables, method types in a language we need a type system. The set of types is twofold: primitive types (value or expanded) and user-defined types (reference).

7.1.1 Primitive types (value)

Primitive types are: boolean, integer and integer array.

7.1.1.1 Type Boolean

Boolean type is a scalar type is represented by the keyword boolean .

7.1.1.2 Type Integer

Type a whole is a scalar type and is represented by the keyword int.

7.1.1.3 Type Integer Array

Type array of integers is a reference type and is represented by the construction int [] .

7.1.2 User-defined types (reference)

7.1.2.1 Class Type

Object class library class this or if this derby to oricarei MiniJava class. User-Defined Types User-defined types are generated by user-defined classes.

7.2 Semantic Rules

7.2.1 Rules for classes and relations between them

• Class names must be unique in the package, for simplicity we use a single one, the default package.
• Check the uniqueness of the class names declared in default package.
• All classes must be public in the default package.
• Inheritance relationships between classes must be recorded in the class table in order to perform several checks. Each entry in the table of classes will have one reference to a possible superclass.
• Circular dependency inheritance cycles are not allowed between classes. In other words, a class can not have ancestors among its descendants. Check the class graph for cicles.
• The inheritance relationship between classes in MiniJava can not be multiple because it is limited by the syntactic rules.

7.2.2 Rules for class members

• In MiniJava members can be of two kinds: attributes or methods.
• Each member has the signature of its own.
• A class may not have two members with the same signature. Check the signature uniqueness of each member in the class.

7.2.3 Rules for method signatures

• The signature of the member consists in its name, the number, order and types of formal parameters.
• The signature does not include return type.
• In one signature is not allowed to have two formal parameters with the same name.

7.2.4 Rules for the local variables

• One method is not allowed to have two local variables with the same name.

7.2.5 Rules for types

 Type ::= id

• For this rule we have to perform a special semantical action. We will look for the "id" identifier in the types table. If it is not found it is possible to be added later in both types and classes table because it can be a class which is defined later in the analysed code.

7.2.6 Rules for instructions

Statement ::= id = exp

Statement ::= id [ exp ] = exp

• For the two instructions we have to look for the "id" identifier in the formal parameter table of the current method.
• If it is not found then it must be looked up in the variable table of the current method.
• If it is not found then it must be looked up in the memmbers table of the current class having the attribute kind, not method.
• If it is not found then it must be looked up in the memmbers table of the superclasses recursively having the attribute kind, not method.
• If it is not found then it must be issued an "unknown identifier" error.

7.2.7 Rules for expressions

Exp ::= new id ()

• previous instruction will search for the identifier id:
• in the table of clases;
• If not found then it generates the error "Invalid constructor".

7.3 The design of the symbol table

• MiniJava Given that it is an object-oriented language, symbol table will be hierarchical, multi-levels or domains.
• For search performance, the table can be implemented with binary trees, but in the context of the laboratory, for simplicity, linear structures are accepted.
• first level of the symbol table is the table of packages that form the universe of classes, but in the context MiniJava starring only the default, this level can be ignored.
• Each table entry packages will have a reference to a table of classes , which are described in classes that contain them.
• All classes that have no parent in the universe is considered in default as a class library are derived from Object.

7.3.1 The classes table

• Each class contains a reference table for a packet table entry.
• An entry in the table shape class class name and a reference to the parent class, if any.
• Adding a class to class table includes checking in advance that class name uniqueness and cyclic rules.
• Search for a class in the class table will be name-based index and returns the item found.
• Search superclaselor a class is based on class name and returns an array / list of index / referenced.

7.3.2 The types table

• An entry in the types table can be:
  • a primitive type that will be modeled through objects (like boolean, int, int []);
  • reference to a class table entry in the case of the user-defined types.
• A type is added is done in the moment of the analysis of that type.
• Searching for a type is done by iterating the type table.
• Searching for a supertype is done by iterating the tables type and investigating the parent field of each class from the table class.

7.3.3 The members table

• Each members table will have a reference / index entry to the class the members belong to.
• An entry in the members table will model the nature (attribute or method) and store a reference to the table of formal parameters and return type.
• Adding a table member implies checking members in advance of the uniqueness of the signature of that member.
• The search of a member in the members table will be based on comparing signatures.
• Signatures may be encoded as follows:

  {member_name, type_of_argument1, type_of_argument2 ,...}.
  

7.3.4 The formal parameters table

• Each formal parameter table will have a reference / index to the entry from methods table the formal parameters belong to.
• An entry in the formal parameters table will model the parameter name amd its return type.
• Adding a member in the table of formal parameters assumes chacking the uniqueness of the name of the parameter.
• A parameter is searched in the parameters table by its name.

7.3.5 The local variables table

• An entry in local variables table models variable name and stores a reference to an entry from the table of types.
• Adding a local variable in the local variables table implies checking in advance the uniqueness of the local variable's name.
• A local variable is searched in the local variables table by its name.

7.3.6 Domain analysis strategy

Firstly, we will build the AST with the help of the generated parser.

Then the visitor object will explore the AST collecting data to be added to the symbol table.

The first class to be analyzed will be the one containing the "main" static method.

Then, we will analyze the rest of the classes from the file.

During the class analysis it is possible to refer type which were not analysed yet.

They are inserted into the types table and into the classes table.

For the analysis to be complete is needed that at the end of the class analysis all entries from the class table to be completed.

Otherwise, it means that it was used a type which was not defined.

7.4 Symbol table example

We consider the following classes for an object oriented system:

class Main
{
 public static void main(String args[])
 {
  System.out.println(new TestShape().test());
 }
}

class Shape
{
 int x;
 int y;

 int print()
 {
  return 0;
 }

 int translate (int dx, int dy)
 {
  x = x + dx;
  y = y + dy;
  return 0;
 }
}

class Rectangle extends Shape
{
 int width;
 int height;

 int print()
 {
  System.out.println(x);
  System.out.println(y);
  System.out.println(widht);
  System.out.println(height);
  return 0;
 }
}

class Circle extends Shape
{
 int radius;

 int print()
 {
  System.out.println(x);
  System.out.println(y);
  System.out.println(radius);
  return 0;
 }
}

class TestShape
{
 int test()
 {
  Shape s;
  Rectangle r;
  Circle c;

  r=new Rectangle();
  c=new Circle();

  s=r;
  s=c;

  s.print();
  s.translate(1,1);
  s.print();

  c.print();
  c.translate(2,2);
  c.print();

  return 0;
 }
}

Due to the syntactical restrictions we have only one package in any analysed object-oriented system we build. The class table for the default package is the following:

Index	Class name	Parent class index	Reference to members table
0	Object	-1	null
1	Main	0	Reference to members table for class Main
2	TestShape	0	Reference to members table for class TestShape
3	Shape	0	Reference to members table for class Shape
4	Rectangle	3	Reference to members table for class Rectangle
5	Circle	3	Reference to members table for class Circle

The types table is unique and global for any analysed object-oriented system. The types table is listed next:

Index	Type name	Type generating class index
0	void	-1
1	boolean	-1
2	int	-1
3	int[]	-1
4	Object	0
5	Main	1
6	TestShape	2
7	Shape	3
8	Rectangle	4
9	Circle	5

At the begining of the table we added the predefined types and afterwards the user defined ones.

The member table for class "Main" is the following:

Index	Member name	Signature	Return type	Member kind	Reference to formal parameter table	Reference to local variables table
0	main	{main,String[]}	void	method	Reference to formal parameters tale of method "main"	null

In class "Main" there is only one method which is the object-oriented system entry point.

The formal parameter table for method "main" is listed next:

Index	Formal parameter name	Signature	Return type
0	args	{String[]}	String

The "main" method formal parameter lists consists in one element. This element represents the argument array of the programe.

The member table for class "Shape" is listed next:

Index	Member name	Signature	Return type	Member kind	Reference to formal parameters table	Reference to local variables table
0	x	{x}	int	field	null	null
1	y	{y}	int	field	null	null
2	print	{print}	int	method	null	null
3	translate	{translate,int,int}	int	method	Reference to method "translate" table of formal parameters	null

For fields the references to formal parameter table and local variable table are both null.

The formal parameters table for the method "translate" is listed next:

Index	Formal parameter name	Signature	Type
0	dx	{dx}	int
1	dy	{dy}	int

The member table for class "Rectangle" is listed next:

Index	Member name	Signature	Return type	Member kind	Reference to formal parameter table	Reference to local variable table
0	width	{width}	int	field	null	null
1	height	{height}	int	field	null	null
2	print	{print}	int	method	null	null

The member table for class "Circle" is listed next:

Index	Member name	Signature	Return type	Member kind	Reference to formal parameter table	Reference to local variable table
0	radius	{radius}	int	field	null	null
1	print	{print}	int	method	null	null

The member table for class "TestShape" is listed next:

Index	Member name	Signature	Return	Member kind	Reference to formal parameter table	Reference to local variable table
0	test	{test}	int	method	null	Reference to the local variable table of "test" method

The local variable table for method "test" is listed next:

Index	Local variable name	Signature	Return type
0	s	{s}	Shape
1	r	{s}	Rectangle
2	c	{s}	Circle

7.5 Errorneous MiniJava Code Examples

The following code sequences may be used to check the built analyzer. The examples capture most of the possible error types.

Class

class Main{ public static void main(String args[]){} }

class A extends A {}

---

class Main{ public static void main(String args[]){} }

class A extends B {}

class B extends A {}

---

class Main{ public static void main(String args[]){} }

class A extends B {}

class B extends C {}

class C extends A {}

---

class Main{ public static void main(String args[]){} }

class A {}

class A {}

Members

class Main{ public static void main(String args[]){} }

class A
{
 int x;

 boolean x;
}

---

class Main{ public static void main(String args[]){} }

class A
{
 int m() {return 0;}

 boolean m() {return false};
}

---

class Main{ public static void main(String args[]){} }

class A
{
 int m() {return 0;}

 boolean m() {return false};
}

---

class Main{ public static void main(String args[]){} }

class A
{
 int m(int x, boolean x) {return 0;}
}

Local variable

class Main{ public static void main(String args[]){} }

class A
{
 int m()
 {
  boolean x;

  int x;

  return 0;
 }
}

7.6 Assignments

1. Model a symbol table in order to perform the domain analysis upon the given rules.

Assignments time: 2 weeks