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

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

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

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

Описание идентификатора на метаязыке Хомского

Метаязык Хомского.

Метаязык Хомского вышел из математической логики; имеет следующую систему обозначений:

· символ ® отделяет левую часть правила от правой; обозначает порождает или это есть;

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

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

· каждое правило определяет порождение одной новой цепочки;

· один и тот же нетерминал может встречаться в нескольких правилах слева.

1. A1 ® A	2. A1 ® B …	26. A1 ® Z
27. A1 ® a	28. A1 ® b …	52. A1 ® z
53. A2 ® 0	54. A2 ® 1 …	62. A2 ® 9
63. A3 ® A1	64. A3 ® A3A1	65. A3 ® A3A2

Описание идентификатора на метаязыке Хомского показывает громоздкость метаязыка, поэтому его можно эффективно использовать только для описания небольших абстрактных языков.

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

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

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

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

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

Введение возможности альтернативного перечисления позволило сократить описание языков.

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

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

_· A ₃ =A ₁ +A ₃ A ₁ +A ₃ A ₂

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

Дата добавления: 2014-01-11