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

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

Комментарии к синтаксическому анализатору

Мы пишем синтаксический анализатор методом рекурсивного спуска. Для этого грамматика должна быть праворекурсивной.

Грамматика нашего языка имеет вид:

 progr -> block 
 stlist -> statement ; stlist | statement
 statement -> assign | block | cycl
 assign -> ID := expr
 expr -> ID | INUM
 block -> BEGIN stlist END
 cycl -> CYCLE expr st   

Здесь правило

 stlist -> statement ; stlist | statement

праворекурсивно. Следует обратить внимание, что точка с запятой разделяет операторы, а не завершает их.

Примеры правильных программ в данной грамматике:

begin
  a := 2
end

begin
  a := 2;
  cycle a
  begin
    b := a;
    c := 234
  end
end

begin
  b := 2
end

Примеры неправильных программ в данной грамматике:

a := 2;

begin
  b := 2
end.

При написании синтаксического анализатора методом рекурсивного спуска следует для каждого нетерминала реализовать процедуру, которая будет распознавать этот нетерминал. При реализации необходимо придерживаться следующей стратегии: перед вызовом каждой процедуры для нетерминала считается, что первая лексема уже считана с помощью NextLexem. Кроме того, каждая процедура после распознавания своей конструкции считывает следующую лексему с помощью NextLexem, подготавливая вызов следующей процедуры.

Ошибки, распознаваемые синтаксическим анализатором, называются синтаксическими и выводятся вызовом процедуры syntaxerror.

Отметим также, что приведенный парсер (синтаксический анализатор) не выполняет никаких семантических действий - он только распознает, принадлежит ли программа языку, порождаемому данной грамматикой.

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

unit SimpleLangParser;
 
interface
 
procedure Progr;
procedure Expr;
procedure Assign;
procedure StatementList;
procedure Statement; 
procedure Block;
procedure Cycle;
procedure syntaxerror(message: string := '');
 
implementation
 
uses 
  SimpleLangLexer;
 
procedure Progr;
begin
  Block
end;
 
procedure Statement;
begin
  case LexKind of
Tok.&Begin: Block; 
Tok.Cycle: Cycle;
Tok.Id: Assign;
else syntaxerror('Ожидался оператор');
  end;
end;
 
procedure Block;
begin
  NextLexem; // Пропуск begin
  StatementList;
  if LexKind=Tok.&End then
    NextLexem
  else syntaxerror('Ожидалось end');    
end;
 
procedure Cycle;
begin
  NextLexem; // Пропуск cycle
  Expr;
  Statement;
end;
 
procedure Assign;
begin
  NextLexem; // Пропуск id
  if LexKind = Tok.ASSIGN then
    NextLexem
  else syntaxerror('Ожидалось :=');  
  Expr;  
end;
 
procedure StatementList;
begin
  Statement;
  while LexKind=Tok.SEMICOLON do
  begin
    NextLexem;
    Statement;
  end
end;
 
procedure Expr; // Выражение - это id или num
begin
  if LexKind in [Tok.ID,Tok.INUM] then
    NextLexem 
  else syntaxerror('Ожидалось выражение');  
end;
 
procedure syntaxerror(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 SimpleLangLexer,SimpleLangParser;
 
begin 
  Init('progr.txt');
  Progr;
  if LexKind=Tok.EOF then
    writeln('программа распознана правильно ')
  else syntaxerror('ожидался конец файла'); 
end.

Основные задания (7 балла)

1. Добавить оператор WHILE expr DO statement(в лексический анализатор - добавлять новые ключевые слова) (1 балл)
2. Добавить оператор FOR ID := expr TO expr DO statement(в лексический анализатор - добавлять новые ключевые слова) (1 балл)

Дополнительные задания (5 баллов)

1. Добавить оператор IF expr THEN stat ELSE stat (предусмотреть полную и неполную форму оператора) (2 балла)
2. Добавить грамматику выражений (3 балла)

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

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