Структура генератора синтаксических анализаторов YACC. Для чего используются позиционные переменные в действиях.

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

декларации

%%

правила

%%

Программы

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

имеет вид:

%%

правила

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

входного файла.

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

Назначение секции деклараций состоит в основном в задании информации о лексемах.

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

38.Постройте магазинный распознаватель для следующей грамматики:…..

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

МП-автомат задается упорядоченной семеркой

где — конечное множество состояний; — алфавит, называемый входным алфавитом; — алфавит, называемый магазинным алфавитом; — начальное состояние; — подмножество заключительных состояний; — начальный магазинный символ; — система команд, определенная как конечное множество команд, каждая из которых записывается в виде (8.8): , где знак " " (стрелка) — внешний символ (не принадлежащий ни одному из указанных алфавитов);

Далее как в вопросе 12.

39.Какие разновидности конфликтов свойственны неоднозначным грамматикам для принятого в YACC метода грамматического разбора. Какие способы разрешения конфликтов предусмотрены генератором YACC для неоднозначных грамматик.

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

expr : expr '-' expr

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

expr - expr - expr

то правило позволяет структурирвоать их либо как

( expr - expr ) - expr

или как

expr - ( expr - expr )

(Первое правило называется левым связыванием, второе - правым связыванием).

Yacc определяет такие двусмысленности, когда пытается построить парсер. Поучительно было бы представить проблему, встающую перед парсером, когда на входе

expr - expr - expr

Когда парсер прочел второе expr, входные данные, которые он прочел, это

expr - expr

соответствующие правой части вышеприведенного правила. Парсер может понизить входные данные, применяя это правило; после применения входные данные понижаются до expr (левой части правила). Парсер затем прочитывает оставшуюся часть данных:

- expr

и снова понижает. Эффектом этого является левоассоциациативная интерпретация.

С другой стороны, когда парсер увидел

expr - expr

он может отложить немедленно применение правила и продолжить читать входные данные, пока не увидит

expr - expr - expr

Теперь он может применить правило к трем самым правым символам, понижая их до expr и оставляя

expr - expr

Теперь правило понижается еще раз; эффектом является правоассоциативная интерпретация. Таким образом, прочтя

expr - expr

парсер может сделать две разрешенные вещи - сдвиг и понижение, и нет способа выбрать отдать одному из них предпочтение. Это называется конфликтом сдвига/ понижения. Также может случиться, что у парсера будет выбор между двумя разрешенными понижениями; это называется конфликт понижения/понижения. Заметьте, что конфликтов сдвиг/сдвиг не бывает.

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

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

В случае конфликта сдвиг/понижение по умолчанию делается сдвиг

.В случае конфликта понижение/понижение по умолчанию производится понижение по первому грамматическому правилу (во входном потоке).