Соотношение классов КС-грамматик

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

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

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

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

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

Рассмотренный в данном посо­бии класс левоанализируемых LL-грамматик является собственным подмноже­ством класса LR-грамматик: любая LL-грамматика является LR-грамматикой, но не наоборот — существуют LR-грамматики, которые не являются LL-грамма-тиками. Значит, любая LL-грамматика является правоанализируемой, но существуют также и другие левоанализируемые грамматики, не попадающие в класс правоанализируемых грамматик.

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