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

+[ К основной странице курса](Страница_курса_%22Методы_построения_компиляторов%22 "wikilink") \_\_NOTOC\_\_
+
+### Комментарии к синтаксическому анализатору
+
+Мы пишем синтаксический анализатор **методом рекурсивного спуска**. Для этого грамматика должна быть *праворекурсивной*.
+
+Грамматика нашего языка имеет вид:
+
+` 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`
+
+праворекурсивно. Следует обратить внимание, что точка с запятой разделяет операторы, а не завершает их.
+
+Примеры правильных программ в данной грамматике:
+
+``` Delphi
+begin
+  a := 2
+end
+```
+
+``` Pascal
+begin
+  a := 2;
+  cycle a
+  begin
+    b := a;
+    c := 234
+  end
+end
+```
+
+``` Pascal
+begin
+  b := 2
+end
+```
+
+Примеры неправильных программ в данной грамматике:
+
+    a := 2;
+
+    begin
+      b := 2
+    end.
+
+При написании синтаксического анализатора методом рекурсивного спуска следует для каждого нетерминала реализовать процедуру, которая будет распознавать этот нетерминал. При реализации необходимо придерживаться следующей стратегии: перед вызовом каждой процедуры для нетерминала считается, что первая лексема уже считана с помощью NextLexem. Кроме того, каждая процедура после распознавания своей конструкции считывает следующую лексему с помощью NextLexem, подготавливая вызов следующей процедуры.
+
+Ошибки, распознаваемые синтаксическим анализатором, называются **синтаксическими** и выводятся вызовом процедуры syntaxerror.
+
+Отметим также, что приведенный парсер (синтаксический анализатор) не выполняет никаких семантических действий - он только распознает, принадлежит ли программа языку, порождаемому данной грамматикой.
+
+### Модуль синтаксического анализатора (парсера)
+
+``` Delphi
+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.
+```
+
+#### Основная программа
+
+``` Delphi
+uses SimpleLangLexer,SimpleLangParser;
+ 
+begin 
+  Init('progr.txt');
+  Progr;
+  if LexKind=Tok.EOF then
+    writeln('программа распознана правильно ')
+  else syntaxerror('ожидался конец файла'); 
+end.
+```
+
+#### Основные задания (7 баллов)
+
+1.  Добавить оператор WHILE expr DO statement(в лексический анализатор - добавлять новые ключевые слова) **(3 балла)**
+2.  Добавить оператор FOR ID := expr TO expr DO statement(в лексический анализатор - добавлять новые ключевые слова) **(4 балла)**
+
+#### Дополнительные задания (7 баллов)
+
+1.  Добавить оператор IF expr THEN stat ELSE stat (предусмотреть полную и неполную форму оператора) (3 балла)
+2.  Добавить грамматику выражений (4 балла)
+
+`E ::= T A`
+`A ::= ε | + T A | - T A`
+`T ::= M B`
+`B ::= ε | * M B | / M B`
+`M ::= id | num | (E)`
+
+Грамматика составлена так, что по ней можно составить ручной анализатор методом рекурсивного спуска.