Семантические действия в синтаксическом анализаторе. Построение дерева программы
Материал из Вики ИТ мехмата ЮФУ
Для построения дерева программы создадим модуль, включающий все синтаксические узлы программы
Содержание
Модуль узлов синтаксического дерева
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;
Дополнительные задания
- Добавить цикл for в грамматику и узел ForNode в модуль узлов синтаксического дерева
- Добавить цикл while в грамматику и узел WhileNode в модуль узлов синтаксического дерева
- Добавить оператор if в грамматику и узел IfNode в модуль узлов синтаксического дерева (предусмотреть полную и неполную форму)
- Добавить грамматику выражений и узел BinaryOperation с параметрами LeftOperand, RightOperand: Expr и OpType: char.
- Добавить оператор вывода в виде print(expr) - print сделать ключевым словом.
- По построенному синтаксическому дереву написать интерпретатор, реализовав в узлах методы Execute (процедура для выполнения операторов) и Evaluate (функция для вычисления выражений, возвращающая integer) и (на предыдущем занятии должна быть реализована грамматика логических выражений) BoolEvaluate (функция для вычисления логических выражений). Данные методы следует включить как виртуальные в класс Node и вызывать тот или иной метод при необходимости. Для простоты в каждой переменной следует хранить ее значение целого типа.