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

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

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

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

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

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 : ExprNode
    {
        public string Name { get; set; }
        public IdNode(string name) { Name = name; }
    }

    public class NumNode : ExprNode
    {
        public int Num { get; set; }
        public NumNode(int num) { Num = num; }
    }

    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)
        {            
        }

    }

}

Задания

Основное задание

Добавить семантические действия, строящие дерево программы с корнем root: ProgrNode. Для этого в модуле парсера превратить все процедуры в функции, создающие соответствующие узлы синтаксического дерева. Для примера приводится преобразованная к нужному виду процедура Assign:

function Assign: AssignNode;
begin
  var Id := new IdNode(LexText);
  NextLexem; 
  if LexKind in [lexAssign..lexAssignMult] then
  begin
    var AssOp := ConvertToAssOp(LexKind); 
    NextLexem
  end
  else syntaxerror('Ожидалось :=');  
  var Ex := Expr;  
  Result := new AssignNode(ID,AssOp,Ex);
end;

По построенному синтаксическому дереву восстановить текст программы, реализовав в каждом классе синтаксического дерева метод Print. Для примера приводится метод Print для AssignNode:

type AssignNode = class
  procedure Print; override;
  begin
    id.Print;
    case AssOp of
  lexAssign: write(':=');  
  ...
    end;
    expr.Print;
    writeln;
  end;
end;
Дополнительные задания
  1. Добавить цикл for в грамматику и узел ForNode в модуль узлов синтаксического дерева
  2. Добавить цикл while в грамматику и узел WhileNode в модуль узлов синтаксического дерева
  3. Добавить оператор if в грамматику и узел IfNode в модуль узлов синтаксического дерева (предусмотреть полную и неполную форму)
  4. Добавить грамматику выражений и узел BinaryOperation с параметрами LeftOperand, RightOperand: Expr и OpType: char.
  5. Добавить оператор вывода в виде print(expr) - print сделать ключевым словом.
  6. По построенному синтаксическому дереву написать интерпретатор, реализовав в узлах методы Execute (процедура для выполнения операторов) и Evaluate (функция для вычисления выражений, возвращающая integer) и (на предыдущем занятии должна быть реализована грамматика логических выражений) BoolEvaluate (функция для вычисления логических выражений). Данные методы следует включить как виртуальные в класс Node и вызывать тот или иной метод при необходимости. Для простоты в каждой переменной следует хранить ее значение целого типа.