From 5166e178bda699d574bd9dfbd1718e86bc9c95f9 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sun, 17 Sep 2023 22:46:22 +0100 Subject: Start on parser --- .../main/java/com/seaofnodes/simple/Parser.java | 254 +++++++++++++++++++++ .../com/seaofnodes/simple/node/ConstantNode.java | 9 +- .../main/java/com/seaofnodes/simple/node/Node.java | 13 +- .../com/seaofnodes/simple/node/RegionNode.java | 11 - .../com/seaofnodes/simple/node/ReturnNode.java | 3 - .../java/com/seaofnodes/simple/node/StartNode.java | 3 - 6 files changed, 263 insertions(+), 30 deletions(-) create mode 100644 chapter01/src/main/java/com/seaofnodes/simple/Parser.java delete mode 100644 chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java (limited to 'chapter01/src/main/java/com') diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java new file mode 100644 index 00000000..bf9791a8 --- /dev/null +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -0,0 +1,254 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; + +import java.text.NumberFormat; +import java.text.ParseException; + +/** + * The Parser converts a Simple source program to the Sea of Nodes intermediate representation + * directly in one pass. There is no intermediate Abstract Syntax Tree structure. The parser also + * does the lexical analysis of the input source. + */ +public class Parser { + + private Token currentToken; + private final NodeIDGenerator _idGenerator; + private StartNode _startNode; + + public Parser() { + _idGenerator = new NodeIDGenerator(); + } + + public Node parse(String source) { + Lexer lexer = new Lexer(source); + _startNode = new StartNode(_idGenerator, new Node[0]); + nextToken(lexer); + return parseProgram(lexer); + } + + private Node parseProgram(Lexer lexer) { + parseReturnStatement(lexer); + return _startNode; + } + + private void nextToken(Lexer lexer) { + currentToken = lexer.next(); + } + + private boolean isToken(Token token, String value) { + return token._str.equals(value); + } + + private void error(Token t, String errorMessage) { + throw new RuntimeException(errorMessage + ": " + t.toString()); + } + + 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 matchIdentifier(Lexer lexer, String identifier) { + if (currentToken._kind == Token.Kind.IDENT && isToken(currentToken, identifier)) { + nextToken(lexer); + } else { + error(currentToken, "syntax error, expected " + identifier); + } + } + + private Node parsePrimary(Lexer lexer) { + switch (currentToken._kind) { + case PUNCT -> { + /* Nested expression */ + return parseNestedExpr(lexer); + } + case NUM -> { + return parseNumberConstant(lexer); + } + default -> { + error(currentToken, "syntax error, expected nested expr or integer literal"); + return null; + } + } + } + + private ConstantNode parseNumberConstant(Lexer lexer) { + var constantNode = new ConstantNode(_idGenerator, currentToken._num.longValue(), _startNode); + nextToken(lexer); + return constantNode; + } + + private Node parseNestedExpr(Lexer lexer) { + matchPunctuation(lexer, "("); + nextToken(lexer); + var node = parsePrimary(lexer); + matchPunctuation(lexer, ")"); + return node; + } + + private Node parseReturnStatement(Lexer lexer) { + matchIdentifier(lexer, "return"); + var returnExpr = parsePrimary(lexer); + matchPunctuation(lexer, ";"); + return new ReturnNode(_idGenerator, _startNode, returnExpr); + } + + 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); + + public String toString() { + return _str; + } + } + + static class Lexer { + + private final char[] _input; + /** + * Tracks current position in input buffer + */ + private int _position = 0; + private char _curCh = ' '; + + 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 nextToken() { + _curCh = advance(); + 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(_curCh)) + nextToken(); + } + + /** + * Parses number in format nnn[.nnn] + * where n is a digit + */ + private Token parseNumber() { + assert Character.isDigit(_curCh); + StringBuilder sb = new StringBuilder(); + sb.append(_curCh); + while (nextToken() && Character.isDigit(_curCh)) + sb.append(_curCh); + if (_curCh == '.') { + sb.append(_curCh); + while (nextToken() && Character.isDigit(_curCh)) + sb.append(_curCh); + } + 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 RuntimeException("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(_curCh); + StringBuilder sb = new StringBuilder(); + sb.append(_curCh); + while (nextToken() && isIdentifierLetter(_curCh)) + sb.append(_curCh); + return Token.newIdent(sb.toString()); + } + + /** + * Gets the next token + */ + public Token next() { + skipWhitespace(); + if (_curCh == 0) + return Token.EOF; + if (Character.isDigit(_curCh)) + return parseNumber(); + if (isIdentifierLetter(_curCh)) + return parseIdentifier(); + Token token = Token.newPunct(Character.toString(_curCh)); + _curCh = ' '; + return token; + } + } +} diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 7f798301..d2f51cd8 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -4,13 +4,8 @@ public class ConstantNode extends Node { long _value; - public ConstantNode(int nid, long value) { - super(nid, OP_CONSTANT); - _value = value; - } - - public ConstantNode(NodeIDGenerator idGenerator, long value) { - super(idGenerator, OP_CONSTANT); + public ConstantNode(NodeIDGenerator idGenerator, long value, StartNode startNode) { + super(idGenerator, OP_CONSTANT, startNode); _value = value; } } 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 0c6cdd3f..c3562b5d 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import java.util.ArrayList; import java.util.Arrays; import java.util.List; @@ -34,18 +35,18 @@ public class Node { */ public final List _inputs; - protected Node(int nid, byte opCode, Node ...inputs) - { - _nid = nid; - _opCode = opCode; - _inputs = Arrays.asList(inputs); - } + public final List _refs = new ArrayList<>(); protected Node(NodeIDGenerator idGenerator, byte opCode, Node ...inputs) { _nid = idGenerator.newNodeID(); _opCode = opCode; _inputs = Arrays.asList(inputs); + for (int i = 0; i < _inputs.size(); i++) { + Node n = _inputs.get(i); + if (n != null) + n._refs.add(this); + } } /** diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java deleted file mode 100644 index b740deff..00000000 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ /dev/null @@ -1,11 +0,0 @@ -package com.seaofnodes.simple.node; - -public class RegionNode extends Node implements Control { - public RegionNode(int nid, Node... inputs) { - super(nid, OP_REGION, inputs); - } - - public RegionNode(NodeIDGenerator idGenerator, Node... inputs) { - super(idGenerator, OP_REGION, inputs); - } -} 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 655fd11f..9c017eef 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,9 +1,6 @@ package com.seaofnodes.simple.node; public class ReturnNode extends Node implements Control { - public ReturnNode(int nid, Node... inputs) { - super(nid, OP_RETURN, inputs); - } public ReturnNode(NodeIDGenerator idGenerator, Node... inputs) { super(idGenerator, OP_RETURN, inputs); diff --git a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java index 8117c4f6..4ae7f71a 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,9 +1,6 @@ package com.seaofnodes.simple.node; public class StartNode extends Node implements Control { - public StartNode(int nid, Node... inputs) { - super(nid, OP_START, inputs); - } public StartNode(NodeIDGenerator idGenerator, Node... inputs) { super(idGenerator, OP_START, inputs); -- cgit v1.2.3