[antlr-interest] I am not understanding tree grammar - please help

Loring Craymer Loring.G.Craymer at jpl.nasa.gov
Mon Jan 3 14:06:17 PST 2005


John--

Ter did a class exercise for a simple interpreter (look at the lab 
exercises at http://www.cs.usfca.edu/~parrt/course/652/index.html).  For 
computation during a tree walk, each rule would tend to have a return value 
(an AST node in your example:  things get messy when you directly return 
data types, so you would want to package the type information--INTLIT or 
STRING_LITERAL--with a string representation of the data.  You might also 
do a custom type to support a wider range of computational types).  If you 
plan to extend your language, it probably makes more sense to go the byte 
code and stack interpreter route.

--Loring


At 11:26 AM 1/3/2005, John MccLain wrote:
>What I want to do is fairly straight forward.
>
>I have a grammar (see below) which builds my AST. The AST nodes are function
>identifiers, logical comparators (e.g., <,>,etc.) and math operators (e.g.,
>+, -, etc..) The children of these nodes are parameters to the operation
>being performed.
>All I want to do is create an action for each AST node that takes the node's
>children (parameters) and calls a java function with those parameters. What
>I need to do is walk the tree, replaceing each AST node with the result of
>the function call in its action. The goal is to return the final result into
>the root node, and then print out that node.
>
>Can I do this with ANTLR tree grammar, and if so, how (code/psuedocode would
>be appreciated)???? Are there any tutorials for this kind of treewalking????
>
>----------------------------------------------------------------------------
>--
>
>class P extends Parser;
>options {buildAST=true;}
>
>class P extends Parser;
>options {buildAST=true;}
>
>prog: expression EOF;
>
>procedureCallStatement
>   : IDENT^ (actualParameters)?
>   ;
>
>actualParameters
>   : LPAREN! (expression (COMMA! expression)*)? RPAREN!
>   ;
>
>expression
>   : relationalExpression (("AND"^|"OR"^) relationalExpression)*
>   ;
>
>relationalExpression
>   : addingExpression ((EQUALS^|NOT_EQUALS^|GT^|GTE^|LT^|LTE^)
>addingExpression)*
>   ;
>
>addingExpression
>   : multiplyingExpression ((PLUS^|MINUS^) multiplyingExpression)*
>   ;
>
>multiplyingExpression
>   : signExpression ((TIMES^|DIV^|"mod"^) signExpression)*
>   ;
>
>signExpression
>   : ((PLUS^|MINUS^))* booleanNegationExpression
>   ;
>
>booleanNegationExpression
>   : ("not"^)* primitiveElement
>   ;
>
>primitiveElement
>   :
>   constantValue
>   | LPAREN! expression RPAREN!
>   | procedureCallStatement
>   ;
>
>constantValue
>   : INTLIT
>   | STRING_LITERAL
>   ;
>
>  class L extends Lexer;
>
>options {
>   charVocabulary = '\0'..'\377';
>   testLiterals=false;    // don't automatically test for literals
>   k=2;                   // two characters of lookahead
>}
>
>// Literals
>protected DIGIT : '0'..'9'
>{System.out.println("1" + getText());};
>
>INTLIT  :  (DIGIT)+
>{System.out.println("2" + getText());};
>CHARLIT : '\''! . '\''!
>{System.out.println("3" + getText());};
>
>// string literals
>STRING_LITERAL
>   : '"'!
>     ( '"' '"'!
>     | ~('"'|'\n'|'\r')
>     )*
>     ( '"'!
>     | // nothing -- write error message
>     )
>{System.out.println("4" + getText());};
>
>
>// Keywords are literals in the parser grammar
>
>// Operators
>DOT        : '.'   ;
>BECOMES    : ":="  ;
>COLON      : ':'   ;
>SEMI       : ';'   ;
>COMMA      : ','   ;
>EQUALS     : '='   ;
>LBRACKET   : '['   ;
>RBRACKET   : ']'   ;
>DOTDOT     : ".."  ;
>LPAREN     : '('
>{System.out.println("5" + getText());};
>RPAREN     : ')'
>{System.out.println("6" + getText());};
>NOT_EQUALS : "/="  ;
>LT         : '<'
>{System.out.println("7" + getText());};
>LTE        : "<="  ;
>GT         : '>'   ;
>GTE        : ">="  ;
>PLUS       : '+'
>{System.out.println("8" + getText());};
>MINUS      : '-'   ;
>TIMES      : '*'   ;
>DIV        : '/'   ;
>
>
>
>// Whitespace -- ignored
>WS
>   : ( ' '
>     | '\t'
>     | '\f'
>
>     // handle newlines
>     | ( "\r\n"  // Evil DOS
>       | '\r'    // Macintosh
>       | '\n'    // Unix (the right way)
>       )
>       { newline(); }
>     )
>     { $setType(Token.SKIP); }
>   ;
>
>
>// an identifier.  Note that testLiterals is set to true!  This means
>// that after we match the rule, we look in the literals table to see
>// if it's a literal or really an identifer
>IDENT
>   options {testLiterals=true;}
>   : ('a'..'z'|'A'..'Z') ('a'..'z'|'A'..'Z'|'0'..'9')*
>{System.out.println("10" + getText());};
>
>
>----------------------------------------------------------------------------
>------------
>
>
>
>John McClain
>Senior Software Engineer
>TCS Healthcare
>jmcclain at tcshealthcare.com
>(530)886-1700x235
>"Before you criticize someone, walk a mile in their shoes.
>That way, you'll be a mile from them, and you'll have their shoes."




More information about the antlr-interest mailing list