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

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

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

Предшествование и ассоциативность связываются с лексемами в разделе определений. Это выполняется с помощью ключевых слов %left, %right и %noassoc, за которыми идет список лексем. Все лексемы на одной строке обладают одним уровнем предшествования и ассоциативности. Строки перечисляются в порядке возрастания приоритета. Таким образом:

определяют предшествование и ассоциативность четырех арифметических операций. Плюс и минус имеют левую ассоциативность и меньший приоритет, чем звездочка и дробная черта. Ключевое слово %right описывает правую ассоциативность, ключевое слово %noassoc описывает операторы, аналогичные оператору .LT. ФОРТРАНА, которые нельзя использовать в выражении подряд (A.LT.B.LT.C). Приведем в качестве примера следующее описание:

Если на вход подается строка

она будет распознана следующим образом:

При использовании этого механизма приоритет выше у унарных операций. Иногда унарная и бинарная операции имеют одинаковый синтаксис, но разный приоритет. Примером может служить минус: унарный минус имеет такую же силу, как и умножение, тогда как приоритет бинарного минуса ниже приоритета умножения. Ключевое слово %prec меняет уровень приоритета, связанный с данным правилом. Оно ставится непосредственно после тела правила перед действием или завершающим символом `;', после него идет имя лексемы или литерала. Это приводит к тому, что приоритет правила становится равным приоритету указанной лексемы или литерала. Например, чтобы приоритеты унарного минуса и умножения совпадали, строки могут выглядеть следующим образом:

Лексемы, указанные в аргументах директив %left, %right и %noassoc не обязательно, хотя и не запрещено указывать в директиве %token. Предшествование и ассоциативность используются yacc для разрешения конфликтов с помощью правил однозначности. Формально, правила работают следующим образом:

1. Для соответствующих лексем и литералов записывается предшествование и ассоциативность.

2. С каждым грамматическим правилом связывается предшествование и ассоциативность: они совпадают с предшествованием и ассоциативностью последнего литерала или лексемы в теле правила. Конструкция %prec переопределяет правила по умолчанию. Для некотрых правил предшествование и ассоциативность могут отсутствовать.

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

4. При конфликте сдвиг-свертка и наличии предшествования и ассоциативности как у правила, так и у входного символа, конфликт разрешается в пользу действия (сдвига или свертки), чей приоритет выше. Если приоритеты одинаковы, применяется ассоциативность: левая ассоциативность подразумевает свертку, права сдвиг. Отсутствие ассоциативности считается ошибкой.

Конфликты, разрешенные по приоритетам, в число сообщаемых yacc конфликтов не попадают. Это означает, что ошибки при задании предшествования могут скрыть ошибки во входной спецификации. Лучше всего использовать задание предшествования так, как сказано в руководстве, пока вы не приобретете достаточного опыта. Для выяснения, что же на самом деле делает распознаватель, очень полезен файл y.output.

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

Набор граматических правил неоднозначен, если входная строка может интерпретироваться по-разному. Например, правило:

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

правило позволяет интерпретировать ввод как

так и как

Первый случай - левая ассоциативность, второй - правая. Yacc при попытке построения распознавателя такие случаи обнаруживает. Полезно рассмотреть действия, выполняемые распознавателем при обнаружении подобных конструкций. При чтении второго выражения строка expr-expr удовлетворяет правой части приведенного правила.Таким образом, можно выполнить свертку. После нее на входе остается expr (левая часть правила). Затем читается оставшаяся часть выражения -expr, после чего снова выполняется свертка. В результате получается левоассоциативная интерпретация.

И наоборот, при чтении expr-expr можно было бы отложить немедленное применение правила и читать дальше до обнаружения expr-expr-expr. тогда свертнуты будут два последних символа, что приведет к правой ассоциативности. Таким обазом, прочитав expr-expr, распознаватель может выполнить два равноправных действия, свертку и сдвиг, и не существует способа выбрать одно из них. Может случиться, что нужно будет выбирать между двумя правомочными свертками, это называется конфликтом свертка-свертка. Заметьте, что конфликтов сдвиг-сдвиг не существует. При обнаружении приведенных конфликтов yacc все равно строит распознаватель. Это выполняется на основе одного из возможных вариантов. Правило, описывающее какие действия предпринимать в данной ситуации, называется правилом однозначности. По умолчанию применяются два правила однозначности:

1. В конфликте сдвиг-свертка предрочтение отдается сдвигу.

2. В конфликте свертка-свертка предпочтение отдается первой встреченной свертке.

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

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

В общем случае, если возможно применить правила однозначности, всегда можно переписать грамматику так, чтобы конфликты не возникали. По этой причине, большинство генераторов рассматривали конфликт как неустранимую ошибку. По нашему мнению, перепись грамматики выглядит неестественно и приводит к медленным распознавателям. Таким образом, yacc всегда строит распознаватель, даже при наличии конфликтов. Как пример мощности правил однозначности, рассмотрим фрагмент программы с конструкцией if-then-else:

Здесь IF и ELSE лексемы, cond - нетерминал, описывающий условные выражения, stat - нетерминал, описывающий операторы. Первое правило назовем простым, второе составным. Эти правила приводят к неоднозначностям, так как входная строка вида

может структурироваться двумя путями:

либо

Второй вариант наиболее распространен. Каждый ELSE связывается с последним IF, непосредственно предшествующим ELSE. Рассмотрим ситуацию, когда на входе IF (C1) IF(C2) S1, и распознаватель ищет ELSE. Можно сразу выполнить свертку по правилу для простого оператора и получить IF (C1) stat, а затем прочесть оставшийся ввод ELSE S2 и выполнить свертку по правилу составного оператора. С другой стороны, ELSE может быть сдвинут, прочитан S2, а правая часть

будет свернута по правилам составного оператора. Это ведет ко второму варианту группирования, что наиболее желательно.

Конфликты сдвиг-свертка возникают только при чтении определенного входного символа, ELSE и уже распознанной конструкции, как например

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

Сообщения о конфликтах лучше всего разбирать по выходному файлу y.output. Возможный пример выдачи приведен ниже:

Первая строка описывает конфликт, определяя состояние и входной символ. Далее идет обычное описание состояния, в котором указано активное правило и действия. Вспомните, что символ подчеркивания отмечает уже прочитанные правила. Распознаватель может выполнить два возможных действия. Если входной символ ELSE, можно выполнить сдвиг в состояние 45. В состоянии 45 будет следующая строка:

Заметьте, что в этом состоянии ELSE всегда сдвигается. В состоянии 23 альтернативное действие, описываемое `.' выполняется в том случае, если входной символ явно в правилах не указан. В этом случае, если входной символ не есть ELSE распознаватель выполняет свертку по правилу 18.

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

Грамматические анализаторы, создаваемые с помощью yacc,

реализуют так называемый LALR(1)-разбор, являющийся модифи-

кацией одного из основных методов разбора "снизу вверх" -

LR(k)-разбора (буквы L(eft) и R(ight) в обоих сокращениях

означают соответственно чтение входных символов слева нап-

раво и использование правостороннего вывода. Индекс в скоб-

ках показывает число предварительно просматриваемых лекси-

ческих единиц).

В каждый момент грамматического разбора анализатор

находится в некотором состоянии, определяемом предысторией

разбора, и в зависимости от очередной лексемы предпринимает

то или иное действие для перехода к новому состоянию. Разли-

чают два типа действий: сдвиг, т.е. чтение следующей входной

лексемы, и свертку, т.е. применение одного из правил подс-

тановки для замещения нетерминалом последовательности симво-

лов, соответствующей правой части правила. Работа yacc по

генерации процедуры грамматического анализа заключается в

построении таблиц, которые для каждого из состояний опреде-

ляют тип действий анализатора и номер следующего состояния в

соответствии с каждой из входных лексем.

Любой метод разбора требует грамматик с определенными

свойствами. В этом смысле yacc предполагает контекстно-

свободные грамматики со свойствами LALR(1). LALR(1)-

грамматики, являясь подмножеством LR(1)-грамматик, допускают

при построении таблиц разбора сокращение общего числа состо-

яний за счет объединения идентичных состояний, различающихся

только набором символов-следователей (символов, которые

могут следовать после применения одного из правил вывода,

если разбор по этому правилу проходил через данное состоя-

ние). Другие грамматики являются неоднозначными для приня-

того в yacc метода разбора и вызовут конфликты (раздел 5).

Однако, если язык, описываемый данной грамматикой, в прин-

ципе допускает задание грамматики, однозначной для данного

метода разбора, то yacc позволяет без перестройки грамматики

построить грамматический анализатор, разрешающий конфликты

на основе механизма приоритетов.

23. Построить синтаксическую диаграмму (R-граф) ДКА для распознавания лексем, обозначаемых регулярным выражением:….

Синтаксическая диаграмма — это направленный граф с одним входным ребром и одним выходным ребром и помеченными вершинами. Синтаксическая диаграмма задаёт язык. Цепочка пометок при вершинах на любом пути от входного ребра к выходному — это цепочка языка, задаваемого синтаксической диаграммой. Поэтому можно считать, что синтаксическая диаграмма — это одна из форм порождающей грамматики автоматных языков. Синтаксические диаграммы и конечные автоматыимеют тесную связь: любой автоматный язык задаётся синтаксической диаграммой и обратно, по любой синтаксической диаграмме можно построить конечный автомат (в общем случае недетерминированный), распознающий тот же язык, который задаёт диаграмма.

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

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

Синтаксические диаграммы

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

1. Каждому правилу вида <A> a₁ | a₂ |...| a_k ставится в соответствие диаграмма, структура которой определяется правой частью правила.
2. Каждое появление терминального символа x в цепочке a_i изображается на диаграмме дугой, помеченной этим символом x, заключенным в кружок.

Рис. 1.

3. Каждому появлению нетерминального символа <A> в цепочке a_i ставится в соответствие на диаграмме дуга, помеченная символом, заключённым в квадрат.

Рис. 2.

4. Порождающее правило, имеющее вид:

<A> a₁a₂...a_n

изображается на диаграмме следующим образом:

Рис. 3.

5. Порождающее правило, имеющее вид:

<A> a₁ | a₂ | ... | a_n

изображается на диаграмме так:

Рис. 4.

6. Если порождающее правило задано в виде итерации:

<A> {a}*,

то ему соответствует диаграмма:

Рис. 5.

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

Правила 3-6 предусматривают, что в качестве цепочки a₁ на объединенной диаграмме могут быть использованы диаграммы построенные для этих цепочек. В качестве примера рассмотрим следующую грамматику с начальным символом <A>:

Г_1.14:

V_т = { x, +, (, ) }, V_A = {<A>, <B>, <C>},

R = {<A> x | (<B>),

<B> <A><C>,

<C> {+<A>}*}

Рис. 6.

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

Рис. 7.