Logo GenDocs.ru

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


Загрузка...

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


Знакомство с генераторами лексических и синтаксических анализаторов 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.doc

Реклама MarketGid:
Загрузка...


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


1



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

сических анализаторов lex и yacc
1 Введение
Задача создания эффективных анализаторов исходного кода возникла вместе с пер-

вым компилятором. С тех пор прошло много времени, и появилась мощная теория,

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

ных автоматов. Программирование анализаторов исходного кода может быть полезно

в учебных или исследовательских целях, но для анализа реальных языков С++,

Python или SQL в настоящее время используют исключительно автоматические

средства генерации лексических и синтаксических анализаторов. Далее речь пойдет

только о них: lex и yacc.

2 Установка
Поскольку изначально lex и yacc были проприетарными программами, Сообщество

разработало их свободные аналоги: flex и bison.

Установка программ происходит очень просто:
# apt-get install flex flex-doc bison bison-doc
Как только команда apt-get завершит свою работу, flex и bison готовы к использова-

нию.

Если по какой-то причине ваша ОС не использует пакетный менеджер APT, обрати-

тесь к документации пакетного менеджера вашей системы, чтобы найти и установить

эти пакеты.

3 flex
flex означает fast lex, и он является генератором лексических анализаторов. Ни для

кого не секрет, что программы на языках программирования состоят не из букв

и цифр, но из более крупных единиц лексем. Лексемы очень удобно задавать

при помощи регулярных выражений. Например, идентификатор программы любого

языка можно описать так:
[A–Za–z_][A–Za–z0–9_]*
Это выражение означает, что идентификатор должен состоять как минимум из одной

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

цифр или знаков подчеркивания.



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


2



flex предназначен для генерации программлексических анализаторов на языках C

и C++. В самом простом случае такой анализатор, встретив очередную лексему,

просто возвращает ее числовой код. В более сложных случаях анализатор совершает

некоторое действие над лексемой, например, преобразует последовательность цифр

в число.

Как правило, flex используется совместно с генератором синтаксических анализато-

ров bison.

4 bison
bison является генератором синтаксических анализаторов, полностью совместимым

с yacc.

Синтаксический анализатор получает на вход поток лексем и проверяет их на соот-

ветствие некоторой контекстно-свободной грамматике. Грамматика в bison описыва-

ется в БНФ:

assignment : NAME ’=’ expr ’;’
По традиции нетерминальные символы грамматики записываются строчными бук-

вами, терминальные прописными или выделяются кавычками.

bison предназначен для генерации программсинтаксических анализаторов на язы-

ках C, C++ и Java. В самом простом случае такой анализатор просто проверяет поток

лексем на соответствие указанной грамматике. В более сложных случаях анализатор

может выполнять некоторые действия, например, вычислять значения математиче-

ских выражений или строить деревья.

Как правило, bison используется совместно с генератором лексических анализаторов

flex.

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 #define 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 и flex.

Аргументами функции являются лексема и ее местоположение во входном потоке.

Функция возвращаем тип лексемы.

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<std::string, Value> 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 buff = yy_scan_string(s.c_str());

28 if(!buff)

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_buffer(buff);

39 return res;

40 }
В строках 24–40 файла driver.cpp находится определение функции parse().

По умолчанию анализаторы читают символы из файла yyin. Но описанная функ-

ция предполагает считывать данные из строки. Для этого необходимо создать де-

скриптор при помощи функции yy_scan_string(). После завершения анализа строки

дескриптор необходимо уничтожить функцией yy_delete_buffer().

Класс 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 %defines

26 %define 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 <memory>

48

49 #include "driver.h"

50

51 typedef std::auto_ptr<std::string> StringPtr;

52 }
Секция code содержит код, помещаемый перед определением класса. Синтаксиче-

скому анализатору необходимо знать структуру класса Driver, чтобы обращаться

к таблице символов.

В строке 51 объявлен синоним типа auto_ptr. Выше упоминалось, что одним из чле-

нов объединения является указатель на строку. Функции, работающие с объединени-

ем, должны освобождать занятые ресурсы. Конечно, в примитивном случае можно

вызвать оператор delete, и это сработает. Но как будет видно дальше, функции име-

ют несколько точек выхода. В таких случаях гораздо эффективнее использовать

один из классов с автоматической сборкой мусора (или создать свой), чем вызывать

оператор delete перед каждой точкой выхода2.

54 %token CONST "const"

55 %token END 0 "end␣of␣file"

56 %token INVALID_CHARACTER "invalid␣character"

57 %token NOT_A_NUMBER "not␣a␣number"

58

59 %token <name> NAME "identifier"

60 %token <value> NUMBER "number"
Строки 54–60 содержат самое интересное (после описания правил грамматики): опи-

сание лексем. Описание лексемы начинается со слова %token, после чего может идти

тип лексемы в терминах YYSTYPE, ее символьное значение, необязательное число-

вое значение (лексема END по соглашению должна быть равна 0) и строку с удобным

описанием лексемы. Последнее позволяет bison-у более понятно сообщать об ошиб-

ках.

Все символьные константы помещаются в структуре yy::Parser::token. Это важно

помнить при написании лексического анализатора.

62 %type <value> expr term
Генерируемые bison-ом функции могут возвращать значения разных типов. В данном

случае типы выражений и термов определяются как value, то есть число.

2Конечно, можно оставить одну точку выхода, однако пострадает понятность исходного кода.

Кроме того, даже в этом случае нет гарантии освобождения ресурсов при внезапно возникшем

исключении.



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

64 %destructor { delete $$; } "identifier"


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.find(∗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.find(∗p);

if(i != driver.symbols.end())

$$ = i−>second.value;

else

{

std::ostringstream msg;

msg << "undefined␣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 Лексический анализатор
Структура входного файла лексического анализатора также состоит из трех частей.

Первая часть файла содержит разнообразные настройки flex-а,

Определения

%%

Правила

%%

Код

определения регулярных выражений и исходный код, помещае-

мый перед кодом анализатора. Вторая часть содержит сами пра-

вила и соответствующие им действия. Как правило, действия

заключаются в возврате той или иной символьной константы.

Последняя часть файла содержит код функций, помещаемых по-

сле кода лексического анализатора. Например, там может быть

функция main(), если программа небольшая.

Теперь рассмотрим файл scanner.l, который содержит исходный код сканера, подроб-

нее.

1 %option 8bit

2 %option noyywrap

3 %option warn
Файл начинается с настроек генератора flex. Здесь указано использование 8-битной

кодировки (можно выбрать и 7-битную), отказ от функции yywrap (необходима для

обработки нескольких входных файлов) и включены все предупреждения flex-а.

Далее в файле описано включение заголовочных файлов, как стандартных, так и при-

надлежащих калькулятору. Как и в 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 #define yyterminate() return yy::Parser::token::END
Разбор лексем завершается вызовом функции yyterminate(), которая возвращает це-

лый 0, что не соответствует типу yy::Parser::token, поэтому функция переопределя-

ется таким образом.

21 %{

22 #define YY_USER_ACTION yylloc−>step(); \

23 yylloc−>columns(yyleng);

24 %}



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


13



flex позволяет добавлять в код действия пользователя после распознания очередной

лексемы. В данном случае начало лексемы передвигается в конец предыдущей, после

чего устанавливается новый конец лексемы. Это необходимо для понятного вывода

информации об ошибках.

Кроме этого в раздел определений можно поместить определения регулярных выра-

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

Второй раздел содержит описание регулярных выражений, которыми описываются

лексемы, и действия анализатора при распознании таких лексем.

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;
Как сообщалось выше, идентификатор начинается с буквы или знака подчеркивания,

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

flex понимает регулярные выражения в формате 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 Отладка
Разумеется, было бы наивно предполагать, что грамматику произвольной сложности

можно сразу описать без ошибок. Для отладки flex и bison имеют специальные опции

и флаги.

Для отладки flex имеет следующие флаги:
–d, %option debug генерирует отладочную версию анализатора. Как только flex

встречает этот флаг и переменная yy_flex_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/
[flx] 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



Скачать файл (274.2 kb.)

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

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