Skip to content

Instantly share code, notes, and snippets.

@yamasushi

yamasushi/Main.java

Last active February 4, 2026 22:42
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save yamasushi/bbfc1dd937617ca43bda9d1defda9218 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save yamasushi/bbfc1dd937617ca43bda9d1defda9218 to your computer and use it in GitHub Desktop.
Download ZIP
Compilers / Chapter 2 , Appendix A
Raw
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.line=1;
var l = new Lexer();
System.out.println("-----------");
printWords(l);
System.out.println("-----------");
int i = 1;
System.out.printf("[%04d]",i);
for( ; ; ) {
var t = l.scan();
assert i <= Lexer.line;
if ( t instanceof Eof e ) {
System.out.printf("<End of File>%n");
break;
} else {
if ( i < Lexer.line ){
i = Lexer.line;
System.out.printf("%n[%04d]",i);
}
if (t instanceof Char c) {
System.out.printf("<%s>",t);
} else {
System.out.printf("<%s,%s>",t.tag,t);
}
}
}
System.out.println("-----------");
printWords(l);
}
static void printWords(Lexer l) {
l.getWords()
.forEach((k,v)->
System.out.printf("key=%-10s , value=(tag=%-10s,lexeme=%s)%n",k,v.tag,v.lexeme));
}
}
// 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; w!=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);
}
}
// A.8 Parser
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment