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