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

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

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

// Распознавание программы на простом языке. Распознаватель грамматики (парсер)
{ Грамматика:
  progr -> stlist 
  stlist -> st ; stlist | st
  st -> assign | comp | cycl
  assign -> id signa expr
  signa -> := | += | -= | *=
  expr -> id | num
  comp -> begin stlist end
  cycl -> cycle expr st   
}
unit SimpleLangParser1;

interface

procedure Expr;
procedure Assign;
procedure StList;
procedure St; 
procedure Comp;
procedure Cycle;
procedure Progr;
procedure error(message: string := '');

implementation

uses 
  System.Collections.Generic,
  System.IO, 
  SimpleLangLexer1;

procedure Progr;
begin
  StList
end;

procedure StList;
begin
  St;
  while Lex=lexSemicolon do
  begin
    NextLexem;
    St;
  end
end;

procedure St;
begin
  case Lex of
lexBegin: Comp; 
lexCycle: Cycle;
lexId: Assign;
else error('Ожидался оператор');
  end;
end;

procedure Comp;
begin
  NextLexem;
  StList;
  if Lex=lexEnd then
    NextLexem
  else error('Ожидалось end');    
end;

procedure Cycle;
begin
  NextLexem;
  Expr;
  St;
end;

procedure Assign;
begin
  NextLexem;
  if Lex in [lexAssign,lexAssignPlus,lexAssignMinus,lexAssignMult] then
    NextLexem
  else error('Ожидалось :=');  
  Expr;  
end;

procedure Expr;
begin
  if lex in [lexId,lexNum] then
    NextLexem 
  else error('Ожидалось выражение');  
end;

procedure error(message: string);
begin
  var ss := System.IO.File.ReadLines(fname).Skip(LexRow-1).First(); // Строка row файла
  writeln('Синтаксическая ошибка в строке ',LexRow,':');
  writeln(ss);
  writeln('^':LexCol-1);
  if message<>'' then 
    writeln(message);
  Done;  
  halt;
end;
 
end.

Основная программа:

uses SimpleLangLexer1,SimpleLangParser1;

begin 
  Init('progr.txt');
  Progr;
  if Lex=lexEot then
    writeln('программа распознана правильно ')
  else error('ожидался конец файла'); 
end.

Задания

1. Добавить цикл for
2. Добавить простые логические выражения вида x<0 (в лексический анализатор придется добавлять знаки отношений, а в expr - ветку id_or_num relop id_or_num)
3. Добавить грамматику выражений

E ::= T A
A ::= ε | + T A | - T A
T ::= M B
B ::= ε | * M B | / M B
M ::= id | num | (E)

Грамматика составлена так, что по ней можно составить ручной анализатор методом рекурсивного спуска.

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

unit ProgramTree;

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

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

  NumNode = class(ExprNode)
    num: integer;  
    constructor (num: integer);
    begin
      Self.num := num;
    end;
  end;
  
  StatementNode = class(Node) // базовый класс для всех операторов
  end;  
  
  AssignOpType = lexAssign..lexAssignMult;
  
  AssignNode = class(StatementNode)
    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)
    ex: ExprNode;
    st: StatementNode;
    constructor (ex: ExprNode; st: StatementNode);
    begin
      Self.ex := ex;
      Self.st := st;
    end;
  end;

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

5. Добавить семантические действия, строящие дерево программы с корнем root: ProgrNode