Карпов - Основы построения трансляторов (2005), страница 12

Такой язык называется меиаязыком. Как мы увидим дальше, это просто соглашения для удобного представления продукций КС- грамматики. Продукции эти, конечно, можно непосредственно использовать в качестве фраз такого языка, но обычно нетерминальные символы имеют связанный с ними смысл, и в грамматике удобнее использовать для нетерминальных символов не абстрактные обозначения, а названия соответствующих конструкций. Исторически первым метаязыком для представления правил КС-грамматики является нотация Бэкуса — Наура или БНФ-нотация, которая названа так в честь Дж. Ьэкуса, главного разработчика первого компилятора для языка Фортран, и Питера Наура, сыгравшего основную роль в разработке Алгола-60. Эта нотация, использованная впервые для строгого определения Алгола-бО, была предшественницей правил порождающей КС-грамматики Хамского.

Нетерминалы здесь помещаются в угловые скобки, символ '.:= ' используется вместо стрелки "— +". Именно здесь было использовано упрощение, при котором альтернативы одного и того же нетерминала записываются в правой части одного правила через знак 1', имеющий смысл "либо". Названия конструкций, представляющие нетерминальные символы КС-грамматики, ограничиваются в ЬНФ-нотации угловыми скобками. Расширенная БНФ-нотация включает две конструкции, полезные при спецификации практических языков программирования. Первая с помощью фигурных скобок позволяет легко описать повторение 0 или большее произвольное число раз некоторой цепочки.

Например, синтаксис Турбо Паскаля представляет структуру описаний переменных так: <чаг1аЫе-дес1агабоп-раг~>::= ~аг <~апайе-дес 1ага6оп> (:, <~аг1аЬ!е-дес!ага6оп>~ При выводе цепочки языка при замене нетерминала левой части продукции правой ее частью содержимое фигурных скобок может повторяться произвольное число раз, в том числе и ни разу, Это, очевидно, соответствует операции итерации Клини для регулярных множеств, что можно представить так: заключение цепочки р в фигурные скобки ',Я в БНФ эквивалентно записи ф)* в регулярных выражениях.

Это, конечно, может быть представлено Языки и грамматики Рис. 2.19. Определение идентификатора синтаксическими диаграммами Рис. 2.20. Синтаксическая диаграмма, задающая все римские числа Рис. 2.21. Синтаксическая диаграмма с и разветвлениями. Очевидно, что так определенное множество синтаксических диаграмм порождает тот же язык, что и грамматика 8 ПРИМЕР 2.22. Грамматике б7.' 67.' Š— ье ) Щ! Е~~Е соответствует следующее эквивалентное множество синтаксических диаграмм (рис.

2.22). Глава 2 74 Рис. 2.22. Синтаксические диаграммы грамматики 87 ПРИМЕР 2.23. Синтаксическая диаграмма рис. 2.23 задает константу в Пас- кале, здесь же приведен и соответствующий недетерминированный конечный автомат. Здесь обозначены Л вЂ” КОНСТАНТА„1 — - ИДЕНТИФИКАТОР КОНСТАНТЫ, Ч вЂ” ЧИСЛО ЬЕЗ ЗНАКА. з — символ. В расширенной БНФ-нотации язык, порождающий константы, легко записы- вается прямо по диаграмме или автомату: По конечному автомату может быть легко построена и эквивалентная КС- грамматика следующим образом. Пометим все состояния автомата нетерми- налами, причем начальное состояние помечается нетерминалом.

соответст- вующим имени синтаксической диаграммы. 0 — заключительное состояние. а) Рис. 2.23. а) Синтаксическая диаграмма константы в Паскале; б) соответствующий конечный автомат Докажем теперь, что по любому набору синтаксических диаграмм можно построить эквивалентную КС-грамматику. Действительно, синтаксическую диаграмму можно считать конечным автоматом, состояния которого соответствуют ребрам синтаксической диаграммы, а переходы — соответствующим символам.

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

Языки и грамматики Теперь искомая КС-грамматика строится просто: а: к -~А!-А!А!'в А-+ХЙ ! ЧЙ В-+яС1"С с- в!'п Таким образом, синтаксические диаграммы — это графическая форма спецификации языков, фактически аналогичная обычным порождающим контекстно-свободным грамматикам Хомского. Удобство синтаксических диаграмм состоит в том„что синтаксические диаграммы явно представляют конечный автомат, в соответствии с алгоритмом функционирования которого может быть построен алгоритм распознавания соответствующей конструкции языка. если этот автоматдетерминированный ~см. рис. 2.23).

2.7.3. Грамматики с рассеянным контекстом Этот класс порождающих грамматик предложен известными исследователями в области формальных языков Шейлой Грейбах и Дж. Хопкрофтом [ГХ751, Грамматики с рассеянным контекстом являются обобщением грамматик Хомского, цель их введения — упростить описание контекстных свойств естественных и искусственных языков (в частности, языков программирования), Авторы обосновывают необходимость введения такого расширения грамматик Хомского следующим. Контекстно-свободные грамматики Хомского слишком слабы, чтобы описать такие свойства языков программирования, как запрет использования неописанной переменной., согласование типов в операторе присваивания и т. и,, поскольку для спецификации подобных контекстных свойств необходимо передавать информацию между частями предложения, отстоящими друг от друга произвольно далеко.

Например, язык ~иси ~ ю~=-~О, 1~*~, абстрагирующий проблему декларации переменных до их использования„не является контекстно-свободным. Другим примером служит контекстно-зависимый язык А = (а Ь с'г1 ~ и. л > 1,'. Он абстрагирует проблему проверки того, что число формальных параметров в декларации процедуры равно числу фактических параметров в вызове этой процедуры, если интерпретировать а' и о как списки формальных параметров в декларациях двух процедур с л и я аргументами, а с и сГ как списки фактических параметров в вызовах этих процедур ~АСУО11. Известно, что контекстно-зависимые грамматики, которые могут порождать подобные языки, неудобны для практического применения, они плохо приспособлены для приписывания смысла предложениям.

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

Так возникла идея грамматик с рассеянным контекстом. Определение 2.8. Порождающей грамматикой с рассеянным контекстом называется четверка объектов: С = (У; Х, 5, Р), где: У вЂ” конечное непустое множество (терминальный словарь); Ж вЂ” конечное непустое множество (нетерминальный словарь); Я вЂ” начальный символ — Л'еЛ~; Р— конечное непустое множество правил (продукций), каждое из которых имеет вид (А ~, ..., А„) — +(и ~, ..., и „), л > 1, где А,еЖ, и и:,е(ТыЖ)'.

Грамматика с рассеянным контекстом, в отличие от грамматики Хомского, имеет в качестве продукций пары векторов, один из которых — заменяемые символы — это только нетерминалы, а другой — соответствующее количество непустых цепочек объединенного словаря. Отношение ' — >' непосредственной выводимости на множестве цепочек в грамматиках с рассеянным контекстом определяется гак: Пусть (А ~, ..., А(!) — +(и'~„...„и~р)е Р и хрб(У ~ ~ Л) . Тогда: У~А ~ ... х>рА)>хц-, ~:-Ф х~и'~ лли !1 л/7~ 1 ' Таким образом, сразу несколько нетерминалов, стоящих произвольно далеко в порождаемой цепочке, могут быль заменены одновременно на соответствующие им цепочки объединенного словаря.

Определим язык, порождаемый грамматикой Ь, как множество 1.(б) = = (ие7 ~5~* и'~. ПРИМЕР 2.24. В качестве примера рассмотрим грамматику с рассеянным контекстом, порождающую язык Л = ~аЪ с ~ л > 0',. Такая грамматика будет иметь три продукции; 5-+АВС (А, В, () — э(аА, ЬВ, сС) ~ ~п, Ь, с) Вывод цепочки а Ь с состоит из следующих шагов: К =.> АВС-=> аАЬВсС ==> ааА60ВссС =-. апаЬЬБссс. Несколько слов о порождающей способности грамматик с рассеянным контекстом. Во-первых, можно легко видеть, что частным случаем таких грам- Глава 2 78 верхностной. Именно поверхностная структура состоит из терминальных символов и соответствует конкретному предложению. Таким образом, транс- формационная часть грамматики ~или Т-компонента) преобразует С-маркеры в поверхностную структуру предложения, которая включает терминалы, т.