Метаязык Хомского-Щутценберже

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

· символ “=” отделяет левую часть правила от правой (вместо символа “  ”);

· нетерминалы обозначаются буквой А с индексом, указывающим на его номер;

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

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

Введение возможности альтернативного перечисления позволило сократить описание языков. Описание идентификатора будет выглядеть следующим образом:

1. A ₁ =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

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

3. A ₃ =A ₁ +A ₃ A ₁ +A ₃ A ₂

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

Метаязыки Хомского и Хомского-Щутценберже использовались в математической литературе при описании простых абстрактных языков. Метаязык, предложенный Бэкусом и Науром, впервые использовался для описания синтаксиса реального языка программирования Алгол 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. < идентификатор>:: = < буква> | < идентификатор> < буква> |
< идентификатор> < цифра>

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

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

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

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

Например, грамматику целых чисел без знака можно записать в виде:

< число>: < цифра> | < цифра> < число>

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

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

Метаязыки, представленные выше, позволяют описывать любой синтаксис. Однако, для повышения удобства и компактности описания, целесообразно вести в язык дополнительные конструкции. В частности, специальные метасимволы были разработаны для описания необязательных цепочек, повторяющихся цепочек, обязательных альтернативных цепочек. Существуют различные расширенные формы метаязыков, незначительно отличающиеся друг от друга. Их разнообразие зачастую объясняется желанием разработчиков языков программирования по-своему описать создаваемый язык. К примерам таких широко известных метаязыков можно отнести: метаязык 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».

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