yaccposix - онлайн у хмарі

ПРОГРАМА:

ІМ'Я

yacc — ще один компілятор компілятора (РОЗВИТОК)

СИНТАКСИС

yacc [−dltv] [−b файл_префікс] [−стр sym_prefix] граматика

ОПИС

Команда yacc утиліта читає опис безконтекстної граматики в граматика і написати C
вихідний код, що відповідає стандарту ISO C, у файл коду та, за бажанням, заголовок
інформацію в заголовний файл у поточному каталозі. Згенерований вихідний код повинен
не залежить від будь-якої невизначеної, невизначеної або визначеної реалізацією поведінки, за винятком у
у випадках, коли він скопійований безпосередньо з наданої граматики, або в тих випадках
задокументовано виконанням. Код C повинен визначати функцію та пов'язані з нею підпрограми
і макроси для автомата, який виконує алгоритм розбору, що відповідає вимогам в
Алгоритми.

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

Вихідний код C і заголовковий файл повинні бути створені у формі, придатній як вхідні дані для C
компілятор (див c99).

ВАРІАНТИ

Команда yacc утиліта повинна відповідати тому Base Definitions POSIX.1-2008, розділ
12.2, Утиліта синтаксис керівні вказівки, крім настанови 9.

Підтримуються такі варіанти:

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

−d Напишіть заголовний файл; за замовчуванням записується лише файл коду. The #визначити
оператори пов’язують коди маркерів, призначені yacc з оголошеним користувачем
назви лексем. Це дозволяє вихідні файли, крім y.tab.c щоб отримати доступ до токена
коди.

−л Створіть файл коду, який не містить жодного #лінія конструкції. Якщо цей варіант
немає, не вказано, чи містить файл коду чи файл заголовка
#лінія директиви. Це слід використовувати лише після граматики та пов’язаного
дії повністю налагоджені.

−стр sym_prefix
Скористайтесь sym_prefix замість yy як префікс для всіх зовнішніх імен, створених
yacc. Назви, на які впливає, повинні включати функції yyparse(), yylex(), і
yyпомилка(), і змінні yylval, yychar та yydebug. (В решті
У цьому розділі шість цитованих символів посилаються на їх імена за замовчуванням
лише для зручності позначення.) Місцеві назви також можуть вплинути на −стр
варіант; однак, −стр опція не впливає #визначити символи, створені за допомогою
yacc.

−t Змініть директиви умовної компіляції, щоб дозволити компіляцію налагодження
код у файлі коду. Оператори налагодження під час виконання завжди повинні міститися в
файл коду, але за замовчуванням директиви умовної компіляції запобігають їх
складання.

−v Напишіть файл, що містить опис аналізатора та звіт про конфлікти
породжені двозначністю в граматиці.

ОПЕРАНДИ

Необхідний наступний операнд:

граматика Шлях до файлу, що містить інструкції, іменований далі граматика, Для
який потрібно створити синтаксичний аналізатор. Формат граматики описано в
розділ РОЗШИРЕНИЙ ОПИС.

STDIN

Не використовується.

ВХІД ФАЙЛИ

Файл граматика має бути текстовим файлом, відформатованим, як зазначено в РОЗШИРЕНОМУ ОПИСІ
.

НАВКОЛИШНЄ СЕРЕДОВИЩЕ ЗМІННІ

Наступні змінні середовища мають впливати на виконання yacc:

МОВА Надайте значення за замовчуванням для змінних інтернаціоналізації, які не встановлені або
нуль. (Дивіться том Base Definitions POSIX.1-2008, розділ 8.2,
Internationalization Змінні за пріоритет інтернаціоналізації
змінні, що використовуються для визначення значень категорій мовного стандарту.)

LC_ALL Якщо встановлено не порожнє значення рядка, замініть значення всіх інших
змінні інтернаціоналізації.

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

LC_MESSAGES
Визначте місцевий стандарт, який слід використовувати для впливу на формат і вміст
діагностичні повідомлення, записані у стандартну помилку.

NLSPATH Визначте розташування каталогів повідомлень для обробки LC_MESSAGES.

Команда МОВА та LC_* змінні впливають на виконання yacc корисність, як зазначено. The основний()
функція, визначена в Якк бібліотека дзвонить:

setlocale(LC_ALL, "")

і, таким чином, програма, створена за допомогою yacc також має впливати на їх зміст
змінні під час виконання.

АСИНХРОННИЙ ПОДІЇ

За замовчуванням.

ВИСТАВКА

Не використовується.

STDERR

Якщо виявлено конфлікти зсуву/зменшення або зменшення/зменшення граматика, yacc напише а
звіт про ці конфлікти до стандартної помилки у невизначеному форматі.

Стандартна помилка також повинна використовуватися для діагностичних повідомлень.

ВИХІД ФАЙЛИ

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

код філе
Цей файл повинен містити вихідний код C для yyparse() функція. Він повинен містити
код для різних семантичних дій з макропідстановкою, що виконується над ними як
описано в розділі РОЗШИРЕНИЙ ОПИС. Він також повинен містити копію #визначити
інструкції в заголовному файлі. Якщо %союзу використовується декларація, декларація для
YYSTYPE також буде включено до цього файлу.

Header філе
Заголовний файл має містити #визначити висловлювання, які пов’язують числа лексем з
назви лексем. Це дозволяє вихідним файлам, відмінним від файлу коду, отримати доступ до кодів маркерів.
Якщо %союзу використовується декларація, декларація для YYSTYPE і an зовнішній YYTYPE yylval
декларація також повинна бути включена до цього файлу.

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

ПОВЕРНЕНІ ОПИС

Команда yacc команда приймає мову, яка використовується для визначення граматики цільової мови
для аналізу таблиць і коду, створеного за допомогою yacc. Мова, прийнята в yacc як
Граматика цільової мови описана нижче за допомогою yacc сама мова введення.

Вхідні дані граматика включає правила, що описують структуру введення цільової мови та
код, який потрібно викликати, коли ці правила розпізнаються, щоб забезпечити пов'язану семантику
дії. Код, який буде виконано, має виглядати як тексти, призначені для C-
код мови. Ці частини тексту не повинні містити триграфів на мові C. C-мова
Вважається, що включення утворюють правильну функцію при обробці yacc в його вихід
файли. Код, включений у такий спосіб, виконується під час розпізнавання
мова перекладу.

З огляду на граматику, yacc утиліта генерує файли, описані в розділі ВИХОДНІ ФАЙЛИ
розділ. Файл коду можна зібрати та зв’язати за допомогою c99. Якщо декларація і
Програмні розділи граматичного файлу не містять визначення основний(), yylex(), і
yyпомилка(), скомпільований висновок вимагає зв'язування з наданими ззовні версіями
функції. Версії за замовчуванням основний() і yyпомилка() поставляються в yacc бібліотека та
можна підключити за допомогою −л y операнд до c99, yacc бібліотечні інтерфейси не потрібні
підтримувати інтерфейси, відмінні від стандартних yy символ префікс. Додаток надає
функція лексичного аналізатора, yylex(); в лекс утиліта спеціально розроблена для
створити таку рутину.

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

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

Лексичні структура of Граматика
The , , і символ ігнорується, за винятком того, що
програма повинна гарантувати, що вони не з'являються в іменах або зарезервовано багато символів
символи. Коментарі додаються до "/* ... */", і може відображатися всюди, де є ім’я
дійсний.

Імена мають довільну довжину, складаються з літер, крапки ("."), підкреслення ('_'), А також
не початкові цифри. Великі та малі літери відрізняються. Відповідні додатки
не можна використовувати назви, які починаються на yy or YY так як yacc парсер використовує такі імена. Багато з
імена відображаються в остаточному виводі yacc, і, таким чином, їх слід вибирати, щоб вони відповідали
з будь-якими додатковими правилами, створеними компілятором C для використання. Зокрема вони з’являються
in #визначити заяви.

Літерал має складатися з одного символу, укладеного в одинарні лапки. Всі
escape-послідовності, підтримувані для символьних констант стандартом ISO C, мають бути
підтримується yacc.

Взаємозв'язок з лексичним аналізатором детально розглянуто нижче.

Програма повинна гарантувати, що символ NUL не використовується в граматичних правилах або
літералів.

Декларації розділ
Розділ декларацій використовується для визначення символів, які використовуються для визначення цільової мови
і їхні стосунки один з одним. Зокрема, велика частина додаткової інформації
Необхідний для вирішення неоднозначностей у безконтекстній граматиці для цільової мови
надані тут.

Зазвичай yacc призначає зв’язок між символічними іменами, які він породжує, та їх
основне числове значення. Розділ декларацій дає змогу контролювати
присвоєння цих значень.

Також можна зберегти семантичну інформацію, пов’язану з токенами на даний момент
стек аналізу на визначеній користувачем мові C союз, якщо членами профспілки є
пов’язані з різними назвами в граматиці. Розділ декларацій передбачає
це також.

Перша група деклараторів нижче всіх приймає список імен як аргументи. Цей список може
необов’язково передувати ім’я члена профспілки C (так називається a тег нижче) з’являється
в '<' та '>'. (Як виняток з типографічних умов решти цього
том POSIX.1‐2008, у цьому випадкутег> представляє не метазмінну, а
літерні символи кутових дужок, що оточують символ.) Використання тег вказує, що
токени, названі в цьому рядку, повинні мати той самий тип C, що й член об’єднання, на який посилається
тег. Про це більш детально йдеться нижче.

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

Проголошує наступне ім'я бути маркером:

%токен [<тег>] ім'я [номер] [ім'я [номер]]...

If тег при наявності, тип C для всіх маркерів у цьому рядку оголошується як тип
посилається на тег. Якщо ціле додатне число, номер, слід а ім'я, це значення має бути
присвоєно маркеру.

Проголошує наступне ім'я бути маркером і призначає йому пріоритет:

% залишилося [<тег>] ім'я [номер] [ім'я [номер]]...
%право [<тег>] ім'я [номер] [ім'я [номер]]...

У цьому розділі може відображатися один або кілька рядків, кожен з яких починається одним із цих символів.
Усі токени в одному рядку мають однаковий рівень пріоритету та асоціативність; лінії
розташовані в порядку збільшення пріоритету або сили зв’язування. % залишилося означає, що
оператори в цій лінії є лівими асоціативними, і %право аналогічно означає право
асоціативні оператори. Якщо тег присутній, він повинен оголошувати тип C для ім'яs, як описано
та цінності %токен.

Проголошує наступне ім'я бути маркером, і вказує, що його не можна використовувати
асоціативно:

%ненац [<тег>] ім'я [номер] [ім'я [номер]]...

Якщо синтаксичний аналізатор стикається з асоціативним використанням цього маркера, він повідомляє про помилку. Якщо тег is
тепер він повинен оголошувати тип C для ім'яs, як описано для %токен.

Далі оголошує, що член профспілки ім'яs є нетерміналами, тому це є обов'язковим
мати а тег поле на його початку:

% тип <тег> ім'я...

Оскільки він має справу лише з нетерміналами, присвоєння номера токена або використання літералу є
також заборонено. Якщо ця конструкція присутня, yacc провести перевірку типу; якщо це
Конструкція відсутня, стек синтаксичного аналізу повинен містити тільки Int тип

Кожна назва, використана в граматика не визначено а %токен, % залишилося, %правоабо %ненац
Передбачається, що декларація представляє нетермінальний символ. The yacc комунальне підприємство звітує
помилка для будь-якого нетермінального символу, який не з’являється з лівого боку принаймні одного
граматичне правило.

Як тільки вказано тип, пріоритет або номер токена імені, це не повинно бути
змінився. Якщо перша декларація маркера не присвоює номер маркера, yacc повинні
присвоїти номер маркера. Після виконання цього призначення номер токена не змінюється
за явним призначенням.

Наступні декларатори не дотримуються попереднього шаблону.

Далі оголошується нетермінал ім'я бути старт символ, що представляє
найбільша, найзагальніша структура, описана граматичними правилами:

%початок ім'я

За замовчуванням це ліва частина першого граматичного правила; це за замовчуванням може бути
замінено цією декларацією.

Наступне оголошує yacc стек значень, щоб бути об’єднанням різних типів значень
бажаний.

%союзу { тіло of союз (in C)}

Тіло об’єднання не повинно містити незбалансованих маркерів попередньої обробки фігурних дужок.

За замовчуванням значення, повернуті діями (див. нижче) і лексичним аналізатором, мають бути
типу Int, yacc утиліта відстежує типи і вставляє відповідні
імена членів об’єднання, щоб виконати сувору перевірку типів результуючого синтаксичного аналізатора.

Як варіант, враховуючи, що принаймні одинтег> використовується конструкція, об'єднання можна оголосити
у файлі заголовка (який повинен бути включений до розділу декларацій за допомогою a #включати
побудувати всередині %{ та %}), і а typedef використовується для визначення символу YYSTYPE для представлення
цей союз. Ефект від %союзу полягає в тому, щоб надати декларацію YYSTYPE безпосередньо з
yacc Вхід

Оголошення та визначення мови C можуть з'являтися в розділі декларацій, що додається
за такими оцінками:

%{ ... %}

Ці оператори повинні бути скопійовані у файл коду та мають глобальну область дії
що їх можна використовувати в правилах і розділах програми. Заяви не повинні містити
"%}" поза коментарем, рядковим літералом або багатосимвольною константою.

Програма повинна гарантувати, що розділ декларацій завершується маркером %%.

Граматика Правила in yacc
Розділ правил визначає безконтекстну граматику, яку буде приймати функція yacc
генерує та пов'язує з цими правилами дії мови C і додатковий пріоритет
інформації. Граматика описана нижче, а далі — формальне визначення.

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

A : BODY ;

Символ A представляє нетермінальне ім'я, і BODY представляє послідовність з нуля або
більше ім'яs, буквальнийs, і смисловий діюs, за якими потім може слідувати необов'язковий
пріоритет правитис. Лише імена та літери беруть участь у формуванні
граматика; семантичні дії та правила пріоритету використовуються іншими способами. The і
в є yacc розділові знаки. Якщо є кілька послідовних граматичних правил с
та ж ліва сторона, ('|') можна використовувати, щоб уникнути переписування
ліва сторона; в даному випадку з’являється лише після останнього правила. Тіло
частина може бути порожньою (або без імен і літералів), щоб вказати, що нетермінал
символ відповідає порожньому рядку.

Команда yacc Утиліта присвоює кожному правилу унікальний номер. Правила використання вертикальної смуги
позначення є різними правилами. Номер, призначений правилу, з’являється в описі
файлу.

Елементами, що входять до складу ТІЛО, є:

ім'я, буквальний
Вони формують правила граматики: ім'я є або a знак або нетермінальний;
буквальний означає себе (за винятком лапок).

смисловий дію
З кожним граматичним правилом користувач може пов’язувати дії, які потрібно виконувати щоразу
правило розпізнається в процесі введення. (Зверніть увагу, що слово ``дія'' може
також посилаються на дії синтаксичного аналізатора — зсув, зменшення тощо.)

Ці дії можуть повертати значення та отримувати значення, повернуті попереднім
дії. Ці значення зберігаються в об’єктах типу YYSTYPE (див %союзу).
значення результату дії має зберігатися в стеку синтаксичного аналізу лівою рукою
стороні правила, доступ до яких мають інші скорочення як частина їх правої сторони
сторона. За допомогоютег> інформація, наведена в розділі декларацій, в
код, згенерований за допомогою yacc можуть бути строго перевірені типом і містити довільні
інформації. Крім того, лексичний аналізатор може надати такі ж види
значення для маркерів, якщо потрібно.

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

У дії можна використовувати певні псевдозмінні. Це макроси для доступу
до структур даних, відомих внутрішньо yacc.

$$ Значення дії можна встановити, призначивши його $$. Якщо тип
перевірка ввімкнена, а тип значення, яке потрібно призначити, не може бути
діагностичне повідомлення може бути згенеровано.

$номер Це відноситься до значення, повернуто компонентом, зазначеним в
знак номер у правій частині правила, читання зліва направо;
номер може бути нульовим або від’ємним. Якщо номер дорівнює нулю або від’ємне, це
посилається на дані, пов’язані з ім’ям у стеку синтаксичного аналізатора
перед крайнім лівим символом поточного правила. (Тобто, "$0"
посилається на ім’я, що безпосередньо передує крайньому лівому імені в
поточне правило, яке можна знайти в стеку аналізатора і "$−1" відноситься до
символ до його ліворуч.) Якщо номер посилається на елемент після поточного
точку в правилі або за нижньою частиною стека, результат є
невизначений. Якщо ввімкнено перевірку типу та тип значення, яке має бути
Призначений не може бути визначений, може бути згенеровано діагностичне повідомлення.

$<тег>номер
Вони точно відповідають відповідним символам без символу тег
включення, але допускають сувору перевірку типу (і виключають небажані
перетворення типів). Ефект полягає в тому, що макрос розширюється для використання тег
щоб вибрати елемент із об’єднання YYSTYPE (за допомогою dataname.tag).
Це особливо корисно, якщо номер не є позитивним.

$<тег>$ Це накладає на посилання тип члена об'єднання, на який посилається
by тег. Ця конструкція застосовна, коли посилання на ліворуч
значення контексту зустрічається в граматиці і забезпечує yacc із засобом
для вибору типу.

Дії можуть відбуватися в будь-якому місці правила (а не тільки в кінці); доступ до дії
значення, що повертаються діями зліва, і, у свою чергу, значення, яке воно повертає, може бути
доступ за допомогою дій праворуч. Дія, що з’являється в середині правила
має бути еквівалентним заміні дії новим нетермінальним символом і
додавання пустого правила з цим нетермінальним символом з лівого боку. The
семантична дія, пов'язана з новим правилом, має бути еквівалентною оригіналу
дії. Використання дій у межах правил може призвести до конфліктів, які ні
інакше існують.

За замовчуванням значення правила має бути значенням першого елемента в ньому.
Якщо перший елемент не має типу (особливо у випадку a
literal) і перевірку типу ввімкнено % тип, з’явиться повідомлення про помилку.

пріоритет
Ключове слово %поперед можна використовувати для зміни рівня пріоритету, пов’язаного з a
конкретне граматичне правило. Прикладами цього є випадки, коли унарний і двійковий
Оператори мають однакове символічне представлення, але мають бути надані іншим
пріоритети або де обробка неоднозначної конструкції if-else
необхідно. Зарезервований символ %поперед може з'явитися відразу після тіла
граматичне правило і може супроводжуватися ім'ям лексеми або літералом. Це має
призведе до того, що пріоритет граматичного правила стане пріоритетом наступної лексеми
ім'я або дослівний. Може наступити дія для правила в цілому %поперед.

Якщо слідує розділ програми, програма має забезпечити відповідність граматичних правил
припинено %%.

програми розділ
Команда програми Розділ може включати визначення лексичного аналізатора yylex(), і будь-який
інші функції; наприклад, ті, що використовуються в діях, зазначених у граматичних правилах. Це
не вказано, чи передує розділ програм, чи слідує за семантичними діями в
вихідний файл; тому, якщо програма містить будь-які макровизначення та
оголошення, призначені для застосування до коду в семантичних діях, він повинен розмістити їх
в "%{ ... %}" в розділі декларації.

вхід Граматика
Наступний вхід до yacc дає синтаксичний аналізатор для введення до yacc. Це формальний синтаксис
має пріоритет перед попереднім описом синтаксису тексту.

Менш точно визначено лексичний склад; Лексичні структура of Граматика визначає
більшість термінів. Відповідність між попередніми термінами та наведеними нижче лексемами виглядає як
слід.

ІДЕНТИФІКАТОР Це відповідає концепції ім'я, наведений раніше. Він також включає
літералів, як визначено раніше.

C_IDENTIFIER
Це ім’я, і, крім того, відомо, що за ним слідує a . А
literal не може дати цей маркер.

НОМЕР Рядок цифр (невід’ємне десяткове число).

TYPE, ЛІВИЙ, MARK, LCURL, RCURL
Вони безпосередньо відповідають % тип, % залишилося, %%, %{ та %}.

{ ... } Це вказує на вихідний код на мові C з можливим включенням '$'
макроси, як обговорювалося раніше.

/* Граматика та цінності вхід до yacc. */
/* базовий записів */
/* Команда після він має визнаний by лексичні аналізатор. */

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

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

%токен ЛІВО ПРАВО NONASSOC TOKEN PREC TYPE START UNION

%token MARK /* Позначка %%. */
%token LCURL /* Позначка %{. */
%token RCURL /* Позначка %}. */

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

%початкова спец

%%

spec : defs MARK правила хвоста
;
хвіст: МАРК
{
/* У цій дії налаштуйте решту файлу. */
}
| /* Порожній; другий MARK є необов'язковим. */
;
defs: /* Порожній. */
| defs def
;
def : ІДЕНТИФІКАТОР ПОЧАТКУ
| СОЮЗ
{
/* Копіювати визначення об'єднання на вихід. */
}
| LCURL
{
/* Скопіюйте код C у вихідний файл. */
}
RCURL
| тег rword nlist
;
rword : ТОКЕН
| ВЛІВО
| ПРАВО
| NONASSOC
| ТИП
;
тег : /* Порожній: ідентифікатор тегу об'єднання необов'язковий. */
| '<' ІДЕНТИФІКАТОР '>'
;
nlist : nmno
| nlist nmno
;
nmno : IDENTIFIER /* Примітка: літерал недійсний із типом %. */
| ІДЕНТИФІКАЦІЙНИЙ НОМЕР /* Примітка: недійсний з типом %. */
;

/* Розділ правил */

правила : C_IDENTIFIER rbody prec
| правила правила
;
правило : C_IDENTIFIER rbody prec
| '|' rbody prec
;
rbody: /* порожній */
| ІДЕНТИФІКАТОР тіла
| rbody act
;
act : '{'
{
/* Дія копіювання, переклад $$ тощо. */
}
'}'
;
prec : /* Порожній */
| ІДЕНТИФІКАТОР PREC
| PREC ІДЕНТИФІКАТОР акт
| prec ';'
;

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

Конфлікти – це або зміщення/зменшення конфліктів, або зменшення/зменшення конфліктів. Зміна/зменшення
Конфлікт – це коли для заданого стану та символу упередження виконуються як дія зсуву, так і а
можливе зменшення дії. Зменшення/зменшення конфлікту – це де, для даного стану і
символ перегляду вперед, можливі скорочення за двома різними правилами.

У наведених нижче правилах описано, як вказати, які дії потрібно вжити, коли виникає конфлікт. ні
усі конфлікти зміни/зменшення можуть бути успішно вирішені таким чином, тому що конфлікт може
може бути викликано чимось іншим, ніж двозначністю, тому необережне використання цих засобів може спричинити
мова, яка прийнята синтаксичним аналізатором, значно відрізняється від тієї, яка була призначена. The
файл опису повинен містити достатню інформацію, щоб зрозуміти причину
конфлікту. Там, де неоднозначність є причиною того, що повинні бути стандартні або явні правила
достатній для створення робочого аналізатора.

Оголошені пріоритети та асоціативності (див Декларації розділ) звикли
вирішувати конфлікти розбору таким чином:

1. З кожним граматичним правилом пов'язаний пріоритет і асоціативність; це
пріоритет і асоціативність останньої лексеми або літералу в тілі правила. Якщо
%поперед використовується ключове слово, воно замінює це значення за замовчуванням. Деякі граматичні правила можуть ні
мають як пріоритет, так і асоціативність.

2. Якщо є конфлікт зсуву/зменшення, і граматичне правило, і символ введення
мають пріоритет і пов'язану з ними асоціативність, тоді конфлікт вирішується
на користь дії (зміщення або зменшення), пов'язаної з вищим пріоритетом. Якщо
пріоритети однакові, тоді використовується асоціативність; лівий асоціативний має на увазі
зменшити, правий асоціативний передбачає зсув, а неасоціативний передбачає помилку в
рядок розбирається.

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

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

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

помилка Обробка
Токен помилка має бути зарезервовано для обробки помилок. Ім'я помилка може використовуватися в
граматичні правила. Він вказує місця, де синтаксичний аналізатор може відновитися після синтаксичної помилки. The
значення за замовчуванням помилка має бути 256. Його значення можна змінити за допомогою a %токен декларація
Лексичний аналізатор не повинен повертати значення помилка.

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

Коли аналізатор виявляє синтаксичну помилку, він зазвичай викликає yyпомилка() із символом
рядок "синтаксис помилка" як його аргумент. Виклик не виконується, якщо синтаксичний аналізатор нерухомий
відновлення після попередньої помилки при виявленні помилки. Вважається, що синтаксичний аналізатор
відновлюватися після попередньої помилки, доки синтаксичний аналізатор не зміниться принаймні на три
звичайні вхідні символи з моменту виявлення останньої помилки або виконання семантичної дії
макрос yyerrok. Парсер не повинен викликати yyпомилка() коли виконується YYERROR.

Функція макросу YYRECOVERING повертає 1, якщо було виявлено синтаксичну помилку та
парсер ще не повністю відновився від нього. В іншому випадку повертається нуль.

Коли синтаксис виявляється синтаксичним аналізатором, він повинен перевірити, чи є попередній синтаксис
виявлено помилку. Якщо була виявлена ​​попередня помилка, і якщо нормальних символів введення немає
були зміщені з моменту виявлення попередньої помилки, аналізатор перевіряє, чи є
Символ погляду вперед є кінцевим маркером (див інтерфейс до Лексичні Аналізатор). Якщо це так, то
синтаксичний аналізатор повертає значення, відмінне від нуля. В іншому випадку має бути символ перегляду вперед
відкинуто, і звичайний аналіз відновиться.

Коли виконується YYERROR або коли синтаксичний аналізатор виявляє синтаксичну помилку і не має попередньої помилки
було виявлено, або принаймні один звичайний вхідний символ був зміщений з попереднього
була виявлена ​​помилка, синтаксичний аналізатор повертатиме один стан за раз, доки не буде виведено стек аналізу
порожній або поточний стан дозволяє перейти помилка. Якщо синтаксичний аналізатор спорожняє синтаксичний аналіз
стека, він повертається з ненульовим значенням. Інакше він переміститься помилка та
потім відновіть звичайний розбір. Якщо синтаксичний аналізатор читає символ упередження до того, як була помилка
Виявлено, цей символ все ще буде символом попередження, коли розбір відновлено.

Макрос yyerrok у семантичній дії змусить синтаксичний аналізатор діяти так, ніби він повністю
відновлено після будь-яких попередніх помилок. Макрос yyclearin змушує синтаксичний аналізатор відкинути
поточний маркер прогнозу. Якщо поточний маркер перегляду ще не прочитано,
yyclearin не матиме ніякого ефекту.

Макрос YYACCEPT змушує синтаксичний аналізатор повертатися з нульовим значенням. Макрос YYABORT
змушує синтаксичний аналізатор повертати ненульове значення.

інтерфейс до Лексичні Аналізатор
Команда yylex() функція — це цілочисельна функція, яка повертає a знак номер
що представляє тип прочитаного токена. Якщо з маркером пов’язане значення
повернуто до yylex() (див. обговорення тег вище), він має бути призначений для
зовнішня змінна yylval.

Якщо парсер і yylex() не погоджуються щодо цих номерів маркерів, надійний зв'язок
між ними не може відбутися. Для (однобайтових) літералів маркером є просто
числове значення символу в поточному наборі символів. Числа для інших жетонів
може бути обраний yacc, або обраний користувачем. У будь-якому випадку, #визначити будувати
C використовується для дозволу yylex(), щоб повернути ці числа символічно. The #визначити заяви
поміщаються у файл коду та файл заголовка, якщо цей файл запитується. Набір з
символів, дозволених yacc в ідентифікаторі більше, ніж дозволено C. Token
імена, які містять такі символи, не включаються в #визначити декларації.

Якщо номери маркерів вибираються за допомогою yacc, призначаються токени, відмінні від літералів
чисел більше 256, хоча порядок не має на увазі. Токен може бути призначений явно
число, після його першої появи в розділі декларацій з числом.
Імена та літерали, не визначені таким чином, зберігають своє визначення за замовчуванням. Усі номери маркерів
призначено yacc має бути унікальним і відмінним від номерів лексем, що використовуються для літералів і
призначені користувачем маркери. Якщо повторювані номери маркерів викликають конфлікти під час генерації аналізатора,
yacc повідомити про помилку; інакше не вказано, чи є призначення маркера
прийнято або повідомляється про помилку.

Кінець введення позначається спеціальним маркером, який називається кінцевий маркер, який має токен
число, яке дорівнює нулю або від’ємне. (Ці значення недійсні для будь-якого іншого маркера.) Усі
Лексичні аналізатори повертають нуль або від’ємне число як маркер після досягнення кінця
їх внесок. Якщо лексеми до, але виключаючи, кінцевий маркер утворюють структуру that
відповідає початковому символу, синтаксичний аналізатор повинен прийняти введення. Якщо кінцевий маркер видно в
будь-якому іншому контексті, це буде вважатися помилкою.

Завершення програма
На додаток до yyparse() і yylex(), функції yyпомилка() і основний() зобов'язані
скласти повну програму. Додаток може надати основний() і yyпомилка(), або ті
рутини можна отримати з yacc бібліотека

Якк бібліотека
Наступні функції відображатимуться лише в yacc бібліотека доступна через −л y
операнд до c99; тому вони можуть бути перевизначені за допомогою відповідної програми:

Int основний(анулювати)
Ця функція має викликати yyparse() і вихід із невизначеним значенням. Інші дії
у цій функції не визначені.

Int yyпомилка(сопзЬ бак *s)
Ця функція записує аргумент, що закінчується NUL, у стандартну помилку, а потім
а .

Порядок −л y та −л l операнди, дані до c99 є значущим; заявка повинна
або надати своє основний() функціонувати або забезпечити це −л y передує −л l.

Налагодження Парсер
Парсер, створений за допомогою yacc має мати діагностичні засоби, які можуть бути опціональними
увімкнено під час компіляції або під час виконання (якщо ввімкнено під час компіляції). The
компіляція коду налагодження під час виконання знаходиться під контролем YYDEBUG, препроцесора
символ. Якщо YYDEBUG має відмінне від нуля значення, необхідно включити код налагодження. Якщо його
значення дорівнює нулю, код не включається.

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

Коли −t вказано, файл коду має бути побудований таким чином, щоб, якщо YYDEBUG ще не встановлено
визначено під час компіляції (за допомогою c99 −D параметр YYDEBUG, наприклад), YYDEBUG повинен
бути встановленим явно в 1. Коли −t не вказано, кодовий файл повинен бути побудований таким чином, щоб,
якщо YYDEBUG ще не визначено, він має бути встановлений явно в нуль.

Формат виводу налагодження не визначено, але містить принаймні достатньо інформації
для визначення дії зсуву і зменшення, а також вхідних символів. Це також забезпечує
інформація про відновлення помилок.

Алгоритми
Синтаксичний аналізатор, створений за допомогою yacc реалізує ан ЛАЛР(1) алгоритм розбору, як задокументовано в
літературу. Не вказано, чи керований синтаксичний аналізатор таблиця чи пряме кодування.

Синтаксичний аналізатор, створений за допомогою yacc ніколи не запитуватиме символ введення yylex() під час а
стан, де єдиними діями, крім дії помилки, є скорочення за одним правилом.

Література теорії розбору дає визначення цим поняттям.

рамки
Команда yacc утиліта може мати кілька внутрішніх таблиць. Мінімальні максимуми для цих таблиць
наведені в наступній таблиці. Точне значення цих значень полягає в реалізації-
визначений. Реалізація повинна визначати зв'язок між цими значеннями та між ними
їх і будь-які повідомлення про помилки, які може генерувати реалізація, якщо вона закінчиться
простір для будь-якої внутрішньої конструкції. Реалізація може поєднувати групи цих ресурсів
в один пул до тих пір, поки загальна сума, доступна користувачеві, не падає нижче суми
розмірів, визначених цим розділом.

Таблиця: Внутрішній рамки in yacc

┌───────────┬─────────┬────────────────────────── ─────┐
│ │ мінімальний │ │
│ Limit │ Максимальний │ Опис │
├────────────┼─────────┼────────────────────────── ──────┤
│{NTERMS} │ 126 │ Кількість жетонів. │
│{NNONTERM} │ 200 │ Кількість нетерміналів. │
│{NPROD} │ 300 │ Кількість правил. │
│{NSTATES} │ 600 │ Кількість станів. │
│{MEMSIZE} │ 5200 │ Довжина правил. Загальна │
│ │ │ довжина в назвах (лексеми та │
│ │ │ нетермінали), з усіх │
│ │ │ правила граматики. │
│ │ │ ліва частина враховується за │
│ │ │ кожне правило, навіть якщо воно не │
│ │ │ явно повторюється, як │
│ │ │ зазначено в Граматика Правила in │
│ │ │ yacc. │
│{ACTSIZE} │ 4000 │ Кількість дій. ``Дії'' │
│ │ │ тут (і в описі │
│ │ │ файл) відносяться до дій аналізатора │
│ │ │ (зміщення, зменшення тощо) не │
│ │ │ до семантичних дій, визначених у │
│ │ │ Граматика Правила in yacc. │
└────────────┴─────────┴────────────────────────── ─────┘

EXIT СТАТУС

Повинні бути повернуті такі вихідні значення:

0 Успішне завершення.

>0 Сталася помилка.

НАСЛІДКИ OF ПОМИЛКИ

Якщо виявлено якісь помилки, запуск припиняється і yacc виходи з ненульовим статусом.
Можуть створюватися файли часткового коду та файли заголовків. Узагальнена інформація в
файл опису завжди створюється, якщо −v прапор присутній.

Команда після розділам він має інформативний.

ЗАСТОСУВАННЯ ВИКОРИСТАННЯ

Історичні реалізації відчувають конфлікти імен щодо імен yacc.tmp, yacc.acts,
yacc.debug, y.tab.c, y.tab.h та y.вихід якщо більше одного примірника yacc працює в а
єдиний каталог за один раз. The −b була додана опція для подолання цієї проблеми. The
пов’язана проблема дозволу кількох yacc синтаксичних аналізаторів для розміщення в одному файлі
адресовано додаванням a −стр можливість замінити жорстко запрограмований раніше yy змінний префікс.

Опис −стр Параметр визначає мінімальний набір імен функцій і змінних
які викликають конфлікт, коли кілька синтаксичних аналізаторів пов’язані разом. YYSTYPE не обов'язково
змінився. Замість цього програміст може використовувати −b щоб надати заголовні файли для різних синтаксичних аналізаторів
різні імена, а потім файл з yylex() для даного аналізатора може включати
заголовок для цього аналізатора. Назви, такі як yyclearerr не потрібно змінювати, тому що вони
використовуються тільки в діях; вони не мають зв'язку. Цілком можливо, що an
Реалізація має інші назви, або внутрішні для реалізації таких речей, як
yyclearerr, або надання нестандартних функцій, які він хоче змінити −стр.

Унарні оператори, які є тим же маркером, що і двійковий оператор, взагалі потребують їх
пріоритет скоригований. Цим займається %поперед рекомендаційний символ, пов'язаний з
конкретне граматичне правило, що визначає цей унарний оператор. (Побачити Граматика Правила in yacc.)
Програми не зобов’язані використовувати цей оператор для унарних операторів, а для граматик
які не вимагають цього рідко.

ПРИКЛАДИ

Доступ до yacc бібліотека отримується з операндами пошуку бібліотеки до c99. Використовувати
yacc бібліотека основний():

c99 y.tab.c −л y

Обидва лекс бібліотека та yacc бібліотека містить основний(). Щоб отримати доступ до yacc основний():

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

Це гарантує, що yacc спочатку шукається бібліотека, щоб її основний() використовується.

Історичний 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 р.). The
швидкість LR(1) аналізатор для будь-якого класу більше залежить від представлення таблиці та
стиснення (або генерування коду, якщо генерується прямий синтаксичний аналізатор), ніж у класі
граматики, яку обробляє генератор таблиць.

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

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

Команда −b була додана опція для забезпечення портативного методу дозволу yacc працювати
кілька окремих синтаксичних аналізаторів в одному каталозі. Якщо каталог містить більше одного
yacc граматику, і обидві граматики будуються одночасно (наприклад, а
паралельно зробити програма), результати конфлікту. Хоча рішення не є історичною практикою,
він виправляє відомий недолік в історичних реалізаціях. Відповідні зміни були
зроблено для всіх розділів, які посилаються на імена файлів y.tab.c (тепер ``файл коду''),
y.tab.h (тепер ``заголовний файл''), і y.вихід (тепер ``файл опису'').

Граматика для yacc введення базується на документації System V. Текстовий опис
показує там, що ';' в кінці правила. Граматика та
реалізація цього не вимагає. (Використання C_IDENTIFIER викликає зменшення в
правильне місце.)

Крім того, у цій реалізації такі конструкції, як %токен може бути припинено а
, але це не дозволяється граматикою. Ключові слова, такі як %токен може
також відображаються у верхньому регістрі, що знову ж таки не обговорюється. У більшості місць де '%' використовується,
можна замінити, і для деяких символів є альтернативні варіанти написання
(наприклад, %ЛІВО може бути "%<" або навіть "\<").

Історично склалося так,тег> може містити будь-які символи, крім '>', включаючи пробіл, у
виконання. Однак, оскільки тег має посилатися на члена профспілки стандарту ISO C, в
Реалізаціям, що відповідають практиці, необхідно підтримувати лише набір символів для ISO C
стандартні ідентифікатори в цьому контексті.

Відомо, що деякі історичні реалізації приймають дії, які припиняються за допомогою a
період. Історичні реалізації часто дозволяють '$' в іменах. Відповідна реалізація
не потребує підтримки жодної з цих форм поведінки.

Вирішити, коли використовувати %поперед ілюструє складність у визначенні поведінки yacc.
Можуть бути ситуації, в яких граматика не є, строго кажучи, помилкою, і все ж
yacc не може це трактувати однозначно. Розв’язання неясностей у граматиці може
у багатьох випадках можна вирішити шляхом надання додаткової інформації, наприклад використання % тип or
%союзу декларації. Часто це простіше і зазвичай дає менший аналізатор
цю альтернативу, коли це доречно.

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

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

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

Звіт внутрішніх таблиць у файлі опису залишається визначеним для реалізації
оскільки всі аспекти цих обмежень також визначаються реалізацією. Деякі реалізації
може використовувати методи динамічного розподілу та не мати конкретних граничних значень для звітування.

Формат y.вихід файл не надається, тому що специфікації формату не було
вбачається для підвищення портативності програм. Перелік в першу чергу призначений для допомоги людям
користувачі розуміють і налагоджують синтаксичний аналізатор; Використання y.вихід відповідним сценарієм програми
було б незвично. Більше того, реалізації не дали послідовних результатів і ні
популярний формат був очевидним. Формат, обраний реалізацією, має бути людським
читається, на додаток до вимоги, щоб це був текстовий файл.

Стандартні звіти про помилки конкретно не описані, оскільки вони рідко використовуються
відповідних додатків і не було підстав обмежувати впровадження.

Деякі реалізації розпізнають "={" як еквівалент '{' тому що воно з'являється в історичних
документація. Ця конструкція була визнана та документально застаріла ще дуже давно
1978 р., у цит Yacc: Все-таки Інший Компілятор-Компілятор. Цей том POSIX.1‐2008
вирішив залишити його як застарілий і опустити.

Багатобайтові символи повинні розпізнаватися лексичним аналізатором і повертатися як маркери.
Їх не слід повертати як багатобайтові символьні літерали. Токен помилка що використовується
для відновлення помилок зазвичай призначається значення 256 в історичній реалізації.
Таким чином, значення маркера 256, яке використовується в багатьох багатобайтових наборах символів, не є таким
доступний для використання як значення визначеного користувачем маркера.

Майбутнє НАПРЯМКИ

Ні.

Використовуйте yaccposix онлайн за допомогою служб onworks.net