Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
C# Abstract Syntax Tree Example: Simple Pascal Compiler
//Rextester.Program.Main is the entry point for your code. Don't change it. //Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5 using System; using System.Collections.Generic; using System.Runtime.Serialization; using System.Text; namespace Rextester { public class Program { public static void Main(string[] args) { string input = string.Empty; Console.WriteLine("Input an expression, for example:" + Environment.NewLine + Environment.NewLine + " begin x := 5; y := 6.5; begin z := 7; z := (2.11*-z*(5+7.18+9.23))+---x+++(-+-+--(y+2))*(-+-3+x)*(5+y)+3*(2+1);end; t := z*2 end."); input = " begin x := 5; y := 6.5; begin z := 7; z := (2.11*-z*(5+7.18+9.23))+---x+++(-+-+--(y+2))*(-+-3+x)*(5+y)+3*(2+1);end; t := z*2 end."; //while (true) { //Console.WriteLine(); //Console.Write("Input (q = quit): "); //Console.WriteLine(); //FlushConsole(); //input = Console.ReadLine(); //if (input == "q") //{ // break; //} try { Parser interpreter = new Parser(input); Node node = interpreter.Parse(); Console.WriteLine(); Console.WriteLine(string.Format("Tree graph:{0}{1}", Environment.NewLine + Environment.NewLine, node.Accept(new GraphBuilder(), GraphBuilder.InitialData))); Console.WriteLine(); Console.WriteLine(); Console.WriteLine(string.Format("Value:{0}{1}", Environment.NewLine + Environment.NewLine, node.Accept(new ValueBuilder(), null))); Console.WriteLine(); Console.WriteLine(); Console.WriteLine(string.Format("Lisp form:{0}{1}", Environment.NewLine + Environment.NewLine, node.Accept(new LispFormBuilder(), null))); Console.WriteLine(); } catch (InvalidSyntaxException ex) { Console.WriteLine(ex.Message); } catch (Exception ex) { Console.WriteLine(ex); } } } static void FlushConsole() { while (Console.KeyAvailable) { Console.ReadKey(false); } } } internal class Parser { private Token curToken; private int curPos; private int charCount; private char curChar; public string Text { get; private set; } public Parser(string text) { this.Text = string.IsNullOrEmpty(text) ? string.Empty : text; this.charCount = this.Text.Length; this.curToken = Token.None(); this.curPos = -1; this.Advance(); } internal Node Parse() { this.NextToken(); Node node = this.GrabCompoundStatement(); this.ExpectToken(TokenType.Dot); return node; } private Node GrabCompoundStatement() { this.EatToken(TokenType.Begin); List<Node> statementList = this.GrabStatementList(); this.EatToken(TokenType.End); return new CompoundStatement(statementList); } private List<Node> GrabStatementList() { List<Node> statementList = new List<Node>(); Node statement = this.GrabStatement(); statementList.Add(statement); while (this.curToken.Type == TokenType.Semi) { this.EatToken(TokenType.Semi); statement = this.GrabStatement(); statementList.Add(statement); } return statementList; } private Node GrabStatement() { Node statement; if (this.curToken.Type == TokenType.Begin) { statement = this.GrabCompoundStatement(); } else if (this.curToken.Type == TokenType.Variable) { statement = this.GrabAssignStatement(); } else { statement = new NoOp(); } return statement; } private Node GrabAssignStatement() { Token varToken = this.EatToken(TokenType.Variable); Token assignToken = this.EatToken(TokenType.Assignment); Node expr = this.GrabExpr(); return new AssignStatement(new Variable(varToken), assignToken, expr); } private Token ExpectToken(TokenType tokenType) { if (this.curToken.Type == tokenType) { return this.curToken; } else { throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Expected {1} but {2} is given.", this.curPos, tokenType, this.curToken.Type.ToString())); } } private Token EatToken(TokenType tokenType) { if (this.curToken.Type == tokenType) { Token token = this.curToken; this.NextToken(); return token; } else { throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Expected {1} but {2} is given.", this.curPos, tokenType, this.curToken.Type.ToString())); } } private Node GrabExpr() { Node left = this.GrabTerm(); while (this.curToken.Type == TokenType.Plus || this.curToken.Type == TokenType.Minus) { Token op = this.curToken; this.NextToken(); Node right = this.GrabTerm(); left = new BinOp(op, left, right); } return left; } private Node GrabTerm() { Node left = this.GrabFactor(); while (this.curToken.Type == TokenType.Multiply || this.curToken.Type == TokenType.Divide) { Token op = this.curToken; this.NextToken(); Node right = this.GrabFactor(); left = new BinOp(op, left, right); } return left; } private Node GrabFactor() { if (this.curToken.Type == TokenType.Plus || this.curToken.Type == TokenType.Minus) { Node node = this.GrabUnaryExpr(); return node; } else if (this.curToken.Type == TokenType.LeftParenthesis) { Node node = this.GrabBracketExpr(); return node; } else if (this.curToken.Type == TokenType.Variable) { Node node = this.GrabVariable(); return node; } else { Token token = this.ExpectToken(TokenType.Number); this.NextToken(); return new Num(token); } } private Node GrabVariable() { Token token = this.ExpectToken(TokenType.Variable); this.NextToken(); return new Variable(token); } private Node GrabUnaryExpr() { Token op; if (this.curToken.Type == TokenType.Plus) { op = this.ExpectToken(TokenType.Plus); } else { op = this.ExpectToken(TokenType.Minus); } this.NextToken(); if (this.curToken.Type == TokenType.Plus || this.curToken.Type == TokenType.Minus) { Node expr = this.GrabUnaryExpr(); return new UnaryOp(op, expr); } else { Node expr = this.GrabFactor(); return new UnaryOp(op, expr); } } private Node GrabBracketExpr() { this.ExpectToken(TokenType.LeftParenthesis); this.NextToken(); Node node = this.GrabExpr(); this.ExpectToken(TokenType.RightParenthesis); this.NextToken(); return node; } private void NextToken() { if (this.curChar == char.MinValue) { this.curToken = Token.None(); return; } if (this.curChar == ' ') { while (this.curChar != char.MinValue && this.curChar == ' ') { this.Advance(); } if (this.curChar == char.MinValue) { this.curToken = Token.None(); return; } } if (this.curChar == '+') { this.curToken = new Token(TokenType.Plus, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == '-') { this.curToken = new Token(TokenType.Minus, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == '*') { this.curToken = new Token(TokenType.Multiply, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == '/') { this.curToken = new Token(TokenType.Divide, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == '(') { this.curToken = new Token(TokenType.LeftParenthesis, this.curChar.ToString()); this.Advance(); return; } if (this.curChar == ')') { this.curToken = new Token(TokenType.RightParenthesis, this.curChar.ToString()); this.Advance(); return; } if (this.curChar >= '0' && this.curChar <= '9') { string num = string.Empty; while (this.curChar >= '0' && this.curChar <= '9') { num += this.curChar.ToString(); this.Advance(); } if (this.curChar == '.') { num += this.curChar.ToString(); this.Advance(); if (this.curChar >= '0' && this.curChar <= '9') { while (this.curChar >= '0' && this.curChar <= '9') { num += this.curChar.ToString(); this.Advance(); } } else { throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Unexpected symbol {1}", this.curPos + 1, this.curChar)); } } this.curToken = new Token(TokenType.Number, num); return; } if ((this.curChar >= 'a' && this.curChar <= 'z') || this.curChar >= 'A' && this.curChar <= 'Z') { string word = string.Empty; word += this.curChar; this.Advance(); if ((this.curChar >= 'a' && this.curChar <= 'z') || (this.curChar >= 'A' && this.curChar <= 'Z') || this.curChar == '_' || (this.curChar >= '0' && this.curChar <= '9')) { while ((this.curChar >= 'a' && this.curChar <= 'z') || (this.curChar >= 'A' && this.curChar <= 'Z') || this.curChar == '_' || (this.curChar >= '0' && this.curChar <= '9')) { word += this.curChar.ToString(); this.Advance(); } } if (string.Compare(word, "BEGIN", true) == 0) { this.curToken = new Token(TokenType.Begin, word); } else if (string.Compare(word, "END", true) == 0) { this.curToken = new Token(TokenType.End, word); } else { this.curToken = new Token(TokenType.Variable, word); } return; } if (this.curChar == ';') { this.curToken = new Token(TokenType.Semi, ";"); this.Advance(); return; } if (this.curChar == '.') { this.curToken = new Token(TokenType.Dot, "."); this.Advance(); return; } if (this.curChar == ':') { if (this.Peek() == '=') { this.Advance(); this.curToken = new Token(TokenType.Assignment, ":="); this.Advance(); return; } } throw new InvalidSyntaxException(string.Format("Invalid syntax at position {0}. Unexpected symbol {1}", this.curPos + 1, this.curChar)); } private void Advance() { this.curPos += 1; if (this.curPos < this.charCount) { this.curChar = this.Text[this.curPos]; } else { this.curChar = char.MinValue; } } private Char Peek() { if (this.curPos + 1 < this.charCount) { return this.Text[this.curPos + 1]; } else { return char.MinValue; } } } internal class AssignStatement : Node { private Variable variable; private Node expr; private Token assignToken; public AssignStatement(Variable variable, Token assignToken, Node expr) { this.variable = variable; this.expr = expr; this.assignToken = assignToken; } public override object Accept(INodeVisitor visitor, object options) { return visitor.VisitAssignStatement(variable, assignToken, expr, options); } } internal class NoOp : Node { public override object Accept(INodeVisitor visitor, object options) { throw new NotImplementedException(); } } internal class CompoundStatement : Node { private List<Node> statementList; public CompoundStatement(List<Node> statementList) { this.statementList = new List<Node>(); foreach (Node node in statementList) { if (node is NoOp) continue; this.statementList.Add(node); } } public override object Accept(INodeVisitor visitor, object options) { return visitor.VisitCompoundStatement(this.statementList, options); } } [Serializable] internal class InvalidSyntaxException : Exception { public InvalidSyntaxException() { } public InvalidSyntaxException(string message) : base(message) { } public InvalidSyntaxException(string message, Exception innerException) : base(message, innerException) { } protected InvalidSyntaxException(SerializationInfo info, StreamingContext context) : base(info, context) { } } internal class GraphBuilder : INodeVisitor { private static string ReplaceLastChar(string str, char rep = ' ') { if (!string.IsNullOrEmpty(str)) { return str.Substring(0, str.Length - 1) + rep.ToString(); } else { return ""; } } const Char SPACE = ' '; const Char L_TURN = '┌'; const Char M_TURN = '├'; const Char R_TURN = '└'; const Char V_PIPE = '│'; const string TAB = " "; const string H_PIPE = "──"; internal static readonly LegacyData InitialData = new LegacyData { LegacyIndent = TAB, LegacyOrientation = BranchOrientation.Right }; private StringBuilder sb; public GraphBuilder() { this.sb = new StringBuilder(); this.sb.AppendLine("(Root)"); } public object VisitBinOp(Token op, INode left, INode right, object options) { LegacyData legacyData = (LegacyData)options; BranchOrientation legacyOrientation = legacyData.LegacyOrientation; string legacyIndent = legacyData.LegacyIndent; if (legacyOrientation == BranchOrientation.Left) { left.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, SPACE) + TAB + L_TURN, LegacyOrientation = BranchOrientation.Left }); } else { left.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, V_PIPE) + TAB + V_PIPE, LegacyOrientation = BranchOrientation.Left }); } if (legacyOrientation == BranchOrientation.Left) { sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " (" + op.ToString() + ")"); } else { sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " (" + op.ToString() + ")"); } if (legacyOrientation == BranchOrientation.Right) { right.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, SPACE) + TAB + R_TURN, LegacyOrientation = BranchOrientation.Right }); } else { right.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, V_PIPE) + TAB + V_PIPE, LegacyOrientation = BranchOrientation.Right }); } return this.sb.ToString(); } public object VisitNum(Token num, object options) { LegacyData legacyData = (LegacyData)options; BranchOrientation legacyOrientation = legacyData.LegacyOrientation; string legacyIndent = legacyData.LegacyIndent; if (legacyOrientation == BranchOrientation.Left) { sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " " + num.ToString()); } else { sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " " + num.ToString()); } return this.sb.ToString(); } public object VisitUnaryOp(Token op, INode node, object options) { LegacyData legacyData = (LegacyData)options; BranchOrientation legacyOrientation = legacyData.LegacyOrientation; string legacyIndent = legacyData.LegacyIndent; if (legacyOrientation == BranchOrientation.Left) { sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " (" + op.ToString() + ")"); } else { sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " (" + op.ToString() + ")"); } if (legacyOrientation == BranchOrientation.Right) { node.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, SPACE) + TAB + R_TURN, LegacyOrientation = BranchOrientation.Right }); } else { node.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, V_PIPE) + TAB + R_TURN, LegacyOrientation = BranchOrientation.Right }); } return this.sb.ToString(); } public object VisitAssignStatement(Variable variable, Token op, Node expr, object options) { LegacyData legacyData = (LegacyData)options; BranchOrientation legacyOrientation = legacyData.LegacyOrientation; string legacyIndent = legacyData.LegacyIndent; if (legacyOrientation == BranchOrientation.Left) { variable.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, SPACE) + TAB + L_TURN, LegacyOrientation = BranchOrientation.Left }); } else { variable.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, V_PIPE) + TAB + V_PIPE, LegacyOrientation = BranchOrientation.Left }); } if (legacyOrientation == BranchOrientation.Left) { sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " (" + op.ToString() + ")"); } else if (legacyOrientation == BranchOrientation.Mid) { sb.AppendLine(ReplaceLastChar(legacyIndent, M_TURN) + H_PIPE + " (" + op.ToString() + ")"); } else { sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " (" + op.ToString() + ")"); } if (legacyOrientation == BranchOrientation.Right) { expr.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, SPACE) + TAB + R_TURN, LegacyOrientation = BranchOrientation.Right }); } else { expr.Accept(this, new LegacyData { LegacyIndent = ReplaceLastChar(legacyIndent, V_PIPE) + TAB + V_PIPE, LegacyOrientation = BranchOrientation.Right }); } return this.sb.ToString(); } public object VisitCompoundStatement(List<Node> statements, object options) { LegacyData legacyData = (LegacyData)options; BranchOrientation legacyOrientation = legacyData.LegacyOrientation; string legacyIndent = legacyData.LegacyIndent; if (legacyOrientation == BranchOrientation.Left) { sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " (Compound)"); } else if (legacyOrientation == BranchOrientation.Mid) { sb.AppendLine(ReplaceLastChar(legacyIndent, M_TURN) + H_PIPE + " (Compound)"); } else { sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " (Compound)"); } string childIndent = legacyIndent; if (legacyOrientation == BranchOrientation.Right) { childIndent = ReplaceLastChar(childIndent, SPACE) + TAB; } else { childIndent = ReplaceLastChar(childIndent, V_PIPE) + TAB; } for (int i = 0; i < statements.Count; i++) { Node statement = statements[i]; if (i < statements.Count - 1) { statement.Accept(this, new LegacyData { LegacyIndent = childIndent, LegacyOrientation = BranchOrientation.Mid }); } else { statement.Accept(this, new LegacyData { LegacyIndent = childIndent, LegacyOrientation = BranchOrientation.Right }); } } return this.sb.ToString(); } public object VisitVariable(Token variable, object options) { LegacyData legacyData = (LegacyData)options; BranchOrientation legacyOrientation = legacyData.LegacyOrientation; string legacyIndent = legacyData.LegacyIndent; if (legacyOrientation == BranchOrientation.Left) { sb.AppendLine(ReplaceLastChar(legacyIndent, L_TURN) + H_PIPE + " " + variable.ToString()); } else { sb.AppendLine(ReplaceLastChar(legacyIndent, R_TURN) + H_PIPE + " " + variable.ToString()); } return this.sb.ToString(); } internal enum BranchOrientation { Mid, Left, Right } internal class LegacyData { public BranchOrientation LegacyOrientation { get; internal set; } public string LegacyIndent { get; internal set; } } } internal class ValueBuilder : INodeVisitor { Dictionary<string, decimal> varLookup = new Dictionary<string, decimal>(); public object VisitBinOp(Token op, INode left, INode right, object options) { switch (op.Type) { case TokenType.Plus: return (decimal)left.Accept(this, options) + (decimal)right.Accept(this, options); case TokenType.Minus: return (decimal)left.Accept(this, options) - (decimal)right.Accept(this, options); case TokenType.Multiply: return (decimal)left.Accept(this, options) * (decimal)right.Accept(this, options); case TokenType.Divide: return (decimal)left.Accept(this, options) / (decimal)right.Accept(this, options); default: throw new Exception(string.Format("Token of type {0} cannot be evaluated.", op.Type.ToString())); } } public object VisitNum(Token num, object options) { return decimal.Parse(num.Value); } public object VisitAssignStatement(Variable variable, Token op, Node expr, object options) { string varName = variable.ToString(); decimal value = (decimal)expr.Accept(this, options); this.varLookup[varName] = value; return value; } public object VisitCompoundStatement(List<Node> statements, object options) { foreach (Node statement in statements) { statement.Accept(this, options); } StringBuilder sb = new StringBuilder(); foreach (String key in this.varLookup.Keys) { sb.AppendLine(string.Format("{0} = {1}", key, this.varLookup[key])); } return sb.ToString(0, sb.Length - 1); } public object VisitUnaryOp(Token op, INode node, object options) { switch (op.Type) { case TokenType.Plus: return (decimal)node.Accept(this, options); case TokenType.Minus: return -(decimal)node.Accept(this, options); default: throw new Exception(string.Format("Token of type {0} cannot be evaluated.", op.Type.ToString())); } } public object VisitVariable(Token variable, object options) { string varName = variable.Value; if (this.varLookup.ContainsKey(varName)) { return this.varLookup[varName]; } else { throw new Exception(string.Format("Variable {0} is not existed.", varName)); } } } internal class LispFormBuilder : INodeVisitor { public object VisitBinOp(Token op, INode left, INode right, object options) { return "(" + op.ToString() + " " + left.Accept(this, options) + " " + right.Accept(this, options) + ")"; } public object VisitNum(Token num, object options) { return num.ToString(); } public object VisitAssignStatement(Variable variable, Token op, Node expr, object options) { return "(" + op.ToString() + " " + variable.Accept(this, options) + " " + expr.Accept(this, options) + ")"; } public object VisitCompoundStatement(List<Node> statements, object options) { StringBuilder sb = new StringBuilder(); foreach (Node expr in statements) { sb.AppendLine(expr.Accept(this, options).ToString()); } return sb.ToString(0, sb.Length - 1); } public object VisitUnaryOp(Token op, INode node, object options) { return "(" + op.ToString() + " " + node.Accept(this, options) + ")"; } public object VisitVariable(Token variable, object options) { return variable.ToString(); } } internal interface INode { object Accept(INodeVisitor visitor, object options); } internal interface INodeVisitor { object VisitNum(Token num, object options); object VisitUnaryOp(Token op, INode node, object options); object VisitBinOp(Token op, INode left, INode right, object options); object VisitAssignStatement(Variable variable, Token op, Node expr, object options); object VisitCompoundStatement(List<Node> statements, object options); object VisitVariable(Token variable, object options); } internal abstract class Node : INode { abstract public object Accept(INodeVisitor visitor, object options); } internal class Num : Node { internal Token Token { get; private set; } public Num(Token token) { this.Token = token; } override public object Accept(INodeVisitor visitor, object options) { return visitor.VisitNum(this.Token, options); } } internal class Variable : Node { internal Token Token { get; private set; } public Variable(Token token) { this.Token = token; } override public object Accept(INodeVisitor visitor, object options) { return visitor.VisitVariable(this.Token, options); } public override string ToString() { return this.Token.ToString(); } } internal class UnaryOp : Node { internal Token Op { get; private set; } internal Node Node { get; private set; } public UnaryOp(Token op, Node node) { this.Op = op; this.Node = node; } override public object Accept(INodeVisitor visitor, object options) { return visitor.VisitUnaryOp(this.Op, this.Node, options); } } internal class BinOp : Node { internal Token Op { get; private set; } internal Node Left { get; private set; } internal Node Right { get; private set; } public BinOp(Token op, Node left, Node right) { this.Op = op; this.Left = left; this.Right = right; } override public object Accept(INodeVisitor visitor, object options) { return visitor.VisitBinOp(this.Op, this.Left, this.Right, options); } } internal class Token { public TokenType Type { get; private set; } public string Value { get; private set; } public Token(TokenType type, string value) { this.Type = type; this.Value = value; } internal static Token None() { return new Token(TokenType.None, ""); } public override string ToString() { return this.Value; } } internal enum TokenType { None, Plus, Minus, Multiply, Divide, Number, LeftParenthesis, RightParenthesis, Variable, Assignment, End, Begin, Dot, Semi } }
run
|
edit
|
history
|
help
0
sorted array
JAVA HELLO
PermuteAString
Word count in string
Palindrome Number
CommandForce3
a5
EqualityComparer
123
Valid Substring