V . Введение в теорию формальных языков

V. Введение в теорию формальных языков

Грамматики с ограничениями на правила

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

Описание идентификатора на метаязыке Хомского-Щутценберже.

1. A ₁ =A+B+C+D+…+Y+Z+a+b+c+d+…+x+y+z

2. A ₂ =0+1+2+4+5+6+7+8+9

_3. A ₃ =A ₁ +A ₃ A ₁ +A ₃ A ₂

5.3. Бэкуса-Наура формы (БНФ).

Метаязыки Хомского и Хомского-Щутценберже использовались в математической литературе при описании простых абстрактных языков. Метаязык, предложенный Бэкусом и Науром, впервые использовался для описания синтаксиса реального языка программирования Алгол 60. Наряду с новыми обозначениями метасимволов, в нем использовались содержательные обозначения нетерминалов, что сделало описание языка нагляднее и позволило в дальнейшем использовать данную нотацию для описания реальных языков программирования. Были использованы следующие обозначения:

· символ::= отделяет левую часть правила от правой;

· нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки < и >;

· терминалы – это символы, используемые в описываемом языке;

· каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты |.

Описание идентификатора с использованием БНФ.

1. <буква>:: = А|В|С|D|E|…|W|X|Y|Z|a|b|c|d|e|…|w|x|y|z

2. <цифра>:: = 0|1|2|3|4|5|6|7|8|9

3. <идентификатор>::= <буква> | <идентификатор><буква> |<идентификатор><цифра>

Правила можно задавать раздельно:

1. <идентификатор>:: = <буква>

2. <идентификатор>:: = <идентификатор> <буква>

3. <идентификатор>:: = <идентификатор> <цифра>

5.4. Расширенные Бэкуса-Наура формы (РБНФ).

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

К таким метаязыкам относятся метаязык PL/I, метаязык Вирта, используемый при описании Модулы-2, метаязык Кернигана-Ритчи, описывающий Си, и они называются расширенными формами Бэкуса-Наура (РБНФ).

Особенности РБНФ, используемые Виртом:

· квадратные скобки [ и ] означают, что заключенная в них синтаксическая конструкция может отсутствовать;

· фигурные скобки { и } означают, что заключенная в них синтаксическая конструкция повторяется (возможно, 0 раз);

· круглые скобки (и) используются для ограничения альтернативных конструкций;

· сочетание фигурных скобок и косой черты {/ и /} используется для обозначения повторения один и более раз;

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

· терминальные символы изображаются словами, написанными буквами латинского алфавита (зарезервированные слова) или цепочками знаков, заключенными в кавычки;

· синтаксическим правилам предшествует знак $ в начале строки;

· каждое правило оканчивается знаком. (точка);

· левая часть правила отделяется от правой знаком = (равно), а альтернативы – вертикальной чертой |.

Синтаксис идентификатора

$ буква = "A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L"|"M"|"N"|"O"|"P"|"Q"|"R"|"S"|

"T"|"U"|"V"|"W"|"X"|"Y"|"Z"|"a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"|"n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z".

$ цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".

$ идентификатор = буква {буква | цифра}.

5.5. Диаграммы Вирта.

Кроме текстовых способов описания синтаксиса языков, используются графические метаязыки, среди которых наиболее широкую известность получил язык диаграмм Вирта, впервые примененный для описания языка Паскаль.

Метасимволы заменены следующими графическими обозначениями (примитивами):

· терминальные символы и их постоянные группы располагаются в окружностях или прямоугольниках со скругленным вертикальными сторонами;

· нетерминальные символы заносятся внутрь прямоугольников;

· каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно рисуются на противоположных сторонах;

· каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;

· альтернативы в правилах задаются ветвлением дуг, а итерации – их слиянием;

· должна быть одна входная дуга (располагается обычно слева и сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа и снизу).

Компоненты распознавателя.

1. Входная лента – это линейная последовательность ячеек (клеток), каждая из которых содержит один входной символ из конечного входного алфавита; могут присутствовать оба концевые маркеры (левый и правый) или только один концевой маркер (левый или правый), а также оба маркера могут отсутствовать.

2. Входная головка в каждый момент читает одну входную ячейку; за один шаг может сдвинуться на одну ячейку влево или вправо или остаться неподвижной.

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

3. Вспомогательная (рабочая) память хранит информацию, построенную только из символов конечного алфавита памяти; может иметь различную организацию: очередь, стек (магазин) и т. д.

Из вспомогательной памяти можно читать и писать в нее. Для стека и очереди используются специфические операции (вталкивание, выталкивание).

Распознаватель может изменять состояние памяти, имеющей структуру конечного линейного списка ячеек или организованную как стек (магазин). Примерами распознавателей являются машина Тьюринга, конечные и магазинные автоматы.

4. Устройство управления с конечной памятью – это программа, управляющая поведением распознавателя; может являться аналогом конечного автомата; определяет перемещение входной головки и работу с памятью на каждом шаге (такте); переходит за шаг из одного состояния в другое.

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

Классы языков.

Каждому классу грамматик из иерархии Хомского соответствует класс распознавателей, определяющий тот же класс языков.

1. Язык L праволинейный тогда и только тогда, когда он определяется конечным, односторонним детерминированным автоматом.

2. Язык L контекстно-свободный тогда и только тогда, когда он определяется односторонним недетерминированным автоматом с магазинной памятью.

3. Язык L контекстно-зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным линейно ограниченным автоматом.

4. Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга.

 

V. Введение в теорию формальных языков