![]() |
![]() |
![]() |
Анимация
JavaScript
|
Главная Библионтека ГРАММАТИКИ Начнем с терминологии. Фигурные скобки используются для обозначения множеств, например {U 2, 3} обозначает множество, содержащее целые числа 1, 2 и 3. Объединение (U) и пересечение () множеств определяются как обьшно: {Г, 2, 3}U {3, 4, 5} = {1. 2, 3, 4. 5), П, 2. 3}П{3,4. 5Н{3}. Мы говорим, что множество A включает () множество S, если каждый элемент В является элементом Л, например {3. 4. 5} э {3). Аналогично множество В включается () в множество А, если каждый элемент В имеется также и в А: 3} £ {3, 4, 5}. Мы употребляем символ s, чтобы показать, что элемент содержится в множестве, например 3 е {3. 4. 5}. Пустое множество обозначается посредством 0. Поэтому Если А есть множество и мы определяем В как то В будет множеством {1, 2} П {3, 4, 5}=0. {2. 4, 9, 8} В~{х\х А и X есть четное число). {2, 4. 8}. В задается с помощью предиката, в данном случае это «х с А и x есть четное число». Мы определяем алфавит (или словарный состав) как множество символов. Например, им может быть латинский или греческий алфавит либо десятичные цифры О - 9. Представим алфавит Д={0..1. 2, 3. 4. 5. б. 7. 8, 9}. Если А есть алфавит, А* (замыкание A) используется для обозначения множества всех строк (включая пустую строку, состоящую из нулей), составленных* из символов, входящих в А. А + обозначает множество всех строк (исключая пустую строку), состоящих из символов, входящих в А. Пустая строка обычно обозначается с помощью s . Синтаксис языка можно специфицировать, пользуясь системой изображения множеств, например Иными словами, этот язык включает строки, состоящие из нуля или нулей и того же числа последующих единиц. Пустая строка включается в язык. Таким же образом можно специфицировать следующие синтаксисы: 1. {a-&Vjn>0): 2. (а™*»"! m, «>0Ь т.е. число а с последующим числом (не обязательно тем же самым) Ь, например будет принадлежать этому языку; 3. {х"\т - простое число); 4. {a"ftVm = n или п=р}. все эти синтаксисы намного проще синтаксисов большинства языков программирования; синтаксис же языка программирования лучше специфицировать с помощью грамматики. Грамматика состоит (частично) из набора правил для получения предложений языка. Возьмем, например, синтаксис, определенный ранее в этом, разделе, и воспользуемся следующими правилами: 1. S-OSl. 2. 5€, Чтобы вывести предложение этого языка, поступим следующим образом. Начнем с символа S и заменим его на 0S1 или s. Если S опять появится в полученной строке, его опять можно заменить с помощью одного из этих правил, и т. д. Полученная таким образом любая строка, не содержащая S, является предложением этого языка. Например, Последовательность указаннтх шагов называется выводом строки 000111, а символ = служит, для разделения шагов вывода. Все предложения данного языка можно вывести, руководствуясь приведенными выше двумя правилами, и любая строка, которую нельзя вывести с их помощью, не является предложением этого языка. Грамматику часто (и справедливо) называют системой перезаписи. Определим теперь грамматику более формально. Грамматика определяется как четверка просто iVj,V, Р, S), где Vт-алфавит, символы которого называются терминальными (или терминалами); VN- алфавит, символы которого называются X J. у - А. X нетерминальными (или нетерминалами), и у Vт, и VN нет общих символов, т. е. V определяется как Vт и VN Р есть набор порождающих правил, каждый элемент которых состоит из пары (а, в), где а находится в V+, a в в V*. а обычно известна как левая часть правила, а в - как правая, и правило записывается следующим образом: SeVN и называется начальным символом (или аксиомой). Этот символ является отправной точкой в получении любого предложения языка. Грамматикой, генерирующей язык является Go, где грамматика, генерирующая строки в наборе имеет вид Здесь элементами р будут ![]() Начав с символа S и применяя последовательно по одному из правил замены не терминала в выводимой строке, мы можем генерировать строку aaabb: Каждая строка, которую можно вывести из начального символа (например, аАВ, аааВ), называется сентенциальной формой. Предложение есть сентенциальная форма, содержащая только терминальные символ означает, что строку (символов) 5 можно вывести из строки у, однократно или неоднократно применяя правила грамматики G. (G можно опустить, если ясно, какая грамматика предполагается). Из изложенного видно, что аАВ аааЬВ. Аналогичным образом ![]() означает, что строку 5 можно вывести из строки у с помощью нуля или более приложений правил грамматики G. (G также можно опустить при соответствующих обстоятельствах.) Например, ![]() Там, где правило используется точно один раз, применяется символ =>, например или, если опускается Gj, АВ аАВ АВаАВ. ![]() ![]() 0 1 2 3 4 5 [ 6 ] 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
![]() |