C# Parse Tree
A parse tree for a grammar G is a tree where
• the root is the start symbol for G
• the interior nodes are the nonterminals of G
• the leaf nodes are the terminal symbols of G.
• the children of a node T (from left to right) correspond to the symbols on the right hand side of some production for T in G.
C# Parse Tree Definitions
According to this definition, let's create a parse tree in C# programming language.
We will first, define a terminal interface.
public interface ITerminal
{
}
Secondly, we will define a class for interior nodes that are nonterminals of G.
public class Nonterminal : ITerminal // Equation, interior node
{
public string Equation { get; set; }
public ITerminal LeftChild { get; set; }
public ITerminal RightChild { get; set; }
public Nonterminal(string equation, ITerminal left, ITerminal right)
{
Equation = equation;
LeftChild = left;
RightChild = right;
}
public override string ToString()
{
return String.Format("{0} {1} {2}", LeftChild, Equation, RightChild);
}
}
Lastly, we will define a class for leaf nodes that are terminals of G.
public class Terminal : ITerminal // Value, leaf node
{
public double Value { get; set; }
public Terminal(double val)
{
Value = val;
}
public override string ToString()
{
return String.Format("{0}", Value);
}
}
Using these classes, we can create a parse tree for any given string.
C# Parse Tree Example
Example: Given the following grammar, create a parse tree for the string "1 + 2 * 3":
var node2 = new Terminal(2);
var node3 = new Terminal(3);
var equation23 = new Nonterminal("*", node2, node3);
var node1 = new Terminal(1);
var root = new Nonterminal("+", node1, equation23);
Console.WriteLine(root);
Then, the output will be:
1 + 2 * 3