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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Модуль синтаксического анализатора (парсера))
Строка 1: Строка 1:
 
[[Страница_курса_%22Методы_построения_компиляторов%22| К основной странице курса]]
 
[[Страница_курса_%22Методы_построения_компиляторов%22| К основной странице курса]]
  
==== Модуль синтаксического анализатора (парсера) ====
+
==== Комментарии к синтаксическому анализатору====  
<source lang="Delphi">
+
Мы пишем синтаксический анализатор методом рекурсивного спуска. Для этого грамматика должна быть праворекурсивной.
// Распознавание программы на простом языке. Распознаватель грамматики (парсер)
+
Начальная грамматика нашего языка имеет вид:
{ Грамматика:
+
Грамматика:
 
   progr -> stlist  
 
   progr -> stlist  
 
   stlist -> st ; stlist | st
 
   stlist -> st ; stlist | st
Строка 13: Строка 13:
 
   block -> begin stlist end
 
   block -> begin stlist end
 
   cycl -> cycle expr st   
 
   cycl -> cycle expr st   
}
+
 
 +
Здесь правило
 +
  stlist -> st ; stlist | st
 +
праворекурсивно. Следует обратить внимание, что точка с запятой разделяет операторы, а не завершает их.
 +
 
 +
Примеры правильных программ в данной грамматике:
 +
<pre>
 +
a := 2
 +
</pre>
 +
 
 +
<pre>
 +
a := 2;
 +
cycle a
 +
begin
 +
  b := a;
 +
  c := 234
 +
end
 +
</pre>
 +
 
 +
==== Модуль синтаксического анализатора (парсера) ====
 +
<source lang="Delphi">
 +
// Распознавание программы на простом языке. Распознаватель грамматики (парсер)
 
unit SimpleLangParserFun;
 
unit SimpleLangParserFun;
  
 
interface
 
interface
 
uses ProgramTree;
 
  
 
procedure Progr;
 
procedure Progr;

Версия 10:14, 28 марта 2013

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

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

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

Грамматика:
 progr -> stlist 
 stlist -> st ; stlist | st
 st -> assign | block | cycl
 assign -> id signa expr
 signa -> := | += | -= | *=
 expr -> id | num
 block -> begin stlist end
 cycl -> cycle expr st   

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

 stlist -> st ; stlist | st

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

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

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

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

// Распознавание программы на простом языке. Распознаватель грамматики (парсер)
unit SimpleLangParserFun;

interface

procedure Progr;
procedure Expr;
procedure Assign;
procedure StatementList;
procedure Statement; 
procedure Block;
procedure Cycle;
procedure error(message: string := '');

implementation

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

procedure Progr;
begin
  StatementList
end;

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

procedure Block;
begin
  NextLexem;
  StatementList;
  if LexKind=lexEnd then
    NextLexem
  else error('Ожидалось end');    
end;

procedure Cycle;
begin
  NextLexem;
  Expr;
  Statement;
end;

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

procedure StatementList;
begin
  Statement;
  while LexKind=lexSemicolon do
  begin
    NextLexem;
    Statement;
  end
end;

procedure Expr;
begin
  if LexKind 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 LexKind=lexEot then
    writeln('программа распознана правильно ')
  else error('ожидался конец файла'); 
end.

Задания

  1. Добавить цикл for
  2. Добавить простые логические выражения вида x<0 (в лексический анализатор придется добавлять знаки отношений, а в expr - ветку id_or_num relop id_or_num)
  3. Добавить оператор if (предусмотреть полную и неполную форму)
  4. Добавить оператор while
  5. Добавить грамматику выражений
E ::= T A
A ::= ε | + T A | - T A
T ::= M B
B ::= ε | * M B | / M B
M ::= id | num | (E)

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