CC S01E04

Antlr 3

Переходим на antlr 3, т.к. он более удобен для реализации первого компилятора.

Итак, crash-course по antlr 3.

Грамматика

Два основных отличая от antlr 4: нельзя использовать левую рекурсию, игнорирование пробельных символов записывается иначе.

calc.g

grammar calc;

calc
	: lines EOF
	;

lines
	: line NL lines?
	;

line
	: expr
	;

expr
	: term ((PLUS | MINUS) term)*
	;

term
	: factor ((MULT | DIV) factor)*
	;

factor
	: (PLUS | MINUS) factor
	| atom
	;

atom
	: INT
	| LPAR expr RPAR
	;

INT
	: '0'..'9'+
	;

PLUS
	: '+'
	;

MINUS
	: '-'
	;

MULT
	: '*'
	;

DIV
	: '/'
	;

LPAR
    : '('
    ;

RPAR
    : ')'
    ;

NL
	: '\r'|'\n'
	;

WHITESPACE
	: ('\t'|' '|'\u000C')+ { $channel = HIDDEN; }
	;

Вычисления

Calc2.g

grammar calc2;

@header {
import java.lang.Integer;
import java.lang.Math;
}

calc
	: lines EOF
	;

lines
	: (line NL)+
	;

line
	: expr {System.out.println($expr.value);}
	;

expr returns [int value]
	: t1=term {$value = $t1.value;} (PLUS t2=term {$value += $t2.value;} | MINUS t2=term {$value -= $t2.value;})*
	;

term returns [int value]
	: f1=factor {$value = $f1.value;} (MULT f2=factor {$value *= $f2.value;} | DIV f2=factor {$value /= $f2.value;})*
	;

factor returns [int value]
	: PLUS f1=factor {$value = $f1.value;}
	| MINUS f2=factor {$value = -$f2.value;}
	| power {$value = $power.value;}
	;

power returns [int value]
	: atom {$value = $atom.value;} (POW f=factor {$value = (int)Math.pow((double)$value, (double)$f.value);})?
	;

atom returns [int value]
	: INT {$value = Integer.parseInt($INT.text);}
	| PI {$value = 3;}
	| E {$value = 2;}
	| LPAR expr RPAR {$value = $expr.value;}
	;

PI
	: 'PI'
	;

E
	: 'E'
	;

INT
	: '0'..'9'+
	;

PLUS
	: '+'
	;

MINUS
	: '-'
	;

MULT
	: '*'
	;

DIV
	: '/'
	;

POW
	: '**'
	;

LPAR
    : '('
    ;

RPAR
    : ')'
    ;

NL
	: '\r'|'\n'
	;

WHITESPACE
	: ('\t'|' '|'\u000C')+ {$channel = HIDDEN;}
	;

AST

Теперь научимся создавать промежуточное абстрактное синтаксическое дерево и затем будем его обрабатывать.

calc5.g

grammar calc5;

options {
    output = AST;
}

tokens {
    EXPR;
}

calc
    : lines EOF!
    ;

lines
    : (line NL!)+
    ;

line
    : expr
    ;

expr
    : t1=term (PLUS^ t2=term | MINUS^ t2=term)*
    ;

term
    : f1=factor (MULT^ f2=factor | DIV^ f2=factor)*
    ;

factor
    : PLUS^ f1=factor
    | MINUS^ f2=factor
    | power
    ;

power
    : atom (POW^ f=factor)?
    ;

atom
    : DOUBLE
    | PI
    | E
    | LPAR! expr RPAR!
    ;

PI
    : 'PI'
    ;

E
    : 'E'
    ;

DOUBLE
    : INT
    | '.' INT
    | INT '.'
    | INT '.' INT
    ;

fragment INT
    : '0'..'9'+
    ;

PLUS
    : '+'
    ;

MINUS
    : '-'
    ;

MULT
    : '*'
    ;

DIV
    : '/'
    ;

POW
    : '**'
    ;

LPAR
    : '('
    ;

RPAR
    : ')'
    ;

NL
    : '\r'|'\n'
    ;

WHITESPACE
    : ('\t'|' '|'\u000C')+ {$channel = HIDDEN;}
    ;

calc5Tree.g

tree grammar calc5Tree;

options {
    tokenVocab=calc5;
    ASTLabelType=CommonTree;
}

@header {
import java.lang.Double;
import java.lang.Math;
}

@members {
boolean unary;
}

calc
    : (expr)+
    ;

expr
    : ^(PLUS e1=expr {unary = true;} (e2=expr {unary = false;})?)  {System.out.println(unary ? "uplus" : "add");}
    | ^(MINUS e1=expr {unary = true;} (e2=expr {unary = false;})?) {System.out.println(unary ? "uminus" : "sub");}
    | ^(MULT e1=expr e2=expr)   {System.out.println("mul");}
    | ^(DIV e1=expr e2=expr)    {System.out.println("div");}
    | ^(POW e1=expr e2=expr)    {System.out.println("pow");}
    | DOUBLE                    {System.out.println("push " + $DOUBLE.text);}
    | PI                        {System.out.println("push " + Math.PI);}
    | E                         {System.out.println("push " + Math.E);}
    ;

Calc.java

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;

public class Calc {
    public static void main(String[] args) throws Exception {
        // create a CharStream that reads from standard input
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        // create a lexer that feeds off of input CharStream
        calc5Lexer lexer = new calc5Lexer(input);
        // create a buffer of tokens pulled from the lexer
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        // create a parser that feeds off the tokens buffer
        calc5Parser parser = new calc5Parser(tokens);
        // begin parsing at rule r
        calc5Parser.calc_return r = parser.calc();

        CommonTree t = (CommonTree)r.getTree();
        System.out.println(t.toStringTree());

        // Walk resulting tree; create treenode stream first
        CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
        // AST nodes have payloads that point into token stream
        nodes.setTokenStream(tokens);
        // Create a tree Walker attached to the nodes stream
        calc5Tree walker = new calc5Tree(nodes);
        // Invoke the start symbol, rule program
        walker.calc();
        //
    }
}

Домашнее задание

Создать с использованием AST + tree grammar транслятор микроязыка с переменными, арифметическими выражениями и вводом-выводом в scheme.