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

Содержание

Слайд 2

2.1 ЯЗЫКИ И ЦЕПОЧКИ СИМВОЛОВ. СПОСОБЫ ЗАДАНИЯ ЯЗЫКОВ ГЛАВА 2. Основы теории формальных языков и грамматик

2.1 ЯЗЫКИ И ЦЕПОЧКИ СИМВОЛОВ. СПОСОБЫ ЗАДАНИЯ ЯЗЫКОВ

ГЛАВА 2. Основы теории

формальных языков и грамматик
Слайд 3

2.1.1 Цепочки символов. Операции над ними Цепочкой (строкой) называется последовательность символов

2.1.1 Цепочки символов. Операции над ними

Цепочкой (строкой) называется последовательность символов записанных

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

2.1.1 Цепочки символов. Операции над ними Если из цепочки единичной длины

2.1.1 Цепочки символов. Операции над ними

Если из цепочки единичной длины |α|=1

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

2.1.1 Цепочки символов. Операции над ними Если α и β -

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.
Слайд 6

2.1.2 Формальное определение языка. Понятие языка Язык – это заданный набор

2.1.2 Формальное определение языка. Понятие языка

Язык – это заданный набор символов

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

2.1.2 Формальное определение языка. Понятие языка V* множество, содержащее все цепочки

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}
Слайд 8

2.1.2 Формальное определение языка. Понятие языка Языком L над алфавитом V

2.1.2 Формальное определение языка. Понятие языка

Языком L над алфавитом V называют

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

2.1.2 Формальное определение языка. Понятие языка Язык L над алфавитом 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) ∪ {ε} .
Слайд 10

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

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

перечисление всех допустимых цепочек языка
с помощью указания способа

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

2.1.4 Синтаксис и семантика Лексема – это языковая конструкция, которая состоит

2.1.4 Синтаксис и семантика

Лексема – это языковая конструкция, которая состоит из

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

2.2 ОПРЕДЕЛЕНИЕ ГРАММАТИКИ ГЛАВА 2. Основы теории формальных языков и грамматик

2.2 ОПРЕДЕЛЕНИЕ ГРАММАТИКИ

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

Слайд 13

2.2.1 Понятие о грамматике языка Грамматика – описание способов построения предложений

2.2.1 Понятие о грамматике языка

Грамматика – описание способов построения предложений некоторого

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

2.2.1 Понятие о грамматике языка Грамматики G1 и G2 называются эквивалентными,

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}
Слайд 15

2.2.2 Формальное определение грамматики По определению Хомского формальная грамматика представляет собой

2.2.2 Формальное определение грамматики

По определению Хомского формальная грамматика представляет собой четвёрку:
G={VT,

VN, P, S}
VТ, T - множество терминальных символов языка,
VN, N – множество нетерминальных символов (или понятий языка или синтаксических единиц)
V = VN ∪ VT
VN ∩ VT = ∅
Р – множество правил подстановки (продукций), имеющий вид α ->β, α є V+, β є V*.
Знак -> означает "непосредственно порождает "или "есть по определению".
S – аксиома грамматики или начальный символ грамматики. S є VN.
Слайд 16

2.2.2 Формальное определение грамматики Грамматика, определяющая целое число без знака: G={VT,VN,P,S}

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}
А - целое число без знака, В - любая цифра.
Слайд 17

2.3 СПОСОБЫ ЗАПИСИ СИНТАКСИСА ЯЗЫКА ГЛАВА 2. Основы теории формальных языков

2.3 СПОСОБЫ ЗАПИСИ СИНТАКСИСА ЯЗЫКА

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

грамматик

Метаязык - язык, предназначенный для описания другого языка

Слайд 18

2.3.1 Метаязык Хомского -> символ отделяет левую часть правила от правой

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

-> символ отделяет левую часть правила от правой (читается

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

2.3.1 Метаязык Хомского Описание идентификатора на метаязыке Хомского

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

Описание идентификатора на метаязыке Хомского

Слайд 20

2.3.2 Бэкуса-Наура формы (БНФ) символ "::=" отделяет левую часть правила от

2.3.2 Бэкуса-Наура формы (БНФ)

символ "::=" отделяет левую часть правила от правой;
нетерминалы

обозначаются произвольной символьной строкой, заключённой в угловые скобки "<" и ">";
терминалы – это символы, используемые в описываемом языке;
каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты “|”.
Слайд 21

2.3.2 Бэкуса-Наура формы (БНФ) 1. ::= A | B| C …|

2.3.2 Бэкуса-Наура формы (БНФ)

1. <буква> ::= A | B| C …|

Z| а| b| c| …| z
2. <цифра> ::= 0| 1| 2 … |9
3. <идентификатор> ::= <буква> | <идентификатор><буква>| <идентификатор><цифра>

Пример описания идентификатора с использованием БНФ

Слайд 22

2.3.2 Бэкуса-Наура формы (БНФ) ::= ::= | ::= БЛАТНОЙ| КОНКРЕТНЫЙ ::=

2.3.2 Бэкуса-Наура формы (БНФ)

<предложение> ::= <фраза существительного> <фраза глагола> <фраза существительного>


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

Упрощенная грамматика русского языка в терминах БНФ

Слайд 23

2.3.3 РБНФ (расширенная) [ ] – синтаксическая конструкция может отсутствовать; {

2.3.3 РБНФ (расширенная)

[ ] – синтаксическая конструкция может отсутствовать;
{ } –

повторение синтаксической конструкции (возможно 0 раз)
( ) – для ограничения альтернативных конструкций
{\ \} – для обозначения повторения один и более раз.
Слайд 24

2.3.3 РБНФ ::= A | B| C …| Z| а| b|

2.3.3 РБНФ

<буква> ::= A | B| C …| Z| а| b|

c| …| z
<цифра> ::= 0| 1| 2 … |9
<идентификатор> ::= <буква> {<буква> | <цифра>}

Пример описания идентификатора с использованием РБНФ

Слайд 25

2.3.4 Диаграмма Вирта терминальный символ, принадлежащий алфавиту языка постоянная группа терминальных

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

терминальный символ, принадлежащий алфавиту языка

постоянная группа терминальных символов, определяющая

название лексемы, ключевое слово и т.д.

нетерминальный символ определяющий название правила

соединительные линии, обеспечивающие связь между терминальными и нетерминальными символами в правилах, заданных диаграммами Вирта

входная дуга с именем правила, определяющая его начало

Слайд 26

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

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

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

Слайд 27

2.4 КЛАССИФИКАЦИЯ ЯЗЫКОВ И ГРАММАТИК ГЛАВА 2. Основы теории формальных языков и грамматик

2.4 КЛАССИФИКАЦИЯ ЯЗЫКОВ И ГРАММАТИК

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

грамматик
Слайд 28

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

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

Слайд 29

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

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

Слайд 30

2.4.1 Классификация грамматик Эта иерархия грамматик – включающая. Грамматика 2 включает

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

Эта иерархия грамматик – включающая.
Грамматика 2 включает 3, но

не наоборот.
Любая грамматика относится к типу 0.
Существуют такие УКС грамматики, которые не относятся к КЗ и неукорачивающим, а относятся к типу без ограничений.
Сложность грамматики обратно пропорциональна тому максимально возможному номеру типа к которому может быть отнесена грамматика.
Слайд 31

2.4.2 Классификация языков Языки классифицируются в соответствие с типами грамматик с

2.4.2 Классификация языков

Языки классифицируются в соответствие с типами грамматик с помощью

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

2.4.2 Классификация языков Грамматика 0 G1 = ({0,1}, {A,S}, P1, S)

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}
Слайд 33

2.4.2 Классификация языков Сложность языка убывает с возрастанием классификационного типа языка.

2.4.2 Классификация языков

Сложность языка убывает с возрастанием классификационного типа языка.
Тип 0.

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

2.4.3 Примеры классификации языков и грамматик Язык типа 2: L(G3) =

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
Слайд 35

2.4.3 Примеры классификации языков и грамматик

2.4.3 Примеры классификации языков и грамматик

 

Слайд 36

2.5 ЦЕПОЧКИ ВЫВОДА. СЕНТЕНЦИАЛЬНАЯ ФОРМА ГЛАВА 2. Основы теории формальных языков и грамматик

2.5 ЦЕПОЧКИ ВЫВОДА. СЕНТЕНЦИАЛЬНАЯ ФОРМА

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

грамматик
Слайд 37

2.5.1 Вывод. Цепочка вывода. Выводом называется процесс порождения предложений языка на

2.5.1 Вывод. Цепочка вывода.

Выводом называется процесс порождения предложений языка на основе

правил, определяющих язык.
Цепочка β ∈ (VT ∪ VN)* непосредственно выводима из цепочки α ∈ (VT ∪ VN)+ в грамматике G = (VT, VN, P, S) (обозначим α ⇒ β), если α = ξ1γξ2, β = ξ1δξ2, где ξ1, ξ2, δ ∈ (VT ∪ VN)*, γ ∈ (VT ∪ VN)+ и правило вывода γ -> δ содержится в P.
Слайд 38

2.5.1 Вывод. Цепочка вывода. Цепочка β ∈ V* выводима из цепочки

2.5.1 Вывод. Цепочка вывода.

Цепочка β ∈ V* выводима из цепочки α

∈ V+ в грамматике G = (VT, VN, P, S) (обозначим α ⇒* β), если:
β непосредственно выводима из α (α ⇒ β)
существует такая цепочка γ, что β непосредственно выводима из γ (γ ⇒ β), а γ выводима из α (α ⇒* γ)
β выводима из α если β непосредственно выводима из α или если можно построить цепочку непосредственных выводов α ⇒ γ0 ⇒ γ1 ⇒ ... ⇒ γn ⇒ β.
Такая последовательность непосредственно выводимых цепочек называется цепочкой вывода.
Каждый переход от одной цепочки к другой называется шагом вывода.
Слайд 39

2.5.1 Вывод. Цепочка вывода. Если цепочка вывода от α к β

2.5.1 Вывод. Цепочка вывода.

Если цепочка вывода от α к β содержит

одну и более промежуточных цепочек, то такая цепочка обозначается α ⇒+ β (β нетривиально выводима из α).
Если количество шагов вывода известно, то его можно указать непосредственно над знаком вывода.
Если α ⇒ β, то один шаг вывода.
Если α ⇒4 β, то β выводима из α за 4 шага.
Если α ⇒0 β, то α = β.
Слайд 40

2.5.1 Вывод. Цепочка вывода. G=({A, S) {0, 1}, Р, S) P:

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;
Слайд 41

2.5.2 Сентенциальная форма грамматики. Основа Вывод называется законченным, если на основе

2.5.2 Сентенциальная форма грамматики. Основа

Вывод называется законченным, если на основе цепочки

β, полученной в результате вывода нельзя сделать ни одного шага вывода, т.е. цепочка β состоит из терминальных символов.
Цепочка β, полученная в результате законченного вывода называется конечной цепочкой вывода.
Цепочка α ∈ (VT ∪ VN)*, для которой S ⇒* α (если α выводима из начального символа грамматики), называется сентенциальной формой в грамматике G = (VT, VN, P, S).
Если α є VT*, то α называется конечной сентенциальной формой или предложением языка.
Слайд 42

2.5.2 Сентенциальная форма грамматики. Основа Пусть G=(VN, VT, P, S) грамматика

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.
Слайд 43

2.5.3 Левосторонний и правосторонний вывод Вывод цепочки β ∈ (VT)* из

2.5.3 Левосторонний и правосторонний вывод

Вывод цепочки β ∈ (VT)* из S

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

2.5.3 Левосторонний и правосторонний вывод Например, для цепочки a+b+a в грамматике

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 – не всегда.
- Предыдущая
Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4)
Следующая -
Проектирование трансляторов языков программирования. Схема работы компилятора. (Глава 1)

Похожие презентации

P9X79 Series Confidential
Электрооборудование. Электроснабжение бортовой сети
Бережливое производство в практике российских предприятий Бизнес-форум 28.02.2012. Пермь Ведущий: А.Б.Семенцов
Статистические свойства системы
«Поведение потребителей автомобилей» Бондарева Лидия Гавриш Кристина Житкова Екатерина Пономарева Виктория
Биография Д.И. Менделеева в датах
Тестирование и отладка программного обеспечения. Нормативно-правовая база
1. К участковому стоматологу обратилась бабушка ребенка 2 мес. с незарощением верхней губы. 1. К участковому стоматологу обратил
Передачи. Ременные, цепные, фрикционные передачи
Жанна д’Арк Национальная героиня Франции
Миграция и религия
ЕИТКС МВД России. Интегрированный банк данных «ИБД-Регион»
Патристика IV - VIII веков. Греческая патристика
Млечный путь
Лекция 5. Тип Круглые черви Nemathelminthes – паразиты человека и животных.
Традиции народа Африки. "Бушмены"
Операции и выражения. Операторы
Государство как универсальный политический институт Кучеров Илья Колосков Игорь
Государственная политика в сфере физической культуры и спорта в условиях становления социального государства
Понятие «физическая готовность» в структуре общей готовности человека к профессиональной деятельности
Презентация Пряжа и нити текстильные
Роль религии в жизни общества
Необычные материалы для скульптуры Выполнила студентка 3Б группы Зубкова Д.А.
Гимнастические залы и площадки
Рождение ислама
Гигиена труда в механических цехах
Презентация Анализ форм занятости населения, видов трудоустройства
Україна – це моя Батьківщина
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть