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.