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

ПРОГРАММА:

ИМЯ

yacc - еще один компилятор компилятора (ТЕХНОЛОГИИ)

СИНТАКСИС

Yacc [−dltv] [-б префикс_файла] [-p sym_prefix] грамматика

ОПИСАНИЕ

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

Форма и значение грамматики описаны в разделе РАСШИРЕННОЕ ОПИСАНИЕ.

Исходный код C и файл заголовка должны быть созданы в форме, подходящей в качестве входных для C
компилятор (см. c99).

ДОПОЛНИТЕЛЬНЫЕ УСЛУГИ, НЕ ВКЛЮЧЕННЫЕ В ПАКЕТ

Ассоциация Yacc утилита должна соответствовать тому Базовые определения POSIX.1-2008, Раздел
12.2, утилита Синтаксис Инструкции, за исключением положения 9.

Поддерживаются следующие варианты:

-б префикс_файла
Используйте префикс_файла вместо y в качестве префикса для всех имен выходных файлов. Код
файл y.tab.c, заголовочный файл y.tab.h (создано, когда -d указано), а
файл описания у.выход (создано, когда -v указано), следует заменить на
префикс_файла.tab.c, префикс_файла.tab.hкачества префикс_файла.выход, Соответственно.

-d Напишите заголовочный файл; по умолчанию записывается только файл кода. В #define
операторы связывают коды токенов, присвоенные Yacc с заявленным пользователем
имена токенов. Это позволяет исходным файлам, отличным от y.tab.c для доступа к токену
коды.

-л Создайте файл кода, который не содержит никаких #линия конструкции. Если этот вариант
отсутствует, не указано, содержит ли файл кода или файл заголовка
#линия директивы. Это следует использовать только после грамматики и связанного
действия полностью отлажены.

-p sym_prefix
Используйте sym_prefix вместо yy в качестве префикса для всех внешних имен, производимых
Yacc. Затронутые имена должны включать функции yyparse(), юлекс(), а также
йеррор(), а переменные Yylval, йычаркачества yydebug. (В оставшейся части
В этом разделе для шести процитированных символов используются их имена по умолчанию.
только для удобства обозначений.) -p
вариант; Однако -p опция не влияет #define символы, созданные
Yacc.

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

-v Напишите файл, содержащий описание парсера и отчет о конфликтах.
порождены двусмысленностями в грамматике.

ОПЕРАНДЫ

Требуется следующий операнд:

грамматика Путь к файлу, содержащему инструкции, в дальнейшем называемый грамматика, Для
который должен быть создан парсер. Формат грамматики описан в
РАСШИРЕННОЕ ОПИСАНИЕ.

СТАНДИН

Не используется.

ВХОД FILES

Файл грамматика должен быть текстовым файлом, отформатированным, как указано в РАСШИРЕННОМ ОПИСАНИИ.
.

ОКРУЖАЮЩАЯ СРЕДА ПЕРЕМЕННЫЕ

Следующие переменные среды должны влиять на выполнение Yacc:

ДЛИННЫЙ Задайте значение по умолчанию для переменных интернационализации, которые не установлены или
нулевой. (См. Том Базовых определений POSIX.1-2008, Раздел 8.2,
Интернационализация Переменные за приоритет интернационализации
переменные, используемые для определения значений категорий локали.)

LC_ALL Если установлено непустое строковое значение, переопределить значения всех остальных
переменные интернационализации.

LC_CTYPE Определите локаль для интерпретации последовательностей байтов текстовых данных
как символы (например, однобайтовые, а не многобайтовые символы в
аргументы и входные файлы).

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

НЛПСАТ Определите расположение каталогов сообщений для обработки LC_MESSAGES.

Ассоциация ДЛИННЫЙ и LC_ * переменные влияют на выполнение Yacc как указано. В main()
функция, определенная в Yacc Библиотека позвонит:

setlocale (LC_ALL, "")

и, таким образом, программа, сгенерированная Yacc также зависит от содержания этих
переменные во время выполнения.

АСИНХРОННЫЙ СОБЫТИЯ

По умолчанию.

стандартный вывод

Не используется.

СТДЕРР

Если в грамматика, Yacc напишу
сообщить об этих конфликтах в стандартную ошибку в неопределенном формате.

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

ВЫВОД FILES

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

Code Файл
Этот файл должен содержать исходный код C для yyparse() функция. Он должен содержать
код для различных семантических действий с макроподстановкой, выполняемой над ними как
описано в разделе РАСШИРЕННОЕ ОПИСАНИЕ. Он также должен содержать копию #define
операторы в заголовочном файле. Если % union декларация используется, декларация для
YYSTYPE также должен быть включен в этот файл.

заголовок Файл
Заголовочный файл должен содержать #define операторы, которые связывают номера токенов с
имена токенов. Это позволяет исходным файлам, отличным от файла кода, получить доступ к кодам токенов.
Если % union используется декларация, декларация YYSTYPE и внешний ГИСТИП Yylval
декларация также должна быть включена в этот файл.

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

РАСПРОСТРАНЕНИЯ ОПИСАНИЕ

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

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

Учитывая грамматику, Yacc утилита генерирует файлы, описанные в ВЫХОДНЫХ ФАЙЛАХ
раздел. Файл кода можно скомпилировать и связать с помощью c99. Если декларация и
программные разделы файла грамматики не включали определения main(), юлекс(), а также
йеррор(), скомпилированный вывод требует связывания с внешними версиями тех
функции. Версии по умолчанию main() и йеррор() поставляются в Yacc библиотека и
можно связать с помощью -л y операнд к c99, Yacc библиотечные интерфейсы не нуждаются
поддержка интерфейсов с отличными от стандартного yy префикс символа. Приложение предоставляет
функция лексического анализатора, юлекс(); в закон утилита специально разработана для
создать такую ​​рутину.

вход Язык
Приложение должно гарантировать, что каждый файл спецификации состоит из трех разделов в
заказ: Заявления, грамматика условиями,качества программы, разделенные двойным
персонажи ("%%"). Разделы объявлений и программ могут быть пустыми. Если последний
пустой, предыдущий "%%" знак, отделяющий его от раздела правил, можно не ставить.

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

лексический Структура of домен Grammar
В , , а также символ игнорируется, за исключением того, что
приложение должно гарантировать, что они не появляются в именах или зарезервированных многосимвольных
символы. Комментарии должны быть заключены в "/ * ... * / ", и может появляться везде, где указано имя
действует.

Имена имеют произвольную длину, состоят из букв, точек (''), подчеркивания ('_'), а также расширение
не начальные цифры. Прописные и строчные буквы различны. Соответствующие приложения
не должен использовать имена, начинающиеся на yy or YY С Yacc парсер использует такие имена. Многие из
имена появляются в окончательном выводе Yacc, и поэтому их следует выбирать так, чтобы они соответствовали
с любыми дополнительными правилами, созданными компилятором C. В частности они появляются
in #define заявления.

Литерал должен состоять из одного символа, заключенного в одинарные кавычки. Все
управляющие последовательности, поддерживаемые для символьных констант стандартом ISO C, должны быть
поддерживается Yacc.

Отношения с лексическим анализатором подробно обсуждаются ниже.

Приложение должно гарантировать, что символ NUL не используется в правилах грамматики или
литералы.

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

Как правило Yacc устанавливает связь между генерируемыми им символическими именами и их
базовое числовое значение. Раздел объявлений позволяет управлять
присвоение этих значений.

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

Первая группа деклараторов ниже все принимает список имен в качестве аргументов. Этот список может
необязательно предшествовать имени члена союза C (называемого день ниже) появляющийся
в '<' и '>'. (В качестве исключения из типографских правил остальной части этого
том POSIX.1-2008, в данном случаедень> не представляет метапеременную, но
буквальные угловые скобки, окружающие символ.) день указывает, что
токены, указанные в этой строке, должны быть того же типа C, что и член объединения, на который ссылается
день. Более подробно это обсуждается ниже.

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

Следующее заявляет имя быть токеном:

% токен [<день>] имя [номер] [имя [номер]]...

If день присутствует, тип C для всех токенов в этой строке должен быть объявлен как тип
на который ссылается день. Если положительное целое число, номер, следует за имя, это значение должно быть
присвоенный токену.

Следующее заявляет имя быть токеном и присваивает ему приоритет:

%левый [<день>] имя [номер] [имя [номер]]...
%Правильно [<день>] имя [номер] [имя [номер]]...

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

Следующее заявляет имя быть токеном и указывает, что это не может быть использовано
ассоциативно:

% nonassoc [<день>] имя [номер] [имя [номер]]...

Если парсер обнаруживает ассоциативное использование этого токена, он сообщает об ошибке. Если день is
присутствует, он должен объявить тип C для имяs, как описано для % токен.

Следующее заявляет, что член профсоюза имяs не являются терминалами, поэтому требуется
иметь день поле в начале:

%тип <день> имя...

Поскольку он имеет дело только с нетерминалами, присвоение номера токена или использование литерала
тоже запрещено. Если эта конструкция присутствует, Yacc выполняет проверку типа; если это
отсутствует конструкция, стек синтаксического анализа должен содержать только Int тип.

Каждое имя, используемое в грамматика не определено % токен, %левый, %Правильноили % nonassoc
Предполагается, что объявление представляет нетерминальный символ. В Yacc коммунальное предприятие должно сообщать
ошибка для любого нетерминального символа, который не появляется в левой части хотя бы одного
грамматическое правило.

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

Следующие деклараторы не соответствуют предыдущему шаблону.

Следующее объявляет нетерминальный имя быть Начало символ, который представляет собой
самая большая, самая общая структура, описываемая правилами грамматики:

%Начните имя

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

Ниже объявляется Yacc стек значений должен быть объединением различных типов значений
желательно.

% union { тело of союз (in C)}

Тело объединения не должно содержать токенов предварительной обработки несбалансированных фигурных скобок.

По умолчанию значения, возвращаемые действиями (см. Ниже) и лексическим анализатором, должны быть
типа Int, Yacc Утилита отслеживает типы и вставляет соответствующие
имена членов union для выполнения строгой проверки типа результирующего синтаксического анализатора.

В качестве альтернативы, если хотя бы одиндень> используется конструкция, объединение может быть объявлено
в файле заголовка (который должен быть включен в раздел объявлений с помощью #включают
строить внутри %{ и %}) и ЬурейеЕ используется для определения символа YYSTYPE для представления
этот союз. Эффект % union заключается в предоставлении объявления YYSTYPE непосредственно из
домен Yacc вход.

Объявления и определения языка C могут появляться в разделе объявлений, прилагаемом
по следующим отметкам:

%{ ... %}

Эти операторы должны быть скопированы в файл кода и иметь в нем глобальную область видимости, поэтому
что их можно использовать в правилах и разделах программы. Заявления не должны содержать
"%}" вне комментария, строкового литерала или многосимвольной константы.

Приложение должно гарантировать, что раздел объявлений завершается токеном %%.

Grammar Правила in Yacc
Раздел правил определяет контекстно-свободную грамматику, которая должна быть принята функцией. Yacc
генерирует и связывает с этими правилами действия на языке C и дополнительный приоритет
Информация. Грамматика описана ниже, а формальное определение следует за ней.

Раздел правил состоит из одного или нескольких грамматических правил. Грамматическое правило имеет вид:

A : BODY ;

Символ A представляет собой нетерминальное имя, и BODY представляет собой последовательность из нуля или
БОЛЕЕ имяs, буквальныйс, а семантический действиеs, за которым может следовать необязательный
старшинство правитьс. Только имена и литералы участвуют в образовании
грамматика; семантические действия и правила приоритета используются другими способами. В а также
в находятся Yacc пунктуация. Если существует несколько следующих друг за другом грамматических правил с
та же левая сторона, ('|') можно использовать, чтобы избежать перезаписи
левая сторона; в этом случае появляется только после последнего правила. Тело
часть может быть пустой (или не содержать имен и литералов), чтобы указать, что нетерминальный
символ соответствует пустой строке.

Ассоциация Yacc Утилита присваивает каждому правилу уникальный номер. Правила с использованием вертикальной черты
обозначения - это отдельные правила. Номер, присвоенный правилу, отображается в описании.
.

Элементы, составляющие ТЕЛО:

имя, буквальный
Они образуют правила грамматики: имя это либо знак или нетерминальный;
буквальный обозначает себя (за вычетом лексически обязательных кавычек).

семантический действие
С каждым правилом грамматики пользователь может связывать действия, которые будут выполняться каждый раз.
правило распознается в процессе ввода. (Обратите внимание, что слово `` действие '' может
также относятся к действиям парсера - сдвиг, уменьшение и т. д.)

Эти действия могут возвращать значения и могут получать значения, возвращенные предыдущим
действия. Эти значения хранятся в объектах типа YYSTYPE (см. % union).
значение результата действия должно храниться в стеке синтаксического анализа с левой
сторона правила, к которой будут иметь доступ другие сокращения как часть их правого
боковая сторона. Используядень> информация, представленная в разделе объявлений,
код, созданный Yacc могут быть строго проверены по типу и содержать произвольные
Информация. Кроме того, лексический анализатор может предоставлять такие же виды
значения для токенов, если это необходимо.

Действие - это произвольный оператор C, который может выполнять ввод или вывод, вызывать
подпрограммы и изменить внешние переменные. Действие - это один или несколько операторов C
заключен в фигурные скобки '{' и '}'. Заявления не должны содержать
токены предварительной обработки несбалансированных фигурных скобок.

В действии могут использоваться определенные псевдопеременные. Это макросы для доступа
к структурам данных, внутренне известным Yacc.

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

$номер Это относится к значению, возвращаемому компонентом, указанным в
знак номер в правой части правила, читая слева направо;
номер может быть нулевым или отрицательным. Если номер равно нулю или отрицательно, это
относится к данным, связанным с именем в стеке парсера
перед крайним левым символом текущего правила. (То есть, "0 $"
относится к имени, непосредственно предшествующему самому левому имени в
текущее правило должно быть найдено в стеке парсера и "-1 доллар" обозначает
символ для его слева.) Если номер относится к элементу за текущим
точка в правиле или за пределами нижней части стека, результат будет
неопределенный. Если проверка типа включена и тип значения, которое будет
назначенный не может быть определен, может быть сгенерировано диагностическое сообщение.

$<день>номер
Они точно соответствуют соответствующим символам без день
включение, но допускает строгую проверку типов (и исключает нежелательные
преобразования типов). Эффект заключается в том, что макрос расширяется для использования день
для выбора элемента из союза YYSTYPE (используя имя_данных.тег).
Это особенно полезно, если номер не положительный.

$<день> $ Это накладывает на ссылку тип указанного члена союза
by день. Эта конструкция применима, когда ссылка на левую
значение контекста встречается в грамматике и обеспечивает Yacc со средствами
для выбора типа.

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

По умолчанию значение правила должно быть значением первого элемента в нем.
Если у первого элемента нет типа (особенно в случае
literal), а проверка типов включается %тип, должно появиться сообщение об ошибке.

старшинство
Ключевое слово % pre может использоваться для изменения уровня приоритета, связанного с
конкретное грамматическое правило. Примеры этого - в случаях, когда унарные и двоичные
имеют одинаковое символическое представление, но должны иметь разные
приоритеты, или когда обработка неоднозначной конструкции if-else
необходимо. Зарезервированный символ % pre может появиться сразу после тела
правила грамматики и могут сопровождаться именем токена или литералом. Он должен
сделать приоритет правила грамматики приоритетом следующего токена
имя или буквальное. Действия для правила в целом могут следовать % pre.

Если следует раздел программы, приложение должно обеспечить соблюдение правил грамматики.
прекращено %%.

Программы Раздел
Ассоциация программы раздел может включать определение лексического анализатора юлекс(), и любые
другие функции; например, те, которые используются в действиях, указанных в правилах грамматики. Это
не указано, предшествует ли раздел программ семантическим действиям в
выходной файл; поэтому, если приложение содержит определения макросов и
декларации, предназначенные для применения к коду в семантических действиях, он должен размещать их
в "% { ... %} " в разделе объявлений.

вход Grammar
Следующий ввод в Yacc дает синтаксический анализатор для ввода в Yacc. Этот формальный синтаксис
имеет приоритет над предыдущим текстовым описанием синтаксиса.

Лексическая структура определяется менее точно; лексический Структура of домен Grammar определяет
большинство условий. Соответствие между предыдущими условиями и токенами ниже:
следующим образом.

ИДЕНТИФИКАТОР Это соответствует концепции имя, данные ранее. Он также включает
литералы, как определено ранее.

C_IDENTIFIER
Это имя, кроме того, известно, что за ним следует . А
literal не может дать этот токен.

НОМЕР Строка цифр (неотрицательное десятичное целое число).

ТИП, ЛЕВЫЙ, МАРК, ЛКУРЛ, РКУРЛ
Они напрямую соответствуют %тип, %левый, %%, %{качества %}.

{ ... } Это указывает на исходный код на языке C с возможным включением '$'
макросы, как обсуждалось ранее.

/* Grammar для домен вход в якк. */
/* Базовый записей. */
/* Ассоциация после Он признанный by домен лексический анализатор. */

% token IDENTIFIER / * Включает идентификаторы и литералы * /
% token C_IDENTIFIER / * идентификатор (но не буквальный)
за которым следует:. * /
% НОМЕР токена / * [0-9] [0-9] * * /

/ * Зарезервированные слова:% type => TYPE% left => LEFT и так далее * /

% токен ЛЕВО ВПРАВО ТОКЕН NONASSOC ПРЕК ТИП НАЧАЛЬНЫЙ СОЮЗ

% token MARK / * Знак %%. * /
% token LCURL / * Метка% {. * /
% token RCURL / * Знак%}. * /

/ * 8-битные символьные литералы означают сами себя; * /
/ * должны быть определены токены для многобайтовых символов. * /

% start spec

%%

spec: defs MARK хвост правил
;
хвост: МАРК
{
/ * В этом действии настраиваем остальную часть файла. * /
}
| /* Пустой; вторая МАРКА не обязательна. * /
;
defs: / * Пусто. * /
| деф деф
;
def: НАЧАЛО ИДЕНТИФИКАТОРА
| СОЮЗ
{
/ * Копируем определение объединения в вывод. * /
}
| ЛКУРЛ
{
/ * Копируем код C в выходной файл. * /
}
РКУРЛ
| тэг rword nlist
;
rword: ТОКЕН
| ЛЕВЫЙ
| ПРАВИЛЬНО
| НОНАССОК
| ТИП
;
tag: / * Пусто: идентификатор тега объединения необязательный. * /
| '<' ИДЕНТИФИКАТОР '>'
;
nlist: nmno
| nlist нмно
;
nmno: IDENTIFIER / * Примечание: литерал недействителен с типом%. * /
| ИДЕНТИФИКАЦИОННЫЙ НОМЕР / * Примечание: недопустимо для типа%. * /
;

/ * Раздел правил * /

правила: C_IDENTIFIER rbody Prec
| правила правила
;
правило: C_IDENTIFIER rbody Prec
| '|' Rbody Prec
;
rbody: / ​​* пусто * /
| ИДЕНТИФИКАТОР rbody
| телесный акт
;
действовать : '{'
{
/ * Копировать действие, перевести $$ и так далее. * /
}
'}'
;
pre: / * Пусто * /
| ПРЕДВАРИТЕЛЬНЫЙ ИДЕНТИФИКАТОР
| PREC IDENTIFIER Акт
| Prec ';'
;

Конфликты
Синтаксический анализатор, созданный для входной грамматики, может содержать состояния, в которых возникают конфликты. В
конфликты возникают из-за того, что грамматика не ЛАЛР(1). Неоднозначная грамматика всегда содержит
хотя бы один ЛАЛР(1) конфликт. В Yacc утилита должна разрешить все конфликты, используя либо
правила по умолчанию или правила приоритета, заданные пользователем.

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

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

Заявленные приоритеты и ассоциативности (см. Объявления Раздел) привыкли
разрешите конфликты синтаксического анализа следующим образом:

1. Приоритет и ассоциативность связаны с каждым правилом грамматики; это
приоритет и ассоциативность последнего токена или литерала в теле правила. Если
домен % pre ключевое слово, оно отменяет это значение по умолчанию. Некоторые правила грамматики могут не
имеют как приоритет, так и ассоциативность.

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

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

4. Когда возникает конфликт сокращения / уменьшения, сокращение выполняется по правилу грамматики, которое
встречается раньше во входной последовательности. Конфликты, разрешенные таким образом, учитываются в
диагностический вывод, описанный в Ошибка Управляемость.

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

Ошибка Управляемость
Токен ошибка должны быть зарезервированы для обработки ошибок. Имя ошибка может быть использован в
грамматические правила. Он указывает места, где синтаксический анализатор может исправить синтаксическую ошибку. В
значение по умолчанию ошибка должно быть 256. Его значение можно изменить с помощью % токен декларация.
Лексический анализатор не должен возвращать значение ошибка.

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

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

Макро-функция YYRECOVERING должна вернуть 1, если была обнаружена синтаксическая ошибка и
парсер еще полностью не восстановился. В противном случае возвращается ноль.

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

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

Макрос Yyerrok в семантическом действии заставляет синтаксический анализатор действовать так, как если бы он полностью
восстановлен после любых предыдущих ошибок. Макрос yyclearin заставит синтаксический анализатор отбросить
текущий маркер просмотра вперед. Если текущий маркер просмотра вперед еще не был прочитан,
yyclearin не будет иметь никакого эффекта.

Макрос YYACCEPT должен заставить синтаксический анализатор возвращать нулевое значение. Макрос YYABORT
должен заставить синтаксический анализатор возвращать ненулевое значение.

Интерфейс в домен лексический Анализатор
Ассоциация юлекс() - это целочисленная функция, которая возвращает знак номер
представляющий вид прочитанного токена. Если с токеном связано значение
вернулся юлекс() (см. обсуждение день выше), он будет отнесен к
внешняя переменная Yylval.

Если парсер и юлекс() не согласны с этими номерами токенов, надежная связь
между ними не может быть. Для литералов (однобайтовых символов) токеном является просто
числовое значение символа в текущем наборе символов. Цифры для других токенов
может быть выбран Yacc, или выбранный пользователем. В любом случае #define строить
C используется, чтобы разрешить юлекс(), чтобы вернуть эти числа символически. В #define отчетность
помещаются в файл кода и файл заголовка, если этот файл запрашивается. Набор
символы разрешены Yacc в идентификаторе больше, чем разрешено C. Token
имена, содержащие такие символы, не включаются в #define деклараций.

Если номера токенов выбраны Yacc, токенам, отличным от литералов, должны быть присвоены
числа больше 256, хотя порядок не подразумевается. Токен может быть явно назначен
номер, после его первого появления в разделе объявлений с номером.
Имена и литералы, не определенные таким образом, сохраняют свое определение по умолчанию. Все номера токенов
назначенный Yacc должен быть уникальным и отличаться от номеров токенов, используемых для литералов и
токены, назначенные пользователем. Если повторяющиеся номера токенов вызывают конфликты при генерации парсера,
Yacc сообщает об ошибке; в противном случае не указано, является ли присвоение токена
принято или сообщается об ошибке.

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

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

Yacc Библиотека
Следующие функции появятся только в Yacc библиотека доступна через -л y
операнд к c99; поэтому они могут быть переопределены соответствующим приложением:

Int main(аннулировать)
Эта функция должна вызывать yyparse() и выйдите с неопределенным значением. Другие действия
внутри этой функции не указаны.

Int йеррор(Const колесница *s)
Эта функция должна записывать аргумент с завершающим нулем в стандартную ошибку, за которым следует
а .

Порядок проведения -л y и -л l операнды, данные c99 имеет значение; приложение должно
либо предоставить свой main() или убедитесь, что -л y предшествует -л l.

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

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

После появления -т указан, файл кода должен быть построен так, чтобы, если YYDEBUG еще не
определены во время компиляции (с использованием c99 −D YYDEBUG, например), YYDEBUG должен
должно быть явно установлено на 1. Когда -т не указано, файл кода должен быть построен так, чтобы,
если YYDEBUG еще не определен, он должен быть явно установлен в ноль.

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

Алгоритмы
Парсер, построенный Yacc реализует ЛАЛР(1) алгоритм синтаксического анализа, как описано в
литература. Не указано, является ли анализатор управляемым таблицей или прямым кодированием.

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

Эти концепции определены в литературе по теории синтаксического анализа.

ограничения
Ассоциация Yacc Утилита может иметь несколько внутренних таблиц. Минимальные максимумы для этих таблиц
показаны в следующей таблице. Точное значение этих значений - реализация -
определенный. Реализация должна определять отношения между этими значениями и между
их и любые сообщения об ошибках, которые реализация может сгенерировать, если у нее закончится
пространство для любой внутренней конструкции. Реализация может объединять группы этих ресурсов.
в единый пул до тех пор, пока общая сумма, доступная пользователю, не упадет ниже суммы
размеров, указанных в этом разделе.

Рабочий стол: внутренний ограничения in Yacc

┌───────────┬──────────┬──────────────────────────── ─────
│ │ минимальный │ │
│ Ограничивать │ максимальная │ Описание │
├───────────┼──────────┼──────────────────────────── ─────
│ {NTERMS} │ 126 │ Количество токенов. │
│ {NNONTERM} │ 200 │ Количество нетерминалов. │
│ {NPROD} │ 300 │ Количество правил. │
│ {NSTATES} │ 600 │ Количество состояний. │
│ {MEMSIZE} │ 5200 │ Длина правил. Итого │
│ │ │ длина, в именах (токены и │
│ │ │ нетерминалов), из всех │
│ │ │ правила грамматики. │
│ │ │ левая часть считается за │
│ │ │ каждое правило, даже если это не так │
│ │ │ явно повторяется, как │
│ │ │ указанные в Grammar Правила in │
│ │ │ Yacc. │
│ {ACTSIZE} │ 4000 │ Количество действий. `` Действия '' │
│ │ │ здесь (и в описании │
│ │ │ файл) относятся к действиям парсера │
│ │ │ (сдвиг, уменьшение и т. Д.) Не │
│ │ │ к семантическим действиям, определенным в │
│ │ │ Grammar Правила in Yacc. │
└───────────┴──────────┴──────────────────────────── ─────

ВЫХОД статус

Должны быть возвращены следующие значения выхода:

0 Успешное завершение.

> 0 Произошла ошибка.

ПОСЛЕДСТВИЯ OF ОШИБКИ

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

Ассоциация после разделах Он информативный.

ЗАЯВЛЕНИЕ ИСПОЛЬЗОВАНИЕ

Исторические реализации сталкиваются с конфликтами имен на именах yacc.tmp, yacc.acts,
yacc.debug, y.tab.c, y.tab.hкачества у.выход если более одной копии Yacc работает в
один каталог за один раз. В -б была добавлена ​​опция для решения этой проблемы. В
связанная проблема разрешения нескольких Yacc парсеры, помещаемые в тот же файл,
решается путем добавления -p возможность переопределить ранее жестко запрограммированные yy префикс переменной.

Описание -p option указывает минимальный набор имен функций и переменных
которые вызывают конфликт, когда несколько синтаксических анализаторов связаны вместе. YYSTYPE не обязательно
измененный. Вместо этого программист может использовать -б предоставить заголовочные файлы для разных парсеров
разные имена, а затем файл с юлекс() для данного парсера может включать
заголовок для этого парсера. Такие имена как yyclearrr не нужно менять, потому что они
используются только в действиях; у них нет связи. Возможно, что
реализация имеет другие имена, либо внутренние для реализации таких вещей, как
yyclearrr, или предоставляя нестандартные функции, которые он хочет изменить с помощью -p.

Унарные операторы, которые являются тем же токеном, что и бинарный оператор, обычно нуждаются в своих
приоритет скорректирован. Этим занимается % pre рекомендательный символ, связанный с
конкретное грамматическое правило, определяющее этот унарный оператор. (Видеть Grammar Правила in Yacc.)
Приложения не обязаны использовать этот оператор для унарных операторов, но грамматики
которые не требуют этого, редки.

ПРИМЕРЫ

Доступ к Yacc библиотека получается с операндами библиотечного поиска для c99. Чтобы использовать
Yacc библиотека main():

c99 y.tab.c -л y

И закон библиотека и Yacc библиотека содержит main(). Чтобы получить доступ к Yacc main():

c99 y.tab.c lex.yy.c -л y -л l

Это гарантирует, что Yacc библиотека ищется в первую очередь, так что ее main() используется.

Исторический Yacc библиотеки содержат две простые функции, которые обычно кодируются
прикладным программистом. Эти функции похожи на следующий код:

#включают
Int основной (пусто)
{
внешний Int yyparse ();

setlocale (LC_ALL, "");

/ * Если следующий парсер создан lex,
приложение должно быть осторожным, чтобы убедиться, что LC_CTYPE
и LC_COLLATE установлены на локаль POSIX. * /
(пусто) yyparse ();
возврат (0);
}

#включает в себя

int yyerror (const char * msg)
{
(void) fprintf (stderr, "% s \ n", msg);
возврат (0);
}

ОБОСНОВАНИЕ

Ссылки в Реферировано Документы может быть полезно при построении парсера
генератор. Упомянутая статья ДеРемера и Пеннелло (вместе с работами,
ссылок) описывает метод создания синтаксических анализаторов, соответствующих этому объему
POSIX.1-2008. Работа в этой области продолжается, поэтому разработчикам следует проконсультироваться
актуальную литературу, прежде чем делать какие-либо новые реализации. Оригинальная статья Кнута - это
теоретическая основа для такого синтаксического анализатора, но генерируемые им таблицы непрактичны.
большой для разумной грамматики и не должен использоваться. Формулировка `` эквивалент '':
намеренно гарантировать, что лучшие таблицы, ЛАЛР(1) можно сгенерировать.

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

Скорость генератора синтаксического анализатора в некоторой степени зависит от класса грамматики.
ручки. Тем не менее, оригинальные алгоритмы статьи Кнута для построения LR-анализаторов были
по мнению автора, в то время она была непрактично медленной. Хотя полный LR больше
сложнее, чем ЛАЛР(1), по мере того, как скорость компьютера и алгоритмы улучшаются, разница (в терминах
приемлемого времени исполнения настенных часов) становится менее значительным.

Предупреждаем потенциальных авторов, что упомянутая статья Де Ремера и Пеннелло
ранее процитированный идентифицирует ошибку (чрезмерное упрощение вычисления ЛАЛР(1)
опережающие наборы) в некоторых ЛАЛР(1) операторы алгоритма, которые предшествовали ему
публикация. Им следует найти время, чтобы найти этот документ, а также актуальные актуальные
работа, особенно Ахо.

Ассоциация -б была добавлена ​​опция, обеспечивающая переносимый метод разрешения Yacc работать на
несколько отдельных парсеров в одном каталоге. Если каталог содержит более одного
Yacc грамматики, и обе грамматики создаются одновременно (например,
параллельно сделать программа), конфликт результатов. Хотя решение не является исторической практикой,
он исправляет известный недостаток в исторических реализациях. Соответствующие изменения были
сделано для всех разделов, которые ссылаются на имена файлов y.tab.c (теперь `` файл кода ''),
y.tab.h (теперь `` файл заголовка '') и у.выход (теперь `` файл описания '').

Грамматика для Yacc ввод основан на документации System V. Текстовое описание
показывает, что ';' требуется в конце правила. Грамматика и
реализация этого не требует. (Использование C_IDENTIFIER вызывает уменьшение в
в нужном месте.)

Кроме того, в этой реализации такие конструкции, как % токен может быть прекращено
, но это не разрешено грамматикой. Ключевые слова, такие как % токен может
также появляются в верхнем регистре, что опять же не обсуждается. В большинстве мест, где '%' используется,
могут быть заменены, и есть альтернативные варианты написания некоторых символов
(например, %ЛЕВЫЙ может быть "% <" или даже "\ <").

Исторически,день> может содержать любые символы, кроме '>', включая пробелы, в
реализация. Однако поскольку день должен ссылаться на стандартный член профсоюза ISO C, в
Практически согласованные реализации должны поддерживать только набор символов для ISO C
стандартные идентификаторы в этом контексте.

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

Решаем, когда использовать % pre иллюстрирует сложность определения поведения Yacc.
Возможны ситуации, в которых грамматика не является, строго говоря, ошибкой, но тем не менее
Yacc не может интерпретировать это однозначно. Разрешение двусмысленностей в грамматике может
во многих случаях можно решить, предоставив дополнительную информацию, например, используя %тип or
% union декларации. Часто это проще, и это обычно дает меньший анализатор, чтобы взять
эта альтернатива, когда это уместно.

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

Статистические сообщения из нескольких исторических реализаций включают следующие типы
информация:

n/ 512 терминалов, n/ 300 нетерминалов
n/ 600 грамматических правил, n/ 1500 штатов
n сдвиг / уменьшение, n уменьшить / уменьшить количество сообщений о конфликтах
nИспользовано 350 рабочих комплектов
Память: состояния и т. Д. n/ 15000, парсер n/ 15000
n/ 600 различных опережающих наборов
n дополнительные закрытия
n сменные записи, n Исключения
n перейти к записям
n записи сохранены с помощью goto по умолчанию
Используемое пространство оптимизатора: ввод n/ 15000, выход n/ 15000
n записи в таблице, n нуль
Максимальный спред: n, Максимальное смещение: n

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

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

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

Некоторые реализации распознают знак равно как эквивалент '{' потому что он появляется в исторических
документация. Эта конструкция была признана и задокументирована устаревшей еще в
1978 г., в указанном Якк: Все же Другой Компилятор-компилятор. Этот том POSIX.1-2008
решил оставить его как устаревший и опустить.

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

БУДУЩЕЕ НАПРАВЛЕНИЯ

Нет.

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