Таким образом, формальные грамматики способны любые перечислимые множества.
Специфика формально лингвистического подхода к описанию множеств цепочек начинает проявляться при рассмотрении более узких классов грамматик. Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик.
Грамматика типа 0 - это грамматика произвольного вида, без ограничений на правила вывода.
Грамматика типа 1 (контекстная грамматика) - это грамматика, все правила которой имеют вид a А b ® a w b, где w Î (V È W)+. Цепочки a и b - это контекст правила. Они не изменяются при его применении.
Грамматика типа 2 или контекстно - свободная грамматика (КС-грамматика) -
грамматика, все правила которой имеют вид А ® a, где a Î (V È W)*.
Грамматика типа 3 или регулярная грамматика - грамматика, все правила которой имеют вид либо А ® aВ, либо А ® a.
Язык L называется языком типа i (i = 0, 1, 2, 3), если существует порождающая его грамматика типа i.
5.2. Контекстно - свободные грамматики
КС - языки являются наиболее изученными классом. Это объясняется тем, что с одной стороны, КС-грамматики оказались весьма подходящим аппаратом для описания строения естественных языков и особенно языков программирования. С другой стороны, благодаря относительной простоте и содержательности структуры КС-языков и наличию удобных средств её описания исследование КС-языков представляет значительный практический интерес.
Появление понятия КС-грамматики практически совпало с разработкой мета языка Бэкуса (или нормальной формы Бэкуса), который был впервые использован при описании языка программирования АДГОЛ - 60 и быстро стал общепринятым средством формального описания языков программирования. Описание языка с помощью нормальных форм Бэкуса представляет собой совокупность так называемых "металингвистических формул" - выражений вида Х::=Y1ïY2ï... ïYn, где Х - некоторый текст, заключенный в угловые скобки и называемый металингвистической переменной, а Y1, ... , Yn - последовательность металингвистических переменных и основных символов языка (букв, цифр, разделителей, неделимых слов типа "begin" и т. п.). Знак ::= называется металингвистической связкой и читается как "есть" или "это". Знак ï- это металингвистическая связка "или". Металингвистическая переменная представляет собой имя конструкции языка.
Металингвистическая формула в целом - это описание различных синтаксических вариантов построения конструкций Х, стоящей в левой части, через другие конструкции и символы языка, указанные в правой части. Перечисление вариантов представления производится с использованием связки "или".
Пример 1. Множество идентификаторов Паскаль - это множество цепочек из букв и цифр, начинающихся с буквы. Тогда понятие идентификатора может быть описано с помощью следующих нормальных форм Бэкуса (металингвистических формул), в которых цепочка из букв и цифр сокращенно называется БЦ-цепочкой:
< идентификатор> ::= <буква>ï<буква><БЦ-цепочка>
<БЦ-цепочка>::= <буква>ï<цифра>ï<буква>ï<буква><БЦ-цепочка>ï<цифра>
<БЦ-цепочка>
<буква>::= a ïb ïc ï ... ïz
<цифра>::=0 ï1 ï2 ï... ï9
Дата добавления: 2015-10-05; просмотров: 477;