From b6098a9b9166da962676e33de31e93ace260d686 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Mon, 21 Aug 2023 18:00:18 +0100 Subject: Implement parser for a simple language that roughly corresponds to appendix A in Aho's 2nd edition --- .../simple/common/CompilerException.java | 11 + .../java/com/seaofnodes/simple/lexer/Lexer.java | 228 ------------------ .../java/com/seaofnodes/simple/lexer/aa/Lexer.java | 228 ++++++++++++++++++ .../java/com/seaofnodes/simple/parser/Ast.java | 132 +++++++++++ .../java/com/seaofnodes/simple/parser/Parser.java | 259 +++++++++++++++++++++ .../com/seaofnodes/simple/lexer/TestLexer.java | 14 +- .../com/seaofnodes/simple/lexer/TestParser.java | 68 ++++++ 7 files changed, 707 insertions(+), 233 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/common/CompilerException.java delete mode 100644 src/main/java/com/seaofnodes/simple/lexer/Lexer.java create mode 100644 src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Ast.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/Parser.java create mode 100644 src/test/java/com/seaofnodes/simple/lexer/TestParser.java diff --git a/src/main/java/com/seaofnodes/simple/common/CompilerException.java b/src/main/java/com/seaofnodes/simple/common/CompilerException.java new file mode 100644 index 00000000..518dcde6 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/common/CompilerException.java @@ -0,0 +1,11 @@ +package com.seaofnodes.simple.common; + +public class CompilerException extends RuntimeException { + public CompilerException(String message) { + super(message); + } + + public CompilerException(String message, Throwable cause) { + super(message, cause); + } +} diff --git a/src/main/java/com/seaofnodes/simple/lexer/Lexer.java b/src/main/java/com/seaofnodes/simple/lexer/Lexer.java deleted file mode 100644 index 06c8f28a..00000000 --- a/src/main/java/com/seaofnodes/simple/lexer/Lexer.java +++ /dev/null @@ -1,228 +0,0 @@ -/** - * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. - * - * Contributor(s): - * - * The Initial Developer of the Original Software is Cliff Click. - * - * This file is part of the Sea Of Nodes Simple Programming language - * implementation. See https://github.com/SeaOfNodes/Simple - * - * 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.lexer; - -import com.seaofnodes.util.AryInt; -import com.seaofnodes.util.SB; - -import java.text.NumberFormat; -import java.text.ParsePosition; - -public class Lexer { - private final String _srcName; // Source for error messages; usually a file name - private final byte[] _buf; - private int _x; // Parser index - private int _lastNWS; // Index of last non-white-space char - private final AryInt _lines; // char offset of each line - - private final NumberFormat _nf; - private final ParsePosition _pp; - private final String _str; - - public Lexer(String srcName, String source) - { - _srcName = srcName; - _buf = source.getBytes(); - _x = 0; - - // Set fields strictly for Java number parsing - _nf = NumberFormat.getInstance(); - _nf.setGroupingUsed(false); - _pp = new ParsePosition(0); - _str = source; // Keep a complete string copy for java number parsing - _lines = new AryInt();// - _lines.push(0); // Line 0 at offset 0 - } - - // Skip WS, return true&skip if match, false & do not skip if miss. - public boolean peek( char c ) { return peek1(skipWS(),c); } - public boolean peek_noWS( char c ) { return peek1(_x >= _buf.length ? -1 : _buf[_x],c); } - // Already skipped WS & have character; - // return true & skip if a match, false& do not skip if a miss. - public boolean peek1( byte c0, char c ) { - assert c0==-1 || c0== _buf[_x]; - if( c0!=c ) return false; - _x++; // Skip peeked character - return true; - } - // Already skipped WS & have character; - // return true&skip if match, false & do not skip if miss. - public boolean peek2( byte c0, String s2 ) { - if( c0 != s2.charAt(0) ) return false; - if( _x+1 >= _buf.length || _buf[_x+1] != s2.charAt(1) ) return false; - _x+=2; // Skip peeked characters - return true; - } - public boolean peek( String s ) { - if( !peek(s.charAt(0)) ) return false; - if( !peek_noWS(s.charAt(1)) ) { _x--; return false; } - return true; - } - // Peek 'c' and NOT followed by 'no' - public boolean peek_not( char c, char no ) { - byte c0 = skipWS(); - if( c0 != c || (_x+1 < _buf.length && _buf[_x+1] == no) ) return false; - _x++; - return true; - } - // Match any of these, and return the match or null - public String peek(String[] toks) { - for( String tok : toks ) if( peek1(tok) ) return tok; - return null; - } - public boolean peek1(String tok) { - for( int i=0; i= _buf.length || _buf[_x+i] != tok.charAt(i) ) - return false; - return true; - } - - - /** Advance parse pointer to the first non-whitespace character, and return - * that character, -1 otherwise. */ - public byte skipWS() { - int oldx = _x; - while( _x < _buf.length ) { - byte c = _buf[_x]; - if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='/' ) { skipEOL() ; continue; } - if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='*' ) { skipBlock(); continue; } - if( c=='\n' && _x+1 > _lines.last() ) _lines.push(_x+1); - if( !isWS(c) ) { - if( oldx-1 > _lastNWS && !isWS(_buf[oldx-1]) ) _lastNWS = oldx-1; - return c; - } - _x++; - } - return -1; - } - public void skipEOL () { while( _x < _buf.length && _buf[_x] != '\n' ) _x++; } - public void skipBlock() { throw new UnsupportedOperationException("Block comments not yet implemented"); } - // Advance parse pointer to next WS. Used for parser syntax error recovery. - public void skipNonWS() { - while( _x < _buf.length && !isWS(_buf[_x]) ) _x++; - } - - /** Return true if `c` passes a test */ - public static boolean isWS (byte c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; } - public static boolean isAlpha0(byte c) { return ('a'<=c && c <= 'z') || ('A'<=c && c <= 'Z') || (c=='_'); } - public static boolean isAlpha1(byte c) { return isAlpha0(c) || ('0'<=c && c <= '9'); } - public static boolean isJava (byte c) { return isAlpha1(c) || (c=='$') || (c=='.'); } - public static boolean isDigit (byte c) { return '0' <= c && c <= '9'; } - - public String token() { skipWS(); return token0(); } - // Lexical tokens. Any alpha, followed by any alphanumerics is a alpha- - // token; alpha-tokens end with WS or any operator character. Any collection - // of the classic operator characters are a token, except that they will break - // un-ambiguously. - public String token0() { - if( _x >= _buf.length ) return null; - byte c=_buf[_x]; int x = _x; - if( isOp0(c) || (c=='_' && _x+1 < _buf.length && isOp0(_buf[_x+1])) ) - while( _x < _buf.length && isOp1(_buf[_x]) ) _x++; - else if( isAlpha0(c) ) - while( _x < _buf.length && isAlpha1(_buf[_x]) ) _x++; - else return null; // Not a token; specifically excludes e.g. all bytes >= 128, or most bytes < 32 - if( (c==':' || c==',') && _x-x==1 ) // Disallow bare ':' as a token; ambiguous with ?: and type annotations; same for ',' - { _x=x; return null; } // Unwind, not a token - if( c=='-' && _x-x>2 && _buf[x+1]=='>' ) // Disallow leading "->", confusing with function parameter list end; eg "not={x->!x}" - _x=x+2; // Just return the "->" - return new String(_buf,x,_x-x); - } - public boolean isOp(String s) { - if( s==null || s.isEmpty() ) return false; - byte c = (byte)s.charAt(0); - if( !isOp0(c) && (c!='_' || !isOp0((byte)s.charAt(1))) ) return false; - for( int i=1; i^[]~/&|".indexOf(c) != -1; } - public static boolean isOp1(byte c) { return isOp0(c) || ":?_{}".indexOf(c) != -1; } - - public String errLocMsg(String s) { - if( s.charAt(0)=='\n' ) return s; - // find line start - int a=_x; - while( a > 0 && _buf[a-1] != '\n' ) --a; - if( _buf[a]=='\r' ) a++; // do not include leading \n or \n\r - // find line end - int b=_x; - while( b < _buf.length && _buf[b] != '\n' ) b++; - if( b < _buf.length ) b--; // do not include trailing \n or \n\r - // Find line number. Bin-search returns the insertion-point, which is the NEXT - // line unless _x is exactly a line start. - int line = _lines.binary_search(_x); // Find zero-based line insertion point - if( line == _lines._len || _lines.at(line)>_x ) line--; - // error message using 1-based line - SB sb = new SB().p(_srcName).p(':').p(line+1).p(':').p(s).nl(); - sb.p(new String(_buf,a,b-a)).nl(); - int line_start = a; - for( int i=line_start; i<_x; i++ ) - sb.p(' '); - return sb.p('^').nl().toString(); - } - - @Override public String toString() { return new String(_buf,_x,_buf.length-_x); } - @Override public boolean equals(Object loc) { - if( this==loc ) return true; - if( !(loc instanceof Lexer p) ) return false; - return _x==p._x && _srcName.equals(p._srcName); - } - @Override public int hashCode() { - return _srcName.hashCode()+_x; - } -} diff --git a/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java b/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java new file mode 100644 index 00000000..162cdea1 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/lexer/aa/Lexer.java @@ -0,0 +1,228 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Cliff Click. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * 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.lexer.aa; + +import com.seaofnodes.util.AryInt; +import com.seaofnodes.util.SB; + +import java.text.NumberFormat; +import java.text.ParsePosition; + +public class Lexer { + private final String _srcName; // Source for error messages; usually a file name + private final byte[] _buf; + private int _x; // Parser index + private int _lastNWS; // Index of last non-white-space char + private final AryInt _lines; // char offset of each line + + private final NumberFormat _nf; + private final ParsePosition _pp; + private final String _str; + + public Lexer(String srcName, String source) + { + _srcName = srcName; + _buf = source.getBytes(); + _x = 0; + + // Set fields strictly for Java number parsing + _nf = NumberFormat.getInstance(); + _nf.setGroupingUsed(false); + _pp = new ParsePosition(0); + _str = source; // Keep a complete string copy for java number parsing + _lines = new AryInt();// + _lines.push(0); // Line 0 at offset 0 + } + + // Skip WS, return true&skip if match, false & do not skip if miss. + public boolean peek( char c ) { return peek1(skipWS(),c); } + public boolean peek_noWS( char c ) { return peek1(_x >= _buf.length ? -1 : _buf[_x],c); } + // Already skipped WS & have character; + // return true & skip if a match, false& do not skip if a miss. + public boolean peek1( byte c0, char c ) { + assert c0==-1 || c0== _buf[_x]; + if( c0!=c ) return false; + _x++; // Skip peeked character + return true; + } + // Already skipped WS & have character; + // return true&skip if match, false & do not skip if miss. + public boolean peek2( byte c0, String s2 ) { + if( c0 != s2.charAt(0) ) return false; + if( _x+1 >= _buf.length || _buf[_x+1] != s2.charAt(1) ) return false; + _x+=2; // Skip peeked characters + return true; + } + public boolean peek( String s ) { + if( !peek(s.charAt(0)) ) return false; + if( !peek_noWS(s.charAt(1)) ) { _x--; return false; } + return true; + } + // Peek 'c' and NOT followed by 'no' + public boolean peek_not( char c, char no ) { + byte c0 = skipWS(); + if( c0 != c || (_x+1 < _buf.length && _buf[_x+1] == no) ) return false; + _x++; + return true; + } + // Match any of these, and return the match or null + public String peek(String[] toks) { + for( String tok : toks ) if( peek1(tok) ) return tok; + return null; + } + public boolean peek1(String tok) { + for( int i=0; i= _buf.length || _buf[_x+i] != tok.charAt(i) ) + return false; + return true; + } + + + /** Advance parse pointer to the first non-whitespace character, and return + * that character, -1 otherwise. */ + public byte skipWS() { + int oldx = _x; + while( _x < _buf.length ) { + byte c = _buf[_x]; + if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='/' ) { skipEOL() ; continue; } + if( c=='/' && _x+1 < _buf.length && _buf[_x+1]=='*' ) { skipBlock(); continue; } + if( c=='\n' && _x+1 > _lines.last() ) _lines.push(_x+1); + if( !isWS(c) ) { + if( oldx-1 > _lastNWS && !isWS(_buf[oldx-1]) ) _lastNWS = oldx-1; + return c; + } + _x++; + } + return -1; + } + public void skipEOL () { while( _x < _buf.length && _buf[_x] != '\n' ) _x++; } + public void skipBlock() { throw new UnsupportedOperationException("Block comments not yet implemented"); } + // Advance parse pointer to next WS. Used for parser syntax error recovery. + public void skipNonWS() { + while( _x < _buf.length && !isWS(_buf[_x]) ) _x++; + } + + /** Return true if `c` passes a test */ + public static boolean isWS (byte c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; } + public static boolean isAlpha0(byte c) { return ('a'<=c && c <= 'z') || ('A'<=c && c <= 'Z') || (c=='_'); } + public static boolean isAlpha1(byte c) { return isAlpha0(c) || ('0'<=c && c <= '9'); } + public static boolean isJava (byte c) { return isAlpha1(c) || (c=='$') || (c=='.'); } + public static boolean isDigit (byte c) { return '0' <= c && c <= '9'; } + + public String token() { skipWS(); return token0(); } + // Lexical tokens. Any alpha, followed by any alphanumerics is a alpha- + // token; alpha-tokens end with WS or any operator character. Any collection + // of the classic operator characters are a token, except that they will break + // un-ambiguously. + public String token0() { + if( _x >= _buf.length ) return null; + byte c=_buf[_x]; int x = _x; + if( isOp0(c) || (c=='_' && _x+1 < _buf.length && isOp0(_buf[_x+1])) ) + while( _x < _buf.length && isOp1(_buf[_x]) ) _x++; + else if( isAlpha0(c) ) + while( _x < _buf.length && isAlpha1(_buf[_x]) ) _x++; + else return null; // Not a token; specifically excludes e.g. all bytes >= 128, or most bytes < 32 + if( (c==':' || c==',') && _x-x==1 ) // Disallow bare ':' as a token; ambiguous with ?: and type annotations; same for ',' + { _x=x; return null; } // Unwind, not a token + if( c=='-' && _x-x>2 && _buf[x+1]=='>' ) // Disallow leading "->", confusing with function parameter list end; eg "not={x->!x}" + _x=x+2; // Just return the "->" + return new String(_buf,x,_x-x); + } + public boolean isOp(String s) { + if( s==null || s.isEmpty() ) return false; + byte c = (byte)s.charAt(0); + if( !isOp0(c) && (c!='_' || !isOp0((byte)s.charAt(1))) ) return false; + for( int i=1; i^[]~/&|".indexOf(c) != -1; } + public static boolean isOp1(byte c) { return isOp0(c) || ":?_{}".indexOf(c) != -1; } + + public String errLocMsg(String s) { + if( s.charAt(0)=='\n' ) return s; + // find line start + int a=_x; + while( a > 0 && _buf[a-1] != '\n' ) --a; + if( _buf[a]=='\r' ) a++; // do not include leading \n or \n\r + // find line end + int b=_x; + while( b < _buf.length && _buf[b] != '\n' ) b++; + if( b < _buf.length ) b--; // do not include trailing \n or \n\r + // Find line number. Bin-search returns the insertion-point, which is the NEXT + // line unless _x is exactly a line start. + int line = _lines.binary_search(_x); // Find zero-based line insertion point + if( line == _lines._len || _lines.at(line)>_x ) line--; + // error message using 1-based line + SB sb = new SB().p(_srcName).p(':').p(line+1).p(':').p(s).nl(); + sb.p(new String(_buf,a,b-a)).nl(); + int line_start = a; + for( int i=line_start; i<_x; i++ ) + sb.p(' '); + return sb.p('^').nl().toString(); + } + + @Override public String toString() { return new String(_buf,_x,_buf.length-_x); } + @Override public boolean equals(Object loc) { + if( this==loc ) return true; + if( !(loc instanceof Lexer p) ) return false; + return _x==p._x && _srcName.equals(p._srcName); + } + @Override public int hashCode() { + return _srcName.hashCode()+_x; + } +} diff --git a/src/main/java/com/seaofnodes/simple/parser/Ast.java b/src/main/java/com/seaofnodes/simple/parser/Ast.java new file mode 100644 index 00000000..a93b230f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/parser/Ast.java @@ -0,0 +1,132 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.common.CompilerException; +import com.seaofnodes.simple.lexer.ecstasy.Token; + +import java.util.ArrayList; +import java.util.List; + +public abstract class Ast { + + public static class Node { + } + + public static class Expr extends Node { + public final Token op; + + public Expr(Token op) { + this.op = op; + } + } + + public static class Identifier extends Expr { + public final String name; + public Identifier(Token op) { + super(op); + name = op.getValueText(); + } + } + + public static class Symbol extends Expr { + public final String name; + public Symbol(Token op) { + super(op); + name = op.getValueText(); + } + } + + public static class Binary extends Expr { + public final Expr expr1, expr2; + + public Binary(Token op, Expr expr1, Expr expr2) { + super(op); + this.expr1 = expr1; + this.expr2 = expr2; + } + } + + public static class Unary extends Expr { + public final Expr expr; + + public Unary(Token op, Expr expr) { + super(op); + this.expr = expr; + } + } + + public static class Constant extends Expr { + public Constant(Token op) { + super(op); + } + } + + public static class Statement extends Node { + } + + public static class IfElse extends Statement { + public final Expr expr; + public final Statement ifStmt, elseStmt; + + public IfElse(Expr expr, Statement ifStmt, Statement elseStmt) { + this.expr = expr; + this.ifStmt = ifStmt; + this.elseStmt = elseStmt; + } + } + + public static class While extends Statement { + public Expr expr; + public Statement stmt; + + public While() { + } + public void init(Expr expr, Statement stmt) { + this.expr = expr; + this.stmt = stmt; + } + } + + public static class Break extends Statement { + public final Statement stmt; + + public Break(Statement stmt) { + if (stmt == null) + { + throw new CompilerException("uneclosed break"); + } + this.stmt = stmt; + } + } + + public static class Assign extends Statement { + public final Identifier identifier; + public final Expr expr; + + public Assign(Identifier identifier, Expr expr) { + this.identifier = identifier; + this.expr = expr; + } + } + + public static class Type extends Node { + public final Token.Id typeId; + + public Type(Token.Id typeId) { + this.typeId = typeId; + } + } + + public static class Declare extends Statement { + public final Type type; + public final Identifier identifier; + + public Declare(Type type, Identifier identifier) { + this.type = type; + this.identifier = identifier; + } + } + + public static class Block extends Statement { + public final List stmtList = new ArrayList<>(); + } +} diff --git a/src/main/java/com/seaofnodes/simple/parser/Parser.java b/src/main/java/com/seaofnodes/simple/parser/Parser.java new file mode 100644 index 00000000..f7b29f40 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/parser/Parser.java @@ -0,0 +1,259 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * The Initial Developer of the Original Software is Dibyendu Majumdar. + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * 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 com.seaofnodes.simple.common.CompilerException; +import com.seaofnodes.simple.lexer.ecstasy.Lexer; +import com.seaofnodes.simple.lexer.ecstasy.Token; +import com.seaofnodes.util.Severity; + +public class Parser { + final Lexer lexer; + Token look; + Ast.Statement statementEnclosing; + + public Parser(Lexer lexer) { + this.lexer = lexer; + } + + Token nextOrEof() { + if (lexer.hasNext()) + return lexer.next(); + return new Token(look.getStartPosition(), look.getEndPosition(), Token.Id.EOF); + } + + void nextToken() { + look = nextOrEof(); + while (look.isComment()) { + look = nextOrEof(); + } + if (look.isContextSensitive() && + look.getId() == Token.Id.IDENTIFIER) { + look = look.convertToKeyword(); + } + } + + void error(Token t, String errorMessage) { + lexer.log(Severity.ERROR, errorMessage, t.getStartPosition(), t.getEndPosition()); + throw new CompilerException(errorMessage + ": " + t.toDebugString()); + } + + void match(Token.Id tag) { + if (look.getId() == tag) { + nextToken(); + } else { + error(look, "syntax error, expected " + tag); + } + } + + public Ast.Node parse() { + nextToken(); + return parseProgram(); + } + + Ast.Statement parseProgram() { + var block = new Ast.Block(); + parseDeclarations(block); + parseStatements(block); + return block; + } + + void parseDeclarations(Ast.Block block) { + while (look.getId() == Token.Id.VAR) { + nextToken(); + var tok = look; + match(Token.Id.IDENTIFIER); + match(Token.Id.COLON); + var type = parseType(); + match(Token.Id.SEMICOLON); + var identifier = new Ast.Identifier(tok); + block.stmtList.add(new Ast.Declare(type, identifier)); + } + } + + Ast.Type parseType() { + if (look.getId() == Token.Id.LIT_INTA) { + nextToken(); + return new Ast.Type(look.getId()); + } + error(look, "syntax error: unsupported type (at present only Int type is allowed)"); + return null; + } + + void parseStatements(Ast.Block block) { + while (look.getId() != Token.Id.EOF && + look.getId() != Token.Id.R_CURLY) { + block.stmtList.add(parseStatement()); + } + } + + Ast.Statement parseStatement() { + Ast.Expr x; + Ast.Statement s1; + Ast.Statement s2; + + switch (look.getId()) { + case IF -> { + match(Token.Id.IF); + match(Token.Id.L_PAREN); + x = parseBool(); + match(Token.Id.R_PAREN); + s1 = parseStatement(); + if (look.getId() != Token.Id.ELSE) { + return new Ast.IfElse(x, s1, null); + } + s2 = parseStatement(); + return new Ast.IfElse(x, s1, s2); + } + case WHILE -> { + var whilenode = new Ast.While(); + var savedStmt = statementEnclosing; + statementEnclosing = whilenode; + match(Token.Id.WHILE); + match(Token.Id.L_PAREN); + x = parseBool(); + match(Token.Id.R_PAREN); + s1 = parseStatement(); + whilenode.init(x, s1); + statementEnclosing = savedStmt; + return whilenode; + } + case BREAK -> { + match(Token.Id.BREAK); + match(Token.Id.SEMICOLON); + return new Ast.Break(statementEnclosing); + } + case L_CURLY -> { + return parseBlock(); + } + default -> { + return parseAssign(); + } + } + } + + Ast.Statement parseBlock() { + match(Token.Id.L_CURLY); + var block = new Ast.Block(); + parseDeclarations(block); + parseStatements(block); + match(Token.Id.R_CURLY); + return block; + } + + Ast.Statement parseAssign() { + match(Token.Id.IDENTIFIER); + Ast.Identifier identifier = new Ast.Identifier(look); + match(Token.Id.ASN); + var s = new Ast.Assign(identifier, parseBool()); + match(Token.Id.SEMICOLON); + return s; + } + + Ast.Expr parseBool() { + var x = parseAnd(); + while (look.getId() == Token.Id.COND_OR) { + var tok = look; + nextToken(); + x = new Ast.Binary(tok, x, parseAnd()); + } + return x; + } + + Ast.Expr parseAnd() { + var x = parseRelational(); + while (look.getId() == Token.Id.COND_AND) { + var tok = look; + nextToken(); + x = new Ast.Binary(tok, x, parseRelational()); + } + return x; + } + + Ast.Expr parseRelational() { + var x = parseAddition(); + while (look.getId() == Token.Id.COMP_EQ || + look.getId() == Token.Id.COMP_NEQ || + look.getId() == Token.Id.COMP_LT || + look.getId() == Token.Id.COMP_GT || + look.getId() == Token.Id.COMP_GTEQ || + look.getId() == Token.Id.COMP_LTEQ) { + var tok = look; + nextToken(); + x = new Ast.Binary(tok, x, parseAddition()); + } + return x; + } + + Ast.Expr parseAddition() { + var x = parseMultiplication(); + while (look.getId() == Token.Id.ADD || + look.getId() == Token.Id.SUB) { + var tok = look; + nextToken(); + x = new Ast.Binary(tok, x, parseMultiplication()); + } + return x; + } + + Ast.Expr parseMultiplication() { + var x = parseUnary(); + while (look.getId() == Token.Id.MUL || + look.getId() == Token.Id.DIV) { + var tok = look; + nextToken(); + x = new Ast.Binary(tok, x, parseUnary()); + } + return x; + } + + Ast.Expr parseUnary() { + if (look.getId() == Token.Id.SUB || + look.getId() == Token.Id.NOT) { + var tok = look; + nextToken(); + return new Ast.Unary(tok, parseUnary()); + } else { + return parsePrimary(); + } + } + + Ast.Expr parsePrimary() { + switch (look.getId()) { + case L_PAREN -> { + nextToken(); + var x = parseBool(); + match(Token.Id.R_PAREN); + return x; + } + case LIT_INT -> { + var x = new Ast.Constant(look); + nextToken(); + return x; + } + case IDENTIFIER -> { + var x = new Ast.Symbol(look); + nextToken(); + return x; + } + default -> { + error(look, "syntax error, expected nested expr, integer value or variable"); + return null; + } + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java b/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java index 335bcf5e..18a4634d 100644 --- a/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java +++ b/src/test/java/com/seaofnodes/simple/lexer/TestLexer.java @@ -3,8 +3,6 @@ * * Contributor(s): * - * The Initial Developer of the Original Software is Cliff Click. - * * This file is part of the Sea Of Nodes Simple Programming language * implementation. See https://github.com/SeaOfNodes/Simple * @@ -17,6 +15,10 @@ package com.seaofnodes.simple.lexer; +import com.seaofnodes.simple.common.ErrorListener; +import com.seaofnodes.simple.lexer.ecstasy.Lexer; +import com.seaofnodes.simple.lexer.ecstasy.Source; +import com.seaofnodes.simple.lexer.ecstasy.Token; import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; @@ -26,8 +28,10 @@ public class TestLexer { public void testLexLineComment() { final String source = "//a comment\nx"; - Lexer lexer = new Lexer("test", source); - String token = lexer.token(); - Assertions.assertEquals("x", token); + Lexer lexer = new Lexer(new Source(source), new ErrorListener()); + Token token = lexer.next(); + Assertions.assertEquals(token.getId(), Token.Id.EOL_COMMENT); + token = lexer.next(); + Assertions.assertEquals("x", token.getValueText()); } } diff --git a/src/test/java/com/seaofnodes/simple/lexer/TestParser.java b/src/test/java/com/seaofnodes/simple/lexer/TestParser.java new file mode 100644 index 00000000..7d2f3752 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/lexer/TestParser.java @@ -0,0 +1,68 @@ +/** + * DO NOT REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Contributor(s): + * + * This file is part of the Sea Of Nodes Simple Programming language + * implementation. See https://github.com/SeaOfNodes/Simple + * + * 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.lexer; + +import com.seaofnodes.simple.common.ErrorListener; +import com.seaofnodes.simple.lexer.ecstasy.Lexer; +import com.seaofnodes.simple.lexer.ecstasy.Source; +import com.seaofnodes.simple.parser.Ast; +import com.seaofnodes.simple.parser.Parser; +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.Test; + +public class TestParser { + + @Test + public void testParseSingleDecl() + { + final String source = "var i: Int;"; + Lexer lexer = new Lexer(new Source(source), new ErrorListener()); + Parser parser = new Parser(lexer); + var ast = parser.parse(); + Assertions.assertTrue(ast instanceof Ast.Block + && ((Ast.Block) ast).stmtList.size() == 1); + } + + @Test + public void testParseTwoDecls() { + final String source = "var i: Int;\nvar j: Int;"; + Lexer lexer = new Lexer(new Source(source), new ErrorListener()); + Parser parser = new Parser(lexer); + var ast = parser.parse(); + Assertions.assertTrue(ast instanceof Ast.Block + && ((Ast.Block) ast).stmtList.size() == 2); + } + + @Test + public void testIfAndWhile() { + final String source = + """ + var i: Int; + var j: Int; + + i = 0; + j = 100; + while ( 1 ) { + i = i + 1; + j = j - 1; + if ( i >= j ) break; + } + """; + Lexer lexer = new Lexer(new Source(source), new ErrorListener()); + Parser parser = new Parser(lexer); + var ast = parser.parse(); + } +} -- cgit v1.2.3