UNIX — универсальная среда программирования - Керниган Брайан Уилсон

Читать онлайн «UNIX — универсальная среда программирования». Страница 101

Автор Керниган Брайан Уилсон

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

NUMBER

; операции из одного символа, такие, как

+

*

, также являются лексическими единицами. По традиции лексические единицы называют лексемами.

На следующем этапе разрабатывается управляющая процедура, которая вызывает анализатор, созданный

yacc

Программа

yacc

преобразует грамматику и семантические процедуры в функцию разбора с именем

yyparse

и записывает ее в виде файла с текстом на Си. Если

yacc

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

Действие

yacc

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

yylex

, так как именно эту функцию инициирует анализатор

yyparse

всякий раз, когда ему нужна следующая лексема. (Все имена, используемые

yacc

, начинаются с

y

Чтобы быть более точными, укажем, что входной поток для

yacc

должен иметь такой вид:

%{

Операторы Си типа #include, описания и т. д.

Эта часть необязательна.

%}

yacc-описания: лексемы, грамматические переменные,

информация о приоритетах и ассоциативности

%%

грамматические правила и действия

%%

еще операторы Си (необязательно):

main() {

...; yyparse(); ...

}

yylex() {

...

}

...

Этот поток поступает на вход

yacc

, а результат записывается в файл

y.tab.c

, имеющий следующую структуру:

Операторы на Си между %{ и %}, если есть

Операторы на Си из части после второй комбинации %%, если есть:

main() {

...; yyparse(); ...

}

yylex() {

...

}

...

yyparse() {

анализатор, который вызывает yylex()

}

Такой подход типичен для системы UNIX:

yacc

выдает текст на Си, а не оттранслированный файл (

.o

), что является наиболее гибким решением, так как созданный текст, переносим и легко поддается любому другому преобразованию (если появится хорошая идея).

Генератор

yacc

сам по себе представляется мощным программным средством. Его изучение потребует от вас, конечно, некоторых усилий, но все ваши "затраты" многократно окупятся. Анализаторы, создаваемые

yacc

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

Использование программ на этапе 1

Исходный текст

hoc1

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

yylex

и функции

main

, хранимых в одном файле

hoc.y

. (Имена файлов, содержащих текст для

yacc

, традиционно оканчиваются на

.y

, но это соглашение в отличие от соглашения о

сс

и .c не поддерживает сам

yacc

.) Грамматика составляет первую половину файла

hoc.y

$ cat hoc.y

%{

#define YYSTYPE double /* data type of yacc stack */

%}

%token NUMBER

%left '+' /* left associative, same precedence */

%left '*' '/' /* left assoc., higher precedence */

%%

list: /* nothing */

| list '\n'

| list expr '\n' { printf("\t%.8g\n", $2); }

;

expr: NUMBER { $$ = $1; }

| expr '+' expr { $$ = $1 + $3; }

| expr '-' expr { $$ = $1 - $3; }

| expr '*' expr { $$ = $1 * $3; }

| expr '/' expr { $$ = $1 / $3; }

| '(' expr ')' { $$ = $2; }

;

%%

/* end of grammar */

...

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

yacc

Альтернативные правила разделены символом

'|'

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

$n

(т.е.

$1

$2

и т.д.) определяет значение, вырабатываемое

n

-м компонентом правила, а

$$

значение, вырабатываемое всеми компонентами правила в целом. Так, в правиле