Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Знакомство с генераторами лексических и синтаксических анализаторов lex и yacc - файл sasw-6-full.txt


Загрузка...
Знакомство с генераторами лексических и синтаксических анализаторов lex и yacc
скачать (274.2 kb.)

Доступные файлы (3):

sasw-6-full.doc448kb.12.05.2009 13:48скачать
sasw-6-full.pdf245kb.07.04.2009 16:42скачать
sasw-6-full.txt41kb.14.06.2009 16:55скачать

sasw-6-full.txt






Лабораторные работы по курсу СППО






1



1	Знакомство с генераторами лексических и синтак-
сических анализаторов lex и yacc

1	Введение

Задача создания эффективных анализаторов исходного кода возникла вместе с пер-
вым компилятором. С тех пор прошло много времени, и появилась мощная теория,
позволившая автоматизировать рутинный процесс написания однообразных конеч-
ных автоматов. Программирование анализаторов исходного кода может быть полезно
в учебных или исследовательских целях, но для анализа реальных языков  С++,
Python или SQL  в настоящее время используют исключительно автоматические
средства генерации лексических и синтаксических анализаторов. Далее речь пойдет
только о них: lex и yacc.


2	Установка

Поскольку изначально lex и yacc были проприетарными программами, Сообщество
разработало их свободные аналоги: ?ex и bison.
Установка программ происходит очень просто:

# apt-get install ?ex ?ex-doc bison bison-doc

Как только команда apt-get завершит свою работу, ?ex и bison готовы к использова-
нию.
Если по какой-то причине ваша ОС не использует пакетный менеджер APT, обрати-
тесь к документации пакетного менеджера вашей системы, чтобы найти и установить
эти пакеты.


3	?ex

?ex означает fast lex, и он является генератором лексических анализаторов. Ни для
кого не секрет, что программы на языках программирования состоят не из букв
и цифр, но из более крупных единиц  лексем. Лексемы очень удобно задавать
при помощи регулярных выражений. Например, идентификатор программы любого
языка можно описать так:

[A–Za–z_][A–Za–z0–9_]*

Это выражение означает, что идентификатор должен состоять как минимум из одной
буквы или знака подчеркивания, после которой может стоять сколько угодно букв,
цифр или знаков подчеркивания.







Лабораторные работы по курсу СППО






2



?ex предназначен для генерации программлексических анализаторов на языках C
и C++. В самом простом случае такой анализатор, встретив очередную лексему,
просто возвращает ее числовой код. В более сложных случаях анализатор совершает
некоторое действие над лексемой, например, преобразует последовательность цифр
в число.
Как правило, ?ex используется совместно с генератором синтаксических анализато-
ров bison.


4	bison

bison является генератором синтаксических анализаторов, полностью совместимым
с yacc.
Синтаксический анализатор получает на вход поток лексем и проверяет их на соот-
ветствие некоторой контекстно-свободной грамматике. Грамматика в bison описыва-
ется в БНФ:
assignment : NAME ’=’ expr ’;’

По традиции нетерминальные символы грамматики записываются строчными бук-
вами, терминальные  прописными или выделяются кавычками.
bison предназначен для генерации программсинтаксических анализаторов на язы-
ках C, C++ и Java. В самом простом случае такой анализатор просто проверяет поток
лексем на соответствие указанной грамматике. В более сложных случаях анализатор
может выполнять некоторые действия, например, вычислять значения математиче-
ских выражений или строить деревья.
Как правило, bison используется совместно с генератором лексических анализаторов
?ex.


5	Проектирование калькулятора

Теперь самое время перейти от абстрактного описания инструментов к реальному
примеру. Реальным примером будет несложный калькулятор. От простого кальку-
лятора	его отличает наличие скобок в выражениях и именованные величины, то
есть константы и переменные. Константность объекта является, как в C++, посто-
янным свойством. Это означает, что переменную нельзя превратить в константу,
а константу  в переменную. Однако любую величину можно скопировать в любую
переменную или создать новую константу со значением любого выражения, содер-
жащего как константы, так и переменные. Это важно для понимания грамматики
и поведения калькулятора.
Грамматика калькулятора имеет следующий вид:










1	program ::= ?






Лабораторные работы по курсу СППО






3

2
3
4
5

| CONST NAME = expr
| NAME = expr
| expr

6	expr ::= expr + expr

7
8
9

| expr ? expr
| expr ? expr
| expr / expr

10	| ?expr
11	| (expr)
12	| term
13
14	term ::= NUMBER
15	| NAME
Итак, программой калькулятора может быть пустая строка. В этом случае значение
выражения не определено и считается равным нулю.
Кроме того программа калькулятора может сохранять значения в переменных или
константах. Константа создается при помощи ключевого слова const, переменная
создается (или изменяется) просто фактом своего присутствия слева. В этом случае
значением всего выражения является значение его левой части.
Интерес представляет необычное опи-
сание математических действий. Обыч-

но предполагается, что операторы низ-
кого приоритета описываются в одном
правиле, операторы высокого  в дру-
гом, причем операндами операций низ-
кого приоритета служат как раз нетер-
миналы с операторами высокого. Одна-
ко на практике писать такие грамма-
тики нелегко, поэтому был найден спо-








имена

Интерфейс



Драйвер



ошибки




ошибки

соб решить проблему приоритета иным
способом. Это будет описано в дальней-
шем.
Сами выражения состоят термов, кото-
рыми являются числа и имена. Регу-
лярные выражения этих лексем можно
увидеть в разделе ѕЛексический анализаторї.

Синтаксический анализатор



Лексический анализатор

Функционально калькулятор состоит из 4-х частей: интерфейса, драйвера, синтак-
сического и лексического анализаторов.







Лабораторные работы по курсу СППО


Основным языком программы является C++. Идеи навеяны главой 6 книги [cpp].


6	Драйвер






4


Драйвер является надстройкой над синтаксическим анализатором. Он предназначен
для хранения результата, значений величин и сообщений об ошибках.
Можно обойтись и без драйвера, bison это позволяет сделать. Но это неудобно по
ряду причин. Во-первых, синтаксический анализатор является классом, интерфейс
(и внутренности) которого менять нельзя. Во-вторых, глобальное пространство имен
засорится типами и глобальными переменными, использование которых неизбежно,
что крайне нежелательно.
Теперь рассмотрим класс драйвера более детально.
8	#include "parser.hpp"

Восьмая строка подключает заголовок, генерируемый bison-ом. В нем находится
класс Parser, который осуществляет синтаксический анализ.
10	#de?ne YY_DECL \
11	yy::Parser::token_type \
12	yylex(yy::Parser::semantic_type? yylval, yy::Parser::location_type? yylloc)
13
14	YY_DECL;

В строках 10–14 помещено объявление функции лексического анализа. Эта функция
объявлена в виде макроса YY_DECL, как это требуется соглашениями о вызовах
между bison и ?ex.
Аргументами функции являются лексема и ее местоположение во входном потоке.
Функция возвращаем тип лексемы.
16	class Driver
17	{
18	friend class yy::Parser;
Со строки 16 начинается собственно объявление драйвера. Класс yy::Parser, генери-
руемый bison-ом, объявлен дружественным. Это вызвано тем обстоятельством, что
таблица символов по архитектурным соображениям является закрытой, а синтакси-
ческий анализатор должен иметь к ней полный доступ.
20	public:
21	class Error
22	{
23	private:

24

int from_;










25









int to_;






Лабораторные работы по курсу СППО






5

26
27

std::string message_;

28	public:

29
30
31
32
33
34
35

Error() {}
Error(const std::string& m) : from_(0), to_(0), message_(m) {}
Error(int f, int t, const std::string& m) : from_(f), to_(t), message_(m) {}

int from() const { return from_; }
int to() const { return to_; }
const std::string& message() const { return message_; }

36	};

Далее идет описание класса Error. Этот класс хранит текстовое описание ошибки
и позиции в исходной строке, где эта ошибка встретилась.
В данном случае обработка ошибок заключается просто в прекращении дальней-
шего анализа строки. Драйвер хранит последнюю ошибку. Альтернативой было бы
использование исключений, никаких препятствий этому нет.
38	private:
39	struct Value
40	{

41
42
43
44
45

bool is_const;
double value;

static Value constant(double v) { Value r = { true, v }; return r; }
static Value variable(double v) { Value r = { false, v }; return r; }

46	};
47	typedef std::map Symbols;
48
49	Symbols symbols;

Строки 38–49 содержат описание таблицы символов. Каждый символ имеет (неизме-
няемый) признак константности и значение. Статические функции constant и variable
предназначены для удобства написания исходного кода.
Сама таблица символов является словарем имен.
51	double result_;
52	bool hasError_;
53	Error error_;

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










Driver и yy::Parser.






Лабораторные работы по курсу СППО






6

24	int Driver::parse(const std::string& s)
25	{
26	hasError_ = false;
27	YY_BUFFER_STATE bu? = yy_scan_string(s.c_str());
28	if(!bu?)
29	{

30
31
32	}
33

setError("a?problem?occured?while?reading?a?string");
return ?1;

34	yy::Parser parser(?this);
35
36	result_ = 0;
37	int res = parser.parse();
38	yy_delete_bu?er(bu?);
39	return res;
40	}

В строках 24–40 файла driver.cpp находится определение функции parse().
По умолчанию анализаторы читают символы из файла yyin. Но описанная функ-
ция предполагает считывать данные из строки. Для этого необходимо создать де-
скриптор при помощи функции yy_scan_string(). После завершения анализа строки
дескриптор необходимо уничтожить функцией yy_delete_bu?er().
Класс yy::Parser содержит в интерфейсе функцию parse(). Эта функция возвращает
0 в случае успеха и отличное от 0 значение при ошибке.
Исходный код драйвера находится в файлах driver.h и driver.cpp.


7	Синтаксический анализатор

Описание синтаксического анализатора находится в файле

%{
Пролог
%}
Объявления bison-а
%%
Правила грамматики
%%
Эпилог

parser.y. Этот файл состоит из трех разделов: пролога, пра-
вил грамматики и эпилога. Кратко рассмотрим назначение
каждого раздела и работу генератора синтаксических ана-
лизаторов bison в целом.
Программа bison генерирует исходный файл на одном из
языков: C, C++ или Java. Далее речь пойдет исключитель-
но о языке C++, но генерация файлов на других языках
выполняется аналогично.
В случае языка C++ bison генерирует файл, содержащий







Лабораторные работы по курсу СППО






7



класс в пространстве имен yy. Имя класса можно менять,
в данном случае класс называется Parser.
Общий принцип работы bison-а таков: при помощи программы m4 bison создает ис-
ходные файлы на языке C++. При этом в начало определения класса и в заголовоч-
ный файл помещаются строки из пролога. Также пролог содержит настройки для
bison-а: имя класса, аргументы функций, типы, лексемы и пр. Основная часть клас-
са, то есть функция yy::Parser::parse(), генерируется на основе правил грамматики.
В конец определения класса помещаются строки из эпилога.
Теперь подробно рассмотрим файл parser.y.
23	%language "C++"
24	%skeleton "lalr1.cc" /? ???C++??? ?/
25	%de?nes
26	%de?ne parser_class_name "Parser"

В первых строках пролога содержится указание целевого языка, шаблон (параметр
%skeleton) и константы. Одной из констант является имя класса, которое здесь при-
нимает значение ѕParserї.
37	%parse?param { Driver& driver }
Параметр parse-param содержит аргументы для функции yyparse(), если программа
генерирует анализатор на языке C, или для конструктора класса Parser, как в данном
случае.
39	%locations

Этот параметр включает трассировку. Каждая лексема снабжается информацией
о местоположении в анализируемом файле. Трассировка замедляет анализ, но зато
позволяет более детально информировать пользователя о ходе разбора и возникаю-
щих ошибках.
41	%union {
42	double value;
43	std::string? name;
44	}

Строки 41–44 содержит описание семантического типа yy::Parser::semantic_type, он
же YYSTYPE. Этот тип представляет собой объединение. В данном случае объеди-
нение содержит два поля: для числовых значений и для имен. Имя определено как
указатель на строку. Это не ограничение bison-а, это ограничение C++1.
1Дело в том, что любой класс имеет свою внутреннюю структуру, которая создается при вызове
конструктора объекта. Запись в поле value разрушила бы структуру name, если бы name был объ-
ектом. Это как минимум вызвало бы утечку ресурсов, а в худшем случае нарушение прав доступа
при вызове деструктора объекта. По этой причине объекты не могут быть членами объединений.










46	%code {






Лабораторные работы по курсу СППО






8

47	#include 
48
49	#include "driver.h"
50
51	typedef std::auto_ptr StringPtr;
52	}

Секция code содержит код, помещаемый перед определением класса. Синтаксиче-
скому анализатору необходимо знать структуру класса Driver, чтобы обращаться
к таблице символов.
В строке 51 объявлен синоним типа auto_ptr. Выше упоминалось, что одним из чле-
нов объединения является указатель на строку. Функции, работающие с объединени-
ем, должны освобождать занятые ресурсы. Конечно, в примитивном случае можно
вызвать оператор delete, и это сработает. Но как будет видно дальше, функции име-
ют несколько точек выхода. В таких случаях гораздо эффективнее использовать
один из классов с автоматической сборкой мусора (или создать свой), чем вызывать
оператор delete перед каждой точкой выхода2.
54	%token CONST "const"
55	%token END 0 "end?of??le"
56	%token INVALID_CHARACTER "invalid?character"
57	%token NOT_A_NUMBER "not?a?number"
58
59	%token  NAME "identi?er"
60	%token  NUMBER "number"

Строки 54–60 содержат самое интересное (после описания правил грамматики): опи-
сание лексем. Описание лексемы начинается со слова %token, после чего может идти
тип лексемы в терминах YYSTYPE, ее символьное значение, необязательное число-
вое значение (лексема END по соглашению должна быть равна 0) и строку с удобным
описанием лексемы. Последнее позволяет bison-у более понятно сообщать об ошиб-
ках.
Все символьные константы помещаются в структуре yy::Parser::token. Это важно
помнить при написании лексического анализатора.
62	%type  expr term

Генерируемые bison-ом функции могут возвращать значения разных типов. В данном
случае типы выражений и термов определяются как value, то есть число.
2Конечно, можно оставить одну точку выхода, однако пострадает понятность исходного кода.
Кроме того, даже в этом случае нет гарантии освобождения ресурсов при внезапно возникшем
исключении.







Лабораторные работы по курсу СППО


64	%destructor { delete $$; } "identi?er"






9


Параметр %destructor описывает действия по уничтожению того или иного типа.
Если возвращаемым значением функции является идентификатор, то его необходимо
уничтожить вызовом оператора delete.
66	%error?verbose
Этот параметр включает подробные сообщения об ошибках.
На этом пролог заканчивается и начинается описание правил грамматики.
70	%start program;
71	program : /? nothing ?/ {}
72	| CONST NAME ’=’ expr { StringPtr p($2);

73
74
75

76
77
78
79
80
81
82
83
84
85
86
87
88
89
90	}

if(driver.symbols.?nd(?p) == driver.symbols.end())
{
driver.symbols.insert(Driver::Symbols::value_type(?p,
Driver::Value::constant($4)));
driver.result_ = $4;
}
else
{
std::ostringstream msg;
msg << "cannot?rebind?’" << ?p << "’";

yy::location l;
l.begin = @1.begin;
l.end = @3.end;

error(l, msg.str());
YYABORT;
}


Bison строит анализатор по схеме LALR(1). Синтаксический анализатор представ-
ляет собой конечный автомат. Автомату необходимо начальное значение. Строка 70
устанавливает это значение.
Правила грамматики, как видно из примера, описываются в виде БНФ, причем после
правила следует собственно действие, соответствующее правилу. Поскольку грамма-
тика допускает пустое правило, то строка 71 содержит просто фигурные скобки без
какого-либо кода.
Зато альтернатива ѕCONST NAME ‘=’ exprї содержит куда больше кода.
Здесь надо отметить, что функция принимает число аргументов, равное числу лексем







Лабораторные работы по курсу СППО


в правой части правила. Каждый аргумент описывается в виде $n:






10


$1


$2


$3	$4

CONST NAME ’=’	expr

Возвращаемое функцией значение описывается как $$. Правило program ничего не воз-
вращает, поэтому значение $$ в нем не используется.
Что касается самой функции, то ее действия описываются просто. По условию кон-
стантность величины не может быть изменена, поэтому функция осуществляет поиск
имени $2 в таблице символов. Если это имя уже есть в таблице, то функций про-
сто завершается с ошибкой (макрос YYABORT в строке 120). В противном случае
в таблицу добавляется новая константа, а переменная result_ драйвера получает ее
значение. Класс StringPtr позволяет не заботиться об освобождении ресурсов в двух
точках выхода (а их тут именно	две). Компилятор вызовет деструктор объекта p
в необходимый момент.
Остальные альтернативы правила program мало отличаются от описанной, поэтому
нет смысла подробно рассматривать их.
119	%left ’+’ ’?’;
120	%left ’?’ ’/’;
121	%right UMINUS;
122	expr : expr ’+’ expr { $$ = $1 + $3; }

123
124
125
126
127
128
129
130
131
132
133
134
135
136	;

| expr ’?’ expr { $$ = $1 ? $3; }
| expr ’?’ expr { $$ = $1 ? $3; }
| expr ’/’ expr { if($3)
$$ = $1 / $3;
else
{
error(@3, "division?by?zero");
YYABORT;
}
}
| ’?’ expr %prec UMINUS { $$ = ?$2; }
| ’(’ expr ’)’ { $$ = $2; }
| term { $$ = $1; }


Правило expr описывает арифметические действия: сложение, вычитание, умноже-
ние, деление, смену знака и скобки. Выполняемые действия тривиальны. Некоторый
интерес представляет операция деления. В случае равенства нулю правого операнда
($3) происходит вызов функции-члена yy::Parser::error(), причем первым параметром
этой функции является @3. Параметры вида @nдоступны только при включенной







Лабораторные работы по курсу СППО






11



опции %locations и содержат местоположение данной лексемы. В случае попытки
деления на 0 синтаксический анализатор точно укажет недопустимое (т. е. нулевое)
подвыражение.
Правило expr описывает все действия невзирая на их приоритет. Все дело в строках
119–121, в которых описаны приоритет и ассоциативность операций. Чем ниже по
коду описана операция, тем выше ее приоритет. Аддитивные и мультипликативные
операции левоассоциативны, тогда как унарный минус правоассоциативен.
Приоритеты специально введены для удобства описания математических выраже-
ний.
138	term : NUMBER { $$ = $1; }

139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156	;

| NAME { StringPtr p($1);
Driver::Symbols::const_iterator i = driver.symbols.?nd(?p);
if(i != driver.symbols.end())
$$ = i?>second.value;
else
{
std::ostringstream msg;
msg << "unde?ned?symbol?’" << ?p << "’";
error(@1, msg.str());
YYABORT;
}
}
| INVALID_CHARACTER { YYABORT; }
| NOT_A_NUMBER {
error(@1, "not?a?number");
YYABORT;
}

В правиле term наибольший интерес представляют две последние альтернативы:
INVALID_CHARACTER и NOT_A_NUMBER. Они предназначены только для од-
ного: обработки ошибок лексического анализатора. Дело в том, что функция yylex()
возвращает целое числономер лексемы. Поэтому единственный способ передать
ѕнаверхї сообщение об ошибке  определить специальную лексему. Еще один спо-
соб заключается в возбуждении исключения.
160	void yy::Parser::error(const yy::Parser::location_type& l, const std::string& m)
161	{

162
163	}

driver.setError(l.begin.column, l.end.column, m);

В эпилоге определена функция-член error(). Эта функция обязательно должна быть







Лабораторные работы по курсу СППО






12



определена программистом. В данном случае функция просто передает ошибку драй-
веру.



8	Лексический анализатор

Структура входного файла лексического анализатора также состоит из трех частей.
Первая часть файла содержит разнообразные настройки ?ex-а,

Определения
%%
Правила
%%
Код

определения регулярных выражений и исходный код, помещае-
мый перед кодом анализатора. Вторая часть содержит сами пра-
вила и соответствующие им действия. Как правило, действия
заключаются в возврате той или иной символьной константы.
Последняя часть файла содержит код функций, помещаемых по-
сле кода лексического анализатора. Например, там может быть
функция main(), если программа небольшая.

Теперь рассмотрим файл scanner.l, который содержит исходный код сканера, подроб-
нее.
1	%option 8bit
2	%option noyywrap
3	%option warn

Файл начинается с настроек генератора ?ex. Здесь указано использование 8-битной
кодировки (можно выбрать и 7-битную), отказ от функции yywrap (необходима для
обработки нескольких входных файлов) и включены все предупреждения ?ex-а.
Далее в файле описано включение заголовочных файлов, как стандартных, так и при-
надлежащих калькулятору. Как и в parser.y, в scanner.l исходный код C++ обрамлен
символами ѕ%{ї и ѕ%}ї.
14	// By default yylex returns int, we use token_type.
15	// Unfortunately yyterminate by default returns 0, which is
16	// not of token_type.
17	#de?ne yyterminate() return yy::Parser::token::END

Разбор лексем завершается вызовом функции yyterminate(), которая возвращает це-
лый 0, что не соответствует типу yy::Parser::token, поэтому функция переопределя-
ется таким образом.
21	%{
22	#de?ne YY_USER_ACTION yylloc?>step(); \
23	yylloc?>columns(yyleng);
24	%}







Лабораторные работы по курсу СППО






13



?ex позволяет добавлять в код действия пользователя после распознания очередной
лексемы. В данном случае начало лексемы передвигается в конец предыдущей, после
чего устанавливается новый конец лексемы. Это необходимо для понятного вывода
информации об ошибках.
Кроме этого в раздел определений можно поместить определения регулярных выра-
жений, но в данном случае в этом нет практического смысла.
Второй раздел содержит описание регулярных выражений, которыми описываются
лексемы, и действия анализатора при распознании таких лексем.
28	[+\??/=()] return yy::Parser::token_type(yytext[0]);
Считанная из потока лексема записывается в переменную yytext. В данном случае
знаки операций и скобок напрямую превращаются в тип token_type. Можно было бы
отдельно описать константы PLUS, MINUS и др., но в данном случае это усложнит
код, не увеличив его понятности.
29	"const" return yy::Parser::token::CONST;

Слово ѕconstї распознается очень простым регулярным выражением.
31	[[:alpha:]_][[:alnum:]_]? yylval?>name = new std::string(yytext); return
yy::Parser::token::NAME;

Как сообщалось выше, идентификатор начинается с буквы или знака подчеркивания,
после чего может следовать любое число букв, цифр или знаков подчеркивания.
?ex понимает регулярные выражения в формате POSIX, что позволяет описывать
алфавитные символы как [:alpha:], а не как [A-Za-z].
Встретив идентификатор, лексический анализатор копирует его в экземпляр класса
std::string. Уничтожить экземпляр класса должен уже синтаксический анализатор.
33	[[:digit:]]+(\.[[:digit:]]?)?|\.[[:digit:]]+ {
34	errno = 0;
35	double d = std::strtod(yytext, 0);
36	if(errno == ERANGE)

37

return yy::Parser::token::NOT_A_NUMBER;

38	yylval?>value = d;
39	return yy::Parser::token::NUMBER;
40	}

Число может быть записано несколькими способами для удобства ввода: как ѕ15ї,
как ѕ3.14ї и даже как ѕ.5ї. Регулярное выражение отражает эти способы. Кроме соб-
ственно распознания лексемы функция преобразует строку в значение типа double.
Если преобразование не удалось, синтаксический анализатор получает ѕлексемуї
NOT_A_NUMBER.










42	[ \t]+ {}






Лабораторные работы по курсу СППО






14

Пробельные символы просто игнорируется.
44	. { return yy::Parser::token::INVALID_CHARACTER; }
Последнее правило определяет действия анализатора на случай непредвиденных лек-
сем. Здесь анализатор возвращает специальную лексему INVALID_CHARACTER,
и уже задачей синтаксического анализатора является обработка ошибки.


9	Отладка

Разумеется, было бы наивно предполагать, что грамматику произвольной сложности
можно сразу описать без ошибок. Для отладки ?ex и bison имеют специальные опции
и флаги.
Для отладки ?ex имеет следующие флаги:

–d, %option debug	генерирует отладочную версию анализатора. Как только ?ex
встречает этот флаг и переменная yy_?ex_debug не равна 0 (по умолчанию
она не равна), лексический анализатор выводит в стандартный поток ошибок
строку вида

–accepting rule at line 53 (“the matched text”)
Номер строки соответствует номеру строки с примененным правилом в исход-
ном файле.
–s, ––nodefault, %option nodefault	изменяет поведение лексического анализато-
ра при считывании неизвестного символа. По умолчанию этот символ дубли-
руется в стандартный вывод. При включенной опции лексический анализатор
немедленно прерывает работу с сообщением об ошибке. Это полезно для поиска
дыр в списке правил.

Для отладки синтаксического анализатора необходимо добавить директиву %debug
а также вызывать функцию yy::Parser::set_debug_level() с ненулевым аргументом.


10	Интерфейс

Калькулятор может работать в пакетном или интерактивном режимах. Если в ко-
мандной строке содержатся аргументы, каждый из них рассматривается как команда
калькулятора. В противном случае калькулятор считывает данные из стандартного
ввода до конца файла. Для упрощения работы с двумя источниками входных данных
описан класс Input.
Исходный текст интерфейса содержится в файле calc.cpp.







Лабораторные работы по курсу СППО


11	Python Lex-Yacc






15


Для языка программирования Python есть специальный модуль ply (Python Lex-
Yacc). Python Lex-Yacc основан на идеях lex и yacc, но описание грамматик хранится
не в отдельных файлах, а непосредственно в .py. Перед запуском такой программы
ply генерирует и компилирует дополнительные модули, основываясь на интерфейсе
.py.
Python предоставляет информацию о любом модуле или классе прямо в ходе рабо-
ты программы. ply извлекает из интерфейса модуля отвечающие соглашению име-
на и генерирует лексический и синтаксический анализаторы. Несмотря на разницу
в подходах, исходные файлы имеют много общего.


11.1	Установка

Установка ply происходит очень просто:

# apt-get install python-ply python-ply-doc

Как только команда apt-get завершит свою работу, ply готов к использованию.
Если по какой-то причине ваша ОС не использует пакетный менеджер APT, обрати-
тесь к документации пакетного менеджера вашей системы, чтобы найти и установить
эти пакеты.


11.2	Проектирование

В версии калькулятора на Python-е нет драйвера по двум причинам. Во-первых, об-
работка ошибок сведена к возбуждению исключений, то есть можно отказаться от
хранения последней ошибки. Во-вторых, тип функции parse() определяется динами-
чески, то есть можно отказаться от переменной result_.
В отличие от примера на C++, где синтаксический анализатор является классом,
а лексический  функцией, здесь все наоборот: лексический анализатор является
классом, а синтаксический  функцией.


11.3	Синтаксический анализатор

Описание синтаксического анализатора находится в файле parser.py.
26	import ply.yacc as yacc

Во-первых, надо подключить модуль ply.yacc.
29	from scanner import Scanner, Error







Лабораторные работы по курсу СППО






16



Потом из модуля scanner, описание которого будет приведено ниже, импортировать
класс Scanner для лексического анализа и класс Error для возбуждения исключений.
32	_symbols = { "pi" : ("const", math.pi),
33	"e" : ("const", math.e) }

Таблица символов представляет собой словарь, как в предыдущем примере.
35	_scanner = Scanner()
36	tokens = Scanner.tokens

Далее необходимо создать объектлексический анализатор и обозначить лексемы
переменной tokens. Константы лексем описываются ниже в классе Scanner модуля
scanner.
38	precedence = (("left", "PLUS", "MINUS"),
39	("left", "MUL", "DIV"),
40	("right", "UMINUS"))

Приоритет и ассоциативность операций по соглашению описываются переменной
precedence.
43	def p_program_empty(p):
44	"""program?:"""
45	p[0] = 0.0

Имена продукций начинаются, опять же по соглашению, с префикса ѕp_ї. Грамма-
тика продукции обозначается в виде docstring, далее идет исходный текст функции.
В данном случае продукция пустая, а результат, как описано выше, равен 0.
47	def p_program_const_assignment(p):
48	"""program?:?CONST?NAME?ASSIGN?expr"""
49	v = _symbols.get(p[2], None)
50	if v:

51

raise Error, ("cannot?rebind?’%s’" % p[2], p.lexspan(1)[0], p.lexspan(3)[1])

52	_symbols[p[2]] = ("const", p[4])
53	p[0] = p[4]

Код функций анализатора похож на код исходных файлов bison-а. Есть разница
в обозначениях: переменная $$ называется p[0], а $n p[n]. Важно помнить, что
отрицательные индексы в данном случае имеют совершенно другой смысл, поэтому
их здесь нельзя использовать.
Переменные @n, в которых хранится положение лексемы в строке, здесь доступны
через вызов функции p.lexspan(n).
114	def p_error(p):







Лабораторные работы по курсу СППО






17



115



raise yacc.SyntaxError, "syntax?error?at?token?’%s’,?position?%d" % (p.value,
p.lexpos)


Функцию p_error() вызывает непосредственно анализатор при возникновении ошиб-
ки.
117	yacc.yacc()

Функция yacc() обрабатывает модуль, создавая синтаксический анализатор. Кроме
того, она выводит в файл parser.out описание сгенерированного конечного автомата
в понятной человеку форме. Этот файл полезен при отладке.
119	def calculate(data):

120

return yacc.parse(data, lexer=_scanner.lexer, tracking=True)


Напоследок определим функцию calculate(), которая вызывает parse() с нужными
параметрами: ссылкой на лексический анализатор и установленным флагом трасси-
ровки. Трассировка, как и в примере на C++, замедляет обработку входных данных,
но позволяет получать информацию о местоположении лексем в исходном тексте.


11.4	Лексический анализатор

Описание лексического анализатора находится в файле scanner.py.
3	import ply.lex as lex

Во-первых, надо импортировать модуль ply.lex.
6	class Error(Exception):

7
8
9
10

def __init__(self, m, begin, end):
Exception.__init__(self, m)
self.begin = begin
self.end = end


Производный класс Error хранит сообщение об ошибке и место ее возникновения.
Класс используется для возбуждения исключений.
12	class Scanner:

Лексический анализатор реализован в виде класса Scanner. Этот класс должен со-
ответствовать определенному интерфейсу.
13	# The list of reserved words. Optional
14	reserved = {

15
16	}

"const" : "CONST"







Лабораторные работы по курсу СППО






18



Переменная reserved необязательна и не является частью интерфейса, однако клю-
чевые слова программы описаны именно в ней. Ниже будет надо объяснение этому
факту.
18	# The list of tokens. Mandatory
19	tokens = [

20
21
22

"NAME", "NUMBER",
"PLUS", "MINUS", "MUL", "DIV",
"ASSIGN", "LP", "RP"

23	] + reserved.values()

В отличие от C++ лексемы определяются не константами-числами, а константами-
строками3.
25	# Regular expressions for simple tokens
26	t_PLUS = r"\+"
27	t_MINUS = r"?"
28	t_MUL = r"\?"
29	t_DIV = r"/"
30	t_ASSIGN = r"="
31	t_LP = r"\("
32	t_RP = r"\)"

Простые лексемы описываются регулярным выражением. По соглашению имена лек-
сем начинаются с префикса ѕt_ї.
34	# Complex tokens
35	def t_NAME(self, t):

36
37
38

r"[A?Za?z_]\w?"
t.type = self.reserved.get(t.value, "NAME")
return t


ѕСложнымиї считаются лексемы, требующие особых действий при их появлении
в исходном тексте. В переменной	docstring	функции описывается регулярное выра-
жение, а сама лексема передается в функцию вторым аргументом (или единствен-
ным, если функция не является методом). Функция t_NAME() устанавливает тип
лексемы, записывая его в переменную t.type.
Лексический анализ в ply немного отличается от bison-овского. Если определить от-
дельное регулярное выражение для ключевого слова ѕconstї, то можно столкнуться
с неприятной ситуацией, когда в исходном тексте появится (допустимый) иденти-
фикатор ѕconstantї. Анализатор разобьет его на две лексемы: ѕconstї и ѕantї, что
недопустимо.
3Впрочем, в Python-е все строки являются константами по соображениями производительности.







Лабораторные работы по курсу СППО






19



Поскольку всякое ключевое слово является правильным именем, но не каждое пра-
вильное имя  ключевым словом, то при обнаружении идентификатора происходит
поиск среди ключевых слов.
58	def __init__(self, ??kwargs):

59

self.lexer = lex.lex(object=self, ??kwargs)

Конструктор объекта Scanner создает лексический анализатор на основе самого себя.
Аргумент **kwargs позволяет регулировать поведение объекта.
61	def input(self, data):

62

self.lexer.input(data)


И, наконец, каждый лексический анализатор должен иметь функцию input(), кото-
рая его запускает.


11.5	Интерфейс

Интерфейс калькулятора находится в файле calc.py.


12	Задание

Пользуясь вышеприведенными примерами и указанными ниже источниками, опро-
бовать генераторы анализаторов.


Список литературы

[cpp] Б. Страуструп. Язык программирования C++, спец. изд./Пер. с англ.  М.;
СПб.: ѕИздательство БИНОМї  ѕНевский Диалектї, 2001 г.  1099 с., ил.	5

[bsn] Bison  GNU parser generator. http://www.gnu.org/software/bison/manual/

[?x] Lexical Analysis With Flex. http://flex.sourceforge.net/manual/

[fb]	Лучшая обработка ошибок с помощью Flex и Bison. Советы по созда-
нию более дружественных к пользователю компиляторов и интерпретаторов.
http://www.ibm.com/developerworks/ru/library/l-flexbison/index.html

[ply] PLY (Python Lex-Yacc). http://www.dabeaz.com/ply/ply.html







Лабораторные работы по курсу СППО


2	Лексический анализ

1	Задание






20


Пользуясь полученными в л. р. № 1 знаниями, написать программу, разделяющую
входной поток на лексемы в соответствии с вариантом. При написании программы
необходимо пользоваться терминологией предметной области. В случае обработки
файлов программа должна сохранять их форматирование.
При обнаружении ошибок программа должна сообщать о них в понятной пользова-
телю форме. Программа должна завершаться с кодом 0, если завершилась успешно,
и с отличным от 0 кодом в случае ошибки.
В тех случаях, где ввод предусмотрен исключительно из стандартного файла, необ-
ходимо реализовать интерактивный режим работы программы.


2	Варианты

1. Подмножество языка Python: целый и строковый типы, списки, словари, опе-
рации над ними и команда del.

2. Конфигурационные файлы формата INI.

3. Файлы паролей /etc/passwd.

4. Подмножество языка Prolog.

5. Файлы описания DNS-зон сервера BIND.

6. Репозитории APT.

7. Предложение SELECT языка SQL.

8. Диалект языка Lisp с возможностью определения лямбда- и обычных функций.

9. Конфигурационный файл команды sudo /etc/sudoers.

10. Файлы конфигурации xorg.conf сервера X-org.

11. Подмножество языка Shell с инструкциями ветвления, циклов и создания функ-
ций.

12. Предложение INSERT языка SQL.

13. Предложение UPDATE языка SQL.

14. Предложение DELETE языка SQL.







Лабораторные работы по курсу СППО






21



15. Подмножество языка С++: типы int, std::string, std::list<>, std::map<> и стан-
дартные операции над ними.

16. Таблицы формата CSV.

17. Сценарии программируемого инженерного калькулятора с базовыми арифме-
тическими операциями, операцией возведения в степень, числами в форматах
с десятичной запятой и экспоненциальном, тригонометрическими и логариф-
мическими функциями.

18. Файлы Cascading Style Sheets (CSS).

19. Булевы уравнения.

20. Алгебраические выражения.

21. Файлы электропочты.


3	Пример

calc> a = 5
NAME = NUMBER
calc> pi * a * a
NAME * NAME * NAME
calc> const a = 6
CONST NAME = NUMBER
calc> p / pi
NAME / NAME
calc> p = pi
NAME = NAME
calc> pi = p
NAME = NAME
calc> a = 6
NAME = NUMBER
calc> 1 + a / (p - pi)
NUMBER + NAME / (NAME - NAME)
calc> 1 + a * e
NUMBER + NAME * NAME







Лабораторные работы по курсу СППО


3	Проверка корректности

1	Задание






22


Пользуясь полученными в л. р. № 1 знаниями и результатами, достигнутыми при
выполнении л. р. № 2, написать программу, проверяющую корректность синтаксиса
входного потока в соответствии с вариантом.
При обнаружении ошибок программа должна сообщать о них в понятной пользова-
телю форме. Программа должна завершаться с кодом 0, если завершилась успешно,
и с отличным от 0 кодом в случае ошибки.
В тех случаях, где ввод предусмотрен исключительно из стандартного файла, необ-
ходимо реализовать интерактивный режим работы программы.


2	Варианты

1. Подмножество языка Python: целый и строковый типы, списки, словари, опе-
рации над ними и команда del.

2. Конфигурационные файлы формата INI.

3. Файлы паролей /etc/passwd.

4. Подмножество языка Prolog.

5. Файлы описания DNS-зон сервера BIND.

6. Репозитории APT.

7. Предложение SELECT языка SQL.

8. Диалект языка Lisp с возможностью определения лямбда- и обычных функций.

9. Конфигурационный файл команды sudo /etc/sudoers.

10. Файлы конфигурации xorg.conf сервера X-org.

11. Подмножество языка Shell с инструкциями ветвления, циклов и создания функ-
ций.

12. Предложение INSERT языка SQL.

13. Предложение UPDATE языка SQL.

14. Предложение DELETE языка SQL.







Лабораторные работы по курсу СППО






23



15. Подмножество языка С++: типы int, std::string, std::list<>, std::map<> и стан-
дартные операции над ними.

16. Таблицы формата CSV.

17. Сценарии программируемого инженерного калькулятора с базовыми арифме-
тическими операциями, операцией возведения в степень, числами в форматах
с десятичной запятой и экспоненциальном, тригонометрическими и логариф-
мическими функциями.

18. Файлы Cascading Style Sheets (CSS).

19. Булевы уравнения.

20. Алгебраические выражения.

21. Файлы электропочты.

calc> a = 5
OK
calc> a 5 =
^ syntax error: operator expected
calc> 1 + a / (p - pi)
OK
calc> const pi
^ syntax error: ‘=’ expected


4	Синтаксический анализ

1	Задание

Пользуясь полученными в л. р. № 1 знаниями и результатами, достигнутыми при
выполнении л. р. № 2 и 3, написать программу, реализующую указанный вариант.
При обнаружении ошибок программа должна сообщать о них в понятной пользова-
телю форме. Программа должна завершаться с кодом 0, если завершилась успешно,
и с отличным от 0 кодом в случае ошибки.
В тех случаях, где ввод предусмотрен исключительно из стандартного файла, необ-
ходимо реализовать интерактивный режим работы программы.










2	Варианты






Лабораторные работы по курсу СППО






24


1. Интерпретатор подмножества языка Python, содержащего целый и строковый
типы, списки, словари, операции над ними и команду del.

2. Интерактивный редактор конфигурационных файлов формата INI.

3. Интерактивный редактор файла паролей /etc/passwd.

4. Интерпретатор подмножества языка Prolog.

5. Интерактивный редактор файлов описания DNS-зон сервера BIND.

6. Интерактивный редактор репозиториев APT.

7. Интерпретатор предложения SELECT над БД, заданной последовательностью
предложений CREATE.

8. Интерактивный интерпретатор диалекта языка Lisp с возможностью определе-
ния лямбда- и обычных функций.

9. Команда fakesudo, проверяющая возможность выполнения указанным пользо-
вателем данной команды с данной машины. Предусмотреть опции для указа-
ния БД пользователей, БД групп и файла настройки sudo. По умолчанию это
должны быть файлы /etc/passwd, /etc/group и /etc/sudoers.

10. Интерактивный редактор файлов конфигурации xorg.conf сервера X-org.

11. Интерпретатор подмножества языка Shell с инструкциями ветвления, циклов
и создания функций.

12. Интерпретатор предложения INSERT над БД, заданной последовательностью
предложений CREATE.

13. Интерпретатор предложения UPDATE над БД, заданной последовательностью
предложений CREATE.

14. Интерпретатор предложения DELETE над БД, заданной последовательностью
предложений CREATE.

15. Интерпретатор подмножества языка С++, содержащего типы int, std::string,
std::list<>, std::map<> и стандартные операции над ними. Реализовать функ-
цию del, удаляющую имя и функцию typeof, возвращающую имя типа.

16. Интерпретатор предложения SELECT над таблицей формата CSV.







Лабораторные работы по курсу СППО






25



17. Интерактивный программируемый инженерный калькулятор с базовыми ариф-
метическими операциями, операцией возведения в степень, числами в форматах
с десятичной запятой и экспоненциальном, тригонометрическими и логарифми-
ческими функциями.

18. Интерактивный редактор подмножества языка CSS.

19. Интерактивная программа решения булевых уравнений.

20. Интерактивная программа упрощения алгебраических выражений.

21. Интерактивный RFC-совместимый редактор файлов электропочты.


3	Пример

calc> a = 5
5
calc> pi * a * a
78.5398
calc> const a = 6
^^^^^^^^^ cannot rebind ’a’
calc> p / pi
^ undefined symbol ’p’
calc> p = pi
3.14159
calc> pi = p
^^^^ cannot rebind ’pi’
calc> a = 6
6
calc> 1 + a / (p - pi)
^^^^^^^^ division by zero
calc> 1 + a * e
17.3097

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации