diff options
Diffstat (limited to 'chapter01')
4 files changed, 166 insertions, 187 deletions
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index cdfff842..a71def25 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -13,23 +13,25 @@ import com.seaofnodes.simple.node.StartNode; */ public class Parser { + private final Lexer _lexer; + /** - * Current token from lexer + * A Global Static, unique to each compilation. This is a public, so we + * can make constants everywhere without having to thread the StartNode + * through the entire parser and optimizer. + * <p> + * To make the compiler multithreaded, this field will have to move into a TLS. */ - private Token _curTok; - - private StartNode _startNode; + public static StartNode START; - public StartNode parse(String source) { - Lexer lexer = new Lexer(source); - nextToken(lexer); - return parseProgram(lexer); + public Parser(String source) { + _lexer = new Lexer(source); + Node.reset(); + START = new StartNode(); } - private StartNode parseProgram(Lexer lexer) { - _startNode = new StartNode(); - parseReturnStatement(lexer); - return _startNode; + public ReturnNode parse() { + return parseReturn(); } /** @@ -39,11 +41,11 @@ public class Parser { * return expr ; * </pre> */ - private ReturnNode parseReturnStatement(Lexer lexer) { - matchIdentifier(lexer, "return"); - var returnExpr = parseExpression(lexer); - matchPunctuation(lexer, ";"); - return new ReturnNode(_startNode, returnExpr); + private ReturnNode parseReturn() { + require("return"); + var returnExpr = parseExpression(); + require(";"); + return new ReturnNode(START, returnExpr); } /** @@ -53,8 +55,8 @@ public class Parser { * expr : primaryExpr * </pre> */ - private Node parseExpression(Lexer lexer) { - return parsePrimary(lexer); + private Node parseExpression() { + return parsePrimary(); } /** @@ -64,16 +66,11 @@ public class Parser { * primaryExpr : integerLiteral * </pre> */ - private Node parsePrimary(Lexer lexer) { - switch (_curTok._kind) { - case NUM -> { - return parseIntegerLiteral(lexer); - } - default -> { - error(_curTok, "syntax error, expected integer literal"); - return null; - } - } + private Node parsePrimary() { + _lexer.skipWhiteSpace(); + if (_lexer.isNumber()) + return parseIntegerLiteral(); + throw error("Syntax error, expected integer literal"); } /** @@ -83,91 +80,32 @@ public class Parser { * integerLiteral: [1-9][0-9]* | [0] * </pre> */ - private ConstantNode parseIntegerLiteral(Lexer lexer) { - var constantNode = new ConstantNode(_curTok._num.longValue(), _startNode); - nextToken(lexer); - return constantNode; - } - - ////////////////////////////////// - // Utilities for lexical analysis - - private void nextToken(Lexer lexer) { - _curTok = lexer.next(); + private ConstantNode parseIntegerLiteral() { + return new ConstantNode(_lexer.parseNumber(), START); } - private boolean isToken(Token token, String value) { - return token._str.equals(value); + static RuntimeException error(String errorMessage) { + return new RuntimeException(errorMessage); } - private void error(Token t, String errorMessage) { - throw new RuntimeException(errorMessage + ": " + t.toString()); - } + ////////////////////////////////// + // Utilities for lexical analysis - private void matchPunctuation(Lexer lexer, String value) { - if (_curTok._kind == Token.Kind.PUNCT && isToken(_curTok, value)) { - nextToken(lexer); - } else { - error(_curTok, "syntax error, expected " + value + " got " + _curTok._str); - } + // Return true and skip if "syntax" is next in the stream. + private boolean match(String syntax) { + return _lexer.match(syntax); } - private void matchIdentifier(Lexer lexer, String identifier) { - if (_curTok._kind == Token.Kind.IDENT && isToken(_curTok, identifier)) { - nextToken(lexer); - } else { - error(_curTok, "syntax error, expected " + identifier); - } + // Require an exact match + private void require(String syntax) { + if (match(syntax)) return; + throw error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); } //////////////////////////////////// // Lexer components - static 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) { - _kind = kind; - _str = str; - _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); - - @Override - public String toString() { return _str; } - } - - static class Lexer { + private static class Lexer { // Input buffer; an array of text bytes read from a file or a string private final byte[] _input; @@ -177,49 +115,88 @@ public class Parser { /** * Record the source text for lexing */ - public Lexer(String source) { this(source.getBytes()); } - public Lexer(byte[] buf) { _input = buf; } + public Lexer(String source) { + this(source.getBytes()); + } + + /** + * Direct from disk file source + */ + public Lexer(byte[] buf) { + _input = buf; + } // True if at EOF - private boolean isEOF() { return _position >= _input.length; } + private boolean isEOF() { + return _position >= _input.length; + } + + // Peek next character, or report EOF + private char peek() { + return isEOF() ? Character.MAX_VALUE // Special value that causes parsing to terminate + : (char) _input[_position]; + } private char nextChar() { char ch = peek(); _position++; return ch; } - // Peek next character, or report EOF - private char peek() { - return isEOF() ? Character.MAX_VALUE // Special value that causes parsing to terminate - : (char)_input[_position]; - } // True if a white space - private boolean isWhiteSpace(char c) { - return c <= ' '; // Includes all the use space, tab, newline, CR + private boolean isWhiteSpace() { + return peek() <= ' '; // Includes all the use space, tab, newline, CR } /** * Return the next non-white-space character */ - private char skipWhiteSpace() { - char c = nextChar(); - while( isWhiteSpace(c) ) - c = nextChar(); - return c; + private void skipWhiteSpace() { + while (isWhiteSpace()) + _position++; + } + + + // Return true, if we find "syntax" after skipping white space; also + // then advance the cursor past syntax. + // Return false otherwise, and do not advance the cursor. + boolean match(String syntax) { + skipWhiteSpace(); + int len = syntax.length(); + if (_position + len > _input.length) + return false; + for (int i = 0; i < len; i++) + if ((char) _input[_position + i] != syntax.charAt(i)) + return false; + _position += len; + return true; + } + + // Used for errors + String getAnyNextToken() { + if (isEOF()) return ""; + if (isIdentifierStart(peek())) + return parseIdentifier(); + if (isPunctuation(peek())) + return parsePunctuation(); + return String.valueOf(peek()); + } + + boolean isNumber() { + return isNumber(peek()); } - private boolean isDigit(char ch) { - return ('0'<=ch && ch<='9'); + boolean isNumber(char ch) { + return Character.isDigit(ch); } - private Token parseNumber() { - int start = _position-1; - while( Character.isDigit( nextChar() ) ) ; - String snum = new String(_input,start,--_position-start); + private long parseNumber() { + int start = _position; + while (isNumber(nextChar())) ; + String snum = new String(_input, start, --_position - start); if (snum.length() > 1 && snum.charAt(0) == '0') - throw error("syntax error: integer values cannot start with '0'"); - return Token.newNum(Integer.parseInt(snum),snum); + throw error("Syntax error: integer values cannot start with '0'"); + return Long.parseLong(snum); } // First letter of an identifier @@ -232,10 +209,10 @@ public class Parser { return Character.isLetterOrDigit(ch) || ch == '_'; } - private Token parseIdentifier() { - int start = _position-1; - while( isIdentifierLetter(nextChar()) ); - return Token.newIdent(new String(_input,start,--_position-start)); + private String parseIdentifier() { + int start = _position; + while (isIdentifierLetter(nextChar())) ; + return new String(_input, start, --_position - start); } // @@ -243,31 +220,10 @@ public class Parser { return "=;[]<>()+-/*".indexOf(ch) != -1; } - private Token parsePuncuation() { - int start = _position-1; - if( isPunctuation(nextChar()) ); - return Token.newPunct(new String(_input,start,--_position-start)); - } - - /** - * Gets the next Token - */ - public Token next() { - char ch = skipWhiteSpace(); - if (ch == Character.MAX_VALUE) - return Token.EOF; - if (isDigit(ch)) - return parseNumber(); - if (isIdentifierStart(ch)) - return parseIdentifier(); - if (isPunctuation(ch)) - return parsePuncuation(); - - throw error("syntax error: unexpected input '" + ch + "'"); - } - - private RuntimeException error(String msg) { - throw new RuntimeException(msg); + private String parsePunctuation() { + int start = _position; + if (isPunctuation(nextChar())) ; + return new String(_input, start, --_position - start); } } diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java index 6b2a19b8..b6ce3160 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -74,6 +74,13 @@ public abstract class Node { public int nOuts() { return _outputs.size(); } + /** + * Used to allow repeating tests in the same JVM. This just resets the + * Node unique id generator, and is done as part of making a new Parser. + */ + public static void reset() { + UNIQUE_ID = 1; + } /* * hashCode and equals implementation to be added in later chapter. */ diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 12a5b464..a2321e2b 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -14,4 +14,12 @@ public class ReturnNode extends Node implements Control { public ReturnNode(Node ctrl, Node data) { super(ctrl, data); } + + public Node ctrl() { + return in(0); + } + + public Node expr() { + return in(1); + } } diff --git a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 14c22437..ce8c2822 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -1,39 +1,42 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.ReturnNode; +import com.seaofnodes.simple.node.StartNode; +import org.junit.Rule; import org.junit.Test; -import static org.junit.Assert.*; +import org.junit.rules.ExpectedException; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; public class Chapter01Test { + @Rule + public ExpectedException exceptionRule = ExpectedException.none(); + @Test public void testSimpleProgram() { - Parser parser = new Parser(); - StartNode startNode = parser.parse("return 1;"); - assertNotNull(startNode); - assertEquals(2, startNode.nOuts()); - for (int i = 0; i < startNode.nOuts(); i++) { - switch( startNode.out(i) ) { - case ReturnNode ret: - assertEquals(2, ret.nIns()); - assertEquals(startNode, ret.in(0)); - assertTrue(ret.in(1) instanceof ConstantNode); - break; - case ConstantNode con: - assertEquals(1, con._value); - assertEquals(1, con.nIns()); - assertEquals(startNode, con.in(0)); - break; - default: - throw new IllegalStateException(); - } + Parser parser = new Parser("return 1;"); + ReturnNode ret = parser.parse(); + StartNode start = Parser.START; + + assertEquals(start, ret.ctrl()); + Node expr = ret.expr(); + if (expr instanceof ConstantNode con) { + assertEquals(start, con.in(0)); + assertEquals(1, con._value); + } else { + fail(); } } @Test public void testZero() { - Parser parser = new Parser(); - StartNode start = parser.parse("return 0;"); + Parser parser = new Parser("return 0;"); + parser.parse(); + StartNode start = Parser.START; for( Node use : start._outputs ) if( use instanceof ConstantNode con ) assertEquals(0,con._value); @@ -41,32 +44,37 @@ public class Chapter01Test { @Test public void testBad1() { - try { new Parser().parse("ret"); } - catch( RuntimeException e ) { assertEquals("syntax error, expected return: ret",e.getMessage()); } + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error, expected return: ret"); + new Parser("ret").parse(); } @Test public void testBad2() { - try { new Parser().parse("return 0123;"); } - catch( RuntimeException e ) { assertEquals("syntax error: integer values cannot start with '0'",e.getMessage()); } + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error: integer values cannot start with '0'"); + new Parser("return 0123;").parse(); } @Test public void testBad3() { - try { new Parser().parse("return --12;"); } - catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: -",e.getMessage()); } + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error, expected integer literal"); + new Parser("return --12;").parse(); } @Test public void testBad4() { - try { new Parser().parse("return 100"); } - catch( RuntimeException e ) { assertTrue(e.getMessage().contains("syntax error, expected ; got :")); } + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error, expected ;:"); + new Parser("return 100").parse(); } // Negative numbers require unary operator support that is not in scope @Test public void testBad5() { - try { new Parser().parse("return -100;"); } - catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: -", e.getMessage()); } + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Syntax error, expected integer literal"); + new Parser("return -100;").parse(); } } |