Семантические действия в синтаксическом анализаторе. Построение дерева программы — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Admin (обсуждение | вклад) (→Модуль узлов синтаксического дерева) |
Admin (обсуждение | вклад) (→Модуль узлов синтаксического дерева на C#) |
||
(не показано 18 промежуточных версий этого же участника) | |||
Строка 16: | Строка 16: | ||
end; | end; | ||
− | IdNode = class(ExprNode) | + | IdNode = class(ExprNode) |
+ | public | ||
name: string; | name: string; | ||
constructor (name: string); | constructor (name: string); | ||
Строка 25: | Строка 26: | ||
NumNode = class(ExprNode) | NumNode = class(ExprNode) | ||
+ | public | ||
num: integer; | num: integer; | ||
constructor (num: integer); | constructor (num: integer); | ||
Строка 38: | Строка 40: | ||
AssignNode = class(StatementNode) | AssignNode = class(StatementNode) | ||
+ | public | ||
id: IdNode; | id: IdNode; | ||
expr: ExprNode; | expr: ExprNode; | ||
Строка 50: | Строка 53: | ||
CycleNode = class(StatementNode) | CycleNode = class(StatementNode) | ||
+ | public | ||
ex: ExprNode; | ex: ExprNode; | ||
st: StatementNode; | st: StatementNode; | ||
Строка 60: | Строка 64: | ||
StatementList = class | StatementList = class | ||
+ | public | ||
stlist: List<StatementNode>; | stlist: List<StatementNode>; | ||
constructor (); | constructor (); | ||
Строка 68: | Строка 73: | ||
begin | begin | ||
stlist := new List<StatementNode>(); | stlist := new List<StatementNode>(); | ||
+ | Add(st); | ||
+ | end; | ||
+ | procedure Add(st: StatementNode); | ||
+ | begin | ||
stlist.Add(st); | stlist.Add(st); | ||
end; | end; | ||
Строка 73: | Строка 82: | ||
BlockNode = class(StatementNode) | BlockNode = class(StatementNode) | ||
+ | public | ||
sl: StatementList; | sl: StatementList; | ||
constructor (sl: StatementList); | constructor (sl: StatementList); | ||
Строка 81: | Строка 91: | ||
ProgrNode = class(Node) | ProgrNode = class(Node) | ||
− | body: | + | public |
− | constructor (body: | + | body: StatementList; |
+ | constructor (body: StatementList); | ||
begin | begin | ||
Self.body := body; | Self.body := body; | ||
Строка 93: | Строка 104: | ||
− | ''' | + | ==== Модуль узлов синтаксического дерева на C#==== |
+ | |||
+ | <source lang="CSharp">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) | ||
+ | { | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | } | ||
+ | </source> | ||
+ | |||
+ | ====Задания==== | ||
+ | |||
+ | =====Основное задание===== | ||
+ | Добавить семантические действия, строящие дерево программы с корнем root: ProgrNode. Для этого в модуле парсера превратить все процедуры в функции, создающие соответствующие узлы синтаксического дерева. Для примера приводится преобразованная к нужному виду процедура Assign: | ||
+ | |||
+ | <source lang="Delphi">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;</source> | ||
+ | По построенному синтаксическому дереву восстановить текст программы, реализовав в каждом классе синтаксического дерева метод Print. Для примера приводится метод Print для AssignNode: | ||
+ | |||
+ | <source lang="Delphi">type AssignNode = class | ||
+ | procedure Print; override; | ||
+ | begin | ||
+ | id.Print; | ||
+ | case AssOp of | ||
+ | lexAssign: write(':='); | ||
+ | ... | ||
+ | end; | ||
+ | expr.Print; | ||
+ | writeln; | ||
+ | end; | ||
+ | end;</source> | ||
− | + | =====Дополнительные задания===== | |
# Добавить цикл for в грамматику и узел ForNode в модуль узлов синтаксического дерева | # Добавить цикл for в грамматику и узел ForNode в модуль узлов синтаксического дерева | ||
# Добавить цикл while в грамматику и узел WhileNode в модуль узлов синтаксического дерева | # Добавить цикл while в грамматику и узел WhileNode в модуль узлов синтаксического дерева | ||
# Добавить оператор if в грамматику и узел IfNode в модуль узлов синтаксического дерева (предусмотреть полную и неполную форму) | # Добавить оператор if в грамматику и узел IfNode в модуль узлов синтаксического дерева (предусмотреть полную и неполную форму) | ||
# Добавить грамматику выражений и узел BinaryOperation с параметрами LeftOperand, RightOperand: Expr и OpType: char. | # Добавить грамматику выражений и узел BinaryOperation с параметрами LeftOperand, RightOperand: Expr и OpType: char. | ||
− | # | + | # Добавить оператор вывода в виде print(expr) - print сделать ключевым словом. |
− | # По построенному синтаксическому дереву написать интерпретатор, реализовав в узлах методы Execute и Evaluate. | + | # По построенному синтаксическому дереву написать интерпретатор, реализовав в узлах методы Execute (процедура для выполнения операторов) и Evaluate (функция для вычисления выражений, возвращающая integer) и (на предыдущем занятии должна быть реализована грамматика логических выражений) BoolEvaluate (функция для вычисления логических выражений). Данные методы следует включить как виртуальные в класс Node и вызывать тот или иной метод при необходимости. Для простоты в каждой переменной следует хранить ее значение целого типа. |
Текущая версия на 20:49, 19 мая 2013
Для построения дерева программы создадим модуль, включающий все синтаксические узлы программы
Содержание
Модуль узлов синтаксического дерева
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 и вызывать тот или иной метод при необходимости. Для простоты в каждой переменной следует хранить ее значение целого типа.