Приветствуют, форумчане лолцтима. Сегодня расскажу, что такое генератор парсера Yacc. Это моя первая статья на данную тематику, прошу отнестись с понимаем. Загрузил на гугл диск статью, здесь не удобно просматривать иллюстрации. Ссылка: https://drive.google.com/open?id=1_1V3Ef5mxCV8sgwDEG7Q0t9qXFm0avDm I. Что такое Yacc? I.1 Что такое Yacc? YACC является генератором парсера, т.е. программа, которая может быть использована для создания парсеров. Он был разработан С.С. Джонсоном в начале 1970-х годов и теперь доступен для всех систем UNIX. Аббревиатура YACC расшифровывается как «еще один компилятор-компилятор», что указывает на то, что одной из целей YACC является разработка компиляторов, но она может использоваться там, где программы должны читать ввод текста. Это имеет место во многих приложениях, например при чтении файлов конфигурации или при реализации протоколов связи (например, TCP / IP или HTTP). Его сила показывает YACC особенно там, где эти входы очень универсальны и различны. В качестве входных данных YACC ожидает файл, содержащий так называемую грамматику (аналогично Backus-Naur-Form). Эта грамматика является описанием набора правил для парсера, который вы хотите сгенерировать. Парсер может распознавать структуры, которые следуют этим правилам, и выполнять определенные действия. YACC генерирует из этой грамматики исходную программу на C, содержащую полный синтаксический анализатор. I.2 Как использовать Yacc? Для использования YACC простой пример: предположим, что вы создали грамматику в файле grammar.y (расширение файла .y является соглашением для исходных файлов YACC). YACC вызывается с помощью yacc grammar.y и получает выходной файл y.tab.c, исходный код C грамматики grammar.y. Затем это можно перевести любым компилятором C, например, с копией y.tab.c. Затем получают исполняемый файл a.out, который содержит готовый исполняемый синтаксический анализатор. II. Синтаксис Yacc II.1 Основные операции парсера Сгенерированный YACC парсер работает с разными типами символов. Они делятся на терминальные и нетерминальные символы, и терминальные символы могут быть литералами или маркерами. Литералы - это отдельные символы, то есть буквы, цифры или другие символы. Маркеры (токены), в отличие от литералов, могут состоять из нескольких символов или целого класса символов, таких как Представляя числа, они являются, так сказать, более общей формой терминальных символов, чем литералы. Терминальные символы - это наименьшие единицы, которые парсер может обработать. Нетерминальные символы состоят из одного или в основном нескольких терминальных символов. Например, терминальный символ может быть числом или математическим оператором, нетерминальный символ может быть целым выражением, состоящим из чисел и операторов. Парсер состоит из двух важных и нескольких менее важных частей, которые реализованы как функции. Первая функция - это yylex (), которая берет на себя задачу сканера. Сканер считывает ввод парсера за символом и преобразует его в поток токенов. Он не возвращает все токены за один раз за "звонок", а только следующий токен. Конечно, все токены должны быть определены заранее. Если символ не может быть идентифицирован как токен, он передается непосредственно как литерал (в принципе, лучше всего определять много входных символов как токены каждый день, тем самым делегируя задачу распознавания литерала от анализатора сканеру), литералы, объявленные как токены, должны быть изменены только один раз в сканере в случае изменений, вместо проверки и изменения каждого вхождения литерала в грамматике). В конце ввода находится предопределенный токен конца $ end, который имеет значение 0 (ноль) или отрицательное значение. Функция сканера считывает символы, распознает соответствующий токен или литерал и возвращает его тип в виде целочисленного значения. Фактическое содержимое токена, например значение числа для числового токена или строка для текстового токена, передается в глобальной переменной yylval. Функция yylex () может быть написана в виде исходного кода на C в программе YACC или сгенерирована с помощью LEX. Вторая важная функция - это yyparse (), фактический парсер. Это часть программы, созданной YACC. Эта функция продолжает вызывать сканер для чтения следующего токена, токена предварительного просмотра. Правила грамматики, которые должны быть указаны в грамматике синтаксического анализатора, применяются к так называемому потоку токенов. Например, такое правило может выглядеть следующим образом: «Выражение состоит из числа или выражения, оператора и другого выражения». Здесь токены - число и оператор, выражение - нетерминальный символ. Если они встречаются в последовательности номеров операторов порядкового номера, они могут быть сведены к выражению оператором выражения правила и снова сведены к выражению, т.е. номер оператора номера токена заменяется в два этапа выражением токена. В то же время можно определить действия C, которые выполняются при обработке правила. Все это станет понятнее на примере позже. Вам также нужна основная программа, которая просто вызывает синтаксический анализатор yyparse (). Это происходит в C в функции main (). Вы можете написать их самостоятельно или включить из библиотеки YACC, например, скомпилировав исходный код C, сгенерированный YACC, с опцией C-compiler -ly. cc y.tab.x -ly. Есть также некоторые другие функции, такие как функция обработки ошибок yyerror (), которая будет обсуждаться в главе II.6. Считываемый текст делится сканером на терминальные символы, то есть на токены и литералы. Они объединяются синтаксическим анализатором путем применения правил грамматики до тех пор, пока нетерминальные символы, т.е. пока весь ввод не будет обработан и останется только один символ (начальный символ) или пока не произойдет ошибка. Это называется восходящим подходом, так как правила грамматики работают, так сказать, снизу вверх. Обратный метод - соответственно стратегия сверху вниз. Там нетерминальные символы заменяются до тех пор, пока не останутся только терминальные символы. Однако это имеет недостаток по сравнению с методом «снизу вверх», так как необходимо считывать сразу несколько токенов, и, возможно, необходим так называемый «возврат». (Подробнее об этом в лекции по PCCTS). Начальный символ должен быть нетерминальным, и все остальные символы должны быть доступны из него, т.е. любой другой символ должен быть уменьшен каким-либо образом отдельно или вместе с другими символами до начального символа. Кроме того, все нетерминальные символы должны быть определены правилами грамматики, поэтому они должны быть хотя бы один раз в левой части правила. II.2 Структура исходной программы yacc Исходная программа YACC состоит из части объявления, части с действующими правилами грамматики и части с дополнительными функциями. В дополнение к фактическим объявлениям YACC, в разделе объявлений по желанию доступны некоторые объявления C. Эти три раздела разделены двойными знаками процента (%%): % {C declarations %}YACC declarations %%grammar rules %%Additional C source code, e.g. yylex () Объявления и функциональная часть являются необязательными, поэтому исходная программа YACC, по крайней мере, состоит из правил грамматики: %% grammar rules II.3 Грамматические правила Наиболее важным компонентом исходной программы YACC являются правила грамматики. Такое грамматическое правило состоит из нетерминального символа слева, за которым следует двоеточие (:) в середине и справа от одного или нескольких вариантов правила, разделенных символом канала (|). Каждая альтернатива правила также может быть написана индивидуально (как одно правило). Эти альтернативы правил состоят из ряда других нетерминальных и терминальных символов, причем литералы заключены в кавычки, а токены всегда должны быть прописными. Затем парсер «знает», что он может уменьшить такую строку символов в потоке токенов до символа перед двоеточием. Правило заканчивается точкой с запятой (;). Также допускается пустая альтернатива правила, парсер может затем уменьшить «ничто» до символа. Таким образом, вышеупомянутое грамматическое правило будет формальным: Expression: NUMBER | NUMBER operator NUMBER; Для каждой альтернативы элемента управления вы можете указать действия C, которые выполняются после выполнения этой альтернативы элемента управления. Эти нормальные операторы C просто пишутся в фигурных скобках после альтернативы правила. Есть также некоторые переменные, которые начинаются со знака доллара. Переменная $$ обозначает значение символа, предшествующего двоеточию, переменная $ 1 обозначает значение первого символа альтернативы правила, переменная $ 2 обозначает значение второго символа и т. Д. Вот несколько более сложный пример, грамматические правила для простого "карманный" калькулятор: %%Input: / * empty * / | Input line; Line: '\ n' | Expression '\ n' {printf ("\ t% .10g \ n", $ 1;}; Expression: NUMBER {$$ = $ 1; } | Expression '+' expression {$$ = $ 1 + $ 3; } | Expression '-' expression {$$ = $ 1 - $ 3; } | Expression '*' Expression {$$ = $ 1 * $ 2; } | Expression '/' expression {$$ = $ 1 / $ 2; } | '(' Expression ')' {$$ = $ 2; }; То есть вход состоит из «вообще ничего» или из ввода и строки (то есть символы ввода и строки, встречающиеся один за другим, могут быть проанализированы с символом ввода, а также «вообще ничего»). Строка должна содержать выражение для расчета. Однако, поскольку калькулятор не всегда завершается после одной строки, вводится "родительский" символ ввода. Строка состоит из символа конца строки ('\ n') или выражения и символа конца строки. Выражение состоит из числа или выражения, оператора (литерала) и другого выражения или составного выражения. Номер является токеном, т.е. символ терминала, который не может быть далее описан правилами. Вы можете видеть, что символы также могут быть рекурсивно определены в правилах, что очень часто имеет место. Конечно, как и во всех рекурсиях, важно, чтобы рекурсия также была разрешена. В этом примере это было бы не так, если бы в правилах для символа выражения отсутствовала альтернатива NUMBER. Здесь дополнительные действия C используются в правилах. Например, когда правило для строки успешно выполнено, переменная $ 1 (значение первого символа после двоеточия, в данном случае значение выражения) выводится в виде числа с плавающей запятой через десять символов после запятой на экране. Это означает, что он выведет результат вычисления входной строки калькулятора. Значение выражения вычисляется в соответствующих нижеприведенных правилах: если выражение состоит только из числа, выражение с выражением $$ = $ 1 получает значение числа. (Часть оператора здесь также может быть опущена, поскольку присваивание $$ = $ 1 выполняется неявно для каждого правила.) Если применяется альтернативное выражение правила: выражение «+», новое выражение получает значение первого выражения плюс значение второго Выражение (то есть значение первого плюс значение третьего символа, $$ = $ 1 + $ 3), в соответствии с другими альтернативами правила. Это (числовое) значение символа получает анализатор от сканера через глобальную переменную yylval. II.4 декларации Все символы, которые не определены правилами грамматики и не являются литералами (все токены), должны быть объявлены. Это делается с помощью ключевого слова% token в объявлениях YACC. Для примера с калькулятором вам, по крайней мере, нужно объявить токен NUMBER: % token NUMBER Вы также можете объявить несколько токенов одновременно использовать: % token NUMBER LETTER Дополнительные возможности определения токенов можно найти в главе IV.1 (левый / правый / неассоциативность операторов). Кроме того, вы можете захотеть, чтобы калькулятор не просто вычислял целые числа, потому что стандартный тип данных токенов в YACC - Integer. Однако это можно определить в объявлениях C с помощью макроса YYSTYPE, например, следующим образом: %{ #define YYSTYPE double %} Макрос YYSTYPE назначает токенам другой тип данных, в данном случае тип double. Это означает, что значение или содержимое токенов, к которым обращается переменная yylval, является числом с плавающей запятой. C include заявления также могут быть указаны здесь. II.5 функции Вы также должны указать функции yylex () и, в конечном счете, main (). Это не требуется YACC, но компилятором C, если вы хотите создать исполняемый синтаксический анализатор. Функция main () также может быть интегрирована через библиотеку YACC (опция компилятора C), как уже упоминалось. Функция yylex () также может быть разработана с помощью LEX (см. Главу V). Если вы обходитесь без него, вы записываете его в третьей части исходной программы YACC в соответствии с декларациями и грамматическими правилами в C, например: color:black;mso-ansi-language:EN-US">/* Grammatik_ */ color:black;mso-ansi-language:EN-US">%% color:black;mso-ansi-language:EN-US">int yylex () color:black;mso-ansi-language:EN-US">{ color:black;mso-ansi-language:EN-US"> int c; color:black;mso-ansi-language:EN-US"> while ((c = getchar ()) == ' ' || c == '\t'); color:black;mso-ansi-language:EN-US"> if (c == '.' || isdigit (c)) color:black;mso-ansi-language:EN-US"> { color:black;mso-ansi-language:EN-US"> ungetc (c, stdin); color:black;mso-ansi-language:EN-US"> scanf ("%1f",&yylval); color:black;mso-ansi-language:EN-US"> return NUMBER; color:black;mso-ansi-language:EN-US"> } color:black;mso-ansi-language:EN-US"> return c; color:black;mso-ansi-language:EN-US">} color:black;mso-ansi-language:EN-US"> color:black;mso-ansi-language:EN-US">int main () { yyparse; } Токены внутренне идентифицируются как числа выше 255, литералы по значению ASCII (число меньше или равно 255). Тем не менее, это обычно не имеет значения для пользователя YACC, потому что эти номера автоматически устанавливаются YACC. Функция yylex () в приведенном выше примере игнорирует пробелы и символы табуляции, возвращает токен NUMBER в числах, записывает его значение в глобальную переменную yylval и возвращает все остальные символы непосредственно в виде значения ASCII, то есть литерала. II.6 Обработка ошибок Если во время синтаксического анализа текста возникает ошибка, синтаксический анализатор, сгенерированный YACC, по умолчанию завершает работу с сообщением об ошибке «синтаксическая ошибка». Выводится с использованием функции yyerror (). Это также включено в опцию C-compiler -ly, или вы можете указать ее самостоятельно. Это может выглядеть так: color:black;mso-ansi-language:EN-US">yyerror ( color:black;mso-ansi-language:EN-US">char * color:black;mso-ansi-language:EN-US">s) { color:black;mso-ansi-language:EN-US">printf ("% color:black;mso-ansi-language:EN-US">s\ color:black;mso-ansi-language:EN-US">n", color:black;mso-ansi-language:EN-US">s); } Однако такое поведение неприемлемо во многих приложениях YACC. Например, в нашем калькуляторе не желательно, чтобы он просто прерывал работу после ошибочного ввода, но он должен возобновить свою работу после обнаружения ошибки и разрешить новый ввод. Это именно то, что вызывает следующее расширение правила грамматики для строки: ... Line: '\ n' | Expression '\ n' {printf ("\ t% .10g \ n", $ 1;} | error '\ n' {yyerrok}; ... Он просто вставляет новую альтернативу правила, которая вступит в силу, если произойдет предопределенная ошибка токена и символ новой строки. Ошибка означает, что произошла ошибка при анализе потока токена. Например, если синтаксический анализатор встречает выражение потока токенов '+' '+' '\ n', выражение '+' '+' не удовлетворяет правилам грамматики и поэтому сводится к ошибке токена. Затем вызывается функция YACC yyerrok (). Это вызывает функцию yyerror () для возврата сообщения об ошибке, а затем возвращается к последнему считанному токену или литералу без прерывания синтаксического анализатора. Последний прочитанный литерал - '\ n', который удовлетворяет альтернативе правила для строки. Тем не менее, не имеет значения, где вы используете yyerrok (). Если вы разместите его неправильно, желаемый эффект не будет получен в наиболее благоприятном случае.В худшем случае синтаксический анализатор устанавливает позицию, которая вызывает другую ошибку и, таким образом, создает бесконечный цикл. Например, если вы поместите оператор yyerrok () непосредственно после ошибки (то есть без каких-либо дополнительных литералов или токенов), yyerrok () будет выполнен непосредственно перед ошибкой, которая, в свою очередь, вызовет yyerrok () и т. Д. Напишите другое альтернативное правило, если вы уверены, что оно может быть настроено снова без ошибок. К сожалению, не так просто изменить текст сообщения об ошибке или выдать сообщение об ошибке в зависимости от ситуации. Эти изменения должны быть сделаны «вручную» в функции yacparse (), сгенерированной YACC, в некоторых случаях даже в main (). Это, конечно, очень громоздко, и реагировать на это выходит за рамки. На мой взгляд, этот недостаток является реальной слабостью YACC. III. Как работает парсер, сгенерированный Yacc? III.1 Процедура Парсер работает со стеком, операциями с этим стеком и состояниями, хранящимися в этом стеке. Параллельно с этим создается стек значений, который записывает (количество) значений символов. Наиболее важными операциями в стеке являются операции сдвига и уменьшения, а также операции перехода, принятия и ошибки. В операции сдвига считывается прогнозный токен, и полученное новое состояние помещается в стек. После этого прогнозный токен удаляется. Операция сокращения выполняется, когда синтаксический анализатор обнаружил правило грамматики, соответствующее текущему состоянию, и, возможно, потребуется запросить маркер предварительного просмотра. Тогда правая часть правила заменяется левой стороной, т.е. состояние в стеке изменено. Операция goto приводит к тому, что в стек помещается новое состояние, очень похожее на операцию сдвига. Однако маркер предпросмотра не удаляется. В случае возникновения ошибки, я. если анализатор обнаружит, что он не может обработать входные токены согласно спецификации, он выполнит операцию с ошибкой. Это приводит к сообщению об ошибке, как описано в главе II.6. Если ошибка не найдена и токен lookahead содержит маркер конца $ (токен '\ 0'), выполняется операция accept. В следующей таблице состояния в стеке представлены обработанными символами. В качестве упрощения операция goto не рассматривается. Столбец «Шаг» обозначает следующую операцию, в столбце «Правило» правило грамматики, после которого следующий шаг сокращается. Столбец стека значений указывает содержимое стека значений. Поперечная штриховка (#) означает, что в yylval для соответствующего символа (например, операторов и других литералов) не передается значение, т.е. yylval является неопределенным. Большой знак (>) указывает (только в операциях сокращения) положение, из которого можно получить доступ к стеку значений в правилах с переменными $ 1, $ 2 и т. Д. Разбор записи "3 * (4 + 2) \ n", то есть "NUMBER '*" (' NUMBER '+' NUMBER ')' '\ n' ", будет выглядеть следующим образом: Маркер Строка токена ввода Правило Шаг Значения маркера NUMBER '*' '(' NUMBER '+' NUMBER ')' '\n' $end shift 0 NUMBER '*' '(' NUMBER '+' NUMBER')' '\n' $end 5 reduce 0,> 3 Expression '*' '(' NUMBER '+' NUMBER')' '\n' $end shift 0,3 Expression '*' '(' NUMBER '+' NUMBER ')' '\n' $end shift 0,3,# Expression '*' '(' NUMBER '+' NUMBER ')' '\n' $end shift 0,3,#,# Expression '*' '(' NUMBER '+' NUMBER ')' '\n' $end 5 reduce 0,> 4 Expression '*' '(' Expression '+' NUMBER ')' '\n' $end shift 0,3,#,#,4 Expression '*' '(' Expression '+' NUMBER ')' '\n' $end shift 0,3,#,#,4,# Expression '*' '(' Expressionk '+' NUMBER ')' '\n' $end 5 reduce 0,3,#,#,4,#,> 2 Expression'*' '(' Expression '+' Expression ')' '\n' $end 6 reduce 0,3,#,#,> 4,#,2 Expression '*' '(' Expression ')' '\n' $end shift 0,3,#,#,6 Expression '*' '(' Expression ')' '\n' $end 10 reduce 0,3,#,> #,6,# Expression '*' Expression '\n' $end 8 reduce 0,> 3,#,6 Expression '\n' $end shift 0,18 Expression '\n' $end 4 reduce 0,> 18,# Line $end 2 reduce 0,> 18 Enter line $end 1 reduce 0 Enter $end accept 0 Сначала первый токен NUMBER перемещается в стек. Затем это может быть сведено к грамматическому правилу 5 к выражению. Затем токены перемещаются снова, пока НОМЕР не может быть снова приведен к выражению. Это переходит к строке 10, где выражение '+' выражение сводится к выражению грамматического правила. Особенно интересна также строка 16, где «ничто» сводится к грамматическому правилу 1 для ввода. В строке 18 определение синтаксиса затем завершается. Хотя маркер предварительного просмотра уже содержит $ end, он извлекается только в строке 18. Это будет зависеть от реализации синтаксического анализатора в состояниях, обсуждаемых в следующем разделе. III.2 Файл y.output Файл y.output может быть создан с помощью опции YACC -v. Он содержит все возможные состояния, которые парсер может принять. Для каждого состояния описаны так называемая конфигурация (описание состояния), доступные операции и операции, выполняемые в случае сокращения. Это полезно для понимания того, как работает сгенерированный синтаксический анализатор, например, для устранения неполадок или общего понимания, поскольку этот файл можно использовать для реконструкции фактического процесса анализа выражения. К образцу грамматики: % color:black;mso-ansi-language:EN-US">token color:black;mso-ansi-language:EN-US">IDENTIFIER %% color:black;mso-ansi-language:EN-US">expression : expression '-' IDENTIFIER color:black;mso-ansi-language:EN-US"> | IDENTIFIER erzeugt YACC die folgende Datei y.output: color:black;mso-ansi-language:EN-US">state 0 color:black;mso-ansi-language:EN-US"> $accept : _expression $end color:black;mso-ansi-language:EN-US"> color:black;mso-ansi-language:EN-US"> IDENTIFIER shift 2 color:black;mso-ansi-language:EN-US"> . error color:black;mso-ansi-language:EN-US"> color:black;mso-ansi-language:EN-US"> expression goto 1 color:black;mso-ansi-language:EN-US">state 1 color:black;mso-ansi-language:EN-US"> $accept : expression_$end color:black;mso-ansi-language:EN-US"> expression : expression_-IDENTIFIER color:black;mso-ansi-language:EN-US"> color:black;mso-ansi-language:EN-US"> $end accept color:black;mso-ansi-language:EN-US"> - shift 3 color:black;mso-ansi-language:EN-US"> . error color:black;mso-ansi-language:EN-US">state 2 color:black;mso-ansi-language:EN-US"> expression : IDENTIFIER_ (2) color:black;mso-ansi-language:EN-US"> color:black;mso-ansi-language:EN-US"> . reduce 2 color:black;mso-ansi-language:EN-US">state 3 color:black;mso-ansi-language:EN-US"> expression : expression -_IDENTIFIER color:black;mso-ansi-language:EN-US"> color:black;mso-ansi-language:EN-US"> IDENTIFIER shift 4 color:black;mso-ansi-language:EN-US"> . error color:black;mso-ansi-language:EN-US">state 4 color:black;mso-ansi-language:EN-US"> expression : expression - IDENTIFIER_ (1) color:black;mso-ansi-language:EN-US"> color:black;mso-ansi-language:EN-US"> . reduce 1 Состояние 0 всегда является начальным состоянием и всегда содержит начальный символ. Строка «$ accept: _expression $ end» описывает конфигурацию: подчеркивание (_) указывает текущую позицию выполнения, то есть до обнаружения выражения. Возможная операция здесь в том случае, если токен предварительного просмотра содержит ИДЕНТИФИКАТОР, операцию перехода в состояние 2, в противном случае - операцию ошибки. Состояние 2 после обнаружения ИДЕНТИФИКАТОРА. Здесь единственно возможная операция - это уменьшение в соответствии с правилом 2. После этого мы возвращаемся к состоянию 0, где затем, когда что-то было преобразовано в выражение, операция goto помещает состояние 1 в стек. Это продолжается до тех пор, пока все входные данные не будут обработаны, как показано в следующей таблице для ввода IDENTIFIER '-' IDENTIFIER: Шаг Стек (Состояние) Предпросмотр-маркера Операция 1 0 IDENTIFIER shift 2 2 0,2 reduce 2 3 0 goto 1 4 0,1 - shift 3 5 0,1,3 IDENTIFIER shift 4 6 0,1,3,4 reduce 1 0,1 $end accept IV. Неопределенности и конфликты IV.1. Левый / правый / неассоциативность операторов Часто желательно определить ассоциативность токенов или операторов, то есть «связывание». Например, в нашем примере калькулятора есть оператор «/» (shared). Если это происходит несколько раз на входе, например в «1/2/3», неясно, означает ли это «(1/2) / 3» или «1 / (2/3)». Обычно, если не указывать скобки явно, подразумевается первая альтернатива. Это ассоциативно слева, так как вначале оценивается разделенный слева, а затем только правый символ. В грамматике YACC этот тип оценки достигается объявлением% left '/' (обычно% left TOKEN или% left LITERAL). Соответственно, правая ассоциативность объявляется с% right TOKEN или% right LITERAL. Также можно объявить токены как неассоциативные (% unassoc TOKEN или% unassoc LITERAL). Это полезно, например, в операторах сравнения в языках программирования. Ввод "x <y <4" был бы тогда недействительным и вызвал бы соответствующее сообщение об ошибке. Если вы не укажете ассоциативность (например, только токен%), тогда оценивается правоассоциативность. IV.2. Приоритет операторов В примере калькулятора возникает другая проблема: приоритет операторов. Вход «1 + 2 * 3» может быть оценен как «1+ (2 * 3)», а также «(1 + 2) * 3». Для достижения обычного правила «вычисление точки перед вычислением линии» необходимо обеспечить правильное объявление грамматики YACC. Ранжирование операторов (то есть, для парсера, порядок вычисления токенов) определяется порядком объявления в грамматике YACC. Чем дальше назад в грамматике объявлен токен, тем больше его приоритет. Например, по объявлению: % left '+' '-' % left '*' '/' вычисление известной точки перед вычислением линии достигается, и все операторы определяются как левоассоциативные одновременно. Иногда возникает проблема, что литерал используется как знак для разных операторов. Например, знак «-» (минус) используется как для вычитания, так и для отрицания. Если вы хотите определить разные приоритеты для операций, контекстно-зависимый приоритет становится необходимым. Это можно решить в YACC для примера (а также в целом) следующим образом: ... % left '+' '-' % left '*' '/' % осталось NEG %% ... | Expression '/' expression {$$ = $ 1 / $ 2; } | '-' expression% prec NEG {$$ = - $ 2} | '(' Expression ')' {$$ = $ 2; }; Здесь вводится вспомогательный токен NEG, который имеет более высокий приоритет, чем все остальные операторы. В правиле грамматики отрицания этому назначается тот же приоритет, что и для NEG, по ключевому слову %prec (для приоритета). IV.3. уменьшить / сдвинуть - конфликты Другой тип конфликта возникает, например, в следующей (неполной) примерной грамматике: color:black;mso-ansi-language:EN-US">if_statement: IF expression THEN statement color:black;mso-ansi-language:EN-US"> | IF expression THEN statement ELSE statement; color:black;mso-ansi-language:EN-US"> При входе Если "x" тогда "y" доминирует; остальное свободно; Для обработки парсером после обработки существует два способа, если y доминирует затем: · Парсер может применить первое правило и выполнить операцию сокращения. В этом примере больше будет принадлежать внешнему, если "x" тогда ... · Парсер также может применить второе правило и выполнить операцию сдвига. В этом примере больше будет принадлежать внутреннему, если "y" доминирует. Поэтому такой конфликт обычно называют конфликтом уменьшения / сдвига. По умолчанию YACC выполняет операцию сдвига, но выдает предупреждение при компиляции исходного кода YACC. Если вы уверены, что операция сдвига является желательной, вы можете подавить это предупреждение с помощью объявления% Ожидаемое n: Если YACC встречает ровно n конфликтов уменьшения / сдвига в грамматике, предупреждения не выдаются. Часто также возможно решить конфликты уменьшения / сдвига, используя декларации ассоциативности (вопрос ассоциативности также является конфликтом уменьшения / сдвига!). В общем, лучше всего сформулировать грамматику однозначно, но во многих случаях (как в этом примере) это абсолютно нетривиальная задача, а иногда и невозможная. IV.4. уменьшить / уменьшить - конфликты Также в следующем (неполном) примере грамматики есть конфликт: set: / * empty * / | much easy word | sentence word; Maybe word: / * blank * / | word; Вот два способа синтаксического разбора слова: · либо синтаксический анализатор может свести слово к псевдослову, а затем к предложению, · или синтаксический анализатор может свести «ничто» к предложению и сократить его до предложения вместе со словом. Такой конфликт обычно называют конфликтом уменьшения / уменьшения, потому что есть две возможности для операции уменьшения. По умолчанию YACC применяет указанное выше правило в грамматике. Тем не менее, здесь также лучше сформулировать грамматику с самого начала, в случае примера, например: set: / * empty * / | sentence word; В этом примере это кажется тривиальным, поскольку обычно никто не использует первое решение в любом случае. Однако в более сложных случаях этот конфликт может быть трудным. V. Сотрудничество со сканером Lex Вместо того, чтобы писать функцию yylex () в C «вручную», было бы неплохо создать ее с помощью LEX, особенно для сканеров, которые должны делать немного больше. LEX создает файл lex.yy.c из исходного файла LEX (см. Лекцию по LEX), который содержит ранее обсужденную функцию yylex (), сканер. Это должно быть интегрировано в функциональную часть грамматики YACC с помощью оператора C #include "lex.yy.c". В качестве альтернативы, вы также можете опустить оператор include, но тогда вы также должны указать исходный код C, сгенерированный LEX при компиляции. Процедура такова: вы создаете сканер с LEX, фактический парсер с YACC, и компилируете все с помощью компилятора C до готового парсера (см. Также рисунок), например, следующим образом: color:black;mso-ansi-language:EN-US">lex taschenrechner.x color:black;mso-ansi-language:EN-US">yacc taschenrechner.y color:black;mso-ansi-language:EN-US">cc y.tab.c -ly -ll bzw. cc y.tab.c lex.yy.c -ly -ll color:black;mso-ansi-language:EN-US"> Опция компилятора C -ll включает в программу стандартную библиотеку LEX. Например, программа LEX, которая описывает сканер для нашего калькулятора, может выглядеть так: color:black;mso-ansi-language:EN-US">%% color:black;mso-ansi-language:EN-US">[0-9]+ {yylval = atoi(yytext); color:black;mso-ansi-language:EN-US"> return NUMBER;} [ \t]+ ; . return(yytext[0]); Приложение A: Калькулятор грамматики завершен % { #include <ctype.h> #include <stdio.h> #define YYSTYPE double %} % token NUMBER % left '+' '-' % left '*' '/' % left NEG %% Input: / * empty * / | Input line; Line: '\ n' | Expression '\ n' {printf ("\ t% .10g \ n", $ 1;} | error '\ n' {yyerrok}; Expression: NUMBER {$$ = $ 1; } | Expression '+' expression {$$ = $ 1 + $ 3; } | Expression '-' expression {$$ = $ 1 - $ 3; } | Expression '*' Expression {$$ = $ 1 * $ 2; } | Expression '/' expression {$$ = $ 1 / $ 2; } | '(' Expression ')' {$$ = $ 2; }; %% #include "lex.yy.c" Спасибо за внимания. Если вам понравилось статья, ставьте лайк и пожалуйста комментируйте. Статья создана Carcinid © 2019, специально для lolzteam.net, перед тем как скопировать - напишите в ЛС об разрешении.