🗊Презентация Теория формальных языков и грамматик. (Глава 2)

ГЛАВА 2 Основы теории формальных языков и грамматик 2.1 Языки и цепочки символов. Способы задания языков 2.1.1 Цепочки символов. Операции над ними 2.1.2 Формальное определение языка. Понятие языка 2.1.3 Способы задания языка 2.1.4 Синтаксис и семантика 2.2 Определение грамматики 2.2.1 Понятие о грамматике языка 2.2.2 Формальное определение грамматики 2.3 Способы записи синтаксиса языка 2.3.1 Метаязык Хомского 2.3.2 Бэкуса-Наура формы (БНФ) 2.3.3 РБНФ (расширенная) 2.3.4 Диаграмма Вирта 2.4 Классификация языков и грамматик 2.4.1 Классификация грамматик 2.4.2 Классификация языков 2.4.3 Примеры классификации языков и грамматик 2.5 Цепочки вывода. Сентенциальная форма 2.5.1 Вывод. Цепочка вывода. 2.5.2 Сентенциальная форма грамматики. Основа 2.5.3 Левосторонний и правосторонний вывод 2.5.4 Дерево вывода

2.1 Языки и цепочки символов. Способы задания языков ГЛАВА 2. Основы теории формальных языков и грамматик

2.1.1 Цепочки символов. Операции над ними Цепочкой (строкой) называется последовательность символов записанных один за одним. α β γ ω Цепочка – последовательность, в которую могут входить все допустимые символы (не обязательно несущие смысл). abc или call_me_1_02 Цепочки символов α и β равны (α = β) тогда и только тогда, когда имеют один и тот же состав символов, и одинаковое их количество и их порядок следования. Количество символов в цепочке называется длиной цепочки. |α| α=abc |α| = 3 α = β |α| = |β|

2.1.1 Цепочки символов. Операции над ними Если из цепочки единичной длины |α|=1 удаляется этот единственный символ, α по прежнему остается цепочкой, но длина ее равна 0. |α|=0 Цепочку нулевой длины будем обозначать ε. |ε|=0 εd=dε Если существует цепочка ω = αβ, то α – голова цепочки, β – хвост цепочки. Причем α – правильная голова, если β – не пустая цепочка. |β| >0. β –правильный хвост, если α – не пустая цепочка. |α| > 0. α = abc , a, ab, abc – головы цепочки. , a, ab – правильные головы.

2.1.1 Цепочки символов. Операции над ними Если  и  - цепочки, то цепочка  называется конкатенацией (или сцеплением) цепочек  и .  = ab и  = cd,  = abcd.  =  = . Коммутативность конкатенации αβ≠ βα, ассоциативность α(βγ)= (αβ)γ Обращением (или реверсом) цепочки  называется цепочка, символы которой записаны в обратном порядке. R.  = abcdef, R = fedcba.  = R. ()R=RR Итерация (повторение, степень) n-ой степенью цепочки  (будем обозначать n) называется конкатенация n цепочек . 0 = ; n = n-1 = n-1. n = , где n є N, n>=0.

2.1.2 Формальное определение языка. Понятие языка Язык – это заданный набор символов и правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных предложений. Алфавит – набор допустимых символов языка. Алфавит – счетное, непустое множество символов. Цепочка символов  является цепочкой над алфавитом (V), если в нее входят только символы, принадлежащие алфавиту V. Для любого алфавита V пустая цепочка  может как являться, так и не являться цепочкой над этим алфавитом. Если |V|=0 и V – множество, то оно называется пустым множеством и обозначается $. |  |=0 | {} |=1

2.1.2 Формальное определение языка. Понятие языка V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку . V* - итерация множества V или транзитивное замыкание. V+ - множество всех цепочек длиной 1 и более, исключив тем самым цепочку . V+ - усечённая итерация множества V или усеченное транзитивное замыкание. V*=V+  {} V= {a,b,c} V* = {а, b, с, аа, bb, сс, aab, abc, abbc … } V+ = {а, b, с, аа, bb, сс, aab, abc, abbc …} Декартовым произведением A  B множеств A и B называется множество { α β | α  A, β  B}. Если A= {a,b} и B={c,d} , то A  B = {ac, ad, bc, bd}

2.1.2 Формальное определение языка. Понятие языка Языком L над алфавитом V называют некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V. L(V) ≤ V* множество цепочек языка не обязано быть конечным хотя каждая цепочка в языке обязана быть конечной длины, эта длина формально ничем не ограничена Предложением языка называется цепочка символов, принадлежащая этому языку.

2.1.2 Формальное определение языка. Понятие языка Язык L над алфавитом V включает в себя язык L’ над алфавитом V (L(V) ≤ L’(V)), если справедливо, что любая цепочка α принадлежащая L, принадлежит и L’. α є L(V) и α є L’(V) Два языка L(V) и L’(V) равны или совпадают если справедливо L(V) ≤ L’(V) и L’(V) ≤ L(V). Два языка L(V) и L’(V) почти эквиваленты, если они отличаются на пустую цепочку L(V) =~ L’(V). L(V)  {} = L’(V)  {} .

2.1.3 Способы задания языка перечисление всех допустимых цепочек языка с помощью указания способа порождения цепочек языка (задать грамматику языка, используемую для порождения языка) определение метода распознавания цепочек языка

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

2.2 Определение грамматики ГЛАВА 2. Основы теории формальных языков и грамматик

2.2.1 Понятие о грамматике языка Грамматика – описание способов построения предложений некоторого языка. Грамматика — один из основных подходов к описанию бесконечного формального языка конечными средствами. Правило (продукция) – упорядоченная пара цепочек (α β ), которое записывается α -> β (α порождает β ). L(G) – язык L, заданный грамматикой G.

2.2.1 Понятие о грамматике языка Грамматики 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)  {}. G1 = ({0,1}, {A,S}, P1, S) G2 = ({0,1}, {S}, P2, S) P1: S -> 0A1 P2: S -> 0S1 |  0A -> 00A1 A ->  L(G1)={0n1n | n>0} L(G2)={0n1n | n>=0}

2.2.2 Формальное определение грамматики По определению Хомского формальная грамматика представляет собой четвёрку: G={VT, VN, P, S} VТ, T - множество терминальных символов языка, VN, N – множество нетерминальных символов (или понятий языка или синтаксических единиц) V = VN  VT VN  VT =  Р – множество правил подстановки (продукций), имеющий вид α ->β, α є V+, β є V*. Знак -> означает "непосредственно порождает "или "есть по определению". S – аксиома грамматики или начальный символ грамматики. S є VN.

2.2.2 Формальное определение грамматики Грамматика, определяющая целое число без знака: G={VT,VN,P,S} VN = {A,B} VТ = {0,1,2,3,4,5,6,7,8,9} Р = {А ->ВА, А ->В, В ->0, В ->1, В->9} S = {A} А - целое число без знака, В - любая цифра.

2.3 Способы записи синтаксиса языка ГЛАВА 2. Основы теории формальных языков и грамматик

2.3.1 Метаязык Хомского -> символ отделяет левую часть правила от правой (читается как "порождает" и "это есть"); нетерминалы обозначаются буквой А с индексом, указывающим на его номер; терминалы - это символы, используемые в описываемом языке; Каждое правило определяет порождение одной новой цепочки, причём один и тот же нетерминал может встречаться в нескольких правилах слева.

2.3.1 Метаязык Хомского

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

2.3.2 Бэкуса-Наура формы (БНФ) 1. <буква> ::= A | B| C …| Z| а| b| c| …| z 2. <цифра> ::= 0| 1| 2 … |9 3. <идентификатор> ::= <буква> | <идентификатор><буква>| <идентификатор><цифра>

2.3.2 Бэкуса-Наура формы (БНФ) <предложение> ::= <фраза существительного> <фраза глагола> <фраза существительного> < фраза существительного > ::= <прилагательное> <существительное> | <существительное> <прилагательное> ::= БЛАТНОЙ| КОНКРЕТНЫЙ <существительное> ::= ПАЦАН| БРАТАН| СИЛА <фраза глагола> ::= <наречие> <глагол> | <глагол> < наречие> ::= ЧИСТО | КОНКРЕТНО| ТИПА| ВНАТУРЕ <глагол> ::= ГОНИШЬ | ЕСТЬ

2.3.3 РБНФ (расширенная) [ ] – синтаксическая конструкция может отсутствовать; { } – повторение синтаксической конструкции (возможно 0 раз) ( ) – для ограничения альтернативных конструкций {\ \} – для обозначения повторения один и более раз.

2.3.3 РБНФ <буква> ::= A | B| C …| Z| а| b| c| …| z <цифра> ::= 0| 1| 2 … |9 <идентификатор> ::= <буква> {<буква> | <цифра>}

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

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

2.4 Классификация языков и грамматик ГЛАВА 2. Основы теории формальных языков и грамматик

2.4.1 Классификация грамматик

2.4.1 Классификация грамматик

2.4.1 Классификация грамматик Эта иерархия грамматик – включающая. Грамматика 2 включает 3, но не наоборот. Любая грамматика относится к типу 0. Существуют такие УКС грамматики, которые не относятся к КЗ и неукорачивающим, а относятся к типу без ограничений. Сложность грамматики обратно пропорциональна тому максимально возможному номеру типа к которому может быть отнесена грамматика.

2.4.2 Классификация языков Языки классифицируются в соответствие с типами грамматик с помощью которых они заданы. Поскольку один и тот же язык в общем случае может быть задан сколь угодным количеством грамматик, которые могут относится к разным типам, то для классификации языка всегда выбирается грамматика с максимальным классификационным типом.

2.4.2 Классификация языков Грамматика 0 G1 = ({0,1}, {A,S}, P1, S) и P1: S -> 0A1 0A -> 00A1 A ->  КС-грамматика G2 = ({0,1}, {S}, P2, S), где P2: S -> 0S1 | 01 описывают один и тот же язык L = L(G1) = L(G2) = { 0n1n | n>0}

2.4.2 Классификация языков Сложность языка убывает с возрастанием классификационного типа языка. Тип 0. Язык с фразовой структурой (естественные языки). Тип 1. Язык контекстно-зависимый. В общем случае время на распознавание предложения этого языка экспоненциально зависит от длины входящей цепочки. Тип 2. Контекстно-свободный язык. Время распознавания предложений КС-языка полиномиально зависит от длины входящей цепочки. Тип 3. Регулярные. Время распознавания предложений языка линейно зависит от длины входящей цепочки.

2.4.3 Примеры классификации языков и грамматик Язык типа 2: L(G3) = {(ac)n (cb)n | n > 0} G3: S -> aQb | accb Q -> cSc Язык типа 3: L(G4) = {  |   {a,b}+, где нет двух рядом стоящих а} G4: S -> A | B A -> a | Ba B -> b | Bb | Ab

2.4.3 Примеры классификации языков и грамматик Язык типа 0: L(G1) = { | n >= 1} G1: S ->aaCFD F ->AFB | AB AB ->bBA Ab->bA AD ->D Cb->bC CB ->C bCD-> Язык типа 1: L(G2) = { anbncn, n >= 1} G2: S ->aSBC | abC CB ->BC bB->bb bC->bc cC->cc

2.5 Цепочки вывода. Сентенциальная форма ГЛАВА 2. Основы теории формальных языков и грамматик

2.5.1 Вывод. Цепочка вывода. Выводом называется процесс порождения предложений языка на основе правил, определяющих язык. Цепочка   (VT  VN)* непосредственно выводима из цепочки   (VT  VN)+ в грамматике G = (VT, VN, P, S) (обозначим   ), если  = 12,  = 12, где 1, 2,   (VT  VN)*,   (VT  VN)+ и правило вывода  ->  содержится в P.

2.5.1 Вывод. Цепочка вывода. Цепочка   V* выводима из цепочки   V+ в грамматике G = (VT, VN, P, S) (обозначим  * ), если:  непосредственно выводима из  (  ) существует такая цепочка , что  непосредственно выводима из  (  ), а  выводима из  ( * )  выводима из  если  непосредственно выводима из  или если можно построить цепочку непосредственных выводов   0  1  ...  n  . Такая последовательность непосредственно выводимых цепочек называется цепочкой вывода. Каждый переход от одной цепочки к другой называется шагом вывода.

2.5.1 Вывод. Цепочка вывода. Если цепочка вывода от  к  содержит одну и более промежуточных цепочек, то такая цепочка обозначается  +  ( нетривиально выводима из ). Если количество шагов вывода известно, то его можно указать непосредственно над знаком вывода. Если   , то один шаг вывода. Если  4 , то  выводима из  за 4 шага. Если  0 , то  = .

2.5.1 Вывод. Цепочка вывода. G=({A, S) {0, 1}, Р, S) P: S -> 0А1 0A -> 00А1 А ->  Приведем вывод для цепочки 0011 є L(G): S  0A1  00A11  0011; S + 0A1; S  + 00A11; S  + 0011; S * S; S m 0A1; S * 00A11; S 3 0011;

2.5.2 Сентенциальная форма грамматики. Основа Вывод называется законченным, если на основе цепочки , полученной в результате вывода нельзя сделать ни одного шага вывода, т.е. цепочка  состоит из терминальных символов. Цепочка , полученная в результате законченного вывода называется конечной цепочкой вывода. Цепочка   (VT  VN)*, для которой S *  (если  выводима из начального символа грамматики), называется сентенциальной формой в грамматике G = (VT, VN, P, S). Если  є VT*, то  называется конечной сентенциальной формой или предложением языка.

2.5.2 Сентенциальная форма грамматики. Основа Пусть G=(VN, VT, P, S) грамматика и цепочка w = 1  2 сентенциальная форма 1, 2 є V*,  є V+, тогда  называют фразой сентенциальной формы w для нетерминала B, если существуют выводы S  * 1 B 2, B + .  называется простой фразой, если существуют выводы S  * 1 B 2, B  . Основой всякой сентенциальной формы называется самая левая простая фраза. если 1 = , то В - голова. если 2 = , то В - хвост. Язык L заданный грамматикой G - это множество всех конечных сентенциальных форм грамматики G.

2.5.3 Левосторонний и правосторонний вывод Вывод цепочки   (VT)* из S  VN в КС-грамматике G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала. Вывод цепочки   (VT)* из S  VN в КС-грамматике G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

2.5.3 Левосторонний и правосторонний вывод Например, для цепочки a+b+a в грамматике G = ({a,b,+}, {S,T}, {S -> T | T+S; T -> a | b}, S) можно построить выводы: (1) S  T+S  T+T+S  T+T+T  a+T+T  a+b+T  a+b+a (2) S  T+S  a+S  a+T+S  a+b+S  a+b+T  a+b+a S  T+S  T+T+S  T+T+T  T+T+a  T+b+a  a+b+a Для грамматик типов 2,3 для любой сентенциальной формы можно построить левый и правый вывод. Для грамматик типов 0,1 – не всегда.

2.5.4 Дерево вывода