Над этой лабой мы сидели очень долго. Сначала было трудно понять, что от нас требуется, а затем оказалось, что работы очень много.
Задание к второй лабе похоже на задание к первой - нужно написать синтаксический анализатор с использованием программы Bison. Снова программа получает правила, а на выходе даёт код анализатора.
Разберёмся, что такое синтаксический анализ.
В википедии написано примерно следущее:синтакси́ческий ана́лиз (па́рсинг) — это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой.
Там же разобран небольшой пример того, как это работает, но самое важное - следущее:
"При парсинге исходный текст преобразуется в структуру данных, обычно — в дерево".
Таким образом вся работа делится на 2 части:
1) Сопоставление лексем грамматике
2) Построение дерева
Рассмотрим обе части подробнее.
1. Сопоставление лексем грамматике.
В каждом языке есть набор правил для исходного кода. Например, в C\C++ функция описывается как
<возвращаемое значение> <имя функции> '(' <аргументы> ')'
'{'
<оператор>
'}'
цикл while описывается так:
'while' '(' <выражение>')'
<оператор>
В общем надеюсь, что идея понятна. Теперь нам нужно описать эти правила в bison-файле.
Структура файла и основные положения неплохо описаны здесь.
Для составления правил нам потребуется пункт 4.3 Синтаксис правил грамматики.
После прочтения рассмотрим небольшой пример.
Допустим, есть выражение
a = b + 42
Попробуем составить для него правило:
//выражение
expression
: IDENTIFIER '=' expression {/*присвоение*/}
| expression '+' expression {/*сложение*/}
| CONSTANT {/*константа*/}
| IDENTIFIER {/*идентификатор, в примере - имена переменных*/}
;
Сразу возникает вопрос - откуда взялись CONSTANT и IDENTIFIER?
Перед началом работы над синтаксическим анализатором будет необходимо преобразовать flex-файл таким образом, чтобы он не печатал значения, а возвращал их, а так же объявить эти значения как токены в bison-файле.
Как понимать это правило?
Это правило гласит, что в выражение expression(результат) можно свернуть присвоение идентификатору другое выражение(компоненты первого правила), сложение одного выражения с другим(компоненты второго правила и т.д.), идентификатор и константу.
Что нам вернёт лексический анализатор примера?
IDENTIFIER '=' IDENTIFIER '+' CONSTANT
Разберёмся, как bison будет работать на этом примере(более точная и полная информация доступна здесь).
Так как bison - LR(1)-генератор(т.е. обрабатывает код слева направо, и, чтобы узнать что ему сделать - сворачивать или сдвигать, смотрит 1 символ левее), то произойдет следущее:
1. Считается a как IDENTFIER по правилу 4.
Прежде чем сворачивать его в expression, бизон посмотрит следующий символ - символ присваивания. Так как для него есть правило, то a уже не будет сворачиваться в expression и произойдёт сдвиг. Стек будет иметь вид IDENTIFIER =
2. Считывается идентификатор b.
Так как после идентифкатора b стоит знак +, а других правил с IDENTIFIER '+' something у нас нет, то bison свернёт считанный идентификатор в expression.
Теперь на верхушке стека лежит IDENTIFIER = expression. Но следующим символом он встречает '+', у которого приоритет выше, чем у присваивания*. Поэтому происходит сдвиг и стек будет иметь вид
IDENTIFIER = expression +
3. Считывается константа 42.
Так как после константы больше ничего нет и существует лишь одно правило, то он свернёт её в expression.
На верхушке стека образуется IDENTFIER = expression '+' expression.
Для последних 3 символов у нас есть правило 2, поэтому произойдёт
4. Свёртка expression '+' expression.
Bison свернёт два выражения в одно, таким образом получим на верхушке стека IDENTIFIER = expression.
Так как для данной последовательности у нас есть правил 1, снова произойдёт
5. Свёртка IDENTIFIER = expression в один expession.
На этом анализатор закончит свою работу.
* приоритеты языка и их описание в bison нужно взять из справочной информации, без правильных приоритетов могут возникать трудноотлавливаемые ошибки.
Если мы хотим, чтобы синтаксический анализатор понимал выражение
a = b + 42;
мы вводим понятие оператора
statement
: expression ';'
;
и так далее...
Особенно в этой части стоит отметить создание рекурсивных списков(аргументов, например).
Подробнее читать здесь.
Вкратце:
Список называется рекурсивным, если его результат появляется в его правой части.
Рекурсия бывает левая:
exprlist
:expr
| exprlist ',' expr
;
и правая:
exprlist
:expr
| expr ',' exprlist
;
Название рекурсий приходит от расположения появившегося exprlist.
Если вы ещё не разобрались, как это работает - запомните, что всегда лучше использовать левую рекурсию, потому что при длинных списках может возникнуть переполнение стека!
Ну и пару слов о пустых списках:
Если возможна ситуация, когда будет что сворачивать и ситуация, когда сворачивать будет нечего(например при вызове функции параметры могут быть, а могут и не быть), можно применить что-нибудь вроде этого:
arguments_list_e
: /*empty, нет аргументов*/
| arguments_list
;
arguments_list
: argument
| arguments_list ',' argument
;
И при вызове функции написать в правиле IDENTIFIER '(' arguments_list_e ')' .
На этом первая часть лабораторной работы заканчивается.
Вторая часть - создание структур под это дерево, которое будет хранить данные.
Для примера выше это будет что-то вроде того:
enum ExprType {
ExprTypeAssign = 0, // =
ExprTypePlus, // +
ExprTypeConst, // константа
ExprTypeIdentifier, // id
...
};
struct Expression {
enum ExprType type; // тип выражения
struct Expression *left; // левый expr
struct Expression *right; // правый expr
int num; // целое число
char *name; // id
....
};
enum StmtType {
...,
StmtTypeExpr, // из expr'а
...
};
struct Statement {
enum StmtType type; // тип
struct Expression *expr; // выражение
...
};
Т.е. мы смотрим на правило, определяем, какие данные нам надо хранить, чтобы мы смогли из любого правила сделать структуру без потерь и записываем их.
Для записи данных в структуры нам будет необходимо написать функции на C (! обращаю внимание на то, что эта ерунда не будет очень долго работать, пока не разберётесь как её включить, стоит очень внимательно изучить #ifndefы и прагмы в declarations.h)
Чтобы заставить bison создавать дерево, нужно будет вызывать наши функции заполнения дерева для каждого из правил.
Например, для сложения это будет выглядеть так:
expression '+' expression {$$ = CreateBinaryExpr(ExprTypeMul, $1, $3)}
$$ - это выражение, в которое свёрнется сложение, т.е. результат
$1 - указатель на expression слева, $3 - справа. Номер, таким образом, обозначает номер интересующей нас переменной в правиле.
Заодно приведу заголовок функции:
// бинарные операции
struct Expression * CreateBinaryExpr(enum ExprType type, struct Expression *left_expr, struct Expression *right_expr);
Связи между структурами и терминалами так же нужно будет прописать в файле bison.
Напоследок скажу, что главный узел дерева необходимо указать после директивы start, например так:
%start program_unit
После построения дерева будет необходимо его вывести, что займёт немало времени, но позволит отловить кучу ошибок. Так что советую посмотреть, как это было сделано в данном проекте и обратить внимание на файлы xml.c\xml.h
Смотреть построенное дерево можно будет любым XML-viewer'ом.
По использованию bison:
bison.exe -d <файл с правилами> --verbose
Ключ -d генерирует не только .tab.c файл, но и .h - а без него не работает.
Ключ --verbose генерирует очень большой файл .output, в котором описывается вся отладочная информация по работе bison с заданными правилами. В процессе отладки может пригодиться.
Чтобы собрать всё это я, кажется, создавал новый проект, в который кидал лексический анализатор, удалял из него main и делал отдельный. В репозитории посмотрите, по log'ам.
На этом по синтаксическому анализатору всё.
Ссылка на репозиторий
http://code.google.com/p/vstu-objective-c/
Путь к файлу с правилами
trunk/Sin/SintaxAnalyzer/SintaxAnalyzer/grammar.y
Ссылка на homepage проекта Bison
http://www.gnu.org/software/bison/
Хороший справочник по Bison на русском языке
http://www.linux.org.ru/books/GNU/bison/bison_toc.html
Задание к второй лабе похоже на задание к первой - нужно написать синтаксический анализатор с использованием программы Bison. Снова программа получает правила, а на выходе даёт код анализатора.
Разберёмся, что такое синтаксический анализ.
В википедии написано примерно следущее:синтакси́ческий ана́лиз (па́рсинг) — это процесс сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой.
Там же разобран небольшой пример того, как это работает, но самое важное - следущее:
"При парсинге исходный текст преобразуется в структуру данных, обычно — в дерево".
Таким образом вся работа делится на 2 части:
1) Сопоставление лексем грамматике
2) Построение дерева
Рассмотрим обе части подробнее.
1. Сопоставление лексем грамматике.
В каждом языке есть набор правил для исходного кода. Например, в C\C++ функция описывается как
<возвращаемое значение> <имя функции> '(' <аргументы> ')'
'{'
<оператор>
'}'
цикл while описывается так:
'while' '(' <выражение>')'
<оператор>
В общем надеюсь, что идея понятна. Теперь нам нужно описать эти правила в bison-файле.
Структура файла и основные положения неплохо описаны здесь.
Для составления правил нам потребуется пункт 4.3 Синтаксис правил грамматики.
После прочтения рассмотрим небольшой пример.
Допустим, есть выражение
a = b + 42
Попробуем составить для него правило:
//выражение
expression
: IDENTIFIER '=' expression {/*присвоение*/}
| expression '+' expression {/*сложение*/}
| CONSTANT {/*константа*/}
| IDENTIFIER {/*идентификатор, в примере - имена переменных*/}
;
Сразу возникает вопрос - откуда взялись CONSTANT и IDENTIFIER?
Перед началом работы над синтаксическим анализатором будет необходимо преобразовать flex-файл таким образом, чтобы он не печатал значения, а возвращал их, а так же объявить эти значения как токены в bison-файле.
Как понимать это правило?
Это правило гласит, что в выражение expression(результат) можно свернуть присвоение идентификатору другое выражение(компоненты первого правила), сложение одного выражения с другим(компоненты второго правила и т.д.), идентификатор и константу.
Что нам вернёт лексический анализатор примера?
IDENTIFIER '=' IDENTIFIER '+' CONSTANT
Разберёмся, как bison будет работать на этом примере(более точная и полная информация доступна здесь).
Так как bison - LR(1)-генератор(т.е. обрабатывает код слева направо, и, чтобы узнать что ему сделать - сворачивать или сдвигать, смотрит 1 символ левее), то произойдет следущее:
1. Считается a как IDENTFIER по правилу 4.
Прежде чем сворачивать его в expression, бизон посмотрит следующий символ - символ присваивания. Так как для него есть правило, то a уже не будет сворачиваться в expression и произойдёт сдвиг. Стек будет иметь вид IDENTIFIER =
2. Считывается идентификатор b.
Так как после идентифкатора b стоит знак +, а других правил с IDENTIFIER '+' something у нас нет, то bison свернёт считанный идентификатор в expression.
Теперь на верхушке стека лежит IDENTIFIER = expression. Но следующим символом он встречает '+', у которого приоритет выше, чем у присваивания*. Поэтому происходит сдвиг и стек будет иметь вид
IDENTIFIER = expression +
3. Считывается константа 42.
Так как после константы больше ничего нет и существует лишь одно правило, то он свернёт её в expression.
На верхушке стека образуется IDENTFIER = expression '+' expression.
Для последних 3 символов у нас есть правило 2, поэтому произойдёт
4. Свёртка expression '+' expression.
Bison свернёт два выражения в одно, таким образом получим на верхушке стека IDENTIFIER = expression.
Так как для данной последовательности у нас есть правил 1, снова произойдёт
5. Свёртка IDENTIFIER = expression в один expession.
На этом анализатор закончит свою работу.
* приоритеты языка и их описание в bison нужно взять из справочной информации, без правильных приоритетов могут возникать трудноотлавливаемые ошибки.
Если мы хотим, чтобы синтаксический анализатор понимал выражение
a = b + 42;
мы вводим понятие оператора
statement
: expression ';'
;
и так далее...
Особенно в этой части стоит отметить создание рекурсивных списков(аргументов, например).
Подробнее читать здесь.
Вкратце:
Список называется рекурсивным, если его результат появляется в его правой части.
Рекурсия бывает левая:
exprlist
:expr
| exprlist ',' expr
;
и правая:
exprlist
:expr
| expr ',' exprlist
;
Название рекурсий приходит от расположения появившегося exprlist.
Если вы ещё не разобрались, как это работает - запомните, что всегда лучше использовать левую рекурсию, потому что при длинных списках может возникнуть переполнение стека!
Ну и пару слов о пустых списках:
Если возможна ситуация, когда будет что сворачивать и ситуация, когда сворачивать будет нечего(например при вызове функции параметры могут быть, а могут и не быть), можно применить что-нибудь вроде этого:
arguments_list_e
: /*empty, нет аргументов*/
| arguments_list
;
arguments_list
: argument
| arguments_list ',' argument
;
И при вызове функции написать в правиле IDENTIFIER '(' arguments_list_e ')' .
На этом первая часть лабораторной работы заканчивается.
Вторая часть - создание структур под это дерево, которое будет хранить данные.
Для примера выше это будет что-то вроде того:
enum ExprType {
ExprTypeAssign = 0, // =
ExprTypePlus, // +
ExprTypeConst, // константа
ExprTypeIdentifier, // id
...
};
struct Expression {
enum ExprType type; // тип выражения
struct Expression *left; // левый expr
struct Expression *right; // правый expr
int num; // целое число
char *name; // id
....
};
enum StmtType {
...,
StmtTypeExpr, // из expr'а
...
};
struct Statement {
enum StmtType type; // тип
struct Expression *expr; // выражение
...
};
Т.е. мы смотрим на правило, определяем, какие данные нам надо хранить, чтобы мы смогли из любого правила сделать структуру без потерь и записываем их.
Для записи данных в структуры нам будет необходимо написать функции на C (! обращаю внимание на то, что эта ерунда не будет очень долго работать, пока не разберётесь как её включить, стоит очень внимательно изучить #ifndefы и прагмы в declarations.h)
Чтобы заставить bison создавать дерево, нужно будет вызывать наши функции заполнения дерева для каждого из правил.
Например, для сложения это будет выглядеть так:
expression '+' expression {$$ = CreateBinaryExpr(ExprTypeMul, $1, $3)}
$$ - это выражение, в которое свёрнется сложение, т.е. результат
$1 - указатель на expression слева, $3 - справа. Номер, таким образом, обозначает номер интересующей нас переменной в правиле.
Заодно приведу заголовок функции:
// бинарные операции
struct Expression * CreateBinaryExpr(enum ExprType type, struct Expression *left_expr, struct Expression *right_expr);
Связи между структурами и терминалами так же нужно будет прописать в файле bison.
Напоследок скажу, что главный узел дерева необходимо указать после директивы start, например так:
%start program_unit
После построения дерева будет необходимо его вывести, что займёт немало времени, но позволит отловить кучу ошибок. Так что советую посмотреть, как это было сделано в данном проекте и обратить внимание на файлы xml.c\xml.h
Смотреть построенное дерево можно будет любым XML-viewer'ом.
По использованию bison:
bison.exe -d <файл с правилами> --verbose
Ключ -d генерирует не только .tab.c файл, но и .h - а без него не работает.
Ключ --verbose генерирует очень большой файл .output, в котором описывается вся отладочная информация по работе bison с заданными правилами. В процессе отладки может пригодиться.
Чтобы собрать всё это я, кажется, создавал новый проект, в который кидал лексический анализатор, удалял из него main и делал отдельный. В репозитории посмотрите, по log'ам.
На этом по синтаксическому анализатору всё.
Ссылка на репозиторий
http://code.google.com/p/vstu-objective-c/
Путь к файлу с правилами
trunk/Sin/SintaxAnalyzer/SintaxAnalyzer/grammar.y
Ссылка на homepage проекта Bison
http://www.gnu.org/software/bison/
Хороший справочник по Bison на русском языке
http://www.linux.org.ru/books/GNU/bison/bison_toc.html
Комментариев нет:
Отправить комментарий