Разработка компиляторов

       

Грамматика ван Вейнгаардена


В конце 60-х годов при разработке языка Algol 68 была предложена новая форма определения языка, позволяющая формулировать не только контекстно-свободный синтаксис, но и контекстные условия. Такой способ определения языка получил название грамматики ван Вейнгаардена. Основная идея заключается в том, что это так называемая двухуровневая грамматика. Синтаксис действует следующим образом: заданы множества "гиперправил" и "метаправил", из которых могут выводиться "порождающие правила". Гиперправила - это просто "заготовки" правил. С помощью метаправил задается контекстная составляющая языка.

Пример. Рассмотрим правило, определяющее присваивание.

REF to MODE NEST assignation: REF to MODE NEST destination, becomes token, MODE NEST source.

Большими буквами в этом правиле написаны метасимволы. Метасимволы REF и MODE задают тип (или, как принято говорить, вид) конструкции, причем метасимвол REF означает, что получатель присваивания (destination) должен быть переменной типа MODE . Метасимвол NEST задает контекст конструкции. Обратите внимание, что контекст получателя и источника присваивания совпадают. Из этого правила может быть выведено, например, порождающее правило:

reference to real assignation: reference to real destination, becomes token, real source



Содержание раздела