btyacc - Интернет в облаке

ПРОГРАММА:

ИМЯ

btyacc - an ЛАЛР(1) генератор парсеров с поддержкой поиска с возвратом

СИНТАКСИС

бтяакк [-б префикс] [-д] [-дИМЯ ...] [-E] [-l] [-r] [-S х.ске] [-телевидение]
имя файла.y

Описание

btyacc - это модифицированная версия byacc (Berkeley YACC), которая, в свою очередь, является общественным достоянием.
версия оригинального генератора синтаксического анализатора AT&T YACC.

btyacc читает спецификацию грамматики в файле имя файла.y и генерирует LR(1)
парсер для него. Парсер состоит из набора ЛАЛР(1) таблицы синтаксического анализа и процедура драйвера
написан на языке программирования C. btyacc обычно записывает таблицы синтаксического анализа и
подпрограмма драйвера в файл префикс.tab.c, Где префикс по умолчанию - `y '.

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

Примечание: Скелет парсера, предоставленный автором восходящего потока btyacc, компилируется только как C ++. Использовать
скелет /usr/doc/btyacc/examples/btyacc-c.ske чтобы сгенерировать парсер, который компилирует оба
как C и C ++. (К сожалению, этот альтернативный скелет в настоящее время не проверяет malloc ()
возвращаемые значения.)

Опции

-b префикс Измените префикс, добавленный к именам выходных файлов, на строку, обозначенную
префикс. Префиксом по умолчанию является символ `y '.

-d Создать файл заголовка с именем префикс.tab.h вместе с префикс.tab.c,
содержащий определения символов и декларацию для ГИСТИП и Yylval.

-DИМЯ Определите переменную препроцессора btyacc ИМЯ, для использования с % ifdef ИМЯ
директивы в файле грамматики.

-E Вывести предварительно обработанную грамматику на стандартный вывод.

-l Не вставлять #линия директивы в сгенерированный код парсера.

-r Записать код парсера и связанные таблицы в разные файлы. В то время как
таблицы можно найти в префикс.tab.c как и раньше, код теперь пишется
в префикс.код.с.

-S х.ске Выберите другой скелет парсера. Каркас по умолчанию встроен в
программу, но копию можно найти в файле btyaccpa.ske.

-t Вызывает компиляцию отладочного кода в сгенерированный синтаксический анализатор.

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

БТИАКК расширения

Откат поддержка
Всякий раз, когда синтаксический анализатор, сгенерированный btyacc, сталкивается с ошибкой сдвига-уменьшения или уменьшения-уменьшения в
таблица синтаксического анализа, она запоминает текущую точку синтаксического анализа (состояние стека и входного потока) и переходит
в пробный режим синтаксического анализа. Затем он продолжает синтаксический анализ, игнорируя большинство действий правил. Если он работает
в ошибку (либо через таблицу синтаксического анализа, либо через вызов действия ДА ОШИБКА), Это
возвращается к последней конфликтной точке и пробует другую альтернативу. Если оно
находит успешный путь (достигает конца ввода или вызывает действие ЙИВАЛИД), Это
возвращается к точке, где он впервые вошел в режим пробного синтаксического анализа, и продолжает полный
parse (выполнение всех действий) по пути успешного испытания.

Действия в btyacc бывают двух видов: {} действия, которые выполняются только когда не в
пробный режим и [] действия, которые выполняются независимо от режима.

Пример. В грамматиках YACC для C стандартным приемом, известным как "прием обратной связи лексера", является
используется для поиска имен typedef. Лексер использует семантическую информацию, чтобы решить, есть ли данные
идентификатор - это имя typedef или нет, и возвращает специальный токен. С btyacc вы нет
дольше нужно это делать; лексер должен всегда возвращать идентификатор. Btyacc
грамматика тогда нуждается в правиле формы:

имя типа: ID [ if (! IsTypeName (LookupId ($ 1))) ДА ОШИБКА; ]

Однако обратите внимание, что добавление правил поиска с возвратом замедляет работу анализатора. На практике вы
следует попытаться ограничить количество конфликтов в грамматике до того, что абсолютно
необходимо. Подумайте об использовании "хака обратной связи лексера", если это чистое решение, и
Зарезервируйте возврат с возвратом для некоторых особых случаев.

btyacc проводит свои испытания, используя правило «сначала попробуйте сдвинуть, затем попробуйте уменьшить в порядке
что конфликтующие правила появляются во входном файле ". Это означает, что вы можете реализовать
правила семантического разрешения неоднозначности, например: (1) Если это похоже на объявление, то это так,
в противном случае (2) Если это похоже на выражение, в противном случае (3) это синтаксическая ошибка
[Эллис и Страуструп, Справочное руководство по C ++ с аннотациями, стр. 93]. Для этого положите все
правила для объявлений перед правилами для выражений в файле грамматики.

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

В настоящее время сгенерированный парсер выполняет нет отсечение альтернативных путей синтаксического анализа. Избегать
экспоненциальный взрыв возможных путей (и времени разбора), вам нужно вручную указать
парсер, когда он может выбросить сохраненные пути, используя ЙИВАЛИД утверждение. В
На практике это оказывается довольно легко сделать. Например, синтаксический анализатор C ++ может просто
содержать [ДЕЙСТВИТЕЛЬНО;] после каждого полного объявления и правила утверждения, в результате чего
состояние обратного отслеживания удаляется после появления символа `; ' или `} '- никогда не будет
ситуация, в которой полезно вернуться назад через любой из них.

Улучшенный знак должность обращение
Компиляторам часто необходимо строить AST (абстрактные синтаксические деревья) так, чтобы каждый узел в дереве
может относиться к исходному тексту проанализированной программы. В ЮПОСН поддерживаемый механизм
by btyacc помогает автоматизировать вычисление позиции текста и назначать
вычисленные позиции текста в узлах AST.

В стандартных YACC каждый токен и каждый нетерминал имеет ГИСТИП семантическое значение
прикреплен к нему. С btyacc каждый токен и каждый нетерминал также имеют ЮПОСН текст
положение прикреплено к нему. ЮПОСН это определяемый пользователем тип.

btyacc поддерживает стек значений позиции текста так же, как он поддерживает стек
семантических значений. Чтобы использовать функцию положения текста, вам необходимо #define домен
следующие:

YYPOSN Символ препроцессора для типа C / C ++ текстовой позиции, прикрепленной к каждому
токен и нетерминал.

yyposn Глобальная переменная типа ЮПОСН. Лексер должен назначить текстовую позицию
вернул токен в yyposn, точно так же, как он присваивает семантическое значение
вернул токен в йылвал.

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

Обычно эта функция извлекает позиции текста из правила правой части.
компоненты и либо присваивает их возвращенной структуре / дереву $$, либо, если нет
возвращается значение $$, помещает их в текстовую позицию ret, где оно будет
позже подобраны по другим правилам. Его прототип:

аннулировать Уменьшить Posn(
YYPOSN & в отставке,
YYPOSN * term_posns,
YYSTYPE * срок_вала,
Int номер_термина,
Int stk_pos,
Int йычар,
YYPOSN & yyposn,
Тип пользователя дополнительно);

ret Ссылка на позицию текста, возвращаемую правилом. Вы должны перезаписать
это с вычисленной позицией текста, которую дает правило, аналогично
семантическое значение $$.

term_posns
Массив компонентов правила правой части ' ЮПОСН текстовые позиции,
аналогично $ 1, $ 2, ..., $ N для семантических значений.

term_val Массив компонентов правила правой части ' ГИСТИП ценности. Эти
сами $ 1, ..., $ N.

term_no Количество компонентов в правой части сокращенного правила, т. е.
размер массивов term_posns и term_val. Также равно N в $ 1, ...,
$ N.

stk_pos ГИСТИП/ЮПОСН положение стека перед сокращением.

yychar Маркер просмотра вперед, который следует сразу за уменьшенной правой частью
компоненты.

yyposn ЮПОСН токена, который следует сразу за сокращенной правой частью
компоненты.

extra Определяемый пользователем дополнительный аргумент, переданный в ReducePosn.

YYREDUCEPOSNFUNCARG
Дополнительный аргумент передан функции ReducePosn. Этот аргумент может быть любым
переменная, определенная в btyaccpa.ske.

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

К сожалению, такой подход приводит к утечке памяти, если ГИСТИП тип указателя. btyacc
позволяет вам предоставлять функции для очистки значений семантической и текстовой позиции,
#defineвставьте следующие символы в преамбулу вашего файла грамматики:

ЙЙДЕЛЕТЕВАЛЬ
Символ препроцессора для функции, вызываемой перед семантическим значением токена
или нетерминальный отбрасывается.

ЙЙДЭЛЕТЕПОСН
Символ препроцессора для функции, вызываемой перед текстовой позицией токена
или нетерминальный отбрасывается.

Обе функции вызываются с двумя аргументами. Первый аргумент типа ГИСТИП or ЮПОСН
это значение, которое будет отброшено. Второй аргумент имеет тип Int и является одним из
три значения:

0 отбрасывание входного токена

1 состояние отбрасывания в стеке

2 очистка стека при прерывании

Детальная синтаксис ошибка сообщения
если ты #define переменная препроцессора YYERROR_DETAILED в вашем файле грамматики вы должны
также определите следующую функцию обработки ошибок:

аннулировать yyerror_detailed(
символ * текст,
Int ошибка,
YYSTYPE &
значение_ошибки,
YYPOSN & errt_posn);

текстовое сообщение об ошибке

код ошибки токена, вызвавшего ошибку

значение_ошибки
значение токена, вызвавшего ошибку

errt_posn текстовая позиция токена, вызвавшего ошибку

препроцессор Директивы
btyacc поддерживает определение символов и воздействие на них с помощью условных директив внутри
файлы грамматики, в отличие от препроцессора C.

%определять ИМЯ
Определите символ препроцессора ИМЯ. Эквивалент переключателя командной строки
-DИМЯ.

% ifdef ИМЯ
Если переменная препроцессора ИМЯ определено, обработайте текст из этого % ifdef в
закрытие % endif, в противном случае пропустите.

% endif Директива закрытия для % ifdef. % ifdefs не могут быть вложенными.

%включают ИМЯ ФАЙЛА
Обрабатывать содержимое файла с именем ИМЯ ФАЙЛА. Только один уровень вложенности %включают
позволено.

% идент STRING
Вставьте `#идентификатор STRING'в выходной файл. STRING должен быть
строковая константа, заключенная в "".

Унаследованный Атрибуты
Унаследованные атрибуты не документируются. (См. README и исходный код btyacc для
мало информации.) Если вы разобрались, как они работают, свяжитесь со мной по[электронная почта защищена]>!

ошибки

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

зубров %ожидать директива не поддерживается.

Здесь нет %еще и % ifndef. % ifdefs и %включаютs не могут быть вложенными.

Авторы

Роберт Корбетт[электронная почта защищена]> /[электронная почта защищена]> был одним из
оригинальные авторы Беркли byacc. Крис Додд[электронная почта защищена]> был блестящим
идея добавления возможностей обратного отслеживания и отвечает за начальный возврат
изменения. Вадим Маслов[электронная почта защищена]> Доработан код.

Этот документ был написан Ричардом Аттерером.[электронная почта защищена]> для Debian
Дистрибутив GNU / Linux, но передан в общественное достояние и, таким образом, может использоваться свободно
для любых целей.

Файлы

/usr/doc/btyacc/examples/btyaccpa.ske

/usr/doc/btyacc/examples/btyacc-c.ske

/ usr / doc / btyacc / README

Читать причислены

бизон(1) (или `info bison '), поакк(1), Yacc(1), Antlr(1)

бтяакк(1)

Используйте btyacc онлайн с помощью сервисов onworks.net