Соотношение классов КС-языков

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

Рисунок 3.7– Соотношение между различными классами КС-языков

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

Также LL-языки являются собственным подмножеством LR-языков: всякий LL-язык является одновременно LR-языком, но существуют LR-языки, которые не являются LL-языками. Поэтому LL-языки образуют более узкий класс, чем LR-языки.

Языки простого предшествования, в свою очередь, также являются собственным подмножеством LR-языков, а языки операторного предшествования - собствен­ным подмножеством языков простого предшествования. Интересно, что языки операторного предшествования представляют собой более узкий класс, чем язы­ки простого предшествования.

В то же время языки простого предшествования и LL-языки несопоставимы ме­жду собой: существуют языки простого предшествования, которые не являются LL-языками, и в то же время существуют LL-языки, которые не являются языка­ми простого предшествования. Однако существуют языки, которые одновремен­но являются и языками простого предшествования, и LL-языками. Аналогичное замечание относится также к соотношению между собой языков операторного предшествования и LL-языков.

Можно еще отметить, что язык арифметических выражений над символами а и b, заданный грамматикой G({+, -, /, *, a, b}, {S, T, E}, P, S), Р = {S->S+T|S-T|T, Т->Т*Е|Т/Е|Е, E->(S)|a|b), который многократно использовался в примерах в данном учебном пособии, подпадает под все указанные выше классы языков. Из приведенных ра­нее примеров можно заключить, что этот язык является и LL-языком, и языком операторного предшествования, а следовательно, и языком простого предшествования и, конечно, LR(1)-языком. В то же время этот язык по мере изложения материала пособия описывался различными грамматиками, не все из которых могут быть отнесены в указанные классы.

Таким образом, соотношение классов КС-языков не совпадает с соотношением задающих их классов КС-грамматик. Это связано с неразрешимостью проблем преобразования и эквивалентности грамматик, которые не имеют строго форма­лизованного решения.