Term
|
Definition
- Parse trees represent derivations
- Each possible path corresponds to possible call stack
- Contains "punctuation"
- tokens: (,), begin,... -> concrete syntax tre
- Contains redundant non-terminal symbols -> chain rules: E -> F -> T ...Too much detail!
|
|
|
Term
| What are abstract syntax trees? |
|
Definition
- Abstract syntax trees represent the essential structure of derivations
- Abstract syntax drops detail
- Punctuation tokens
- Chain productions
- Abstract syntax rules can be ambiguous
- Only describe structure for legal trees
- not meant for parsing
- Usually allows unparsing(text reconstruction)
- ASTs are clean interfaces
|
|
|
Term
| How would you manually build an AST in JAva? |
|
Definition
- One abstract class per non-terminal
- One concrete class per rule
- One field per non-terminal on rhs
|
|
|
Term
| Give an example of how would you build a Java class for an AST |
|
Definition
- public abstract class Expr{}
- public class Num extends Expr{
- public int val;
- public Num(int v) {val=v;}
- }
- public class Sum extends Expr {
- public Expr left, right;
- public Sum(Expr 1, Expr 2) ....
|
|
|
Term
| What are the main keys to remember when building ASTs in ANTLR |
|
Definition
- Rules of the form
- rule: rule-elems1 -> build instr1
- | rule-elems2 -> build instr2
- ...
- Build instructions are automatically executed when rule is applied
- Build instructions return AST node or AST node list
- use with options{output=AST;ASTLabelType=CommonTree;}
|
|
|
Term
| What are some basic AST building instructions in ANTLR? |
|
Definition
- trm: '(' exp ')' -> exp; //return exp AST ignore ()
- add: l=exp '+' r=exp -> $l $r;
- ext: 'exit' exp -> ^('exit' exp);
- dcl: type ID -> ^(VARDCL ID type);
- virtual tag token must be defined in TOKENS
|
|
|
Term
| How to collect duplicate elements in ANTLR? |
|
Definition
- args: arg (',' arg)* -> arg+;
- dcl: type ID (',' ID)* -> ^(VARDCL type ID+);
- dcl: type ID (',' ID)* -> ^(VARDCL type ID)+;
|
|
|
Term
| How to deal with optional attributes in trees in ANTLR? |
|
Definition
- init: exp? -> ^(INIT exp)?;
- skip: -> ^SKIP;
- for: 'for' '(' dcl? ';' c=exp? ';' i=exp? ')' stmts
- -> ('for' dcl? ^(COND $c)? ^(ITER $i)? stmts);
- if: 'if' '(' expr ')' s1=stmt
- ('else' s2=stmt -> ^(IFELSE expr $s1 $s2)
- | -> ^('if' expr $s1) );
|
|
|
Term
| Give an example of updating trees in ANTLR? |
|
Definition
- exp: (INT -> INT)
- ('+' i=INT -> ^('+' $exp $i))*;
|
|
|
