Compilers / Chapter 2 , Appendix A

Main.java

// https://gist.github.com/yamasushi/bbfc1dd937617ca43bda9d1defda9218
// Compilers Chapter 2 , Appendix A
// 
// Java17

import java.io.*;
import java.util.Map;
import java.util.HashMap;
import java.util.Collections;

public class Main{
    public static void main(String[] args) throws IOException {
        Lexer lex = new Lexer();
        Parser parse = new Parser(lex);
        parse.program();
        System.out.write('\n');
    }
}

// A.3 Lexical Analyzer

public enum Tag {
    EOF  ,
    CHAR ,
    //
    AND  ,
    BASIC,
    BREAK,
    DO   ,
    ELSE ,
    EQ   ,
    FALSE,
    GE   ,
    ID   ,
    IF   ,
    INDEX,
    LE   ,
    MINUS,
    NE   ,
    NUM  ,
    OR   ,
    REAL ,
    TEMP ,
    TRUE ,
    WHILE ;
}


public class Token {
    public final Tag tag;
    protected Token (Tag t) { this.tag = t;}
}

public class Char extends Token {
    public final char value;
    public Char (char v) {super(Tag.CHAR); this.value = v;}
    @Override
    public String toString() {
        return "" + this.value;}
}

public class Eof extends Token {
    public Eof () {super(Tag.EOF);}
    @Override
    public String toString() { return "<EOF>";}
}

public class Num extends Token {
    public final int value;
    public Num(int v){super(Tag.NUM); this.value = v;}
    @Override
    public String toString() {
        return "" + this.value;}
}


public class Real extends Token {
    public final double value;
    public Real(double v){super(Tag.REAL); this.value = v;}
    @Override
    public String toString() {
        return "" + this.value;}
}

public class Word extends Token {
    public final String lexeme;
    public Word( String s, Tag tag) { super(tag); this.lexeme=s; }
    @Override
    public String toString() {return this.lexeme;}
    
    public static final Word and = new Word("&&",Tag.AND);
    public static final Word or  = new Word("||",Tag.OR );
    public static final Word eq  = new Word("==",Tag.EQ);
    public static final Word ne  = new Word("!=",Tag.NE);
    public static final Word le  = new Word("<=",Tag.LE);
    public static final Word ge  = new Word(">=",Tag.GE);
    
    public static final Word minus = new Word("minus" ,Tag.MINUS);
    public static final Word True  = new Word("true"  ,Tag.TRUE);
    public static final Word False = new Word("false" ,Tag.FALSE);
    public static final Word temp  = new Word("t"     ,Tag.TEMP);
}


public class Lexer {
    public static int line = 1;
    int peek = ' ';
    Map<String,Word> words = new HashMap<>();
    
    public Map<String,Word> getWords(){
       return  Collections.unmodifiableMap(this.words); }
    
    void reserve(Word w){words.put(w.lexeme,w);}
    public Lexer(){
        this.reserve(new Word("if"   ,Tag.IF));
        this.reserve(new Word("else" ,Tag.ELSE));
        this.reserve(new Word("while",Tag.WHILE));
        this.reserve(new Word("do"   ,Tag.DO));
        this.reserve(new Word("break",Tag.BREAK));
        this.reserve(Word.True);
        this.reserve(Word.False);
        this.reserve(Type.Int);
        this.reserve(Type.Char);
        this.reserve(Type.Bool);
        this.reserve(Type.Float);
    }

    private int nextChar() throws IOException {
        return System.in.read();  }
    
    private void readch() throws IOException {
        this.peek = this.nextChar(); }
    
    private boolean readch(char c) throws IOException {
        readch();
        if(this.peek != c ) return false;
        this.peek = ' ';
        return true;
    }
        
    public Token scan() throws IOException {
        // Remove blank & comments (Exercise 2.6.1)
        blankLoop : for ( ; ; this.readch() ){
            switch (this.peek) {
            case ' ':
            case '\t':
                continue;
            case '\n':
                Lexer.line ++; continue;
            case -1:
                return new Eof();
            case '/':
                this.readch();
                switch(this.peek){
                case '/':
                    this.skipLineComments();
                    if(this.peek==-1) return new Eof();
                    Lexer.line++; continue;
                case '*':
                    this.skipComments();
                    if(this.peek==-1) return new Eof();
                    continue;
                default:
                    return new Char('/');
                }
            default:
                break blankLoop;
            }
        }

        // Operators (Exercise 2.6.2)]
        switch (this.peek){
        case '&':
            if(this.readch('&')) return Word.and; else return new Char('&');
        case '|':
            if(this.readch('|')) return Word.or;  else return new Char('|');
        case '=':
            if(this.readch('=')) return Word.eq;  else return new Char('=');
        case '!':
            if(this.readch('=')) return Word.ne;  else return new Char('!');
        case '<':
            if(this.readch('=')) return Word.le;  else return new Char('<');
        case '>':
            if(this.readch('=')) return Word.ge;  else return new Char('>');
        }
        
        // Numerals (Exercise 2.6.3)
        if ( Character.isDigit (this.peek)) {
            int i = 0;
            do {
                i = 10*i + Character.digit(this.peek,10);
                this.readch();
            } while(Character.isDigit(this.peek));
            if (this.peek != '.') {
                return new Num(i);   
            } else {
                this.readch();
                if(Character.isDigit(this.peek)){
                    return new Real(i + this.scanDecimal());
                    
                } else {
                    return new Real (i);
                }
            }
        } else if ( this.peek == '.' ){
            this.readch();
            if (Character.isDigit(this.peek)){
                return new Real (this.scanDecimal());
            } else {
                return new Char('.');
            }
        }

        // this.peek must be neither a digit nor a '.'
        
        // Id
        if (Character.isLetter(this.peek)){
            var b = new StringBuilder();
            do{
                b.append((char)this.peek); this.readch();
            } while (Character.isLetterOrDigit(this.peek));
            String s = b.toString();
            var    w = this.words.get(s);
            if(w != null) return w;
            w = new Word(s,Tag.ID);
            this.words.put(s,w);
            return w;
        }
        
        // Others
        var tok =  new Char((char)this.peek);
        this.peek = ' ';
        return tok;
    }
    
    private void skipLineComments() throws IOException {
        for(;;){
            this.readch();
            switch(this.peek) {
            case '\n': return;
            case -1  : return;
            default  : continue;
            }
        }
    }

    private void skipComments() throws IOException {
        for(;;){
            this.readch();
            switch(this.peek){
            case '\n' : Lexer.line++; continue;
            case '*':
                this.readch();
                switch(this.peek){
                case '/'  : return;
                case '\n' : Lexer.line++; continue;
                case -1   : return;
                default   : continue;
                }
            case -1 : return;
            default: continue;
            }
        }
    }

    private double scanDecimal() throws IOException {
        // peek must be a digit
        int i = 0;
        int k = 1;
        do {
            i = 10*i + Character.digit(this.peek,10);
            k = 10*k;
            this.readch();
        } while (Character.isDigit(this.peek)) ;
        return ((double)i) / ((double)k); 
    }
}

// A-3 Symbol Tables and Types

public class Env {
    private Map<String,Id> table;
    protected final Env prev;
    public Env(Env n){
        this.table = new HashMap<String,Id>();
        this.prev  = n;
    }
    public final void put(Token w,Id i) {this.table.put(w.toString(),i);}
    public final Id get(Token w){
        var s = w.toString();
        for(Env e = this; e !=null ; e=e.prev){
            Id found = e.table.get(s);
            if(found != null) return found;
        }
        return null;
    }
}



public class Type extends Word{
    public final int width ;
    public Type (String s,Tag tag,int w){super(s,tag); this.width=w;}

    public static final Type Int   = new Type("int"   , Tag.BASIC ,4);
    public static final Type Float = new Type("float" , Tag.BASIC ,8);
    public static final Type Char  = new Type("char"  , Tag.BASIC ,1);
    public static final Type Bool  = new Type("bool"  , Tag.BASIC ,1);

    public static boolean numeric(Type p){
        if(p==Type.Char || p==Type.Int || p==Type.Float) return true;
        else return false;
    }

    public static Type max(Type p1,Type p2){
        if( !Type.numeric(p1) || !Type.numeric(p2)) return null;
        else if (p1 == Type.Float || p2 == Type.Float ) return Type.Float;
        else if (p1 == Type.Int   || p2 == Type.Int   ) return Type.Int;
        else return Type.Char;
    }
}

public class Array extends Type {
    public final Type of;   // array *of* type
    public final int  size; // number of elements
    public Array(int sz,Type p){
        super("[]",Tag.INDEX,sz*p.width);
        this.size = sz;
        this.of   = p;
    }

    @Override
    public String toString() {return "["+this.size+"]"+this.of.toString();}
}

// A.5 Intermediate Code for Expressions

public class Node{
    private final int lexline;
    protected Node(){this.lexline = Lexer.line;}
    protected final void error(String s){throw new Error("near line "+this.lexline+": "+s);}

    private static int  labels = 0;
    public  static int  newlabel(){return ++Node.labels;}
    public  static void emitlabel(int i){System.out.print("L"+i+":");}
    public  static void emit(String s) {System.out.println("\t"+s);}
}


public class Expr extends Node {
    public final Token op;
    public Type  type;
    protected Expr(Token tok,Type p) {
        this.op=tok;
        this.type=p;
    }

    public Expr gen() {return this;}
    public Expr reduce() {return this;}
    public void jumping(int t,int f){Expr.emitjumps(this.toString(),t,f);}

    public static void emitjumps(String test , int t , int f) {
        if(t != 0 && f != 0){
            Node.emit("if "+test+" goto L"+t);
            Node.emit("goto L"+f);
        }else if(t != 0){
            Node.emit("if "+test+" goto L"+t);
        }else if(f != 0){
            Node.emit("ifFalse "+test+" goto L"+f);
        }else{
            // fall through
        }
    }

    @Override
    public String toString(){return this.op.toString();}
}

public class Id extends Expr{
    public final int offset;
    public Id (Word id,Type p,int b){
        super(id,p);
        this.offset=b;
    }
}

public class Op extends Expr {
    public Op (Token tok,Type p) {super(tok,p);}
    @Override
    public Expr reduce() {
        Expr x = this.gen();
        Temp t = new Temp(type);
        Node.emit(t.toString() + " = " + x.toString() );
        return t;
    }
}

public class Arith extends Op {
    public final Expr expr1;
    public final Expr expr2;
    public Arith(Token tok,Expr x1,Expr x2){
        super(tok,null);
        this.expr1 = x1;
        this.expr2 = x2;
        this.type  = Type.max(this.expr1.type , this.expr2.type);
        if( this.type == null) this.error("type error");
    }
    @Override
    public Expr gen() {
        return new Arith(this.op , this.expr1.reduce() , this.expr2.reduce());
    }
    @Override
    public String toString() {
        return this.expr1.toString() + " " + this.op.toString() + " " + this.expr2.toString();
    }
}

public class Temp extends Expr {
    private static int count = 0;
    private final  int number;
    public Temp(Type p){
        super(Word.temp,p);
        this.number = ++Temp.count;
    }
    @Override
    public String toString(){return "t"+this.number;}
}

public class Unary extends Op {
    public final Expr expr;
    public Unary (Token tok, Expr x){
        super(tok,null);
        this.expr = x;
        this.type = Type.max(Type.Int , this.expr.type);
        if(this.type == null) this.error("type error");
    }
    @Override
    public Expr gen(){
        return new Unary(this.op , this.expr.reduce() );
    }
    @Override
    public String toString() {
        return this.op.toString() + " " + this.expr.toString();
    }
}

// A.6 Jumping Code for Boolean Expression

public class Constant extends Expr {
    public Constant(Token tok , Type p){super(tok,p);}
    public Constant(int i){super(new Num(i),Type.Int);}

    public static final Constant True  = new Constant(Word.True,  Type.Bool);
    public static final Constant False = new Constant(Word.False, Type.Bool);

    @Override
    public void jumping(int t , int f){
        if     (this==Constant.True  && t!=0 ) Node.emit("goto L"+t);
        else if(this==Constant.False && f!=0 ) Node.emit("goto L"+f);
    }
    
}

public class Logical extends Expr {
    public final Expr expr1;
    public final Expr expr2;
    Logical (Token tok,Expr x1,Expr x2){
        super(tok,null);
        this.expr1 = x1;
        this.expr2 = x2;
        this.type  = this.check(this.expr1.type,this.expr2.type);
        if(this.type==null) this.error("type error");
    }

    public Type check (Type p1,Type p2){
        if(p1==Type.Bool && p2==Type.Bool) return Type.Bool;
        else return null;
    }

    @Override
    public Expr gen(){
        int f = Node.newlabel();
        int a = Node.newlabel();
        Temp temp = new Temp(this.type);
        this.jumping(0,f);
        Node.emit(temp.toString() + " = true");
        Node.emit("goto L"+a);
        Node.emitlabel(f);
        Node.emit(temp.toString() + " = false");
        Node.emitlabel(a);
        return temp;
    }

    @Override
    public String toString(){
        return this.expr1.toString()+" "+this.op.toString()+" "+this.expr2.toString();
    }
}

public class Or extends Logical {
    public Or(Token tok,Expr x1,Expr x2){super(tok,x1,x2);}
    @Override
    public void jumping(int t,int f){
        int label = (t!=0) ? t : Node.newlabel();
        this.expr1.jumping(label,0);
        this.expr2.jumping(t,f);
        if(t==0) Node.emitlabel(label);
    }
}

public class And extends Logical {
    public And(Token tok,Expr x1,Expr x2){super(tok,x1,x2);}
    @Override public void jumping(int t,int f){
        int label = (f!=0) ? f : Node.newlabel();
        this.expr1.jumping(0,label);
        this.expr2.jumping(t,f);
        if(f==0) Node.emitlabel(label);
    }
}

public class Not extends Logical {
    public Not(Token tok,Expr x2){super(tok,x2,x2);}

    @Override
    public void jumping(int t,int f){this.expr2.jumping(f,t);}

    @Override
    public String toString(){
        return this.op.toString()+" "+this.expr2.toString();
    }
}

public class Rel extends Logical {
    public Rel(Token tok,Expr x1,Expr x2){super(tok,x1,x2);}

    @Override
    public Type check(Type p1,Type p2){
        if(p1 instanceof Array || p2 instanceof Array) return null;
        else if(p1==p2) return Type.Bool;
        else return null;
    }

    @Override
    public void jumping(int t ,int f){
        Expr a = this.expr1.reduce();
        Expr b = this.expr2.reduce();
        String test=a.toString()+" "+this.op.toString()+" "+b.toString();
        Expr.emitjumps(test,t,f);
    }
}

public class Access extends Op {
    public final Id array;
    public final Expr index;
    public Access(Id a,Expr i,Type p){
        super(new Word("[]",Tag.INDEX),p);
        this.array = a;
        this.index = i;
    }

    @Override
    public Expr gen(){
        return new Access(this.array,this.index.reduce(),this.type);
    }

    @Override
    public String toString(){
        return this.array.toString()+" [ "+this.index.toString()+" ]";
    }
}

// A.7 Intermediate Code for Statement

public class Stmt extends Node{
    public Stmt() {}
    public static final Stmt Null = new Stmt();

    public void gen(int b,int a) {}

    protected int after = 0;

    public static Stmt Enclosing = Stmt.Null;
}

public class If extends Stmt {
    private final Expr expr;
    private  Stmt stmt;
    public If(Expr x , Stmt s){
        this.expr=x;
        this.stmt=s;
        if(this.expr.type!=Type.Bool) this.expr.error("boolean required in if");
    }

    @Override
    public void gen(int b , int a){
        int label = Node.newlabel();
        this.expr.jumping(0,a);
        Node.emitlabel(label);
        this.stmt.gen(label,a);
    }
}

public class Else extends Stmt {
    private final Expr expr;
    private final Stmt stmt1;
    private final Stmt stmt2;
    public Else(Expr x,Stmt s1,Stmt s2){
        this.expr  = x;
        this.stmt1 = s1;
        this.stmt2 = s2;
        if(this.expr.type != Type.Bool) this.expr.error("boolean required in if");
    }

    @Override
    public void gen(int b , int a){
        int label1 = Node.newlabel();
        int label2 = Node.newlabel();
        
        this.expr.jumping(0,label2);

        Node.emitlabel(label1);
        this.stmt1.gen(label1,a);
        Node.emit("goto L"+a);

        Node.emitlabel(label2);
        this.stmt2.gen(label2,a);
        
    }
}

public class While extends Stmt{
    private Expr expr;
    private Stmt stmt;
    public While(){
        this.expr=null;
        this.stmt=null;
    }

    public final void init(Expr x,Stmt s){
        this.expr = x;
        this.stmt = s;
        if(this.expr.type!=Type.Bool)this.expr.error("boolean required in While");
    }

    @Override
    public void gen(int b,int a){
        this.after = a;
        
        this.expr.jumping(0,a);
        
        int label = Node.newlabel();
        Node.emitlabel(label);
        this.stmt.gen(label,b);
        Node.emit("goto L"+b);
    }
}

public class Do extends Stmt {
    private Expr expr;
    private Stmt stmt;
    public Do () {
        this.expr = null;
        this.stmt = null;
    }

    public final void init(Stmt s,Expr x){
        this.expr = x;
        this.stmt = s;
        if(this.expr.type != Type.Bool) this.expr.error("boolean required in Do");
    }

    @Override
    public void gen(int b,int a){
        this.after = a;
        int label = Node.newlabel();
        this.stmt.gen(b,label);
        Node.emitlabel(label);
        this.expr.jumping(b,0);
    }
}

public class Set extends Stmt {
    private final Id   id;
    private final Expr expr;
    public Set(Id i,Expr x){
        this.id   = i;
        this.expr = x;
        if(Set.check( this.id.type , this.expr.type ) ==null)this.error("type error");
    }
    private static Type check(Type p1,Type p2){
        if     ( Type.numeric(p1) && Type.numeric(p2) ) return p2;
        else if( p1==Type.Bool && p2==Type.Bool ) return p2;
        else return null;
    }
    @Override
    public void gen(int b,int a){
        Node.emit(this.id.toString()+" = "+this.expr.gen().toString());
    }
}


public class SetElem extends Stmt {
    private final Id   array;
    private final Expr index;
    private final Expr expr;
    public SetElem(Access x,Expr y){
        this.array = x.array;
        this.index = x.index;
        this.expr  = y;
        if ( SetElem.check(x.type , this.expr.type)==null) this.error("type error");
    }

    private static Type check(Type p1,Type p2){
        if(p1 instanceof Array || p2 instanceof Array) return null;
        else if(p1==p2) return p2;
        else if(Type.numeric(p1)&&Type.numeric(p2)) return p2;
        else return null;
    }

    @Override
    public void gen(int b,int a){
        String s1 = this.index.reduce().toString();
        String s2 = this.expr .reduce().toString();
        Node.emit(this.array.toString()+" [ "+s1+" ] = "+s2);
    }
}

public class Seq extends Stmt {
    private final Stmt stmt1;
    private final Stmt stmt2;
    public Seq(Stmt s1,Stmt s2){
        this.stmt1 = s1;
        this.stmt2 = s2;
    }

    @Override
    public void gen(int b,int a){
        if     (this.stmt1==Stmt.Null) this.stmt2.gen(b,a);
        else if(this.stmt2==Stmt.Null) this.stmt1.gen(b,a);
        else{
            int label = Node.newlabel();
            this.stmt1.gen(b,label);
            Node.emitlabel(label);
            this.stmt2.gen(label,a);
        }
    }
}

public class Break extends Stmt {
    private final Stmt stmt;
    public Break(){
        if(Stmt.Enclosing==null) this.error("unenclose break");
        this.stmt = Stmt.Enclosing;
    }
    @Override
    public void gen(int b,int a){
        Node.emit("goto L"+this.stmt.after);
    }
}


// A.8 Parser

public class Parser {
    private Lexer lex;
    private Token look;
    private Env   top;
    private int   used = 0;
    public Parser(Lexer l) throws IOException {
        this.lex = l;
        this.move();
    }

    final void move() throws IOException {
        this.look = this.lex.scan();
    }
    final void error(String s){
        throw new Error(String.format("near line %d (look=<%s>) : %s" , Lexer.line,this.look , s));
    }
    final void match(Tag t) throws IOException{
        if(this.look.tag == t) this.move();
        else this.error("syntax.error");
    }
    final void match(char c) throws IOException{
        if(this.look instanceof Char t && t.value == c) this.move();
        else this.error("syntax.error");        
    }

    //-------------------------------------------------------------

    public void program() throws IOException {
        Stmt s = this.block();
        int begin = Node.newlabel();
        int after = Node.newlabel();
        Node.emitlabel(begin);
        s.gen(begin,after);
        Node.emitlabel(after);
    }

    Stmt block() throws IOException {
        this.match('{');
        Env savedEnv = this.top;
        this.top = new Env(this.top);
        this.decls();
        Stmt s = this.stmts();
        this.match('}');
        this.top = savedEnv;
        return s;
    }

    void decls() throws IOException{
        while ( this.look.tag == Tag.BASIC ) {
            Type p = this.type();
            Token tok = this.look;
            this.match(Tag.ID);
            this.match(';');
            if(tok instanceof Word w) {
                Id id = new Id(w , p , this.used);
                this.top.put(w,id);
                this.used += p.width;
            } else {
                this.error("syntax error");
            }
        }
    }

    Type type() throws IOException {
        if ( this.look instanceof Type p ){
            this.match( Tag.BASIC );
            if(this.look instanceof Char c && c.value == '[' ) return this.dims(p);
            return p;
        } else {
            this.error("syntax error");
            return null;
        }
    }

    Type dims (Type p) throws IOException {
        this.match('[');
        Token tok = this.look;
        this.match(Tag.NUM);
        this.match(']');
        if(this.look instanceof Char c && c.value =='[') p = this.dims(p);
        if(tok instanceof Num n){
            return new Array(n.value , p);
        }else{
            this.error("illegal token id");
            return null;
        }
    }

    Stmt stmts() throws IOException{
        if(this.look instanceof Char c && c.value =='}') return Stmt.Null;
        else return new Seq(this.stmt() , this.stmts());
    }

    Stmt stmt() throws IOException{
        Expr x;
        Stmt s,s1,s2;
        Stmt savedStmt;
        switch(this.look.tag){
        case CHAR:
            if(this.look instanceof Char c){
                switch(c.value){
                case ';':
                    this.move();
                    return Stmt.Null;
                case '{':
                    return this.block();
                default :
                    this.error ("syntax error");
                    return null;
                }
            } else {
                this.error("illegal token id");
            }
        case IF:
            this.match(Tag.IF); this.match('('); x=this.bool(); this.match(')');
            s1 = this.stmt();
            if(this.look.tag != Tag.ELSE) return new If(x,s1);
            this.match(Tag.ELSE);
            s2 = this.stmt();
            return new Else(x,s1,s2);

        case WHILE:
            While whilenode = new While();
            savedStmt = Stmt.Enclosing; Stmt.Enclosing = whilenode;
            this.match(Tag.WHILE); this.match('('); x=this.bool(); this.match(')');
            s1 = this.stmt();
            whilenode.init(x,s1);
            Stmt.Enclosing = savedStmt;
            return whilenode;

        case DO:
            Do donode = new Do();
            savedStmt = Stmt.Enclosing; Stmt.Enclosing = donode;
            this.match(Tag.DO);
            s1 = this.stmt();
            this.match(Tag.WHILE); this.match('('); x=this.bool(); this.match(')'); this.match(';');
            donode.init(s1,x);
            Stmt.Enclosing = savedStmt;
            return donode;

        case BREAK:
            this.match(Tag.BREAK); this.match(';');
            return new Break();

        case ID:
            return this.assign();

        default:
            this.error("syntax error");
            return null;
        }
    }

    Stmt assign() throws IOException {
        Stmt stmt;
        Token t = this.look;
        this.match(Tag.ID);
        Id id = this.top.get(t);
        if( id==null) error(t.toString() + " undeclared");
        if(this.look instanceof Char c && c.value=='='){
            this.move();
            stmt=new Set(id,this.expr());
        } else {
            Access x = this.offset(id);
            this.match('=');
            stmt = new SetElem(x,this.expr());
        }
        this.match(';');
        return stmt;
    }
    
    Expr bool() throws IOException {
        Expr x = this.join();
        while(this.look.tag == Tag.OR){
            Token tok = this.look;
            this.move();
            x = new Or( tok , x , this.join());
        }
        return x;
    }

    Expr join() throws IOException {
        Expr x = this.equality();
        while(this.look.tag == Tag.AND){
            Token tok = this.look;
            this.move();
            x = new And( tok , x , this.equality() );
        }
        return x;
    }

    Expr equality() throws IOException {
        Expr x = this.rel();
        while( this.look.tag==Tag.EQ || this.look.tag==Tag.NE ){
            Token tok = this.look;
            this.move();
            x = new Rel ( tok , x , this.rel() );
        }
        return x;
    }
    Expr rel() throws IOException {
        //System.out.printf("rel() : look=<%s>%n",this.look);
        Expr x = this.expr();
        //System.out.printf("rel() :look=<%s>%n",this.look);
        switch(this.look.tag){
        case CHAR:
            if(this.look instanceof Char c){
                switch(c.value){
                case '<':
                case '>':
                    Token tok = this.look;
                    this.move();
                    return new Rel( tok , x , this.expr() );
                default:
                    return x;
                }
            } else {
                this.error("illegal token id");
                return null;
            }
        case LE:
        case GE:
            //System.out.print("LE/GE\n");
            Token tok = this.look;
            this.move();
            return new Rel( tok , x , this.expr() );

        default:
            return x;
        }
    }

    Expr expr() throws IOException {
        Expr x = this.term();
        while(this.look instanceof Char c && (c.value=='+'||c.value=='-')){
            Token tok = this.look;
            this.move();
            x = new Arith( tok , x , this.term() );
        }
        return x;
    }

    Expr term() throws IOException {
        Expr x = this.unary();
        while(this.look instanceof Char c && (c.value=='*'||c.value=='/')){
            Token tok=this.look;
            this.move();
            x = new Arith( tok , x , this.unary() );
        }
        return x;
    }

    Expr unary() throws IOException {
        //System.out.printf("unary() : look=%s%n",this.look);
        if (this.look instanceof Char c){
            if( c.value=='-' ){
                this.move();
                return new Unary (Word.minus , this.unary());
            } else if ( c.value=='!' ){
                Token tok = this.look;
                this.move();
                return new Not( tok , this.unary() );
            } else{
                return this.factor();
            }
        } else {
            return this.factor();
        }
    }

    Expr factor() throws IOException {
        //System.out.printf("factor() : look=%s(%s)%n",this.look,this.look.tag);
        Expr x = null;
        switch( this.look.tag ){
        case CHAR:
            if(this.look instanceof Char c && c.value=='('){
                this.move();
                x = this.expr();
                this.match(')');
                return x;
            } else {
                this.error("syntax error");
                return null;
            }
            
        case NUM:
            x = new Constant( this.look , Type.Int);
            this.move();
            return x;

        case REAL:
            x = new Constant( this.look , Type.Float);
            this.move();
            return x;

        case TRUE:
            x = Constant.True;
            this.move();
            return x;

        case FALSE:
            x = Constant.False;
            this.move();
            return x;

        case ID:
            Id id = this.top.get(this.look);
            if(id == null){
                this.error(this.look.toString() + " undeclared");
                return null;
            }
            this.move();
            //System.out.printf("factor() : look=%s(%s)%n",this.look,this.look.tag);
            if( this.look instanceof Char c){
                if( c.value != '[' ) return id;
                else return this.offset(id);
            } else {
                return id;
            }
            
        default:
            this.error("syntax error");
            return null;
        }
    }
    
    Access offset(Id a) throws IOException{
        Expr i;
        Expr w;
        Expr t1,t2;
        Expr loc;
        Type type = a.type;
        if( type instanceof Array t) {
            type = t.of;
            this.match('[');
            i = this.expr();
            this.match(']');
            w = new Constant (type.width);
            t1 = new Arith(new Char('*') , i , w );
            loc = t1;
            while( this.look instanceof Char c && c.value == '[' ){
                if (type instanceof Array u){
                    this.match('[');
                    i = this.expr();
                    this.match(']');
                    type = u.of;
                    w  = new Constant (type.width);
                    t1 = new Arith( new Char('*') , i   , w );
                    t2 = new Arith( new Char('+') , loc , t1);
                    loc = t2;
                } else {
                    this.error("syntax error");
                    return null;
                }
                
            }
            
        } else {
            this.error("syntax error");
            return null;
        }

        return new Access( a , loc , type );
    }
}