Таким образом, формальные грамматики способны любые перечислимые множества.

Специфика формально лингвистического подхода к описанию множеств цепочек начинает проявляться при рассмотрении более узких классов грамматик. Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского, содержащая четыре типа грамматик.

Грамматика типа 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; просмотров: 540;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.