🗊Презентация Задача описания входного языка. (Лекция 2)

Лекция 02. Задача описания входного языка

Основной аппарат Формальные языки и грамматики математические модели, использующие представление текстов в виде цепочек символов

Замечания (1) Для описания языков программирования используются контекстно-свободные грамматики (КСГ). КСГ – мощный аппарат, но не может определить все возможные языки. Эффективны для описания вложенных структур, например, скобок и блоков в языках программирования.

Замечания (2) Основная идея заключается в использовании «переменных» для определения «множеств» цепочек символов. Эти переменные определены рекурсивно (с помощь рекурсивных «правил вывода»). Рекурсивные правила для переменной («продукции") включают в себя только конкатенацию. Альтернативные правила для переменной позволяют объединять цепочки.

Основные определения (1) Алфавит Определение: алфавит - это конечное множество символов. Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов. Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита. Определение: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ .

Основные определения (2) Операции над цепочками Определение: если a и b - цепочки, то цепочка ab называется конкатенацией (или сцеплением) цепочек a и b. Например, если a = ab и b = cd, то ab = abcd. Для любой цепочки a всегда a = a = a. Определение: обращением (или реверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке. Обращение цепочки a будем обозначать aR. Например, если a = abcdef, то aR = fedcba. Для пустой цепочки:  = R. Определение: n-ой степенью цепочки a (будем обозначать an) называется конкатенация n цепочек a. a0 = ; an = aan-1 = an-1a.  Определение: длина цепочки - это число составляющих ее символов.

Основные определения (3) Язык. Итерация Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите. Определение: обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку . Например, если V={0,1}, то V* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}. Определение: обозначим через V+ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку . Следовательно, V* = V+  {}. Определение: декартовым произведением A × B множеств A и B называется множество {(a,b) | a  A, b  B}.

Порождающая грамматика Определение: порождающая грамматика G - это четверка (VT, VN, P, S), где VT - алфавит терминальных символов (терминалов), VN - алфавит нетерминальных символов (нетерминалов, «переменных»), не пересекающийся с VT, P - конечное подмножество множества (VT  VN)+  (VT  VN)*; элемент (, ) множества P называется правилом вывода и записывается в виде   , S - начальный символ (цель, аксиома) грамматики, S  VN. Для записи правил вывода с одинаковыми левыми частями   1,    2, ...,    n будем пользоваться сокращенной записью    1 |  2 |...|  n. Каждое  i , i= 1, 2, ... ,n , будем называть альтернативой правила вывода из цепочки .

Порождающая грамматика Пример грамматики: G1 = ({0,1}, {A,S}, P, S), VT = {0,1} VN = {A,S} P состоит из правил S  0A1 0A  00A1 A  

Основные определения (4) Выводимость. Выводы Определение: цепочка   (VT  VN)* непосредственно выводима из цепочки   (VT  VN)+ в грамматике G = (VT, VN, P, S) (обозначим   ), если  = 12,  = 12, где 1, 2,   (VT  VN)*,   (VT  VN)+ и правило вывода    содержится в P. Например, цепочка 00A11 непосредственно выводима из 0A1 в G1.  Определение: цепочка   (VT  VN)* выводима из цепочки   (VT  VN)+ в грамматике G = (VT, VN, P, S) (обозначим   ), если существуют цепочки 0, 1, ... , n (n ≥ 0), такие, что  = 0  1  ...  n= .  Определение: последовательность 0, 1, ... , n называется выводом длины n. Например, S  000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S  0A1  00A11  000A111. Длина вывода равна 3.

Непосредственная выводимость Мы говорим, что A   (из A выводимо ), если A   правило грамматики. Пример: S  01; S  0S1. S  0S1  00S11  000111.

Выводимость  означает “выводится за ноль или более шагов” Базис:    для самой цепочки . Индукция: если    и   , то   .

Выводимость. Пример Пусть S  01; S  0S1 – правила грамматики. S  0S1  00S11  000111 – вывод в грамматике. Тогда S  S S  0S1 S  00S11 S  000111

Пример: CFG для { 0n1n | n > 1} Правила: S -> 01 S -> 0S1 Базис (основа): цепочка 01 принадлежит языку. Индукция: если w принадлежит языку, то и 0w1 принадлежит языку.

Основые определения (5) Язык. Сентенциальные формы Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G)={  VT* | S  }. Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P. Например, L(G1) = {0n1n | n>0}. Определение: цепочка a  (VT  VN)*, для которой S  , называется сентенциальной формой в грамматике G = (VT, VN, P, S). Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.

Основные определения (6) Эквивалентные грамматики Определение: грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2). Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где P1: S  0A1 P2: S  0S1 | 01 0A  00A1 A   эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0n1n | n>0}.   Определение: грамматики G1 и G2 почти эквивалентны, если L(G1)  {} = L(G2)  {}.

Классификация грамматик и языков по Хомскому ТИП 0: Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).   ТИП 1: Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид   , где   (VT  VN)+,   (VT  VN)+ и |  |  |  |.  Грамматика G = (VT, VN, P, S) называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид   , где  = 1A2;  = 12; A  VN;   (VT  VN)+; 1,2  (VT  VN)*.

Классификация грамматик и языков по Хомскому ТИП 2: Грамматика G = (VT, VN, P, S) называется контекстно-свободной (КС), если каждое правило из Р имеет вид A  , где A  VN,   (VT  VN)+. Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-свободной (УКС), если каждое правило из Р имеет вид A  , где A  VN,   (VT  VN)*.   ТИП 3: Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A  tB либо A  t, где A  VN, B  VN, t  VT. Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A  Bt либо A  t, где A  VN, B  VN, t  VT.

Соотношения между типами грамматик любая регулярная грамматика является КС-грамматикой; любая регулярная грамматика является УКС-грамматикой; любая КС-грамматика является КЗ-грамматикой; любая КС-грамматика является неукорачивающей грамматикой; любая КЗ-грамматика является грамматикой типа 0. любая неукорачивающая грамматика является грамматикой типа 0. Замечание: УКС-грамматика, содержащая правила вида A  , не является КЗ-грамматикой и не является неукорачивающей грамматикой

Соотношения между типами языков каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными (например, L = {anbn | n>0}). каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками (например, L = {anbncn | n>0}). каждый КЗ-язык является языком типа 0. Например, КЗ-грамматика G1 = ({0,1}, {A,S}, P1, S) и КС-грамматика G2 = ({0,1}, {S}, P2, S), где P1: S  0A1 P2: S  0S1 | 01 0A  00A1 A   описывают один и тот же язык L = L(G1) = L(G2) = { 0n1n | n>0}. Язык L будет КС-языком,

Пример. Язык типа 0: L = {a2 bn^2-1| n ≥ 1} P: S  aaCFD F  AFB | AB AB  bBA Ab  bA AD  D Cb  bC CB  C bCD  

Пример. Язык типа 1: L = {цепочки из 0 и 1 с одинаковым числом 0 и 1} P: S  ASB | AB AB  BA A  0 B  1

Пример. Язык типа 2: L = {(ac)n (cb)n | n > 0} P: S  aQb | accb Q  cSc

Пример. Язык типа 3: L = {  |   {a,b}+, где нет двух рядом стоящих а} P: S  A | B A  a | Ba B  b | Bb | Ab

Следующая тема: «Проблема грамматического разбора. Распознаватели»