Применение КС-грамматик

В описании языка гипертекстовых ссылок HTML применяется КС-грамматика:

Рассмотрим вывод цепочки языка HTML, соответствующего тексту:

Вещи, которые я люблю:

1. Бананы.

2. Людей общительных, ответственных.

Element → <P>Doc → <P> Element Doc → <P> Text Element Doc →

<P>Char Text <EM>Doc</EM>Element Doc →

<P>В Char Text <EM> Element Doc </EM><OL>List</OL> Doc →

<P>Вe Char Text <EM> Text </EM> <OL>Listitem List</OL> →

<P>Вeщ Char Text <EM> Char Text </EM> <OL><LI>Doc Listitem</OL> →

<P>Вeщи Char Text <EM> л Char Text </EM> <OL><LI>Element Doc <LI>Doc </OL> →

<P>Вeщи, Char Text <EM> лю Char Text </EM> <OL><LI>Text Doc <LI> Element Doc </OL> →

<P>Вeщи, Char Text <EM> люб Char Text </EM> <OL><LI> Char Text <LI> Text </OL> →

<P>Вeщи, к Char Text <EM> любл Char Text </EM> <OL><LI> Б Char Text <LI> Char Text </OL> →

…

<P>Вещи, которые я <EM>люблю</EM>:

<OL>

<LI>Бананы.

<LI>Людей общительных, ответственных.

</OL>

Закрепление материала: составить последовательность вывода цепочки языка HTML, соответствующего тексту:

Мне нравится весна:

1) травой зеленой;

2) теплым солнцем.

КС-грамматики часто используются в описании языков программирования. В этом случае грамматики записываются в определенных формах (метаязыках). Рассмотрим наиболее применимые из них – формы Бэкуса-Наура.

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

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

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

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

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

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

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

1. <буква>::= А|В|С|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

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

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

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

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

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

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

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

Для повышения удобства и компактности описания, целесообразно вести в язык дополнительные конструкции. Существуют различные расширенные формы метаязыков, незначительно отличающиеся друг от друга. Их разнообразие зачастую объясняется желанием разработчиков языков программирования по-своему описать создаваемый язык. К примерам таких широко известных метаязыков можно отнести: метаязык PL/I, метаязык Вирта, метаязык Кернигана-Ритчи, описывающий Си. Зачастую такие языки называются расширенными формами Бэкуса-Наура (РБНФ).

В частности, РБНФ, используемые Виртом, имеют следующие особенности:

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

– фигурные скобки «{» и «}» означают ее повторение (возможно, 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".

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

В качстве примера опишем синтаксис демонстрационного языка программирования с помощью расиренных форм Бэкуса-Наура.

Дата добавления: 2015-05-26