Создание синтаксического анализатора простого языка программирования — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Admin (обсуждение | вклад) (→Модуль синтаксического анализатора (парсера)) |
Admin (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
[[Страница_курса_%22Методы_построения_компиляторов%22| К основной странице курса]] | [[Страница_курса_%22Методы_построения_компиляторов%22| К основной странице курса]] | ||
− | ==== | + | ==== Комментарии к синтаксическому анализатору==== |
− | + | Мы пишем синтаксический анализатор методом рекурсивного спуска. Для этого грамматика должна быть праворекурсивной. | |
− | + | Начальная грамматика нашего языка имеет вид: | |
− | + | Грамматика: | |
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 | ||
− | |||
− | |||
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.
Задания
- Добавить цикл for
- Добавить простые логические выражения вида x<0 (в лексический анализатор придется добавлять знаки отношений, а в expr - ветку id_or_num relop id_or_num)
- Добавить оператор if (предусмотреть полную и неполную форму)
- Добавить оператор while
- Добавить грамматику выражений
E ::= T A A ::= ε | + T A | - T A T ::= M B B ::= ε | * M B | / M B M ::= id | num | (E)
Грамматика составлена так, что по ней можно составить ручной анализатор методом рекурсивного спуска.