Отношения между классами кс-грамматик

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

Можно еще, например, упомянуть класс грамматик ограниченного правого контекста (m,n) – ОПК(m,n). Это грамматики, допускающие построение распознавателя, основанного на алгоритме “сдвиг-свертка”, в котором однозначный выбор между сдвигом и сверткой делается исходя из анализа m символов, находящихся на верхушке стека, и n текущих символов входной цепочки, считая от положения считывающей головки расширенного МП-автомата. Все ОПК(m,n)-грамматики для всех значений m и n составляют класс ОПК-грамматик. Простейшим вариантом грамматик такого класса являются ОПК(1,1)-грамматики. Интересно, что с помощью этих грамматик, как и с помощью LR-грамматик, можно определить любой детерминированный КС-язык.

Далее будут рассмотрены различные классы КС-грамматик и существующие между ними нетривиальные соотношения.

В общем случае можно выделить правоанализируемые и левоанализируемые КС-грамматики. Первые предполагают построение левостороннего (восходящего) распознавателя, вторые – правостороннего (нисходящего). Это вовсе не значит, что для КС-языка, заданного, например, некоторой левоанализируемой грамматикой, невозможно построить расширенный МП-автомат, который порождает правосторонний вывод. Указанное разделение грамматик относится только к построению на их основе детерминированных МП-автоматов и детерминированных расширенных МП-автоматов. Только эти типы автоматов представляют интерес при создании компиляторов и анализе входных цепочек языков программирования. Недетерминированные автоматы, порождающие как левосторонние, так и правосторонние выводы, можно построить в любом случае для языка заданного любой КС-грамматикой, но для создания компилятора такие автоматы интереса не представляют.

На рис. 4.3 изображена условная схема, дающая представление о соотношении классов левоанализируемых и правоанализируемых КС-грамматик.

Рис. 4.3. Соотношение классов левоанализируемых и правоанализируемых КС-грамматик

Интересно, что классы левоанализируемых и правоанализируемых грамматик являются несопоставимыми. То есть существуют левоанализируемые КС-грамматики, на основе которых нельзя построить детерминированный расширенный МП-автомат, порождающий правосторонний вывод; и наоборот – существуют правоанализируемые КС-грамматики, не допускающие построение МП-автомата, порождающего левосторонний вывод. Конечно, существуют грамматики, подпадающие под оба класса и допускающие построение детерминированных автоматов как с правосторонним, так и с левосторонним выводом.

Следует помнить также, что все упомянутые классы КС-грамматик – это счетные, но бесконечные множества. Нельзя построить и рассмотреть все возможные левоанализируемые грамматики или даже все возможные LL(1)-грамматики. Сопоставление классов КС-грамматик производится исключительно на основе анализа структуры их правил. Только на основании такого рода анализа произвольная КС-грамматика может быть отнесена в тот или иной класс (или несколько классов).

Класс левоанализируемых LL-грамматик является собственным подмножеством класса LR-грамматик: любая LL-грамматика является LR-грамматикой, но не наоборот – существуют LR-грамматики, которые не являются LL-грамматиками. Этот факт также нашел свое отражение в схеме на рис. 4.3. Значит, любая LL-грамматика является правоанализируемой, но существуют также и другие левоанализируемые грамматики, не попадающие в класс правоанализируемых грамматик.

Для LL(k)-грамматик, составляющих класс LL-грамматик, интересна еще одна особенность: доказано, что всегда существует язык, который может быть задан LL(k)-грамматикой для некоторого k0, но не может быть задан LL(k–1)-грамматикой. Таким образом, все LL(k)-грамматики для всех k представляют определенный интерес (другое дело, что распознаватели для них при больших значениях k будут слишком сложны). Интересно, что проблема эквивалентности для двух LL(k)-грамматик разрешима.

С другой стороны, для LR(k)-грамматик, составляющих класс LR-грамматик, доказано, что любой язык, заданный LR(k)-грамматикой с
k1, может быть задан LR(1)-грамматикой. То есть LR(k)-грамматики с k1 интереса не представляют. Однако доказательство существования LR(1)-грамматики вовсе не означает, что такая грамматика всегда может быть построена (проблема преобразования КС-грамматик неразрешима).

На рис. 4.4 условно показана связь между некоторыми классами КС-грамматик, упомянутых в данном пособии. Из этой схемы видно, например, что любая ОПК-грамматика является LR-грамматикой, а также любая LL-грамматика является LR-грамматикой, но не всякая LL-грамматика является LR(1)-грамматикой.

Рис. 4.4. Схема взаимосвязи некоторых классов КС-грамматик

Статьи к прочтению:

ООП С++. Часть 1. Отношения между классами. UML обозначения.

Похожие статьи: