Created
February 25, 2022 03:17
-
-
Save gszauer/50afae03180679fb06602b0b37c8e59a to your computer and use it in GitHub Desktop.
RecursiveDescentParser
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace ExpressionParser { | |
class ASTNode { | |
} | |
abstract class Statement : ASTNode { | |
public abstract Object Execute(Environment env); | |
} | |
abstract class Expression : ASTNode { | |
public abstract double Evaluate(Environment env); | |
} | |
class VarDeclStatement : Statement { | |
public string Name; | |
public Expression Initializer; | |
public VarDeclStatement(string name, Expression initializer) { | |
Name = name; | |
Initializer = initializer; | |
} | |
public override Object Execute(Environment env) { | |
double initialValue = 0.0; | |
if (Initializer != null) { | |
initialValue = Initializer.Evaluate(env); | |
} | |
env.Declare(Name, initialValue); | |
return null; | |
} | |
} | |
class ExpressionStatement : Statement { | |
public Expression Expression; | |
public ExpressionStatement(Expression expression) { | |
Expression = expression; | |
} | |
public override Object Execute(Environment env) { | |
Expression.Evaluate(env); | |
return null; | |
} | |
} | |
class BlockStatement : Statement { | |
public List<Statement> Statements; | |
public BlockStatement(List<Statement> statements) { | |
Statements = statements; | |
} | |
public override Object Execute(Environment env) { | |
Environment local = new Environment(env); | |
foreach (Statement statement in Statements) { | |
Object result = statement.Execute(local); | |
if (result != null) { | |
return result; | |
} | |
} | |
return null; | |
} | |
} | |
class PrintStatement : Statement { | |
public Expression Expression; | |
public PrintStatement(Expression expression) { | |
Expression = expression; | |
} | |
public override Object Execute(Environment env) { | |
if (Expression != null) { | |
Console.WriteLine(Expression.Evaluate(env)); | |
} | |
else { | |
Console.WriteLine(); | |
} | |
return null; | |
} | |
} | |
class IfStatement : Statement { | |
public Expression Condition; | |
public Statement True; | |
public Statement False; | |
public IfStatement(Expression condition, Statement _true, Statement _false) { | |
Condition = condition; | |
True = _true; | |
False = _false; | |
} | |
public override Object Execute(Environment env) { | |
double cond = Condition.Evaluate(env); | |
Object result = null; | |
if (cond != 0) { | |
result = True.Execute(env); | |
} | |
else if (False != null) { | |
result = False.Execute(env); | |
} | |
return result; | |
} | |
} | |
class ReturnStatement : Statement { | |
Expression Result; | |
public ReturnStatement(Expression result) { | |
Result = result; | |
} | |
public override Object Execute(Environment env) { | |
if (Result == null) { | |
return 0.0; | |
} | |
return Result.Evaluate(env); | |
} | |
} | |
class FunctionDeclStatement : Statement { | |
public string Name; | |
public List<String> Args; | |
public List<Statement> Body; | |
public FunctionDeclStatement(string name, List<Token> args, BlockStatement body) { | |
Name = name; | |
Args = new List<string>(); | |
foreach (Token token in args) { | |
Args.Add(token.Lexeme); | |
} | |
Body = body.Statements; | |
} | |
public override Object Execute(Environment env) { | |
UserFnction funcInstance = new UserFnction(Name, Args, Body); | |
env.Declare(Name, funcInstance); | |
return null; | |
} | |
} | |
class WhileStatement : Statement { | |
public Expression Condition; | |
public Statement Body; | |
public WhileStatement(Expression condition, Statement body) { | |
Condition=condition; | |
Body = body; | |
} | |
public override Object Execute(Environment env) { | |
while (Condition.Evaluate(env) != 0) { | |
Object result = Body.Execute(env); | |
if (result != null) { | |
return result; | |
} | |
} | |
return null; | |
} | |
} | |
class CallExpression : Expression { | |
public string Name; | |
public List<Expression> Args; | |
public CallExpression(string name, List<Expression> args) { | |
Name = name; | |
Args = args; | |
} | |
public override double Evaluate(Environment env) { | |
Object callee = env.Get(Name); | |
if (!(callee is FunctionImpl)) { | |
throw new Exception("Function calee is not a callable function"); | |
} | |
FunctionImpl func = (FunctionImpl)callee; | |
Environment executionEnv = new Environment(env); | |
return func.Execute(executionEnv, Args); | |
} | |
} | |
class LiteralExpression : Expression { | |
public double Value; | |
public LiteralExpression(double value) { | |
Value = value; | |
} | |
public override double Evaluate(Environment env) { | |
return Value; | |
} | |
} | |
class AssignmentExpression : Expression { | |
public string Name; | |
public Expression Value; | |
public AssignmentExpression(string name, Expression value) { | |
Name = name; | |
Value = value; | |
} | |
public override double Evaluate(Environment env) { | |
double val = Value.Evaluate(env); | |
env.Set(Name, val); | |
return val; | |
} | |
} | |
class UnaryExpression : Expression { | |
public Expression Right; | |
public Token Operator; | |
public UnaryExpression(Token op, Expression right) { | |
Right = right; | |
Operator = op; | |
} | |
public override double Evaluate(Environment env) { | |
if (Operator.Type == TokenType.MINUS) { | |
return -1.0f * Right.Evaluate(env); | |
} | |
throw new Exception("Can't evaluate unary expression"); | |
} | |
} | |
class BinaryExpression : Expression { | |
public Expression Left; | |
public Expression Right; | |
public Token Operator; | |
public BinaryExpression(Expression left, Token op, Expression right) { | |
Left = left; | |
Right = right; | |
Operator = op; | |
} | |
public override double Evaluate(Environment env) { | |
switch (Operator.Type) { | |
case TokenType.PLUS: | |
return Left.Evaluate(env) + Right.Evaluate(env); | |
case TokenType.MINUS: | |
return Left.Evaluate(env) - Right.Evaluate(env); | |
case TokenType.STAR: | |
return Left.Evaluate(env) * Right.Evaluate(env); | |
case TokenType.SLASH: | |
return Left.Evaluate(env) / Right.Evaluate(env); | |
case TokenType.POW: | |
return Math.Pow(Left.Evaluate(env), Right.Evaluate(env)); | |
case TokenType.EQUAL_EQUAL: | |
return (Left.Evaluate(env) == Right.Evaluate(env))? 1.0 : 0.0; | |
case TokenType.NOT_EQUAL: | |
return (Left.Evaluate(env) != Right.Evaluate(env)) ? 1.0 : 0.0; | |
case TokenType.LESS: | |
return (Left.Evaluate(env) < Right.Evaluate(env)) ? 1.0 : 0.0; | |
case TokenType.LESS_EQUAL: | |
return (Left.Evaluate(env) <= Right.Evaluate(env)) ? 1.0 : 0.0; | |
case TokenType.GREATER: | |
return (Left.Evaluate(env) > Right.Evaluate(env)) ? 1.0 : 0.0; | |
case TokenType.GREATER_EQUAL: | |
return (Left.Evaluate(env) >= Right.Evaluate(env)) ? 1.0 : 0.0; | |
} | |
throw new Exception("Invalid binary expression"); | |
} | |
} | |
class VariableExpression : Expression { | |
public string Name; | |
public VariableExpression(string name) { | |
Name = name; | |
} | |
public override double Evaluate(Environment env) { | |
Object result = env.Get(Name); | |
if (!(result is double)) { | |
throw new Exception("Variable expression evaluates to not double"); | |
} | |
return (double)result; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace ExpressionParser { | |
class Environment { | |
Dictionary<string, Object> Variables; | |
Environment Parent; | |
public Environment(Environment parent) { | |
Parent = parent; | |
Variables = new Dictionary<string, Object>(); | |
} | |
public void Declare(string name, Object val) { | |
if (Variables.ContainsKey(name)) { | |
throw new Exception("Variable re-declaration: " + name); | |
} | |
Variables[name] = val; | |
} | |
public Object Get(string name) { | |
if (!Variables.ContainsKey(name)) { | |
if (Parent != null) { | |
return Parent.Get(name); | |
} | |
throw new Exception("Accessing undeclared variable: " + name); | |
} | |
return Variables[name]; | |
} | |
public void Set(string name, double val) { | |
if (!Variables.ContainsKey(name)) { | |
if (Parent != null) { | |
Parent.Set(name, val); | |
return; | |
} | |
throw new Exception("Accessing undeclared variable: " + name); | |
} | |
Variables[name] = val; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace ExpressionParser { | |
abstract class FunctionImpl { | |
public abstract int Arity(); | |
public abstract double Execute(Environment env, List<Expression> args); | |
} | |
class SqrtNative : FunctionImpl { | |
public override int Arity() { | |
return 1; | |
} | |
public override double Execute(Environment env, List<Expression> args) { | |
if (1 != args.Count) { | |
throw new Exception("Calling SqrtNative with wrong number of arguments"); | |
} | |
double num = args[0].Evaluate(env); | |
return Math.Sqrt(num); | |
} | |
} | |
class UserFnction : FunctionImpl { | |
public string Name; | |
public List<String> Args; | |
public List<Statement> Body; | |
public UserFnction(string name, List<string> args, List<Statement> body) { | |
Name = name; | |
Args = args; | |
Body = body; | |
} | |
public override int Arity() { | |
return Args.Count; | |
} | |
public override double Execute(Environment env, List<Expression> args) { | |
if (Args.Count != args.Count) { | |
throw new Exception("Calling " + Name + " with wrong number of arguments"); | |
} | |
for (int i = 0; i < Args.Count; ++i) { | |
env.Declare(Args[i], args[i].Evaluate(env)); | |
} | |
foreach (Statement s in Body) { | |
Object result = s.Execute(env); | |
if (result != null) { | |
if (!(result is double)) { | |
throw new Exception("Wrong return type"); | |
} | |
return (double)result; | |
} | |
} | |
return 0.0; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
// program -> topLevelDeclaration* EOF; | |
// topLevelDeclaration = "fun" IDENTIFIER "(" paramaters? ")" blockStatement | declaration; | |
// declaration -> varDeclaration | statement; | |
// varDeclaration -> var IDENTIFIER (= expression )? ";"; | |
// statement -> exprStatement | blockStatement | printStatement | ifStatement | whileStatement | returnStatement; | |
// exprStatement -> expression ";"; | |
// blockStatement -> "{" declaration* "}"; | |
// printStatement -> "print" "(" expression ")" ";"; | |
// ifStatement -> "if" "(" expression ")" statement ("else" statement)?; | |
// whileStatement -> "while" "(" expression ")" statement; | |
// returnStatement -> "return" expression? ";"; | |
// expression -> assignment; | |
// assignment -> IDENTIFIER "=" expression | equality; | |
// equality -> comparison (("==" | "!=") comparison)*; | |
// comparison -> term ((">=" | ">" | "<=" | "<") term)*; | |
// term -> factor (("+" | "-") factor)*; | |
// factor -> power (("*" | "/") power)*; | |
// power -> unary ("^" power)*; | |
// unary -> ("-")? unary | call; | |
// call -> IDENTIFIER ( "(" arguments? ")" )* | primary; | |
// primary -> NUMBER | "(" expression ")" | IDENTIFIER; | |
// arguments -> expression ("," expression)*; | |
// paramaters -> IDENTIFIER ("," IDENTIFIER)*; | |
namespace ExpressionParser { | |
class Parser { | |
public List<Statement> Statements; | |
private List<Token> Tokens; | |
private int CurrentToken; | |
public Parser(List<Token> tokens) { | |
Statements = new List<Statement>(); | |
Tokens = tokens; | |
CurrentToken = 0; | |
while (Current().Type != TokenType.EOF) { | |
Statements.Add(ParseTopLevelDeclaration()); | |
} | |
Tokens = null; | |
} | |
Token Current() { | |
if (CurrentToken < Tokens.Count) { | |
return Tokens[CurrentToken]; | |
} | |
return Tokens[Tokens.Count - 1]; | |
} | |
Statement ParseTopLevelDeclaration() { | |
if (Current().Type == TokenType.FUN) { | |
CurrentToken++; | |
if (Current().Type != TokenType.IDENTIFIER) { | |
throw new Exception("Function name must be identifier"); | |
} | |
Token name = Current(); | |
CurrentToken++; | |
if (Current().Type != TokenType.LPAREN) { | |
throw new Exception("Missing ( after function name"); | |
} | |
CurrentToken++; | |
List<Token> paramaters = ParseParamaters(); | |
if (Current().Type != TokenType.RPAREN) { | |
throw new Exception("Missing ( after function name"); | |
} | |
CurrentToken++; | |
BlockStatement body = (BlockStatement)ParseBlockStatement(); | |
return new FunctionDeclStatement(name.Lexeme, paramaters, body); | |
} | |
return ParseDeclaration(); | |
} | |
List<Token> ParseParamaters() { | |
List<Token> result = new List<Token>(); | |
while (Current().Type != TokenType.RPAREN) { | |
if (Current().Type == TokenType.IDENTIFIER) { | |
result.Add(Current()); | |
} | |
else { | |
throw new Exception("function paramater needs to be an identifier"); | |
} | |
CurrentToken++; | |
if (Current().Type == TokenType.COMMA) { | |
CurrentToken++; | |
} | |
else if (Current().Type != TokenType.RPAREN) { | |
throw new Exception("Unexpected token in paramater list"); | |
} | |
} | |
return result; | |
} | |
Statement ParseDeclaration() { | |
if (Current().Type == TokenType.VAR) { | |
return ParseVariableDeclaration(); | |
} | |
return ParseStatement(); | |
} | |
Statement ParseVariableDeclaration() { | |
if (Current().Type != TokenType.VAR) { | |
throw new Exception("Variable declaration should start with var keyword"); | |
} | |
CurrentToken++; | |
if (Current().Type != TokenType.IDENTIFIER) { | |
throw new Exception("Missing identifier in variable declaration"); | |
} | |
string name = Current().Lexeme; | |
Expression initializer = null; | |
CurrentToken++; | |
if (Current().Type == TokenType.EQUAL) { | |
CurrentToken++; | |
initializer = ParseExpression(); | |
} | |
if (Current().Type != TokenType.SEMICOLON) { | |
throw new Exception("Variable declaration must end with semicolor"); | |
} | |
CurrentToken++; | |
return new VarDeclStatement(name, initializer); | |
} | |
Statement ParseStatement() { | |
if (Current().Type == TokenType.PRINT) { | |
return ParsePrintStatement(); | |
} | |
else if (Current().Type == TokenType.LBRACE) { | |
return ParseBlockStatement(); | |
} | |
else if (Current().Type == TokenType.IF) { | |
return ParseIfStatement(); | |
} | |
else if (Current().Type == TokenType.WHILE) { | |
return ParseWhileStatement(); | |
} | |
else if (Current().Type == TokenType.RETURN) { | |
return ParseReturnStatement(); | |
} | |
return ParseExpressionStatement(); | |
} | |
Statement ParseReturnStatement() { | |
CurrentToken++; // Eat return | |
Expression result = null; | |
if (Current().Type != TokenType.SEMICOLON) { | |
result = ParseExpression(); | |
} | |
if (Current().Type != TokenType.SEMICOLON) { | |
throw new Exception("Return statement should end in semicolon"); | |
} | |
CurrentToken++; // Eat ; | |
return new ReturnStatement(result); | |
} | |
Statement ParseWhileStatement() { | |
CurrentToken++; // Eat while | |
if (Current().Type != TokenType.LPAREN) { | |
throw new Exception("while statement missing opening paren"); | |
} | |
CurrentToken++; | |
Expression cond = ParseExpression(); | |
if (Current().Type != TokenType.RPAREN) { | |
throw new Exception("while statement missing closing paren"); | |
} | |
CurrentToken++; | |
Statement body = ParseStatement(); | |
return new WhileStatement(cond, body); | |
} | |
Statement ParseIfStatement() { | |
CurrentToken++; // Eat if | |
if (Current().Type != TokenType.LPAREN) { | |
throw new Exception("If statement missing opening paren"); | |
} | |
CurrentToken++; | |
Expression cond = ParseExpression(); | |
if (Current().Type != TokenType.RPAREN) { | |
throw new Exception("If statement missing closing paren"); | |
} | |
CurrentToken++; | |
Statement t = ParseStatement(); | |
Statement f = null; | |
if (Current().Type == TokenType.ELSE) { | |
CurrentToken++; | |
f = ParseStatement(); | |
} | |
return new IfStatement(cond, t, f); | |
} | |
Statement ParsePrintStatement() { | |
if (Current().Type != TokenType.PRINT) { | |
throw new Exception("Print statement should start with print keyword"); | |
} | |
CurrentToken++; | |
if (Current().Type != TokenType.LPAREN) { | |
throw new Exception("Print statement needs parenthesized paramaters"); | |
} | |
CurrentToken++; | |
Expression expression = null; | |
if (Current().Type != TokenType.RPAREN) { | |
expression = ParseExpression(); | |
} | |
if (Current().Type != TokenType.RPAREN) { | |
throw new Exception("Missing right paren for print statement"); | |
} | |
CurrentToken++; | |
Token dbg = Current(); | |
if (Current().Type != TokenType.SEMICOLON) { | |
throw new Exception("Print statement needs to end with ;"); | |
} | |
CurrentToken++; | |
return new PrintStatement(expression); | |
} | |
Statement ParseExpressionStatement() { | |
Expression expression = ParseExpression(); | |
if (Current().Type != TokenType.SEMICOLON) { | |
throw new Exception("Expression statement needs to end with ;"); | |
} | |
CurrentToken++; | |
return new ExpressionStatement(expression); | |
} | |
Statement ParseBlockStatement() { | |
if (Current().Type != TokenType.LBRACE) { | |
throw new Exception("Block statement needs to start with left brace"); | |
} | |
CurrentToken++; | |
List<Statement> result = new List<Statement>(); | |
while (Current().Type != TokenType.RBRACE) { | |
result.Add(ParseDeclaration()); | |
} | |
if (Current().Type != TokenType.RBRACE) { | |
throw new Exception("Block statement needs to end with right brace"); | |
} | |
CurrentToken++; | |
return new BlockStatement(result); | |
} | |
Expression ParseExpression() { | |
return ParseAssignment(); | |
} | |
Expression ParseAssignment() { | |
Expression left = ParseEquality(); | |
if (Current().Type == TokenType.EQUAL) { | |
CurrentToken++; // Eat = | |
Expression value = ParseExpression(); | |
if (left is VariableExpression) { | |
VariableExpression variable = (VariableExpression)left; | |
return new AssignmentExpression(variable.Name, value); | |
} | |
throw new Exception("Left side of assignment must be a variable"); | |
} | |
return left; | |
} | |
Expression ParseEquality() { | |
Expression left = ParseComparison(); | |
while (Current().Type == TokenType.EQUAL_EQUAL || | |
Current().Type == TokenType.NOT_EQUAL) { | |
Token op = Current(); | |
CurrentToken++; | |
Expression right = ParseComparison(); | |
left = new BinaryExpression(left, op, right); | |
} | |
return left; | |
} | |
Expression ParseComparison() { | |
Expression left = ParseTerm(); | |
while (Current().Type == TokenType.GREATER || | |
Current().Type == TokenType.GREATER_EQUAL || | |
Current().Type == TokenType.LESS || | |
Current().Type == TokenType.LESS_EQUAL) { | |
Token op = Current(); | |
CurrentToken++; | |
Expression right = ParseTerm(); | |
left = new BinaryExpression(left, op, right); | |
} | |
return left; | |
} | |
Expression ParseTerm() { | |
Expression left = ParseFactor(); | |
Token _operator = Current(); | |
while (_operator.Type == TokenType.PLUS || | |
_operator.Type == TokenType.MINUS) { | |
CurrentToken++; | |
Expression right = ParseFactor(); | |
left = new BinaryExpression(left, _operator, right); | |
_operator = Current(); | |
} | |
return left; | |
} | |
Expression ParseFactor() { | |
Expression left = ParsePower(); | |
Token _operator = Current(); | |
while (_operator.Type == TokenType.STAR || | |
_operator.Type == TokenType.SLASH) { | |
CurrentToken++; | |
Expression right = ParsePower(); | |
left = new BinaryExpression(left, _operator, right); | |
_operator = Current(); | |
} | |
return left; | |
} | |
Expression ParsePower() { | |
Expression left = ParseUnary(); | |
Token _operator = Current(); | |
if (_operator.Type == TokenType.POW) { | |
CurrentToken++; | |
Expression right = ParsePower(); | |
left = new BinaryExpression(left, _operator, right); | |
} | |
return left; | |
} | |
Expression ParseUnary() { | |
if (Current().Type == TokenType.MINUS) { | |
Token _operator = Current(); | |
CurrentToken++; | |
Expression right = ParseUnary(); | |
return new UnaryExpression(_operator, right); | |
} | |
return ParseCall(); | |
} | |
Expression ParseCall() { | |
if (Current().Type == TokenType.IDENTIFIER) { | |
Token identifier = Current(); | |
CurrentToken++; | |
if (Current().Type == TokenType.LPAREN) { | |
CurrentToken++; | |
List<Expression> args = ParseArguments(); | |
if (Current().Type != TokenType.RPAREN) { | |
throw new Exception("Function call missing closing parenthesis"); | |
} | |
CurrentToken++; | |
return new CallExpression(identifier.Lexeme, args); | |
} | |
else { | |
CurrentToken--; // Roll back and parse primary | |
} | |
} | |
return ParsePrimary(); | |
} | |
List<Expression> ParseArguments() { | |
List<Expression> result = new List<Expression>(); | |
while (Current().Type != TokenType.RPAREN) { | |
result.Add(ParseExpression()); | |
if (Current().Type == TokenType.COMMA) { | |
CurrentToken++; | |
} | |
else if (Current().Type != TokenType.RPAREN) { | |
throw new Exception("Unexpected token in argument list"); | |
} | |
} | |
return result; | |
} | |
Expression ParsePrimary() { | |
Token current = Current(); | |
if (current.Type == TokenType.LPAREN) { | |
CurrentToken++; | |
Expression expr = ParseExpression(); | |
if (Current().Type != TokenType.RPAREN) { | |
throw new Exception("Expected right paren to close expression"); | |
} | |
CurrentToken++; | |
return expr; | |
} | |
else if (current.Type == TokenType.NUMBER) { | |
double value = current.Value; | |
CurrentToken++; | |
return new LiteralExpression(value); | |
} | |
else if (current.Type == TokenType.IDENTIFIER) { | |
string name = current.Lexeme; | |
CurrentToken++; | |
return new VariableExpression(name); | |
} | |
throw new Exception("Syntax Error"); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// expression -> term (("+" | "-") term)*; | |
// term -> power (("*" | "/") power)*; | |
// power -> unary ("^" power)*; | |
// unary -> ("-")? unary | factor; | |
// factor -> NUMBER | "(" expression ")"; | |
using ExpressionParser; | |
class Program { | |
public static void Main(String[] args) { | |
//Program p = new Program("--3"); | |
Console.WriteLine("Scanner test:"); | |
Scanner debugScanner = new Scanner(File.ReadAllText("../../../tests/math_script.txt")); | |
/*foreach (Token token in debugScanner.Tokens) { | |
Console.WriteLine(token.ToString()); | |
}*/ | |
Parser debugParserarser = new Parser(debugScanner.Tokens); | |
ExpressionParser.Environment global = new ExpressionParser.Environment(null); | |
global.Declare("SqrtNative", new SqrtNative()); | |
foreach (var statement in debugParserarser.Statements) { | |
statement.Execute(global); | |
} | |
ExpressionParser.Environment environment = new ExpressionParser.Environment(null); | |
Statement program = new PrintStatement( | |
new BinaryExpression( | |
new LiteralExpression(2), | |
new Token(TokenType.PLUS, "+"), | |
new BinaryExpression( | |
new LiteralExpression(3), | |
new Token(TokenType.STAR, "*"), | |
new LiteralExpression(6) | |
) // End BinaryExpression "*" | |
) // End BinaryExpression "+" | |
); // End PrintStatement | |
//print(2 + 3 * 6) | |
program.Execute(environment); | |
Console.ReadLine(); | |
} | |
int Token; | |
string Source; | |
public Program(string source) { | |
Source = source; | |
Token = 0; | |
Console.WriteLine("Result: " + Expression()); | |
} | |
char Current() { | |
if (Token >= Source.Length) { | |
return '\0'; | |
} | |
return Source[Token]; | |
} | |
void SkipWhitespace() { | |
char c = Current(); | |
while (c == ' ' || c == '\t' || c == '\r' || c == '\n') { | |
Token++; | |
c = Current(); | |
} | |
} | |
double Expression() { | |
// <expression> -> <term> (("+" | "-") <term>)* | |
double left = Term(); | |
SkipWhitespace(); | |
char c = Current(); | |
while (c == '+' || c == '-') { | |
Token++; // Eat + or - | |
double right = Term(); | |
if (c == '+') { | |
left = left + right; | |
} else if (c == '-') { | |
left = left - right; | |
} | |
SkipWhitespace(); | |
c = Current(); | |
} | |
return left; | |
} | |
double Term() { | |
// <term> -> <power> (("*" | "/") <power>)* | |
double left = Power(); | |
SkipWhitespace(); | |
char c = Current(); | |
while (c == '*' || c == '/') { | |
Token++; // Eat * or / | |
double right = Power(); | |
if (c == '*') { | |
left = left * right; | |
} | |
else if (c == '/') { | |
left = left / right; | |
} | |
SkipWhitespace(); | |
c = Current(); | |
} | |
return left; | |
} | |
double Power() { | |
// <power> -> <unary> ("^" <power>)* | |
double factor = Unary(); | |
SkipWhitespace(); | |
char c = Current(); | |
if (c == '^') { | |
Token++; // Eat ^ | |
double power = Power(); | |
return Math.Pow(factor, power); | |
} | |
return factor; | |
} | |
double Unary() { | |
// <unary> -> ("-")? <unary> | <factor> | |
SkipWhitespace(); | |
char c = Current(); | |
if (c == '-') { | |
Token++; // Eat negative | |
return -1.0 * Unary(); | |
} | |
return Factor(); | |
} | |
double Factor() { | |
SkipWhitespace(); | |
char c = Current(); | |
if (c == '(') { | |
Token++; // Eat ( | |
double expr = Expression(); | |
SkipWhitespace(); | |
c = Current(); | |
if (c != ')') { | |
throw new Exception("Invalid expression in factor"); | |
} | |
Token++; // Eat ) | |
return expr; | |
} | |
return Number(); | |
} | |
double Number() { | |
SkipWhitespace(); | |
char c = Current(); | |
if (c >= '0' && c <= '9') { | |
string tmp = String.Empty; | |
while (c >= '0' && c <= '9') { | |
tmp += c.ToString(); | |
Token++; | |
c = Current(); | |
} | |
if (c == '.') { | |
tmp += c.ToString(); | |
Token++; // Eat . | |
c = Current(); | |
if (c >= '0' && c <= '9') { | |
while (c >= '0' && c <= '9') { | |
tmp += c.ToString(); | |
Token++; | |
c = Current(); | |
} | |
} | |
else { | |
throw new Exception("Invalid number format"); | |
} | |
} | |
return Double.Parse(tmp); | |
} | |
throw new Exception("Invalid number"); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace ExpressionParser { | |
class Scanner { | |
public List<Token> Tokens; | |
private string Source; | |
private int CurChar; | |
private int StartChar; | |
private Dictionary<string, TokenType> Reserved; | |
public Scanner(string source) { | |
Tokens = new List<Token>(); | |
Reserved = new Dictionary<string, TokenType>() { | |
{ "var", TokenType.VAR }, | |
{ "fun", TokenType.FUN }, | |
{ "return", TokenType.RETURN }, | |
{ "if", TokenType.IF }, | |
{ "else", TokenType.ELSE }, | |
{ "while", TokenType.WHILE }, | |
{ "print", TokenType.PRINT } | |
}; | |
CurChar = 0; | |
Source = source; | |
SkipWhitespace(); | |
while (CurChar < Source.Length) { | |
StartChar = CurChar; | |
Token token = GetToken(); | |
if (token.Type != TokenType.SLASH_SLASH) { | |
Tokens.Add(token); | |
} | |
SkipWhitespace(); | |
} | |
Tokens.Add(new Token(TokenType.EOF, String.Empty)); | |
source = null; | |
Reserved = null; | |
} | |
private void SkipWhitespace() { | |
for (char c = Current(); | |
c == ' ' || c == '\t' || c == '\n' || c == '\r'; | |
CurChar++, c = Current()) ; | |
} | |
private char Current() { | |
if (CurChar < Source.Length) { | |
return Source[CurChar]; | |
} | |
return '\0'; | |
} | |
private string Lexeme() { | |
return Source.Substring(StartChar, CurChar - StartChar); | |
} | |
private Token GetToken() { | |
char c = Current(); | |
CurChar++; | |
char n = Current(); | |
switch(c) { | |
case ';': return new Token(TokenType.SEMICOLON, Lexeme()); | |
case '(': return new Token(TokenType.LPAREN, Lexeme()); | |
case ')': return new Token(TokenType.RPAREN, Lexeme()); | |
case '{': return new Token(TokenType.LBRACE, Lexeme()); | |
case '}': return new Token(TokenType.RBRACE, Lexeme()); | |
case '+': return new Token(TokenType.PLUS, Lexeme()); | |
case '-': return new Token(TokenType.MINUS, Lexeme()); | |
case '*': return new Token(TokenType.STAR, Lexeme()); | |
case '^': return new Token(TokenType.POW, Lexeme()); | |
case ',': return new Token(TokenType.COMMA, Lexeme()); | |
case '/': | |
if (n == '/') { | |
while (CurChar < Source.Length && Current() != '\n') { | |
CurChar++; | |
} | |
return new Token(TokenType.SLASH_SLASH, Lexeme()); | |
} | |
else { | |
return new Token(TokenType.SLASH, Lexeme()); | |
} | |
case '<': | |
if (n == '=') { | |
CurChar++; | |
return new Token(TokenType.LESS_EQUAL, Lexeme()); | |
} | |
else { | |
return new Token(TokenType.LESS, Lexeme()); | |
} | |
case '>': | |
if (n == '=') { | |
CurChar++; | |
return new Token(TokenType.GREATER_EQUAL, Lexeme()); | |
} | |
else { | |
return new Token(TokenType.GREATER, Lexeme()); | |
} | |
case '=': | |
if (n == '=') { | |
CurChar++; | |
return new Token(TokenType.EQUAL_EQUAL, Lexeme()); | |
} | |
else { | |
return new Token(TokenType.EQUAL, Lexeme()); | |
} | |
case '!': | |
if (n == '=') { | |
CurChar++; | |
return new Token(TokenType.NOT_EQUAL, Lexeme()); | |
} | |
// Just ignore if no equal sign, we don't have a ! operator | |
break; | |
default: | |
if (c >= '0' && c <= '9') { | |
return GetNumber(); | |
} | |
else if ((c >= 'a' && c <= 'z') || | |
(c >= 'A' && c <= 'Z') || | |
(c == '_')) { | |
string parsed = GetString(); | |
if (Reserved.ContainsKey(parsed)) { // Identifier or keyword | |
return new Token(Reserved[parsed], parsed); | |
} | |
return new Token(TokenType.IDENTIFIER, parsed); | |
} | |
break; | |
} | |
throw new Exception("Scanner error"); | |
} | |
private Token GetNumber() { | |
// No need to rewind, will use lexeme | |
for (char c = Current(); | |
(c >= '0' && c <= '9'); | |
CurChar++, c = Current()); | |
if (Current() == '.') { | |
CurChar++; | |
for (char c = Current(); | |
(c >= '0' && c <= '9'); | |
CurChar++, c = Current()) ; | |
} | |
string lexeme = Lexeme(); | |
return new Token(TokenType.NUMBER, lexeme, Double.Parse(lexeme)); | |
} | |
private string GetString() { | |
for (char c = Current(); | |
(c >= '0' && c <= '9') || | |
(c >= 'a' && c <= 'z') || | |
(c >= 'A' && c <= 'Z') || | |
(c == '_'); | |
CurChar++, c = Current()); | |
return Lexeme(); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace ExpressionParser { | |
enum TokenType { | |
SEMICOLON, LPAREN, RPAREN, LBRACE, RBRACE, | |
PLUS, MINUS, SLASH, STAR, POW, COMMA, | |
LESS, GREATER, LESS_EQUAL, GREATER_EQUAL, | |
EQUAL, EQUAL_EQUAL, NOT_EQUAL, | |
VAR, FUN, RETURN, IF, ELSE, WHILE, PRINT, | |
IDENTIFIER, NUMBER, SLASH_SLASH, EOF | |
} | |
class Token { | |
public TokenType Type; | |
public string Lexeme; | |
public double Value; | |
public Token(TokenType type, string lexeme, double value = 0.0) { | |
Type = type; | |
Lexeme = lexeme; | |
Value = value; | |
} | |
public override string ToString() { | |
string result = "Token: " + Type.ToString() + ", Lexeme: " + Lexeme + ", Value: " + Value; | |
if (Type == TokenType.NUMBER) { | |
result += ", Value: " + Value; | |
} | |
return result; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment