примеры синтаксических диаграмм вирта

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

1.44 Mb.Название страница5/18Дата конвертации21.11.2012Размер1.44 Mb.Тип источник

Способы записи синтаксиса языка - Основы разработки трансляторов Содержание курса лекций