ANTLR exercises

16 March 2016

Below is a fragment of the grammar for the language Standard ML.. We’ve done a lot with standard arithmetic expressions, so this is a bit of a departure — we’re representing types.

grammar LittleML;

top : type EOF;

type    : type ID
        | '(' type (',' type)+ ')' ID
        | type '*' type
        | <assoc=right> type '->' type
        | '{' record? '}'
        | '(' type ')'
        | TVAR
        | ID
        ;

record  : ID ':' type (',' record)?;

ID : [A-Za-z] [A-Za-z0-9]*;
TVAR : '\'' [A-Za-z0-9]+;
WS : (' '|'\t'|'\n')+ -> skip;

1. Which of the following expressions is valid according to this grammar? If it’s valid, draw the parse tree.

   1. int32
   2. unsigned_int
   3. 'a
   4. 'a list
   5. int list tree
   6. int * float + char
   7. int * char tree
   8. {}
   9. {x:int, y:float}
   10. ()
   11. (int, char) tree
   12. ('a, 'b) (int * float)
   13. 'a -> 'b
   14. 'a list * int -> int * int

2. Which of these methods are part of the generated LittleMLBaseVisitor class?

   1. visitTVAR(TVARContext cxt)
   2. visitType(TypeContext cxt)
   3. visitRecord(RecordContext cxt)
   4. visitWS(WSContext cxt)
   5. visitOp(OpContext cxt)

3. Now suppose we label the different alternatives of the type rule using the hash notation:

   type    : type ID                       #TypeApp
           | '(' type (',' type)+ ')' ID   #TypeApp
           | type '*' type                 #TypePair
           | <assoc=right> type '->' type  #TypeArrow
           | '{' record? '}'               #TypeRecord
           | '(' type ')'                  #TypeParen
           | TVAR                          #TypeVar
           | ID                            #TypeName
           ;

   Now which of these methods are part of the generated LittleMLBaseVisitor class?

   1. visitTypeRecord(TypeRecordContext cxt)
   2. visitType(TypeContext cxt)
   3. visitRecord(RecordContext cxt)
   4. visitTypeArrow(TypeArrowContext cxt)

4. When the following type expressions are parsed, what is the order in which the (hash-tagged) visitor methods are called in a standard pre-order traversal? Hint: draw the tree first.

   1. int list tree
   2. 'a list * int -> int * int
   3. {x:int, y:float}
   4. {x:int * float, y: 'a list} * d

PDF