Можно ли разделить понятие приоритета и ассоциации в YACC

Question

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

Ассоциативность (*) используется для указания типа применяемой ассоциации (слева, справа, без ассоциации....) Фактически

%left '+' '*'

проинструктировать, что плюс и умножение остаются ассоциативными. Все идет нормально. (не совсем, но это служит цели примера)

Приоритет (**) используется для предоставления приоритета одному оператору над другим.

%left '+'
%left '*'

умножение имеет более высокий приоритет, чем операция плюс. Таким образом, мы получили искомый разбор для E+E*E

E+(E*E) in case of (**)
(E+E)*E in case of only (*) --> this is clearly wrong - but it's fine for the example

Итак, вопрос в том, могу ли я четко отделить ассоциативность от приоритета, не используя концепцию ассоциативности? Даже неассоциированность подразумевает знание ассоциативности... так что... как, если возможно, я могу говорить о них отдельно?

Answer 1

Нет. В определении синтаксического анализатора ассоциативность - это лишь небольшая деталь в алгоритме приоритета.

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

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

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

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

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

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

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

Учитывая, что существует не более одного возможного действия сокращения и не более одного возможного действия сдвига (поскольку задан следующий входной символ, если таковой имеется), единственная проблема заключается в принятии решения о том, следует ли сдвигать или уменьшать. Алгоритм приоритета включает в себя функцию приоритета PREC (A → α, a) ⇒ { SHIFT, REDUCE }, аргументами которой являются производные A → α и терминальный символ a, которые отображаются на SHIFT или REDUCE.

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

В простых случаях, однако, можно реализовать PREC, используя числовые сравнения. Для этого мы определяем две функции, которые отображают произведения и терминалы соответственно на целые числа: f (A → α) и g (a). Мы используем их для вычисления PREC:

PREC (A → α, a) ≡
УМЕНЬШИТЬ, если f (A → α)> g (a)
SHIFT, если f (A → α) < g (a) [Примечание 2]

В любом случае, алгоритм приоритета для данной конфигурации стека:

1. Определите производство P (= A → α) возможных восстановительных действий, если таковые имеются.

2. Если возможно только смещение или только уменьшение, сделайте это. В противном случае, если возможны как уменьшение, так и сдвиг, вычислите PREC (P, input) и уменьшите, используя P, если результат равен REDUCE; в противном случае сдвиг ввода.

Теперь это может показаться запутанным, поскольку большинство описаний отношений предшествования описывают их так, как будто они сравнивают терминалы, а не продукт с терминалом. Это потому, что это нормально, чтобы "назвать" каждое производство, используя последний терминал в производстве. Обычно это однозначно из-за ограничения на правые стороны производства: поскольку две правые части должны различаться, вполне вероятно, что все правые стороны производства имеют разные терминальные символы. [Заметка 3]

Хотя этот сокращенный вариант позволяет нам, например, сказать, что " * имеет более высокий приоритет, чем + " вместо несколько более громоздкого "производство E → E * E имеет приоритет над терминалом + ", важно помнить, что последнее утверждение - то, что мы действительно имеем в виду.

Приоритет также относится к отдельным операторам. С большинством операторов мы предпочитаем группировать слева направо, так что E-E-E должен быть проанализирован, как если бы он был написан (E-E)-E, Тем не менее, некоторые операторы, такие как группа возведения в степень справа, означают, что E**E**E должен быть разобран как E**(E**E), Это легко определить с помощью функции PREC; для оператора левой группировки have мы будем иметь:

PREC (E → E ⊕ E, ⊕) ≡ УМЕНЬШЕНИЕ

в то время как оператор правой группировки ⊗ будет иметь

PREC (E → E ⊗ E, ⊗) ≡ SHIFT

Это ясно, когда мы используем фактические аргументы для PREC, но это сбивает с толку, когда мы используем сокращенную запись, из-за чего мы пытаемся сказать, что ⊕ имеет более высокий приоритет, чем ⊕, а ⊗ имеет более низкий приоритет, чем ⊗. Чтобы избежать двусмысленности и все же позволить нам уйти от сокращения, мы описываем ⊕ как "левоассоциативную" (%left) и ⊗ как "право-ассоциативный" (%right). Но реализация - это просто применение обычного алгоритма приоритета.

В качестве примера рассмотрим простой язык выражений:

E → E + E
E → E * E
E → E ** E
E → id

Здесь мы ожидаем, что * будет более тесно связываться, чем + с ** самым жестким связыванием; первые две группы слева, а группы возведения в степень справа. Для этого мы можем назначить функции f и g следующим образом:

Production   f(Production)     Terminal  g(Terminal)
E → E + E         2                +          1
E → E * E         4                *          3
E → E ** E        5                **         6
E → id            8                id         7

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

Скобки могут быть легко добавлены; Я оставлю это как упражнение.

---

Заметки

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

2. Вы увидите формулировки, использующие <и ≥ (или ≤ и>), но чтобы избежать путаницы, я предполагаю, что диапазоны f и g - это разные наборы целых чисел. Поскольку функции произвольны, это не ограничивает общности.

3. Это не всегда так. Например, языки, которые позволяют - быть унарным или бинарным оператором, будут иметь произведения с правыми сторонами - E а также E - E, Производные от Yacc парсеры используют %prec TERMINAL декларация для связи производства с терминалом, отличным от значения по умолчанию.

Answer 2

Это все очень запутано.

Ассоциативность... Используется для определения приоритета одного оператора над другим

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

%left '+' '*'

Это говорит о том, что + а также * оба являются левоассоциативными и имеют одинаковый приоритет, потому что они оба находятся на одной строке. И поэтому это неправильно.

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

Извините, но это просто бессмысленно.