Простая грамматика приоритета

Простая грамматика приоритета — это контекстно-свободная формальная грамматика , которую можно проанализировать с помощью простого анализатора приоритета . Концепция была впервые создана в 1964 году Клодом Пайром . и позже был заново открыт на основе идей Роберта Флойда Никлаусом Виртом и Гельмутом Вебером, которые опубликовали статью под названием «ЭЙЛЕР: обобщение АЛГОЛА и его формальное определение» , опубликованную в 1966 году в « Сообщениях ACM» .

Формальное определение

G = ( N , Σ, P , S ) является простой грамматикой предшествования, если все производственные правила в P соответствуют следующим ограничениям:

• Нет правил стирания (ε-продукций)
• Нет бесполезных правил (недостижимых символов или непродуктивных правил)
• Для каждой пары символов X , Y ( X , Y $\in$ ( N ∪ Σ)) существует только одно отношение предшествования Вирта–Вебера .
• G однозначно обратима

Примеры

$S\to aSSb|c$

таблица приоритетов

${\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&{\dot {=}}&\lessdot &{\dot {=}}&\lessdot &\\a&{\dot {=}}&\lessdot &&\lessdot &\\b&&\gtrdot &&\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}$

Ссылки

• Альфред В. Ахо, Джеффри Д. Ульман (1977). Принципы проектирования компиляторов . 1-е издание. Аддисон-Уэсли.
• Уильям А. Барретт, Джон Д. Коуч (1979). Построение компилятора: теория и практика . научный сотрудник.
• Жан-Поль Трамбле, П.Г. Соренсон (1985). Теория и практика написания компиляторов . МакГроу-Хилл.

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

• «Простые отношения старшинства» в Университете Клемсона