Семантические действия в синтаксическом анализаторе. Построение дерева программы

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск

К основной странице курса

Для построения дерева программы создадим модуль, включающий все синтаксические узлы программы

Модуль узлов синтаксического дерева

unit ProgramTree;

uses 
  System.Collections.Generic,
  SimpleLangLexer;
  
type 
  Node = class // базовый класс для всех узлов    
  end;
  
  ExprNode = class(Node) // базовый класс для всех выражений
  end;

  IdNode = class(ExprNode)
  public 
    name: string;
    constructor (name: string);
    begin
      Self.name := name;
    end;
  end;

  NumNode = class(ExprNode)
  public 
    num: integer;  
    constructor (num: integer);
    begin
      Self.num := num;
    end;
  end;
  
  StatementNode = class(Node) // базовый класс для всех операторов
  end;  
  
  AssignOpType = lexAssign..lexAssignMult;
  
  AssignNode = class(StatementNode)
  public 
    id: IdNode;
    expr: ExprNode;
    assop: AssignOpType;
    constructor (id: IdNode; expr: ExprNode; assop: AssignOpType);
    begin
      Self.id := id;
      Self.expr := expr;
      Self.assop := assop;
    end;
  end;
  
  CycleNode = class(StatementNode)
  public 
    ex: ExprNode;
    st: StatementNode;
    constructor (ex: ExprNode; st: StatementNode);
    begin
      Self.ex := ex;
      Self.st := st;
    end;
  end;

  StatementList = class
  public 
    stlist: List<StatementNode>;
    constructor ();
    begin
      stlist := new List<StatementNode>();
    end;
    constructor (st: StatementNode);
    begin
      stlist := new List<StatementNode>();
      Add(st);
    end;
    procedure Add(st: StatementNode);
    begin
      stlist.Add(st);
    end;
  end;
  
  BlockNode = class(StatementNode)
  public 
    sl: StatementList;
    constructor (sl: StatementList);
    begin
      Self.sl := sl;
    end;
  end;
  
  ProgrNode = class(Node)
  public 
    body: StatementList;
    constructor (body: StatementList);
    begin
      Self.body := body;
    end;
  end;
  
var root: ProgrNode;
  
end.


Модуль узлов синтаксического дерева на C#

namespace SimpleSynTree
{
    public enum AssignType { Assign, AssignPlus, AssignMinus, AssignMult, AssignDivide };

    public class Node // базовый класс для всех узлов    
    {
    }

    public class ExprNode : Node // базовый класс для всех выражений
    {
    }
    
    public class IdNode : Node
    {
        public string Name { get; set; }
        public IdNode(string name) { Name = name; }
    }

    public class StatementNode : Node // базовый класс для всех операторов
    {
    }

    public class AssignNode: StatementNode
    {
        public IdNode Id { get; set; }
        public ExprNode Expr { get; set; }
        public AssignType AssOp { get; set; }
        public AssignNode (IdNode id, ExprNode expr, AssignType assop)
        {
            Id = id;
            Expr = expr;
            AssOp = assop;
        }
    }

    public class CycleNode : StatementNode
    {
        public ExprNode Expr { get; set; }
        public StatementNode Stat { get; set; }
        public CycleNode(ExprNode expr, StatementNode stat)
        {
            Expr = expr;
            Stat = stat;
        }
    }

    public class StatementList // Это - не узел синтаксического дерева, а вспомогательный узел
    {
        public List<StatementNode> StList = new List<StatementNode>();
        public StatementList(StatementNode stat)
        {
            Add(stat);
        }
        public void Add(StatementNode stat)
        {
            StList.Add(stat);
        }
    }

    public class BlockNode : StatementNode
    {
        public StatementList SL { get; set; }
        public BlockNode(StatementList sl)
        {
            SL = sl;
        }
    }

    public class ProgrNode : BlockNode
    {
        public ProgrNode(StatementList sl): base(sl)
        {            
        }

    }

}

Задания

  1. Добавить семантические действия, строящие дерево программы с корнем root: ProgrNode. Для этого в модуле парсера превратить все процедуры в функции, создающие соответствующие узлы синтаксического дерева
  2. Добавить цикл for в грамматику и узел ForNode в модуль узлов синтаксического дерева
  3. Добавить цикл while в грамматику и узел WhileNode в модуль узлов синтаксического дерева
  4. Добавить оператор if в грамматику и узел IfNode в модуль узлов синтаксического дерева (предусмотреть полную и неполную форму)
  5. Добавить грамматику выражений и узел BinaryOperation с параметрами LeftOperand, RightOperand: Expr и OpType: char.
  6. Добавить оператор вывода в виде print(expr) - print сделать ключевым словом.
  7. По построенному синтаксическому дереву восстановить текст программы, реализовав в каждом классе синтаксического дерева метод ToString
  8. По построенному синтаксическому дереву написать интерпретатор, реализовав в узлах методы Execute (для выполнения операторов) и Evaluate (для вычисления выражений).

Для этого в каждой переменной хранить ее значение целого типа.