上一章节我们介绍了词法分析,就是将字符串翻译成标记,
本章将介绍语法树,用于表示字符串或源代码的抽象语法结构,是一种树状表示方法.
语法树的构成一般由根节点,内部节点,叶子节点组成.
内部节点:代表语法规则中的非终结符,如语句、表达式等。这些节点通常包含其他子节点。
叶子节点:代表语法规则中的终结符,如标识符、常量、运算符等。这些节点是语法树中的基本元素,它们不再包含其他子节点。
语法树的作用
语法检查:通过遍历语法树,以检查源代码是否符合语言的语法规则
语义分析:在语法树的基础上,以进一步进行语义分析,如类型检查、作用域分析等。这些分析有助于确保源代码在语义上是正确的。
代码生成:对于编译器而言,语法树是生成目标代码的重要基础。编译器可以遍历语法树,并根据每个节点的类型生成相应的目标代码。
我们先定义一个抽象节点
abstract class Node{public abstract int Eval();}
表示数值的节点
// 表示数值的节点class NumNode : Node{public int Value { get; }public NumNode(int value){Value = value;}public override int Eval(){return Value;}}
表示二元运算的节点
// 表示二元运算的节点class BinOpNode : Node{public Node Left { get; }public TokenType Op { get; }public Node Right { get; }public BinOpNode(Node left, TokenType op, Node right){Left = left;Op = op;Right = right;}public override int Eval(){int leftVal = Left.Eval();int rightVal = Right.Eval();switch (Op){case TokenType.Plus:return leftVal + rightVal;case TokenType.Minus:return leftVal - rightVal;case TokenType.Multiply:return leftVal * rightVal;// 可以添加更多运算符的处理default:throw new InvalidOperationException($"Unknown operator: {Op}");}}}
测试代码
class Program{static void Main(string[] args){// 构建语法树,表示表达式 "3 + 5 - 2"Node tree = new BinOpNode(new BinOpNode(new NumNode(3), '+', new NumNode(5)),'-',new NumNode(2));// 评估语法树并输出结果int result = tree.Eval();Console.WriteLine(result); // 输出: 6}}
注意理解二元运算节点类,左右节点可以又是二元运算节点.形成嵌套.