Лекция № 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. 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. <идентификатор>::= <буква> | <идентификатор> <буква> |
<идентификатор> <цифра>

 

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

 

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

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

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