Type checker of a grammar

[syrmsin]

Hi, I have a this grammar: 

 prog ::= [ decl ; ]* stmt EOF
 decl ::= var ID [ , ID ]* : type
 type ::= integer | boolean
 expr ::= andExpr [ or andExpr ]*
 andExpr ::= relExpr [ and relExpr ]*
 relExpr ::= addExpr [ = addExpr | != addExpr
 | <= addExpr | >= addExpr
 | < addExpr  | >  addExpr ]?
 addExpr ::= mulExpr [ + mulExpr | - mulExpr ]*
 mulExpr ::= unExpr [ * unExpr | / unExpr ]*
 unExpr ::= + unExpr | - unExpr | not unExpr | primary
 primary ::= ( expr ) | ID | NUM | true | false
 stmt ::= ID := expr
 | print( expr )
 | if( expr ) then stmt [ else stmt]*
 | while( expr ) do stmt
 | begin stmt [ ; stmt ]* end

Now I have to implement a type checker. So I need to verify the correctness of such programs. 

The rules that I must follow are:

1. Arithmetic operators can only be applied to operands of type integer. 

For example, the expression 5 + true, which uses the arithmetic operator + applied to an operand Boolean is syntactically correct but not semantically correct and herefore can not be translated.

2. The logical operators can only be applied to operands of type boolean. 

3. The operators of order <,>, <= and> = can only be applied to operands numbers, while the operators = and <> are overloaded, or can be applied either to operands of type numeric or Boolean, as long as both operands are of the same type. 

4. Commands assignment is correct if the type of the expression to the right of the operator: = is equal to the type of the identifier to the left of the operator: =. 

5. The controls contain iterative and conditional expression that must be Boolean. 

In addition, there are two other errors not related to the types that the compiler must handle: 

1a. Each identifier must be declared before use. 

2a. An identifier can not be declared more than once.

Grammar code:

 @members {
 SymbolTable st = new SymbolTable();
 }


 public enum Type { INTEGER, BOOLEAN }


 prog
 : ( decl ';')* stmt EOF
 ;
 
 decl
 : 'var' i1 = ID ( ',' i2 = ID )* ':' type
 {
 /* CODE... */
 }
 ;
 
 type
 : 'integer' | 'boolean'
 ;


 expr returns [Type type]
 : e1 = andExpr
 ( 'or' e2 = andExpr
 { if(($e1.type || $e2.type) != Type.BOOLEAN)
 throw new IllegalArgumentException("Type error in OR ");
  $type = Type.BOOLEAN;
   }
 )*
 ;


 andExpr returns [Type type]
 : e1 = relExpr
 ( 'and' e2 = relExpr
 { if(($e1.type || $e2.type) != Type.BOOLEAN)
 throw new IllegalArgumentException("Type error in AND ");
  $type = Type.BOOLEAN;
   }
 )*
 ;
 
 relExpr returns [Type type]
 : e1 = addExpr { $type = $e1.type; }
 ( '=' e2 = addExpr
 { if($e1.type != $e2.type)
 throw new IllegalArgumentException("Type error in = ");
  $type = Type.BOOLEAN;
 }
 | '<''>' e3 = addExpr
 { if($e1.type != $e3.type)
 throw new IllegalArgumentException("Type error in <> ");
  $type = Type.BOOLEAN;
 }
 | '<''=' e4 = addExpr
 { if(($e1.type || $e4.type) != Type.INTEGER)
 throw new IllegalArgumentException("Type error in <= ");
  $type = Type.BOOLEAN;
 }
 | '>''=' e5 = addExpr
 { if(($e1.type || $e5.type) != Type.INTEGER)
 throw new IllegalArgumentException("Type error in >= ");
  $type = Type.BOOLEAN;
 }
 | '<' e6 = addExpr
 { if(($e1.type || $e6.type) != Type.INTEGER)
 throw new IllegalArgumentException("Type error in < ");
  $type = Type.BOOLEAN;
 }  
 | '>' e7 = addExpr
 { if(($e1.type || $e7.type) != Type.INTEGER)
 throw new IllegalArgumentException("Type error in > ");
  $type = Type.BOOLEAN;
 }
 )?
 ;


 addExpr returns [Type type]
 : e1 = mulExpr { $type = $e1.type; }
 ( '+' e2 = mulExpr
 { if(($e1.type || $e2.type) != Type.INTEGER)
 throw new IllegalArgumentException("Type error in + ");
  $type = Type.INTEGER;
 }
 | '-' e3 = mulExpr
 { if(($e1.type || $e3.type) != Type.INTEGER)
 throw new IllegalArgumentException("Type error in - ");
  $type = Type.INTEGER;
 }
 )*
 ;
 
 mulExpr returns [Type type]
 : e1 = unExpr { $type = $e1.type; }
 ( '*' e2 = unExpr
 { if(($e1.type || $e2.type) != Type.INTEGER)
 throw new IllegalArgumentException("Type error in * ");
  $type = Type.INTEGER;
 }
 | '/' e3 = unExpr
 { if(($e1.type || $e3.type) != Type.INTEGER)
 throw new IllegalArgumentException("Type error in / ");
  $type = Type.INTEGER;
 }
 )*
 ;


 unExpr returns [Type type]
 : '+' e1 = unExpr
 { if($e1.type != Type.INTEGER)
 throw new IllegalArgumentException("Type error in + ");
  $type = Type.INTEGER;
 }
 | '-' e2 = unExpr
 { if($e2.type != Type.INTEGER)
 throw new IllegalArgumentException("Type error in - ");
  $type = Type.INTEGER;
 }
 | 'not' e3 = unExpr
 { if($e3.type != Type.BOOLEAN)
 throw new IllegalArgumentException("Type error in not ");
  $type = Type.BOOLEAN;
 }
 | primary { $type = $primary.type; }
 ;
 
 primary returns [Type type]
 : '(' expr ')' { $type = $expr.type; }
 | ID { $type = st.lookupType($ID.text); }
 | NUM { $type = Type.INTEGER; }
 | 'true' { $type = Type.BOOLEAN; }
 | 'false' { $type = Type.BOOLEAN; }
 ;
 
 stmt
 : ID ':''=' expr
 { if(st.lookupType($ID.text) != $expr.type)
 throw new IllegalArgumentException (" errore di tipo ");
 }
 | 'print' '(' expr ')' { $type = $expr.type; }
 | 'if' expr 'then' s1 = stmt ( 'else' s2 = stmt )?
 { if(expr != Type.BOOLEAN)
 throw new IllegalArgumentException("Type error in ( expr ) ");
 }
 | 'while' expr 'do' s1 = stmt
 { if(expr != Type.BOOLEAN)
 throw new IllegalArgumentException("Type error in ( expr ) ");
 }
 | 'begin' s1 = stmt ( ';' s2 = stmt )* 'end'
 ;
 
 ID : ('a'.. 'z'|'A'.. 'Z') ('a'.. 'z'|'A'.. 'Z'|'0'.. '9'|'_')* ;


 NUM : '0'.. '9'+ ;


 WS : (' ' | '\t' | '\r' | '\n')+ { skip(); } ;

The symbol table:

 import java.util.*;


 public class SymbolTable {
 private Map <String, Type> typeMap = new HashMap <String, Type>();
 
 public void insert(String s, Type t) {
 if(!typeMap.containsKey(s))
 typeMap.put(s, t);
 else
 throw new IllegalArgumentException("Error " + s);
 }
 
 public Type lookupType(String s) {
 if(typeMap.containsKey(s))
 return typeMap.get(s);
 else
 throw new IllegalArgumentException("Error " + s);
 }
 }

I think I've done correctly all cases except the last two (1a. and 2a.). 

These two relate to the rule "decl".

I thought about using a loop: browse the string until you can find the assignment (var : type). Put every assignment in the symbol table. 

But I don't know how to do it, someone help me?

Thanks

[Terence Parr]

rather than do your homework for you, could you ask a simpler more direct question?

Ter

--
You received this message because you are subscribed to the Google Groups "antlr-discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to antlr-discussi...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[syrmsin]

Of sure. I do not know how to count the possible occurrences of, for example, "var a, b, c, d: integer". I don't know how many statements the user writes, they could be 1 or 1000. 

And then I don't know how many, I do not know how to do the for loop to make sure that in each case enter the values ​​in the symbol table. 

My idea (which I do not know how to develop) is: 

until (there are no occurrences)
      enter the value in the symbol table ID and Type

But I do not know how to do the loop...

  $type = Type<span style="color

...

[Terence Parr]

All you have to do is get the list of statements, for example from stmt in a begin and end block. the context object will have an accessor method for stmt(). It’s a list of StmtContext of objects.

Ter

[syrmsin]

Thanks for the reply but I don't understand.. Sorry..
What do you mean with 'a list of StmtContext'?

[David Whitten]

Read the generated code for your grammar.

You should be able to find StmtContext in the code.

On Mon, Apr 7, 2014 at 4:02 AM, syrmsin <ventur...@gmail.com> wrote:

Thanks for the reply but I don't understand.. Sorry..
What do you mean with 'a list of StmtContext'?

[Terence Parr]

ah. I see that you need to take a tour of the generated code ;) I also suggest reading the book. You can’t build something complicated like this without really understanding what’s going on.

Ter

On Apr 7, 2014, at 1:02 AM, syrmsin <ventur...@gmail.com> wrote:

> Thanks for the reply but I don't understand.. Sorry..
> What do you mean with 'a list of StmtContext'?
>

[syrmsin]

I looked at the generated code, and yet I still have not figured out how to do..

Il giorno domenica 6 aprile 2014 20:11:56 UTC+2, syrmsin ha scritto:

  $type = Type<span style="color

...

[David Whitten]

So let's start with the requirements of your task:

1. Arithmetic operators can only be applied to operands of type integer. 

For example, the expression 5 + true, which uses the arithmetic operator + applied to an operand Boolean is syntactically correct but not semantically correct and herefore can not be translated.

Can you find (in the generated code) where arithmetic operators are recognized in your grammar?

What are the specific rules involved?

Is there an action associated with those rules?

How does your (generated) code know that a particular matching text represents an operand?

How does your (generated) code know what data type is supposed to be associated with an operand?

I'll stop here and wait for your answers.

David

713-870-3834

--

[syrmsin]

Hello, thank you very much for the help you're giving me. I tried to answer your questions (I hope that are correct):

1. Can you find (in the generated code) where arithmetic operators are recognized in your grammar? What are the specific rules involved?

    The rules involved by the arithmetic operators are addExpr, mulExpr and unExpr

2. Is there an action associated with those rules? 

    Yes, there is an action associated with these rules

3. How does your (generated) code know that a particular matching text represents an operand? 

    A text is an operand if it is an integer

4. How does your (generated) code know what data type is supposed to be associated with an operand?

    In the generated code, there is this code:

if((e1 || e3) != Type.INTEGER)

   throw new IllegalArgumentException("Type error in - ");

   type = Type.INTEGER;
}

However I have seen that there were some mistakes in my grammar .g so I changed it.

@members {

SymbolTable st = new SymbolTable();

}

prog

: ( decl ';')* stmt EOF

;

decl

: 'var' i1 = ID ( ',' i2 = ID )* ':' type

{ String[] sing;

 for(el = split(" , | : ") && el != null) {

  el = split(" , | : ");

{ if(st.lookupType($ID.text) != st.lookupType($expr.text))

throw new IllegalArgumentException ("Errore di tipo.");

}

| 'print' '(' expr ')' 

| 'if' expr 'then' s1 = stmt ( 'else' s2 = stmt )?

{ if(expr != Type.BOOLEAN)

throw new IllegalArgumentException("Type error in ( expr ) "); 

}

| 'while' expr 'do' s1 = stmt

{ if(expr != Type.BOOLEAN)

throw new IllegalArgumentException("Type error in ( expr ) "); 

}

| 'begin' s1 = stmt ( ';' s2 = stmt )* 'end'

;

ID : ('a'.. 'z'|'A'.. 'Z') ('a'.. 'z'|'A'.. 'Z'|'0'.. '9'|'_')* ;

NUM : '0'.. '9'+ ;

WS : (' ' | '\t' | '\r' | '\n')+ { skip(); } ;

Il giorno domenica 6 aprile 2014 20:11:56 UTC+2, syrmsin ha scritto:

  $type = Type<span style="color

...

[syrmsin]

No one knows how to help me?

Il giorno domenica 6 aprile 2014 20:11:56 UTC+2, syrmsin ha scritto:

  $type = Type<span style="color

...

[Terence Parr]

you are asking us to write a compiler book for you here.

T

[syrmsin]

No.. I tried to do it, but I can't. If I wanted you to do my "homework", I would not have written a single line of code...

Il giorno domenica 6 aprile 2014 20:11:56 UTC+2, syrmsin ha scritto:

  $type = Type<span style="color

...

[Terence Parr]

just because you want an answer doesn’t mean we’ll write you a book on this channel. also note you could spend a few dollars and read my book on this subject or would you like me to rewrite the book for you this morning?

[syrmsin]

Okay, sorry. I thought that I could find hel on this page is, but apparently it is not. 

Thanks anyway, I will solve my problem in another way.

Il giorno domenica 6 aprile 2014 20:11:56 UTC+2, syrmsin ha scritto:

  $type = Type<span style="color

...

[Sam Harwell]

I’m sure there are several people on this list that know multiple ways to address this issue. The problem is you asked a question which requires significant time to answer fully, and that time has real opportunity costs associated with it.

 

Personally, the presentation of the problem appeared to be the transcription of a homework problem plus a minimal amount of work attempting to solve it. The missing part for me is I didn’t feel like the time I put into creating a solution would be truly appreciated by anyone. It might end up as part of a good grade on some assignment, but I already know I could get a great grade on it.

 

If you can explain, in detail, how an answer to this problem would benefit the larger community, then I’ll put time into helping you with it. Just remember that I’ll be helping you instead of spending my weekend time with my family and/or working on research problems (e.g. issues #490 and #522) that will hopefully lead to me graduating.

 

Sam

--