Презентация Теория формальных языков и грамматик. (Глава 2) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Теория формальных языков и грамматик. (Глава 2) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 45 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Теория формальных языков и грамматик. (Глава 2)
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:45 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:588.75 kB
- Просмотров:169
- Скачиваний:1
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
![ГЛАВА Основы теории](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img0.jpg)
Содержание слайда: ГЛАВА 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 Дерево вывода
№3 слайд
![. . Цепочки символов.](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img2.jpg)
Содержание слайда: 2.1.1 Цепочки символов. Операции над ними
Цепочкой (строкой) называется последовательность символов записанных один за одним. α β γ ω
Цепочка – последовательность, в которую могут входить все допустимые символы (не обязательно несущие смысл). abc или call_me_1_02
Цепочки символов α и β равны (α = β) тогда и только тогда, когда имеют один и тот же состав символов, и одинаковое их количество и их порядок следования.
Количество символов в цепочке называется длиной цепочки. |α|
α=abc |α| = 3
α = β |α| = |β|
№4 слайд
![. . Цепочки символов.](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img3.jpg)
Содержание слайда: 2.1.1 Цепочки символов. Операции над ними
Если из цепочки единичной длины |α|=1 удаляется этот единственный символ, α по прежнему остается цепочкой, но длина ее равна 0. |α|=0
Цепочку нулевой длины будем обозначать ε.
|ε|=0
εd=dε
Если существует цепочка ω = αβ, то α – голова цепочки, β – хвост цепочки.
Причем α – правильная голова, если β – не пустая цепочка. |β| >0. β –правильный хвост, если α – не пустая цепочка. |α| > 0.
α = abc
, a, ab, abc – головы цепочки. , a, ab – правильные головы.
№5 слайд
![. . Цепочки символов.](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img4.jpg)
Содержание слайда: 2.1.1 Цепочки символов. Операции над ними
Если и - цепочки, то цепочка называется конкатенацией (или сцеплением) цепочек и .
= ab и = cd, = abcd.
= = .
Коммутативность конкатенации αβ≠ βα, ассоциативность α(βγ)= (αβ)γ
Обращением (или реверсом) цепочки называется цепочка, символы которой записаны в обратном порядке. R.
= abcdef, R = fedcba.
= R.
()R=RR
Итерация (повторение, степень) n-ой степенью цепочки (будем обозначать n) называется конкатенация n цепочек .
0 = ; n = n-1 = n-1.
n = , где n є N, n>=0.
№6 слайд
![. . Формальное определение](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img5.jpg)
Содержание слайда: 2.1.2 Формальное определение языка. Понятие языка
Язык – это заданный набор символов и правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных предложений.
Алфавит – набор допустимых символов языка. Алфавит – счетное, непустое множество символов.
Цепочка символов является цепочкой над алфавитом (V), если в нее входят только символы, принадлежащие алфавиту V.
Для любого алфавита V пустая цепочка может как являться, так и не являться цепочкой над этим алфавитом.
Если |V|=0 и V – множество, то оно называется пустым множеством и обозначается $.
| |=0
| {} |=1
№7 слайд
![. . Формальное определение](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img6.jpg)
Содержание слайда: 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 слайд
![. . Формальное определение](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img7.jpg)
Содержание слайда: 2.1.2 Формальное определение языка. Понятие языка
Языком L над алфавитом V называют некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V. L(V) ≤ V*
множество цепочек языка не обязано быть конечным
хотя каждая цепочка в языке обязана быть конечной длины, эта длина формально ничем не ограничена
Предложением языка называется цепочка символов, принадлежащая этому языку.
№9 слайд
![. . Формальное определение](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img8.jpg)
Содержание слайда: 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) {} .
№11 слайд
![. . Синтаксис и семантика](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img10.jpg)
Содержание слайда: 2.1.4 Синтаксис и семантика
Лексема – это языковая конструкция, которая состоит из элементов алфавита языка и не содержит других конструкций.
Синтакис – набор правил, определяющих допустимые конструкции языка. Синтаксис определяет форму языка.
Семантика – это раздел языка, определяющий значения предложений языка (определяющий содержание, смысл языка).
№13 слайд
![. . Понятие о грамматике](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img12.jpg)
Содержание слайда: 2.2.1 Понятие о грамматике языка
Грамматика – описание способов построения предложений некоторого языка.
Грамматика — один из основных подходов к описанию бесконечного формального языка конечными средствами.
Правило (продукция) – упорядоченная пара цепочек (α β ), которое записывается α -> β (α порождает β ).
L(G) – язык L, заданный грамматикой G.
№14 слайд
![. . Понятие о грамматике](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img13.jpg)
Содержание слайда: 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 слайд
![. . Формальное определение](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img14.jpg)
Содержание слайда: 2.2.2 Формальное определение грамматики
По определению Хомского формальная грамматика представляет собой четвёрку:
G={VT, VN, P, S}
VТ, T - множество терминальных символов языка,
VN, N – множество нетерминальных символов (или понятий языка или синтаксических единиц)
V = VN VT
VN VT =
Р – множество правил подстановки (продукций), имеющий вид α ->β, α є V+, β є V*.
Знак -> означает "непосредственно порождает "или "есть по определению".
S – аксиома грамматики или начальный символ грамматики. S є VN.
№18 слайд
![. . Метаязык Хомского - gt](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img17.jpg)
Содержание слайда: 2.3.1 Метаязык Хомского
-> символ отделяет левую часть правила от правой (читается как "порождает" и "это есть");
нетерминалы обозначаются буквой А с индексом, указывающим на его номер;
терминалы - это символы, используемые в описываемом языке;
Каждое правило определяет порождение одной новой цепочки, причём один и тот же нетерминал может встречаться в нескольких правилах слева.
№20 слайд
![. . Бэкуса-Наура формы БНФ](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img19.jpg)
Содержание слайда: 2.3.2 Бэкуса-Наура формы (БНФ)
символ "::=" отделяет левую часть правила от правой;
нетерминалы обозначаются произвольной символьной строкой, заключённой в угловые скобки "<" и ">";
терминалы – это символы, используемые в описываемом языке;
каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты “|”.
№22 слайд
![. . Бэкуса-Наура формы БНФ lt](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img21.jpg)
Содержание слайда: 2.3.2 Бэкуса-Наура формы (БНФ)
<предложение> ::= <фраза существительного> <фраза глагола> <фраза существительного>
< фраза существительного > ::= <прилагательное> <существительное> | <существительное>
<прилагательное> ::= БЛАТНОЙ| КОНКРЕТНЫЙ
<существительное> ::= ПАЦАН| БРАТАН| СИЛА
<фраза глагола> ::= <наречие> <глагол> | <глагол>
< наречие> ::= ЧИСТО | КОНКРЕТНО| ТИПА| ВНАТУРЕ
<глагол> ::= ГОНИШЬ | ЕСТЬ
№30 слайд
![. . Классификация грамматик](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img29.jpg)
Содержание слайда: 2.4.1 Классификация грамматик
Эта иерархия грамматик – включающая.
Грамматика 2 включает 3, но не наоборот.
Любая грамматика относится к типу 0.
Существуют такие УКС грамматики, которые не относятся к КЗ и неукорачивающим, а относятся к типу без ограничений.
Сложность грамматики обратно пропорциональна тому максимально возможному номеру типа к которому может быть отнесена грамматика.
№31 слайд
![. . Классификация языков](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img30.jpg)
Содержание слайда: 2.4.2 Классификация языков
Языки классифицируются в соответствие с типами грамматик с помощью которых они заданы. Поскольку один и тот же язык в общем случае может быть задан сколь угодным количеством грамматик, которые могут относится к разным типам, то для классификации языка всегда выбирается грамматика с максимальным классификационным типом.
№33 слайд
![. . Классификация языков](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img32.jpg)
Содержание слайда: 2.4.2 Классификация языков
Сложность языка убывает с возрастанием классификационного типа языка.
Тип 0. Язык с фразовой структурой (естественные языки).
Тип 1. Язык контекстно-зависимый.
В общем случае время на распознавание предложения этого языка экспоненциально зависит от длины входящей цепочки.
Тип 2. Контекстно-свободный язык.
Время распознавания предложений КС-языка полиномиально зависит от длины входящей цепочки.
Тип 3. Регулярные.
Время распознавания предложений языка линейно зависит от длины входящей цепочки.
№37 слайд
![. . Вывод. Цепочка вывода.](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img36.jpg)
Содержание слайда: 2.5.1 Вывод. Цепочка вывода.
Выводом называется процесс порождения предложений языка на основе правил, определяющих язык.
Цепочка (VT VN)* непосредственно выводима из цепочки (VT VN)+ в грамматике G = (VT, VN, P, S) (обозначим ), если = 12, = 12, где 1, 2, (VT VN)*, (VT VN)+ и правило вывода -> содержится в P.
№38 слайд
![. . Вывод. Цепочка вывода.](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img37.jpg)
Содержание слайда: 2.5.1 Вывод. Цепочка вывода.
Цепочка V* выводима из цепочки V+ в грамматике G = (VT, VN, P, S) (обозначим * ), если:
непосредственно выводима из ( )
существует такая цепочка , что непосредственно выводима из ( ), а выводима из ( * )
выводима из если непосредственно выводима из или если можно построить цепочку непосредственных выводов 0 1 ... n .
Такая последовательность непосредственно выводимых цепочек называется цепочкой вывода.
Каждый переход от одной цепочки к другой называется шагом вывода.
№39 слайд
![. . Вывод. Цепочка вывода.](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img38.jpg)
Содержание слайда: 2.5.1 Вывод. Цепочка вывода.
Если цепочка вывода от к содержит одну и более промежуточных цепочек, то такая цепочка обозначается + ( нетривиально выводима из ).
Если количество шагов вывода известно, то его можно указать непосредственно над знаком вывода.
Если , то один шаг вывода.
Если 4 , то выводима из за 4 шага.
Если 0 , то = .
№41 слайд
![. . Сентенциальная форма](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img40.jpg)
Содержание слайда: 2.5.2 Сентенциальная форма грамматики. Основа
Вывод называется законченным, если на основе цепочки , полученной в результате вывода нельзя сделать ни одного шага вывода, т.е. цепочка состоит из терминальных символов.
Цепочка , полученная в результате законченного вывода называется конечной цепочкой вывода.
Цепочка (VT VN)*, для которой S * (если выводима из начального символа грамматики), называется сентенциальной формой в грамматике G = (VT, VN, P, S).
Если є VT*, то называется конечной сентенциальной формой или предложением языка.
№42 слайд
![. . Сентенциальная форма](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img41.jpg)
Содержание слайда: 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 слайд
![. . Левосторонний и](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img42.jpg)
Содержание слайда: 2.5.3 Левосторонний и правосторонний вывод
Вывод цепочки (VT)* из S VN в КС-грамматике
G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.
Вывод цепочки (VT)* из S VN в КС-грамматике
G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.
№44 слайд
![. . Левосторонний и](/documents_6/3f7c8749b044d7de6da6ae9dc84ed394/img43.jpg)
Содержание слайда: 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 – не всегда.
Скачать все slide презентации Теория формальных языков и грамматик. (Глава 2) одним архивом:
Похожие презентации
-
Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3)
-
Требования на экзамене по курсу Теория формальных языков и трансляций
-
Элементы теории языков. Лекция 24
-
Генератор лексического анализатора и генератор синтаксического анализатора языков программирования. (Глава 6)
-
Генерация кода языков программирования. (Глава 5)
-
Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4)
-
Проектирование трансляторов языков программирования. Схема работы компилятора. (Глава 1)
-
Базовые типы данных языков программирования высокого уровня
-
Введение в теорию алгоритмов. Блок-схема алгоритма
-
Базовые типы данных языков программирования высокого уровня. Лекция 3