2014-02-04
1027
Метаязык Хомского-Щутценберже
Метаязык Хомского
Метаязык Хомского вышел из недр математической логики. Он имеет следующую систему обозначений:
- символ “ ® ” отделяет левую часть правила от правой (читается как "порождает" и "это есть");
- нетерминалы обозначаются буквой А с индексом, указывающим на его номер;
- терминалы - это символы используемые в описываемом языке;
- каждое правило определяет порождение одной новой цепочки, причем один и тот же нетерминал может встречаться в нескольких правилах слева.
Описание идентификатора на метаязыке Хомского будет выглядеть следующим образом:
| 1. A1 ® A | 23. A1 ® W | 45. A1 ® s |
| 2. A1 ® B | 24. A1 ® X | 46. A1 ® t |
| 3. A1 ® C | 25. A1 ® Y | 47. A1 ® u |
| 4. A1 ® D | 26. A1 ® Z | 48. A1 ® v |
| 5. A1 ® E | 27. A1 ® a | 49. A1 ® w |
| 6. A1 ® F | 28. A1 ® b | 50. A1 ® x |
| 7. A1 ® G | 29. A1 ® c | 51. A1 ® y |
| 8. A1 ® H | 30. A1 ® d | 52. A1 ® z |
| 9. A1 ® I | 31. A1 ® e | 53. A2 ® 0 |
| 10. A1 ® J | 32. A1 ® f | 54. A2 ® 1 |
| 11. A1 ® K | 33. A1 ® g | 55. A2 ® 2 |
| 12. A1 ® L | 34. A1 ® h | 56. A2 ® 3 |
| 13. A1 ® M | 35. A1 ® i | 57. A2 ® 4 |
| 14. A1 ® N | 36. A1 ® j | 58. A2 ® 5 |
| 15. A1 ® O | 37. A1 ® k | 59. A2 ® 6 |
| 16. A1 ® P | 38. A1 ® l | 60. A2 ® 7 |
| 17. A1 ® Q | 39. A1 ® m | 61. A2 ® 8 |
| 18. A1 ® R | 40. A1 ® n | 62. A2 ® 9 |
| 19. A1 ® S | 41. A1 ® o | 63. A3 ® A1 |
| 20. A1 ® T | 42. A1 ® p | 64. A3 ® A3A1 |
| 21. A1 ® U | 43. A1 ® q | 65. A3 ® A3A2 |
| 22. A1 ® V | 44. A1 ® r |
Приведенный в предыдущем разделе пример описания идентификатора показывает громоздкость метаязыка Хомского, что позволяет эффективно использовать его только для описания небольших абстрактных языков. Более компактное описание возможно с применением метаязыка Хомского-Щутценберже, использующего следующие обозначения метасимволов:
|
|
|
- символ “=” отделяет левую часть правила от правой (вместо символа “ ® ”);
- нетерминалы обозначаются буквой А с индексом, указывающим на его номер;
- терминалы - это символы используемые в описываемом языке;
- каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом “+”, что позволяет, при желании, использовать в левой части только разные нетерминалы.
Введение возможности альтернативного перечисления позволило сократить описание языков. Описание идентификатора будет выглядеть следующим образом:
1. A 1 =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 2 =0+1+2+4+5+6+7+8+9
3. A 3 =A 1 +A 3 A 1 +A 3 A 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. <идентификатор>::= <буква> | <идентификатор><буква> |
<идентификатор><цифра>
Правила можно задавать и раздельно:
3. <идентификатор>:: = <буква>
4. <идентификатор>:: = <идентификатор> <буква>
5. <идентификатор>:: = <идентификатор> <цифра>
