ЛЕКЦИЯ № 4 СПОСОБЫ ЗАПИСИ СИНТАКСИСА ЯЗЫКА. РАСПОЗНАВАТЕЛИ
Существуют различные способы записи синтаксических правил, что в основном определяется условными обозначениям и ограничениями на структуру правил, принятыми в используемых метаязыках. Метаязыки используются для задания грамматики языков программирования со времен Алгола 60. Еще раньше они начали использоваться при описании небольших языков в статьях, посвященных формальным грамматикам. Кратко рассмотрим основные вехи становления и развития метаязыков. Во всех случаях будем определять идентификатор.
Метаязык Хомского
Метаязык Хомского вышел из недр математической логики. Он имеет следующую систему обозначений:
– символ «®» отделяет левую часть правила от правой (читается как «порождает» и «это есть»);
– нетерминалы обозначаются буквой А с индексом, указывающим на его номер;
– терминалы – это символы используемые в описываемом языке;
– каждое правило определяет порождение одной новой цепочки, причем один и тот же нетерминал может встречаться в нескольких правилах слева.
Описание идентификатора на метаязыке Хомского будет выглядеть следующим образом:
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. A1 = 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. A2 = 0 + 1 + 2 + 4 + 5 + 6 + 7 + 8 + 9
3. A3 = A1 + A3A1 + A3A2
Бэкуса-Наура формы (БНФ)
Метаязыки Хомского и Хомского-Щутценберже использовались в математической литературе при описании простых абстрактных языков. Метаязык, предложенный Бэкусом и Науром, впервые использовался для описания синтаксиса реального языка программирования Алгол 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. <идентификатор> ::= <буква> | <идентификатор> <буква> |
<идентификатор> <цифра>
Правила можно задавать и раздельно:
<идентификатор> :: = <буква>
<идентификатор> :: = <идентификатор> <буква>
<идентификатор> :: = <идентификатор> <цифра>