Грамматика приоритета операторов

Грамматика приоритета операторов — это разновидность грамматики формальных языков .

Технически грамматика приоритета операторов — это контекстно-свободная грамматика , обладающая свойством (среди прочего) ^[1] что ни одна продукция не имеет ни пустой правой части, ни двух соседних нетерминалов в своей правая сторона. Эти свойства позволяют отношения устанавливать старшинства. определяется между терминалами грамматики. Анализатор , использующий эти отношения, значительно проще, чем анализаторы более общего назначения, такие как анализаторы LALR . Анализаторы приоритета операторов могут быть созданы для большого класса контекстно-свободных грамматик.

Отношения старшинства

Грамматики приоритета операторов основаны на следующих трех отношениях приоритета между терминалами: ^[2]

Связь	Значение
$a\lessdot b$	$a$ уступает приоритет $b$
$a\doteq b$	$a$ имеет тот же приоритет, что и $b$
$a\gtrdot b$	$a$ имеет приоритет над $b$

Эти отношения приоритета операторов позволяют разграничивать дескрипторы в правильных формах предложений : $\lessdot$ отмечает левый конец, $\doteq$ появляется внутри ручки, и $\gtrdot$ отмечает правый конец. В отличие от других анализаторов сдвига-сокращения, все нетерминалы считаются равными с целью идентификации дескрипторов. ^[3] Отношения не обладают теми же свойствами, что и их аналоги без точек; е. г. $a\doteq b$ вообще не подразумевает $b\doteq a$ , и $b\gtrdot a$ не следует от $a\lessdot b$ . Более того, $a\doteq a$ вообще не соблюдается, и $a\gtrdot a$ возможно.

Предположим, что между терминалами $a i$ и $a i +1$ всегда существует ровно одно отношение предшествования. Предположим, что $ — это конец строки. Тогда для всех терминалов $b$ определяем: $\$\lessdot b$ и $b\gtrdot \$$ . Если мы удалим все нетерминалы и разместим правильное отношение приоритета: $\lessdot$ , $\doteq$ , $\gtrdot$ между остальными терминалами остаются строки, которые можно проанализировать легко разрабатываемым восходящим парсером .

Пример

Например, можно использовать следующие отношения приоритета операторов. быть введено для простых выражений: ^[4]

{\begin{array}{c|cccc}&\mathrm {id} &+&*&\$\\\hline \mathrm {id} &&\gtrdot &\gtrdot &\gtrdot \\+&\lessdot &\gtrdot &\lessdot &\gtrdot \\*&\lessdot &\gtrdot &\gtrdot &\gtrdot \\\$&\lessdot &\lessdot &\lessdot &\end{array}}

Они следуют из следующих фактов: ^[5]

+ имеет более низкий приоритет, чем * (следовательно, $+\lessdot *$ и $*\gtrdot +$ ).
И +, и * левоассоциативны (следовательно, $+\gtrdot +$ и $*\gtrdot *$ ).

Входная строка ^[4]

\mathrm {id} _{1}+\mathrm {id} _{2}*\mathrm {id} _{3}

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

\$\lessdot \mathrm {id} _{1}\gtrdot +\lessdot \mathrm {id} _{2}\gtrdot *\lessdot \mathrm {id} _{3}\gtrdot \$

Анализ приоритета операторов

Наличие отношений приоритета позволяет идентифицировать дескрипторы следующим образом: ^[4]

сканируйте строку слева, пока не увидите $\gtrdot$
сканирование назад (справа налево) по любому $\doteq$ пока не увижу $\lessdot$
все между двумя отношениями $\lessdot$ и $\gtrdot$ , включая любые промежуточные или окружающие нетерминалы, образует дескриптор

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

Алгоритм анализа приоритета операторов

Приведенный ниже алгоритм взят из Aho et al.: ^[6]

If $ is on the top of the stack and ip points to $ then return
else
    Let a be the top terminal on the stack, and b the symbol pointed to by ip
    if a  $\lessdot$  b or a  $\doteq$  b then
        push b onto the stack
        advance ip to the next input symbol
    else if a  $\gtrdot$  b then
        repeat
            pop the stack
        until the top stack terminal is related by  $\lessdot$  to the terminal most recently popped
    else error()
end

Функции приоритета

Анализатор приоритета операторов обычно не хранит таблицу приоритетов с отношениями, которая может стать довольно большой. функции приоритета f и g . Вместо этого определены ^[7] Они отображают терминальные символы в целые числа, поэтому отношения старшинства между символами реализуются путем числового сравнения: ⁠ $f(a)<g(b)$ ⁠ должно сохраняться, если $a\lessdot b$ держится и т. д.

Не каждая таблица отношений предшествования имеет функции предшествования, но на практике для большинства грамматик такие функции могут быть разработаны. ^[8]

Алгоритм построения функций предшествования

Приведенный ниже алгоритм взят из Aho et al.: ^[9]

Создайте символы $f a$ и $g a$ для каждого грамматического терминала $a$ и для символа конца строки;
Разбейте созданные символы на группы так, чтобы $f a$ и $g b$ находились в одной группе, если $a\doteq b$ (в одной группе могут находиться символы, даже если их терминалы не связаны этим отношением);
Создайте ориентированный граф , узлами которого являются группы. Для каждой пары ⁠ $(a,b)$ ⁠ терминалов сделать: поместить ребро из группы $g b$ в группу $f a$ , если $a\lessdot b$ , в противном случае, если $a\gtrdot b$ поместите ребро из группы $f a$ в группу $g b$ ;
Если построенный граф имеет цикл, то функций предшествования не существует. Если циклов нет, пусть ⁠ $f(a)$ ⁠ — длина самого длинного пути из группы $f a$ , и пусть ⁠ $g(a)$ ⁠ — длина самого длинного пути из группы $g a$ .

Пример

Рассмотрим следующую таблицу (повторенную сверху): ^[10]

{\begin{array}{c|cccc}&\mathrm {id} &+&*&\$\\\hline \mathrm {id} &&\gtrdot &\gtrdot &\gtrdot \\+&\lessdot &\gtrdot &\lessdot &\gtrdot \\*&\lessdot &\gtrdot &\gtrdot &\gtrdot \\\$&\lessdot &\lessdot &\lessdot &\end{array}}

Использование алгоритма приводит к следующему графику:

    gid
      \
 fid   f*
    \  /
     g*
    /
  f+  
   | \
   |  g+
   |  |
  g$  f$

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

	идентификатор	+	*	$
ж	4	2	4	0
г	5	1	3	0

Языки приоритета операторов

Класс языков, описываемых грамматиками приоритета операторов, т. е. языков с приоритетом операторов, строго содержится в классе детерминированных контекстно-свободных языков и строго содержит языки с видимым смещением вниз . ^[11]

Языки с приоритетом операторов обладают многими свойствами замыкания: объединением, пересечением, дополнением, ^[12] конкатенация, ^[11] и это самый большой известный класс, замкнутый относительно всех этих операций и для которого разрешима проблема пустоты. Еще одной особенностью языков с приоритетом операторов является их локальная разборчивость. ^[13] что обеспечивает эффективный параллельный анализ.

Существуют также характеристики, основанные на эквивалентной форме автоматов и монадической логике второго порядка. ^[14]

Примечания

^ Ахо, Сети и Уллман 1988 , стр. 203
^ Ахо, Сети и Уллман 1988 , стр. 203–204
^ Ахо, Сети и Уллман 1988 , стр. 205–206
^ Jump up to: ^а ^б ^с Ахо, Сети и Уллман 1988 , с. 205
^ Ахо, Сети и Уллман 1988 , стр. 204
^ Ахо, Сети и Уллман 1988 , стр. 206
^ Ахо, Сети и Уллман 1988 , стр. 208–209
^ Ахо, Сети и Уллман 1988 , стр. 209
^ Ахо, Сети и Уллман 1988 , стр. 209–210
^ Ахо, Сети и Уллман 1988 , стр. 210
^ Jump up to: ^а ^б Креспи Региззи и Мандриоли, 2012 г.
^ Креспи Региззи, Мандриоли и Мартин 1978
^ Баренги и др. 2015 год
^ Лонати и др. 2015 год

Ссылки

Ахо, Альфред В.; Сетхи, Рави; Уллман, Джеффри Д. (1988). Компиляторы — принципы, методы и инструменты . Аддисон-Уэсли.
Креспи Региззи, Стефано; Мандриоли, Дино (2012). «Приоритет операторов и свойство визуального нажатия» . Журнал компьютерных и системных наук . 78 (6): 1837–1867. дои : 10.1016/j.jcss.2011.12.006 .
Креспи Региззи, Стефано; Мандриоли, Дино; Мартин, Дэвид Ф. (1978). «Алгебраические свойства языков приоритета операторов» . Информация и контроль . 37 (2): 115–133. дои : 10.1016/S0019-9958(78)90474-6 .
Баренги, Алессандро; Креспи Региззи, Стефано; Мандриоли, Дино; Панелла, Федерика; Праделла, Маттео (2015). «Параллельный анализ стал практичным» . Наука компьютерного программирования . 112 (3): 245–249. дои : 10.1016/j.scico.2015.09.002 . HDL : 11311/971391 .
Лонати, Виолетта; Мандриоли, Дино; Панелла, Федерика; Праделла, Маттео (2015). «Языки приоритета операторов: их теоретико-автоматная и логическая характеристика». SIAM Journal по вычислительной технике . 44 (4): 1026–1088. дои : 10.1137/140978818 . hdl : 2434/352809 .

Дальнейшее чтение

Флойд, RW (июль 1963 г.). «Синтаксический анализ и приоритет операторов» . Журнал АКМ . 10 (3): 316–333. дои : 10.1145/321172.321179 . S2CID 19785090 .

Внешние ссылки

Николай Николаев: IS53011A Language Design and Implementation , Конспекты курса для CIS 324, 2010.

[1] Ахо, Сети и Уллман 1988 , стр. 203

[2] Ахо, Сети и Уллман 1988 , стр. 203–204

[3] Ахо, Сети и Уллман 1988 , стр. 205–206

[Asu-4] Jump up to: ^а ^б ^с Ахо, Сети и Уллман 1988 , с. 205

[5] Ахо, Сети и Уллман 1988 , стр. 204

[6] Ахо, Сети и Уллман 1988 , стр. 206

[7] Ахо, Сети и Уллман 1988 , стр. 208–209

[8] Ахо, Сети и Уллман 1988 , стр. 209

[9] Ахо, Сети и Уллман 1988 , стр. 209–210

[10] Ахо, Сети и Уллман 1988 , стр. 210

[CrespiReghizziMandrioli-JCSS2012-11] Jump up to: ^а ^б Креспи Региззи и Мандриоли, 2012 г.

[CrespiReghizziMandrioliMartin-1978-12] Креспи Региззи, Мандриоли и Мартин 1978

[13] Баренги и др. 2015 год

[14] Лонати и др. 2015 год

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v т и Алгоритмы разбора
Сверху вниз	Эрли LL Рекурсивный спуск Хвостовая рекурсия
Вверх дном	Приоритет Простой Оператор Маневровый двор ЛР Простой смотреть вперед Канонический Обобщенный ГАЛОЧКА Рекурсивное восхождение Shift-уменьшить
Смешанное, другое	Комбинатор Диаграмма Левый угол Статистический
Связанные темы	ПЭГ Определенная грамматика предложения Детерминированный анализ Динамическое программирование Мемоизация Генератор парсера ЛАЛР Дерево разбора АСТ Бессканерный парсинг История создания компилятора Сравнение генераторов парсеров Грамматика приоритета операторов