Skip to content

Instantly share code, notes, and snippets.

Embed
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
You can’t perform that action at this time.