SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе

Тема 2. Основы теории языков и формальных грамматик

Предупреждение! На странице используется шрифт Symbol. Если Вас это не устраивает - пиште. Жду замечаний и рекомендаций по более удобному оформлению данной страницы. (А.Л.)

[ предыдущая страница | содержание | следующая страница ]


Способы записи синтаксиса языка

Существуют различные способы записи синтаксических правил, что в основном определяется условными обозначениям и ограничениями на структуру правил, принятыми в используемых метаязыках. Метаязыки используются для задания грамматики языков программирования со времен Алгола 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. <идентификатор> ::= <буква> | <идентификатор><буква> |
    <идентификатор><цифра>

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

  1. <идентификатор> :: = <буква>
  2. <идентификатор> :: = <идентификатор> <буква>
  3. <идентификатор> :: = <идентификатор> <цифра>

Расширенные Бэкуса-Наура формы (РБНФ)

Метаязыки, представленные выше, позволяют описывать любой синтаксис. Однако, для повышения удобства и компактности описания, целесообразно вести в язык дополнительные конструкции. В частности, специальные метасимволы были разработаны для описания необязательных цепочек, повторяющихся цепочек, обязательных альтернативных цепочек. Существуют различные расширенные формы метаязыков, незначительно отличающиеся друг от друга. Их разнообразие зачастую объясняется желанием разработчиков языков программирования по-своему описать создаваемый язык. К примерам таких широко известных метаязыков можно отнести: метаязык PL/I, метаязык Вирта, используемый при описании Модулы-2, метаязык Кернигана-Ритчи, описывающий Си. Зачастую такие языки называются расширенными формами Бэкуса-Наура (РБНФ).

В частности, РБНФ, используемые Виртом, имеют следующие особенности:

  • Квадратные скобки "[" и "]" означают, что заключенная в них синтаксическая конструкция может отсутствовать;
  • фигурные скобки "{" и "}" означают ее повторение (возможно, 0 раз);
  • круглые скобки "(" и ")" используются для ограничения альтернативных конструкций;
  • сочетание фигурных скобок и косой черты "{/" и "/}" используется для обозначения повторения один и более раз. Нетерминальные символы изображаются словами, выражающими их интуитивный смысл и написанными на русском языке.

Если нетерминал состоит из нескольких смысловых слов, то они должны быть написаны слитно. В этом случае для повышения удобства в восприятии фразы целесообразно каждое ее слово начинать с заглавной буквы или разделять слова во фразах символом подчеркивания. Терминальные символы изображаются словами, написанными буквами латинского алфавита (зарезервированные слова) или цепочками знаков, заключенными в кавычки. Синтаксическим правилам предшествует знак "$" в начале строки. Каждое правило оканчивается знаком "." (точка). Левая часть правила отделяется от правой знаком "=" (равно), а альтернативы - вертикальной чертой "|". Этот вариант РБНФ и будет использоваться для описания синтаксиса языков в лабораторной работе. В соответствии с данными правилами синтаксис идентификатора будет выглядеть следующим образом:

$ буква = "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".

$ цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".

$ идентификатор = буква {буква | цифра}.

Диаграммы Вирта

Наряду с текстовыми способами описания синтаксиса языков широко используются и графические метаязыки, среди которых наиболее широкую известность получил язык диаграмм Вирта, впервые примененный для описания языка Паскаль. Метасимволы заменены следующими графическими обозначениями (рис. 2.1):

  • терминальные символы и их постоянные группы располагаются в окружностях или прямоугольниках со скругленным вертикальными сторонами;
  • нетерминальные символы заносятся внутрь прямоугольников;
  • каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно рисуются на противоположных сторонах;
  • каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;
  • альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием;
  • должна быть одна входная дуга (располагается обычно слева и сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа и снизу).

Пример описания идентификатора с использованием диаграмм Вирта представлен на рис 2.2.

Обычно стрелки на дугах диаграмм не ставятся, а направления связей отслеживаются движением от начальной дуги в соответствии с плавными изгибами промежуточных дуг и ветвлений. Таким же образом определяются входы и выходы терминалов и нетерминалов. Специальных стандартов на диаграммы Вирта нет, поэтому графические обозначения могут меняться в зависимости от средств рисования. Можно, например, использовать псевдографику или просто текстовые символы, связи со стрелками. Однако такой вид правил менее удобен для восприятия и поэтому применяется крайне редко.

Диаграммы Вирта позволяют задавать альтернативы, рекурсии, итерации и по изобразительной мощности эквивалентны РБНФ. Но графическое отображение правил более наглядно. Кроме этого допускается произвольное проведение дуг, что уменьшает количество элементов в правиле за счет его неструктурированности. Диаграммы Вирта являются удобным исходным документом для построения лексического и синтаксического анализаторов.


[ предыдущая страница | содержание | следующая страница ]



Статьи