diff options
Diffstat (limited to 'chapter01/src/main/java')
5 files changed, 330 insertions, 82 deletions
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/parser/Ast.java b/chapter01/src/main/java/com/seaofnodes/simple/parser/Ast.java index 51c7b7ac..c271d4b6 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/parser/Ast.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/parser/Ast.java @@ -16,8 +16,6 @@ */ package com.seaofnodes.simple.parser; -import com.seaofnodes.simple.lexer.ecstasy.Token; - import java.util.ArrayList; import java.util.List; import java.util.stream.Collectors; @@ -47,7 +45,7 @@ public class Ast { public Identifier(Token op) { super(op); - name = op.getValueText(); + name = op.str; } @Override @@ -64,7 +62,7 @@ public class Ast { public Symbol(Token op) { super(op); - name = op.getValueText(); + name = op.str; } @Override @@ -85,7 +83,7 @@ public class Ast { @Override public String toString() { - return "(" + expr1 + op.getValueText() + expr2 + ")"; + return "(" + expr1 + op.toString() + expr2 + ")"; } } @@ -99,7 +97,7 @@ public class Ast { @Override public String toString() { - return "(" + op.getValueText() + "(" + expr + "))"; + return "(" + op.toString() + "(" + expr + "))"; } } @@ -110,7 +108,7 @@ public class Ast { @Override public String toString() { - return op.getValueText(); + return op.toString(); } } @@ -174,15 +172,15 @@ public class Ast { } public static class Type extends Ast { - public final Token.Id typeId; + public final String typeId; - public Type(Token.Id typeId) { + public Type(String typeId) { this.typeId = typeId; } @Override public String toString() { - return typeId.TEXT; + return typeId; } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/parser/CompilerException.java b/chapter01/src/main/java/com/seaofnodes/simple/parser/CompilerException.java new file mode 100644 index 00000000..a62fa034 --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/parser/CompilerException.java @@ -0,0 +1,27 @@ +/* + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * <p> + * Contributor(s): + * <p> + * The Initial Developer of the Original Software is Dibyendu Majumdar. + * <p> + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * <p> + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.simple.parser; + +public class CompilerException extends RuntimeException { + public CompilerException(String message) { + super(message); + } + + public CompilerException(String message, Throwable cause) { + super(message, cause); + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/parser/Lexer.java b/chapter01/src/main/java/com/seaofnodes/simple/parser/Lexer.java new file mode 100644 index 00000000..fbe8c239 --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/parser/Lexer.java @@ -0,0 +1,151 @@ +/* + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * <p> + * Contributor(s): + * <p> + * The Initial Developer of the Original Software is Dibyendu Majumdar. + * <p> + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * <p> + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.simple.parser; + +import java.text.NumberFormat; +import java.text.ParseException; + +public class Lexer { + + private final char[] input; + /** + * Tracks current position in input buffer + */ + private int position = 0; + private char peek = ' '; + + private final NumberFormat numberFormat; + + public Lexer(String source) { + input = source.toCharArray(); + numberFormat = NumberFormat.getInstance(); + numberFormat.setGroupingUsed(false); + } + + private boolean isEOF() { + return position >= input.length; + } + + private char advance() { + if (isEOF()) + return 0; // Special value that causes parsing to terminate + return input[position++]; + } + + private boolean readch() { + peek = advance(); + return true; + } + + private boolean readch(char c) { + if (readch() && peek != c) + return false; + peek = ' '; + return true; + } + + /** + * Note that EOF is not whitespace! + */ + private boolean isWhiteSpace(char c) { + return c == ' ' || + c == '\t' || + c == '\n' || + c == '\r'; + } + + private void skipWhitespace() { + while (isWhiteSpace(peek)) + readch(); + } + + /** + * Parses number in format nnn[.nnn] + * where n is a digit + */ + private Token parseNumber() { + assert Character.isDigit(peek); + StringBuilder sb = new StringBuilder(); + sb.append(peek); + while (readch() && Character.isDigit(peek)) + sb.append(peek); + if (peek == '.') { + sb.append(peek); + while (readch() && Character.isDigit(peek)) + sb.append(peek); + } + String str = sb.toString(); + Number number = parseNumber(str); + return Token.newNum(number, str); + } + + private Number parseNumber(String str) { + try { + return numberFormat.parse(str); + } catch (ParseException e) { + throw new CompilerException("Failed to parse number " + str, e); + } + } + + private boolean isIdentifierStart(char ch) { + return Character.isAlphabetic(ch) || ch == '_'; + } + + private boolean isIdentifierLetter(char ch) { + return Character.isLetterOrDigit(ch) || ch == '_'; + } + + private Token parseIdentifier() { + assert isIdentifierStart(peek); + StringBuilder sb = new StringBuilder(); + sb.append(peek); + while (readch() && isIdentifierLetter(peek)) + sb.append(peek); + return Token.newIdent(sb.toString()); + } + + public Token scan() { + skipWhitespace(); + switch (peek) { + case 0: + return Token.EOF; + case '&': + return readch('&') ? Token.newPunct("&&") : Token.newPunct("&"); + case '|': + return readch('|') ? Token.newPunct("||") : Token.newPunct("|"); + case '=': + return readch('=') ? Token.newPunct("==") : Token.newPunct("="); + case '<': + return readch('=') ? Token.newPunct("<=") : Token.newPunct("<"); + case '>': + return readch('=') ? Token.newPunct(">=") : Token.newPunct(">"); + default: { + return scanOthers(); + } + } + } + + private Token scanOthers() { + if (Character.isDigit(peek)) + return parseNumber(); + else if (isIdentifierLetter(peek)) + return parseIdentifier(); + Token token = Token.newPunct(Character.toString(peek)); + peek = ' '; + return token; + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/parser/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/parser/Parser.java index fe224105..7e333b71 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/parser/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/parser/Parser.java @@ -16,17 +16,13 @@ */ package com.seaofnodes.simple.parser; -import com.seaofnodes.simple.lexer.ecstasy.CompilerException; -import com.seaofnodes.simple.lexer.ecstasy.Lexer; -import com.seaofnodes.simple.lexer.ecstasy.Token; -import com.seaofnodes.simple.lexer.ecstasy.Severity; - public class Parser { private Token currentToken; /** * Parse and return a top level Ast * At present this is an Ast.Block + * * @see Ast.Block */ public Ast parse(Lexer lexer) { @@ -34,37 +30,41 @@ public class Parser { return parseProgram(lexer); } - private Token nextOrEof(Lexer lexer) { - if (lexer.hasNext()) - return lexer.next(); - return new Token(currentToken.getStartPosition(), currentToken.getEndPosition(), Token.Id.EOF); + private void nextToken(Lexer lexer) { + currentToken = lexer.scan(); } - private void nextToken(Lexer lexer) { - currentToken = nextOrEof(lexer); - // skip comments - while (currentToken.isComment()) { - currentToken = nextOrEof(lexer); - } - if (currentToken.isContextSensitive() && - currentToken.getId() == Token.Id.IDENTIFIER) { - currentToken = currentToken.convertToKeyword(); + private void error(Token t, String errorMessage) { + throw new CompilerException(errorMessage + ": " + t.toString()); + } + + private void matchKind(Lexer lexer, Token.Kind kind) { + if (currentToken.kind == kind) { + nextToken(lexer); + } else { + error(currentToken, "syntax error, expected " + kind); } } - private void error(Lexer lexer, Token t, String errorMessage) { - lexer.log(Severity.ERROR, errorMessage, t.getStartPosition(), t.getEndPosition()); - throw new CompilerException(errorMessage + ": " + t.toDebugString()); + private void matchPunctuation(Lexer lexer, String value) { + if (currentToken.kind == Token.Kind.PUNCT && isToken(currentToken, value)) { + nextToken(lexer); + } else { + error(currentToken, "syntax error, expected " + value + " got " + currentToken.str); + } } - private void match(Lexer lexer, Token.Id tag) { - if (currentToken.getId() == tag) { + private void matchIdentifier(Lexer lexer, String identifier) { + if (currentToken.kind == Token.Kind.IDENT && isToken(currentToken, identifier)) { nextToken(lexer); } else { - error(lexer, currentToken, "syntax error, expected " + tag); + error(currentToken, "syntax error, expected " + identifier); } } + private boolean isToken(Token token, String value) { + return token.str.equals(value); + } private Ast.Statement parseProgram(Lexer lexer) { var block = new Ast.Block(); @@ -74,27 +74,34 @@ public class Parser { } private boolean isTypeName(Token tok) { - return switch (tok.getId()) { - case TYPE_INT, TYPE_CHAR, TYPE_FLOAT -> true; - default -> false; - }; + return tok.kind == Token.Kind.IDENT && + (isToken(tok, "int") || + isToken(tok, "char") || + isToken(tok, "float")); } private void parseDeclarations(Lexer lexer, Ast.Block block) { while (isTypeName(currentToken)) { - var type = new Ast.Type(currentToken.getId()); + var type = new Ast.Type(currentToken.str); nextToken(lexer); var tok = currentToken; - match(lexer, Token.Id.IDENTIFIER); - match(lexer, Token.Id.SEMICOLON); + matchKind(lexer, Token.Kind.IDENT); + matchPunctuation(lexer, ";"); var identifier = new Ast.Identifier(tok); block.stmtList.add(new Ast.Declare(type, identifier)); } } + private boolean isEOF(Token tok) { + return tok.kind == Token.Kind.EOZ; + } + + private boolean isPunct(Token tok, String str) { + return tok.kind == Token.Kind.PUNCT && isToken(tok, str); + } + private void parseStatements(Lexer lexer, Ast.Block block) { - while (currentToken.getId() != Token.Id.EOF && - currentToken.getId() != Token.Id.R_CURLY) { + while (!isEOF(currentToken) && !isPunct(currentToken, "}")) { block.stmtList.add(parseStatement(lexer)); } } @@ -104,33 +111,33 @@ public class Parser { Ast.Statement s1; Ast.Statement s2; - switch (currentToken.getId()) { - case IF -> { - match(lexer, Token.Id.IF); - match(lexer, Token.Id.L_PAREN); + switch (currentToken.str) { + case "if" -> { + matchIdentifier(lexer, "if"); + matchPunctuation(lexer, "("); x = parseBool(lexer); - match(lexer, Token.Id.R_PAREN); + matchPunctuation(lexer, ")"); s1 = parseStatement(lexer); - if (currentToken.getId() != Token.Id.ELSE) { + if (!isToken(currentToken, "else")) { return new Ast.IfElse(x, s1, null); } s2 = parseStatement(lexer); return new Ast.IfElse(x, s1, s2); } - case WHILE -> { - match(lexer, Token.Id.WHILE); - match(lexer, Token.Id.L_PAREN); + case "while" -> { + matchIdentifier(lexer, "while"); + matchPunctuation(lexer, "("); x = parseBool(lexer); - match(lexer, Token.Id.R_PAREN); + matchPunctuation(lexer, ")"); s1 = parseStatement(lexer); return new Ast.While(x, s1); } - case BREAK -> { - match(lexer, Token.Id.BREAK); - match(lexer, Token.Id.SEMICOLON); + case "break" -> { + matchIdentifier(lexer, "break"); + matchPunctuation(lexer, ";"); return new Ast.Break(); } - case L_CURLY -> { + case "{" -> { return parseBlock(lexer); } default -> { @@ -140,27 +147,27 @@ public class Parser { } private Ast.Statement parseBlock(Lexer lexer) { - match(lexer, Token.Id.L_CURLY); + matchPunctuation(lexer, "{"); var block = new Ast.Block(); parseDeclarations(lexer, block); parseStatements(lexer, block); - match(lexer, Token.Id.R_CURLY); + matchPunctuation(lexer, "}"); return block; } private Ast.Statement parseAssign(Lexer lexer) { Token tok = currentToken; - match(lexer, Token.Id.IDENTIFIER); + matchKind(lexer, Token.Kind.IDENT); Ast.Identifier identifier = new Ast.Identifier(tok); - match(lexer, Token.Id.ASN); + matchPunctuation(lexer, "="); var s = new Ast.Assign(identifier, parseBool(lexer)); - match(lexer, Token.Id.SEMICOLON); + matchPunctuation(lexer, ";"); return s; } private Ast.Expr parseBool(Lexer lexer) { var x = parseAnd(lexer); - while (currentToken.getId() == Token.Id.COND_OR) { + while (isToken(currentToken, "||")) { var tok = currentToken; nextToken(lexer); x = new Ast.Binary(tok, x, parseAnd(lexer)); @@ -170,7 +177,7 @@ public class Parser { private Ast.Expr parseAnd(Lexer lexer) { var x = parseRelational(lexer); - while (currentToken.getId() == Token.Id.COND_AND) { + while (isToken(currentToken, "&&")) { var tok = currentToken; nextToken(lexer); x = new Ast.Binary(tok, x, parseRelational(lexer)); @@ -180,12 +187,12 @@ public class Parser { private Ast.Expr parseRelational(Lexer lexer) { var x = parseAddition(lexer); - while (currentToken.getId() == Token.Id.COMP_EQ || - currentToken.getId() == Token.Id.COMP_NEQ || - currentToken.getId() == Token.Id.COMP_LT || - currentToken.getId() == Token.Id.COMP_GT || - currentToken.getId() == Token.Id.COMP_GTEQ || - currentToken.getId() == Token.Id.COMP_LTEQ) { + while (isToken(currentToken, "==") || + isToken(currentToken, "!=") || + isToken(currentToken, "<=") || + isToken(currentToken, "<") || + isToken(currentToken, ">") || + isToken(currentToken, ">=")) { var tok = currentToken; nextToken(lexer); x = new Ast.Binary(tok, x, parseAddition(lexer)); @@ -195,8 +202,8 @@ public class Parser { private Ast.Expr parseAddition(Lexer lexer) { var x = parseMultiplication(lexer); - while (currentToken.getId() == Token.Id.ADD || - currentToken.getId() == Token.Id.SUB) { + while (isToken(currentToken, "-") || + isToken(currentToken, "+")) { var tok = currentToken; nextToken(lexer); x = new Ast.Binary(tok, x, parseMultiplication(lexer)); @@ -206,8 +213,8 @@ public class Parser { private Ast.Expr parseMultiplication(Lexer lexer) { var x = parseUnary(lexer); - while (currentToken.getId() == Token.Id.MUL || - currentToken.getId() == Token.Id.DIV) { + while (isToken(currentToken, "*") || + isToken(currentToken, "/")) { var tok = currentToken; nextToken(lexer); x = new Ast.Binary(tok, x, parseUnary(lexer)); @@ -216,8 +223,8 @@ public class Parser { } private Ast.Expr parseUnary(Lexer lexer) { - if (currentToken.getId() == Token.Id.SUB || - currentToken.getId() == Token.Id.NOT) { + if (isToken(currentToken, "-") || + isToken(currentToken, "!")) { var tok = currentToken; nextToken(lexer); return new Ast.Unary(tok, parseUnary(lexer)); @@ -227,25 +234,27 @@ public class Parser { } private Ast.Expr parsePrimary(Lexer lexer) { - switch (currentToken.getId()) { - case L_PAREN -> { + switch (currentToken.kind) { + case PUNCT -> { + /* Nested expression */ + matchPunctuation(lexer, "("); nextToken(lexer); var x = parseBool(lexer); - match(lexer, Token.Id.R_PAREN); + matchPunctuation(lexer, ")"); return x; } - case LIT_INT -> { + case NUM -> { var x = new Ast.Constant(currentToken); nextToken(lexer); return x; } - case IDENTIFIER -> { + case IDENT -> { var x = new Ast.Symbol(currentToken); nextToken(lexer); return x; } default -> { - error(lexer, currentToken, "syntax error, expected nested expr, integer value or variable"); + error(currentToken, "syntax error, expected nested expr, integer value or variable"); return null; } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/parser/Token.java b/chapter01/src/main/java/com/seaofnodes/simple/parser/Token.java new file mode 100644 index 00000000..d45bef5a --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/parser/Token.java @@ -0,0 +1,63 @@ +/* + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * <p> + * Contributor(s): + * <p> + * The Initial Developer of the Original Software is Dibyendu Majumdar. + * <p> + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * <p> + * The contents of this file are subject to the terms of the + * Apache License Version 2 (the "APL"). You may not use this + * file except in compliance with the License. A copy of the + * APL may be obtained from: + * http://www.apache.org/licenses/LICENSE-2.0 + */ +package com.seaofnodes.simple.parser; + +public class Token { + + enum Kind { + IDENT, + NUM, + PUNCT, + EOZ // Special kind to signal end of file + } + + public final Kind kind; + /** + * String representation of a token - always + * populated + */ + public final String str; + /** + * The parsed number value, only populated for Kind.NUM + */ + public final Number num; + + public Token(Kind kind, String str, Number num) { + this.kind = kind; + this.str = str; + this.num = num; + } + + public static Token newIdent(String str) { + return new Token(Kind.IDENT, str.intern(), null); + } + public static Token newNum(Number num, String str) { + return new Token(Kind.NUM, str, num); + } + public static Token newPunct(String str) { + return new Token(Kind.PUNCT, str.intern(), null); + } + + /** + * Special token that indicates that source has been exhausted + */ + public static Token EOF = new Token(Kind.EOZ, "", null); + + public String toString() { + return str; + } +} |