Создание синтаксического анализатора простого языка программирования
Комментарии к синтаксическому анализатору
Мы пишем синтаксический анализатор методом рекурсивного спуска. Для этого грамматика должна быть праворекурсивной.
Грамматика нашего языка имеет вид:
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 баллов)
- Добавить оператор WHILE expr DO statement(в лексический анализатор - добавлять новые ключевые слова) (3 балла)
- Добавить оператор FOR ID := expr TO expr DO statement(в лексический анализатор - добавлять новые ключевые слова) (4 балла)
Дополнительные задания (7 баллов)
- Добавить оператор IF expr THEN stat ELSE stat (предусмотреть полную и неполную форму оператора) (3 балла)
- Добавить грамматику выражений (4 балла)
E ::= T A A ::= ε | + T A | - T A T ::= M B B ::= ε | * M B | / M B M ::= id | num | (E)
Грамматика составлена так, что по ней можно составить ручной анализатор методом рекурсивного спуска.