Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
An example of how to do syntax tree construction without using return values
using System;
using System.Collections.Generic;
using System.Text;
namespace StackMachineTreeConstruction
{
public class Class1
{
enum TokenType
{
None,
Number,
Operator,
LeftParen,
RightParen
}
struct Token
{
public readonly TokenType Type;
public readonly string Text;
public Token(TokenType type, string text)
{
this.Type = type;
this.Text = text;
}
}
static IEnumerable<Token> GetInputStream()
{
yield return new Token(TokenType.Number, "1");
yield return new Token(TokenType.Operator, "+");
yield return new Token(TokenType.Number, "2");
}
static IEnumerable<Token> GetInputStream2()
{
yield return new Token(TokenType.Number, "1");
yield return new Token(TokenType.Operator, "+");
yield return new Token(TokenType.LeftParen, "(");
yield return new Token(TokenType.Number, "2");
yield return new Token(TokenType.Operator, "-");
yield return new Token(TokenType.Number, "3");
yield return new Token(TokenType.RightParen, ")");
}
static IEnumerable<Token> GetInputStream3()
{
yield return new Token(TokenType.LeftParen, "(");
yield return new Token(TokenType.Number, "2");
yield return new Token(TokenType.Operator, "-");
yield return new Token(TokenType.Number, "3");
yield return new Token(TokenType.RightParen, ")");
yield return new Token(TokenType.Operator, "+");
yield return new Token(TokenType.Number, "1");
}
abstract class SyntaxTree
{
protected SyntaxTree()
{
}
public override string ToString()
{
var sb = new StringBuilder();
ToString(sb, 0);
return sb.ToString();
}
public abstract void ToString(StringBuilder sb, int indent);
}
class SyntaxNode : SyntaxTree
{
public readonly string NodeName;
public readonly List<SyntaxTree> Children;
public SyntaxNode(string nodeName)
{
this.NodeName = nodeName;
this.Children = new List<SyntaxTree>();
}
public override void ToString(StringBuilder sb, int indent)
{
sb.Append('(');
sb.Append(NodeName);
if (Children.Count <= 1)
{
foreach (var child in Children)
{
sb.Append(' ');
child.ToString(sb, indent);
}
}
else
{
foreach (var child in Children)
{
sb.AppendLine().Append(' ', indent + 1);
child.ToString(sb, indent + 1);
}
sb.AppendLine().Append(' ', indent);
}
sb.Append(')');
}
}
class TokenNode : SyntaxTree
{
public readonly Token Token;
public TokenNode(Token token)
{
Token = token;
}
public override void ToString(StringBuilder sb, int indent)
{
sb.Append('"').Append(Token.Text).Append('"');
}
}
class ParserBase
{
private readonly IEnumerator<Token> _inputStream;
private readonly List<SyntaxTree> _stack;
public SyntaxTree SyntaxTree { get { return _stack[_stack.Count - 1]; } }
public ParserBase(IEnumerable<Token> inputStream)
{
_inputStream = inputStream.GetEnumerator();
_stack = new List<Class1.SyntaxTree>();
Read();
}
private Token _token;
private void Read()
{
if (_inputStream.MoveNext())
{
_token = _inputStream.Current;
}
else
{
_token = default(Token);
}
}
protected bool Accept(TokenType type)
{
if (_token.Type == type)
{
_stack.Add(new TokenNode(_token)); // push
Read();
return true;
}
return false;
}
protected void Reduce(int nodeCount, string nodeName)
{
var tree = new SyntaxNode(nodeName);
for (int i = 0; i < nodeCount; i++)
{
tree.Children.Add(_stack[_stack.Count - nodeCount + i]); // reverse pop
}
for (int i = 0; i < nodeCount; i++)
{
_stack.RemoveAt(_stack.Count - 1);
}
_stack.Add(tree);
}
}
class Parser : ParserBase
{
public Parser(IEnumerable<Token> inputStream)
: base(inputStream)
{
}
public void Expression()
{
Primary();
if (Accept(TokenType.Operator))
{
Expression();
Reduce(3, "BinaryExpression");
return;
}
}
public void Primary()
{
if (Accept(TokenType.Number))
{
Reduce(1, "NumberLiteral");
return;
}
if (Accept(TokenType.LeftParen))
{
Expression();
if (!Accept(TokenType.RightParen))
{
throw new InvalidOperationException();
}
Reduce(3, "EvalExpression");
return;
}
}
}
public static void Main()
{
WriteLine(GetInputStream());
WriteLine(GetInputStream2());
WriteLine(GetInputStream3());
}
private static void WriteLine(IEnumerable<Token> inputStream)
{
var i = 0;
foreach (var token in inputStream)
{
if (i > 0)
{
Console.Write(" -> ");
}
Console.Write("{0}", token.Type);
i++;
}
Console.WriteLine();
var parser = new Parser(inputStream);
parser.Expression();
Console.WriteLine(parser.SyntaxTree);
Console.WriteLine();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment