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

В данном учебном пособии было рассмотрено несколько основных классов КС-грамматик, для которых существуют линейные распознаватели, – это 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)-грамматикой для некоторого k > 0, но не может быть задан LL(k–1)-грамматикой. Таким образом, все LL(k)-грамматики для всех k представляют опре­деленный интерес (другое дело, что распознаватели для них при больших значе­ниях k будут слишком сложны). Интересно, что проблема эквивалентности для двух LL(k)-грамматик разрешима.

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

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

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