Основы теории языков и формальных грамматик Содержание темы Способы определения языков. Формальные грамматики. Грамматики с ограничениями на правила. Способы записи синтаксиса языка. Распознаватели. 1Трансляторы

Два основных способа определения языков: механизм порождения или генератор; механизм распознавания или распознаватель. Они тесно связаны. Первый обычно используется для описания языков, а второй для их реализации. Оба способа позволяют описать языки конечным образом, несмотря на бесконечное число порождаемых ими цепочек. Неформально язык L - это множество цепочек конечной длины в алфавите T. 2Трансляторы

Механизм порождения позволяет описать языки с помощью системы правил, называемой грамматикой. Цепочки (предложения) языка строятся в соответствии с этими правилами. Достоинство определения языка с помощью грамматик в том, что операции, производимые в ходе синтаксического анализа и перевода можно делать проще, если воспользоваться структурой, предписываемой цепочкам с помощью этих грамматик. Механизм распознавания использует алгоритм, который для произвольной входной цепочки остановится и ответит " да " после конечного числа шагов, если эта цепочка принадлежит языку. Если цепочка не принадлежит языку, алгоритм ответит " нет ". Распознаватели используются непосредственно при построении синтаксических анализаторов и являются как бы их формальной моделью. Строятся на основе теорий конечных автоматов и автоматов с магазинной памятью. 3Трансляторы

Формальные грамматики Грамматикой называется четверка G = (N, T, P, S), где N -конечное множество нетерминальных символов (нетерминалов), T -множество терминалов (не пересекающихся с N ), S -символ из N, называемый начальным, Р -конечное подмножество множества: (N T) * N (N T) * x (N T) *, называемое множеством правил. Множество правил Р описывает процесс порождения цепочек языка. Элемент p i = (, ) множества Р называется правилом (продукцией) и записывается в виде. Здесь и - цепочки, состоящие из терминалов и нетерминалов. Данная запись может читаться одним из следующих способов: цепочка порождает цепочку ; из цепочки выводится цепочка. 4Трансляторы

Таким образом, правило P имеет две части: левую, определяемую, и правую, подставляемую. То есть правило p i - это двойка ( p i1, p i2 ), где p i1 = (N T) N * (N T) * - цепочка, содержащая хотя бы один нетерминал, p i2 = (N T) * - произвольная, возможно пустая цепочка ( - цепочка). Если цепочка содержит p i1, то, в соответствии с правилом p i, можно образовать новую цепочку заменив одно вхождение p i1 на p i2. Говорят также, что цепочка выводится из в данной грамматике. 5Трансляторы

Простой метаязык терминалы обозначим буквами a, b, c, d или цифрами 0, 1,..., 9; нетерминалы будем обозначать буквами A, B, C, D, S (причем нетерминал S - начальный символ грамматики); буквы U, V,..., Z используем для обозначения отдельных терминалов или нетерминалов; через,,... обозначим цепочки терминалов и нетерминалов; u, v, w, x, y, z - цепочки терминалов; для обозначения пустой цепочки (не содержащей ни одного символа) будем использовать знак ; знак будет отделять левую часть правила от правой и читаться как порождает или есть по определению. Например, A cd, читается как A порождает cd. 6Трансляторы

Метаязык - язык, предназначенный для описания другого языка Пример грамматики G1: G1 = ({A, S}, {0, 1}, P, S), где P: 1. S 0A1; 2. 0A 00A1; 3. A. 7Трансляторы

Выводимая цепочка грамматики G, не содержащая нетерминалов, называется терминальной цепочкой, порождаемой грамматикой G. Язык L(G), порождаемый грамматикой G, - это множество терминальных цепочек, порождаемых грамматикой G. 8Трансляторы

Введем отношение G непосредственного вывода на множестве (N T) *, которое будем записывать следующим образом: G. Данная запись читается: непосредственно выводима из для грамматики G = (N, T, P, S) и означает: если - цепочка из множества (N T) * и - правило из Р, то G. 9Трансляторы

Через G + обозначим транзитивное замыкание (нетривиальный вывод за один и более шагов). Тогда G + читается как: выводима из нетривиальным образом. Через G * обозначим рефлексивное и транзитивное замыкание (вывод за ноль и более шагов). Тогда G * означает: выводима из. Пусть k – k-я степень отношения То есть, если k, то существует последовательность k из k+1 цепочек = 0, 1,... i -1 i,1 i k и k =. 10Трансляторы

Пример выводов для грамматики G1 S 0A1 00A ; S 1 0A1; S 2 00A11; S ; S + 0A1; S + 00A11; S ; S * S; S * 0A1; S * 00A11; S * 0011; где 0011 L(G1). 11Трансляторы

Грамматики с ограничениями на правила В соответствии с классификацией Хомского грамматика G называется: праволинейной, если каждое правило из Р имеет вид: A xB или A x, где A, B - нетерминалы, x - цепочка, состоящая из терминалов; контекстно-свободной (КС) или бесконтекстной, если каждое правило из Р имеет вид: A, где A N, а (N T)*, то есть является цепочкой, состоящей из множества терминалов и нетерминалов, возможно пустой; контекстно-зависимой или неукорачивающей, если каждое правило из P имеет вид:, где То есть, вновь порождаемые цепочки не могут быть короче, чем исходные, а, значит, и пустыми (другие ограничения отсутствуют); грамматикой свободного вида, если в ней отсутствуют выше упомянутые ограничения. 12Трансляторы

Пример праволинейной грамматики: G2 = ({S,}, {0,1}, P, S), где P: 1. S 0S; 2. S 1S; 3. S, определяет язык {0, 1}*. Пример КС грамматики: G3 = ({E, T, F}, {a, +, *, (,)}, P, E) где P: 1. E T 2. E E + T 3. T F 4.T T * F 5. F (E) 6. F a. Данная грамматика порождает простейшие арифметические выражения 13Трансляторы

Пример КЗ грамматики: G4 = ({B, C, S}, {a, b, c}, P, S) где P: 1. S aSBC; 2. S abC; 3. CB BC; 4. bB bb; 5. bC bc; 6. cC сc, порождает язык {a n b n c n }, n 1. 14Трансляторы

Примечание 1. Согласно определению каждая праволинейная грамматика является контекстно свободной. Примечание 2. По определению КЗ грамматика не допускает правил: А ( - правила), т.е. КС грамматика с - правилами не является КЗ. Наличие - правил ведет к грамматике без ограничений. Соглашение. Если язык L порождается грамматикой типа G, то L называется языком типа G. Пример: L(G3) - КС язык типа G3. 15Трансляторы

Способы записи синтаксиса языка Метаязык Хомского вышел из недр математической логики. Он имеет следующую систему обозначений: символ отделяет левую часть правила от правой (читается как "порождает" и "это есть"); нетерминалы обозначаются буквой А с индексом, указывающим на его номер; терминалы - это символы используемые в описываемом языке; каждое правило определяет порождение одной новой цепочки, причем один и тот же нетерминал может встречаться в нескольких правилах слева. 16Трансляторы

Описание идентификатора на метаязыке Хомского 1. A 1 A 18. A 1 R 35. A 1 i 52. A 1 z 2. A 1 B 19. A 1 S 36. A 1 j 53. A A 1 C 20. A 1 T 37. A 1 k 54. A A 1 D 21. A 1 U 38. A 1 l 55. A A 1 E 22. A 1 V 39. A 1 m 56. A A 1 F 23. A 1 W 40. A 1 n 57. A A 1 G 24. A 1 X 41. A 1 o 58. A A 1 H 25. A 1 Y 42. A 1 p 59. A A 1 I 26. A 1 Z 43. A 1 q 60. A A 1 J 27. A 1 a 44. A 1 r 61. A A 1 K 28. A 1 b 45. A 1 s 62. A A 1 L 29. A 1 c 46. A 1 t 63. A 3 A A 1 M 30. A 1 d 47. A 1 u 64. A 3 A 3 A A 1 N 31. A 1 e 48. A 1 v 65. A 3 A 3 A A 1 O 32. A 1 f 49. A 1 w 16. A 1 P 33. A 1 g 50. A 1 x 17. A 1 Q 34. A 1 h 51. A 1 y 17Трансляторы

Метаязык Хомского-Щутценберже Более компактное описание с использованием обозначений: символ = отделяет левую часть правила от правой (вместо символа ); нетерминалы обозначаются буквой А с индексом, указывающим на его номер; терминалы - это символы используемые в описываемом языке; каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом +, что позволяет, при желании, использовать в левой части только разные нетерминалы. 18Трансляторы

Описание идентификатора на метаязыке Хомского-Щутценберже 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 = A 3 =A 1 +A 3 A 1 +A 3 A 2 19Трансляторы

Бэкуса-Наура формы (БНФ) символ "::=" отделяет левую часть правила от правой; нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки " "; терминалы - это символы используемые в описываемом языке; каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты "|". 20Трансляторы

Пример описания идентификатора с использованием БНФ: 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. ::= | | Правила можно задавать и раздельно: :: = :: = :: = 21Трансляторы

Расширенные Бэкуса-Наура формы (РБНФ) РБНФ, используемые Виртом, имеют следующие особенности: Квадратные скобки " [ " и " ] "" означают, что заключенная в них синтаксическая конструкция может отсутствовать; фигурные скобки " { " и " } " означают ее повторение (возможно, 0 раз); круглые скобки " ( " и " ) " используются для ограничения альтернативных конструкций; сочетание фигурных скобок и косой черты " {/ " и " /} " используется для обозначения повторения один и более раз. Нетерминальные символы изображаются словами, выражающими их интуитивный смысл и написанными на русском языке. 22Трансляторы

Синтаксис идентификатора с использованием РБНФ $ буква = "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". $ идентификатор = буква {буква | цифра}. 23Трансляторы

Диаграммы Вирта - терминальный символ, A begin блок принадлежащий алфавиту языка - постоянная группа терминальных символов, определяющая название лексемы, ключевое слово и т.д. - нетерминальный символ, определяющий название правила - соединительные линии, обеспечивающие связь между терминальными и нетерминальными символами в правилах, заданных диаграммами Вирта - входная дуга с именем правила, определяющая его начало Графические примитивы, используемые при построении диаграмм Вирта. 24Трансляторы

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

буква A B C D E F G H IJK L M N O P Q R S T U V W X Y Z abcdefghijklm nopqrs t uvw x yz цифра буква Идентификатор буква цифра Описание идентификатора с использованием диаграмм Вирта. 26Трансляторы

Распознаватели Распознаватель - это очень схематизированный алгоритм, определяющий некоторое множество. Его можно представить в виде устройства (автомата). Этот автомат состоит из трех частей: входной ленты, устройства управления с конечной памятью и вспомогательной (рабочей) памяти. 27Трансляторы

Правый Клетка (ячейка) Входная лента [a0 Левый концевой маркер (необязателен) концевой маркер (необязателен) a1a2an] Входной символ Входная головка Устройство управления с конечной памятью Вспомогательная (рабочая) память Обобщенная структура распознавателя 28Трансляторы

Входная лента - линейная последовательность клеток (ячеек), каждая из которых содержит один входной символ из конечного входного алфавита. Могут присутствовать левый и правый концевые маркеры, может присутствовать только один концевой маркер (левый или правый), могут отсутствовать оба маркера. Входная головка - в каждый момент читает одну входную ячейку. За один шаг входная головка может сдвинуться на одну ячейку влево, вправо и остаться неподвижной. Распознаватель, никогда не передвигающий входную головку влево, называется односторонним. Обычно предполагается, что входная головка только читает. Но могут быть и такие распознаватели, у которых входная головка читает и пишет. Память - хранит информацию, построенную только из символов конечного алфавита памяти. Может иметь различную структуру: очередь, стек (магазин) и т. д. Можно читать из вспомогательной памяти и писать в нее. Для стека и очереди используются специфические операции (вталкивание, выталкивание). Устройство управления с конечной памятью - программа, управляющая поведением распознавателя. Может являться аналогом конечного автомата. Определяет перемещение входной головки и работу с памятью на каждом шаге (такте). Переходит за шаг из одного состояния в другое. 29Трансляторы

Конфигурация распознавателя - мгновенный снимок, на котором изображены: 1. состояние устройства управления; 2. содержимое входной ленты; 3. содержимое памяти. Начальная конфигурация - устройство управления находится в заданном начальном состоянии, входная головка читает самый левый символ на входной ленте, память имеет заранее установленное начальное содержимое. Заключительная конфигурация - устройство управления находится в одном из состояний, принадлежащем заранее выделенному множеству заключительных состояний, входная головка обозревает правый концевой маркер или, если маркер отсутствует, сошла с конца входной ленты. Иногда требуется, чтобы заключительная конфигурация памяти удовлетворяла некоторым условиям. 30Трансляторы

Распознаватель допускает входную цепочку, если, начиная с начальной конфигурации, в которой цепочка записана на входной ленте, распознаватель может проделать последовательность шагов, заканчивающуюся заключительной конфигурацией. Язык, определяемый распознавателем - это множество цепочек, которые он допускает. 31Трансляторы

Для каждой из грамматик, приведенных выше в соответствии с иерархией Хомского, существуют распознаватели определяющие один и тот же класс языков. 1. Язык L праволинейный тогда и только тогда, когда он определяется конечным односторонним детерминированным автоматом. 2. Язык L контекстно-свободный тогда и только тогда, когда он определяется односторонним недетерминированным автоматом с магазинной памятью. 3. Язык L контекстно-зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным линейно ограниченным автоматом. 4. Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга. 32Трансляторы

Демонстрационный язык программирования Литература Дейкстра Э. Дисциплина программирования. М.: Мир, Грис Д. Наука программирования. М.: Мир, Трансляторы

Элементарные конструкции Представляют набор базовых понятий языка программирования Имея в своем распоряжении набор базовых кирпичиков, легче изучать более сложные понятия; В большинстве языков программирования смысл и представление элементарных конструкций совпадают, поэтому, поняв их в ходе изучения одного языка, легче перейти к следующему. 34Трансляторы

$ буква = "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}" {/ "0" | "1" /}. $ восьмиричное = "{8}"{/ "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7" /}. $ десятичное = ["{10}"] {/ цифра /}. $ шестнадцатиричное = "{16}" {/ цифра |"A"|"B"|"C"|"D"|"E"|"F"| "a"|"b"|"c"|"d"|"e"|"f" /}. 35Трансляторы

Синтаксис элементарных конструкций Использование РБНФ $ действительное = числовая_строка порядок | числовая_строка "." [числовая_строка] [порядок] | "." числовая_строка [порядок]. $ числовая_строка = {/ цифра /}. $ порядок = ("E"|"e")["+"|"-"] числовая_строка. $ пробельный_символ = {/ пробел | табуляция | перевод_строки | перевод_формата | комментарий /}. $ комментарий = "/*" { символ } "*/". $ строка = "" { символ | ""} "". 36Трансляторы

$ ключевое_слово = abort | begin | case | end | float | goto | int | loop | or | read | skip | space | tab | var | write |. $ разделитель = "(" | ")" | "[" | "]" | "," | ";" | ":" | ":=" | "*" | "/" | "%" |"+" | "-" | "->" |" " | " =" | "!=". 37Трансляторы

Элементарные конструкции. Использование ДВ буква 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 ab c d efg h ijk l m n o p q rstu v w x y z цифра Трансляторы

буква идентификатор буква цифра целое число действительное целое двоичное восьмиричное десятичное шестнадцатиричное 39Трансляторы

двоичное 0 { 2} 1 восьмиричное { 8} десятичное { 10} цифра шестнадцатиричное { 16} ab c d ef цифра A B C D E F 40Трансляторы

действительное числовая строка порядок числовая строка цифра Е + порядок цифра е - 41Трансляторы

Пробельный символ пробел табуляция перевод строки перевод формата комментарий символ комментарий /**/ символ строка 42Трансляторы

разделитель ( )[],;:%*/ +--> =!=:= ключевое слово abort goto space beginint tab caseloop var endread write floatskip or 43Трансляторы

Синтаксис составных конструкций Использование РБНФ $ программа = begin ( описание | оператор ) { ";" ( описание | оператор ) } end. $ описание = var идентификатор [ размер ] { "," идентификатор [ размер ] } ":" тип. $ тип = int | float. $ размер = целое. $ оператор = метка непомеченный. $ метка = идентификатор ":". $ непомеченный = присваивания | условный | цикла | пустой | ошибки | ввода | вывода | перехода. $ присваивания = переменная ":=" выражение | переменная "," присваивания "," выражение. 44Трансляторы

$ переменная = идентификатор [ "[" выражение "]" ]. $ выражение = [ "-" ] операнд { операция [ "-" ] операнд }. $ операнд = "(" выражение ")" | число | переменная. $ операция = "*" | "/" | "%" | "+" | "-" | " " | ">=" | "" оператор { ";" оператор }. $ пустой = skip |. $ прерывания = abort [строка]. $ ввода = read переменная { "," переменная }. $ вывода = write ( выражение | спецификатор | строка ) { "," ( выражение | спецификатор | строка ) }. $ перехода = goto идентификатор. $ спецификатор = ( space | tab | skip ) [ выражение ]. 45Трансляторы

Составные конструкции. Использование ДВ программа ; begin описание end оператор описание, var идентификатор [ размер ] : тип Тип int float размер целое 46Трансляторы

оператор метка непомеченный присваивания условный цикла ввода вывода пустой прерывания перехода 47Трансляторы

присваивания переменная := выражение переменная, присваивания, выражение переменная идентификатор [ выражение ] операция - операнд 48Трансляторы

операция * /% +- >=!= оператор 49Трансляторы

Оператор присваивания обеспечивает одновременное присваивание нескольким переменным, расположенным слева от знака ":=" значений предварительно вычисленных выражений, расположенных в правой части. Каждой переменной соответствует свое выражение. Присваивания начинаются только после вычисления всех выражений, результаты которых временно сохраняются. Это позволяет произвести обмен значений переменных с использованием только одного оператора присваивания: x, y := y, x В обычных языках программирования необходимо написать три отдельных оператора: t := x; x := y; y := t 50Трансляторы

Выражения задаются в традиционной инфиксной форме. Порядок выполнения операций определяется их приоритетом и скобками. В начале выполняются выражения в скобках. Наивысший приоритет имеет унарный минус "-", далее следуют мультипликативные операции "*", "/", "%" (вычисление остатка), затем аддитивные "+", "-" и, наконец операции отношения " ", " =", "!=". 51Трансляторы

пустой skip ошибки abort ввода read строка, переменная 52Трансляторы

вывода write спецфикатор tab space skip перехода goto, выражение спецификатор строка выражение идентификатор 53Трансляторы

Для представления пустой оператора Дейкстра намеренно использовал специальное ключевое слово skip (что мотивировал соответствующим текстом), хотя в большинстве языков программирования пустой оператор - это пустое место: $ пустой =. 54Трансляторы

Пример 1. Алгоритм Евклида (нахождение наибольшего общего делителя) begin var x, y: int;/* описание переменных */ read x, y;/* ввод операндов */ /* выполнять до равенства аргументов */ loop x != y -> case x > y -> x := x - y or y > x -> y := y - x end end; write x/* полученный НОД */ end 55Трансляторы

Пример 2. Одновременное нахождение наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК). Begin /* описание переменных */ var x, y, u, v: int; read x, y;/* ввод операндов */ u, v := y, x; /* выполнять до равенства аргументов */ loop x > y -> x, v := x - y, v + u or y > x -> y, u := y - x, u +v end; write НОД =, x;/* НОД */ write skip, НОК =, (u + v) / 2/* НОК */ end 56Трансляторы

Пример 3. Суммирование n элементов из входного потока. begin var a, i, s, n: int; i,s := 0,0; read n; loop i read a; s,i := s+a,i+1 end; write s end 57Трансляторы

Пример 4. Сортировка элементов вектора. begin var A[100], i, n: int; i := 0; read n; /* чтение числа элементов */ /* ввод вектора */ loop i read A[ i ]; i := i +1 end; i := 0; /* сортировка методом пузырька loop i case A[ i ] > A[ i+1 ] -> A[ i ],A[ i+1 ],i := A[ i + 1],A[ i ],0 or A[ i ] i := i + 1 end end; /* вывод вектора */ i := 0; loop i write A[ i ], skip; i := i + 1 end 58Трансляторы