Грамота
<<  Теория формальных языков и грамматик Псковская судная грамота  >>
Классификация грамматик и языков (классификация Хомского)
Классификация грамматик и языков (классификация Хомского)
Тип 0: грамматики с фразовой структурой
Тип 0: грамматики с фразовой структурой
Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики
Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики
Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики
Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики
Неукорачивающиеся грамматики
Неукорачивающиеся грамматики
Тип 2: контекстно-свободные (КС) грамматики
Тип 2: контекстно-свободные (КС) грамматики
Тип 3: регулярные грамматики (2 класса – леволинейные и праволинейные)
Тип 3: регулярные грамматики (2 класса – леволинейные и праволинейные)
Иерархия грамматик (по Хомскому)
Иерархия грамматик (по Хомскому)
Классификация языков
Классификация языков
Пример
Пример
Пример
Пример
Пример регулярной грамматики
Пример регулярной грамматики
Пример регулярной грамматики
Пример регулярной грамматики
Пример контекстно-свободной грамматики
Пример контекстно-свободной грамматики
Пример контекстно-зависимой грамматики
Пример контекстно-зависимой грамматики
Грамматика без ограничений
Грамматика без ограничений
Цепочки вывода
Цепочки вывода
Цепочки вывода
Цепочки вывода
Цепочки вывода
Цепочки вывода
Пример1
Пример1
Пример2 вывода предложения aaaabbbbcccc для грамматики G языка
Пример2 вывода предложения aaaabbbbcccc для грамматики G языка
Законченная цепочка вывода
Законченная цепочка вывода
Сентенциальная форма грамматики
Сентенциальная форма грамматики
Левосторонний и правосторонний выводы
Левосторонний и правосторонний выводы
Левосторонний и правосторонний выводы
Левосторонний и правосторонний выводы
Пример2
Пример2
Цепочки вывода
Цепочки вывода
Дерево вывода
Дерево вывода
Классификация грамматик и языков (классификация Хомского)
Классификация грамматик и языков (классификация Хомского)
Построение дерева сверху вниз
Построение дерева сверху вниз
Построение дерева снизу вверх
Построение дерева снизу вверх
Построение дерева
Построение дерева
Дерево вывода
Дерево вывода
Дерево вывода
Дерево вывода
Дерево вывода
Дерево вывода
Дерево вывода
Дерево вывода
КС- -грамматики
КС- -грамматики

Презентация на тему: «Классификация грамматик и языков (классификация Хомского)». Автор: Татьяна_2. Файл: «Классификация грамматик и языков (классификация Хомского).ppt». Размер zip-архива: 433 КБ.

Классификация грамматик и языков (классификация Хомского)

содержание презентации «Классификация грамматик и языков (классификация Хомского).ppt»
СлайдТекст
1 Классификация грамматик и языков (классификация Хомского)

Классификация грамматик и языков (классификация Хомского)

Рейн Т.С.

2 Тип 0: грамматики с фразовой структурой

Тип 0: грамматики с фразовой структурой

На структуру их правил не накладывается никаких ограничений: для грамматики вида G (VT, VN, P, S), V = VN U VT, правила имеют вид ? ? ?, где ? из V+, ? из V*. Это самый общий тип грамматик. Грамматики, которые относятся только к типу 0 и не могут быть отнесены к другим типам, являются самыми сложными по структуре. Практического применения грамматики, относящиеся только к типу 0, не имеют.

3 Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики

Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики

В этот тип входят два основных класса грамматик: Цепочки ?1 и ?2 в правилах грамматики обозначают контекст (?1 – левый контекст, ?2 – правый контекст), в общем случае любая из них (или даже обе) может быть пустой.

4 Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики

Тип 1: контекстно-зависимые (КЗ) и неукорачивающие грамматики

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

5 Неукорачивающиеся грамматики

Неукорачивающиеся грамматики

Неукорачивающие грамматики имеют такую структуру правил, что при построении предложений языка, заданного грамматикой, любая цепочка символов может быть заменена на цепочку символов не меньшей длины. Отсюда и название неукорачивающие. Доказано, что эти два класса грамматик эквивалентны. Для любого языка, заданного КЗ-грамматикой, можно построить неукорачивающую грамматику, которая будет задавать эквивалентный язык Для любого языка, заданного неукорачивающей грамматикой, можно построить КЗ-грамматику, которая будет задавать эквивалентный язык.

6 Тип 2: контекстно-свободные (КС) грамматики

Тип 2: контекстно-свободные (КС) грамматики

Неукорачивающие контекстно-свободные (НКС) грамматики G (VT, VN, P, S), V = VN U VT, имеют правила вида А ? ?, где А из VN, ? из V+. Такие грамматики называют НКС-грамматиками, поскольку видно, что в правой части правил у них должен всегда стоять как минимум один символ. Существует также почти эквивалентный им класс грамматик – укорачивающие контекстно-свободные (УКС) грамматики G (VT, N, P, S), V = VN U VT, правила которых могут иметь вид: А ? ?, где А из VN, ? из V*. Эти два класса составляют тип контекстно-свободных грамматик.

7 Тип 3: регулярные грамматики (2 класса – леволинейные и праволинейные)

Тип 3: регулярные грамматики (2 класса – леволинейные и праволинейные)

Леволинейные грамматики G (VT, VN, P, S), V = VN U VT, могут иметь правила двух видов: А ? B? или А ? ?, где А, В из VN, ? из VT*. Праволинейные грамматики G (VT, VN, P, S), V = VN U VT, могут иметь правила тоже двух видов: А ? ?В или А ? ?, где А, В из VN, ? из VT*.

8 Иерархия грамматик (по Хомскому)

Иерархия грамматик (по Хомскому)

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

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

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

10 Пример

Пример

Если язык L может быть задан грамматиками G1 и G2, относящимися к типу 1 (КЗ), грамматикой G3, относящейся к типу 2 (КС), и грамматикой G4, относящейся к типу 3 (регулярные), сам язык должен быть отнесён к типу 3 и является регулярным языком.

11 Пример

Пример

Грамматика типа 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) = {0^n 1^n | n > 0} Язык L называют КС-языком, т.к. существует КС-рамматика, его описывающая. Но он не является регулярным языком, т.к. не существует регулярной грамматики, описывающей этот язык.

12 Пример регулярной грамматики

Пример регулярной грамматики

Грамматика S ? aS | a является праволинейной (неукорачивающей) грамматикой. Она порождает регулярный язык {a^n | n> 0}. Этот язык может быть порожден и леволинейной грамматикой: S ? Sa | a.

13 Пример регулярной грамматики

Пример регулярной грамматики

S ? aS | ? является праволинейной и порождает регулярный язык {a^n | n >= 0}. Для любого регулярного языка существует неукорачивающая регулярная грамматика. Неукорачивающаяся регулярная грамматика для данного языка: S

14 Пример контекстно-свободной грамматики

Пример контекстно-свободной грамматики

является контекстно-свободной (неукорачивающей) и порождает КС-язык {(ac)^n (cb)^n | n > 0}, который, как язык {a^n b^n | n >0}, не является регулярным, т. е. не может быть порожден ни одной регулярной грамматикой.

15 Пример контекстно-зависимой грамматики

Пример контекстно-зависимой грамматики

Неукорачивающая порождает язык , который является языком типа 1, но не является языком типа {a^n b^n c^n, n>0}

16 Грамматика без ограничений

Грамматика без ограничений

В грамматике типа 0 S ? SS SS ? ? второе правило не удовлетворяет ограничениям неукорачивающей грамматики. Существует бесконечно много выводов в данной грамматике, однако порождаемый язык конечен и состоит из единственной цепочки: {?}.

17 Цепочки вывода

Цепочки вывода

Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматики. Цепочка ? = ?1 ? ?2 называется непосредственно выводимой из цепочки ? = ?1 ? ?2 в грамматике G (VT, VN, P, S), V = VN U VT; ?1, ?, ?2 из V*, ? из V+, если в грамматике существует правило ?? ?.

18 Цепочки вывода

Цепочки вывода

Иными словами, цепочка ? выводима из цепочки ? в том случае, если можно взять несколько символов в цепочке ?, поменять их на другие символы, согласно некоторому правилу грамматики, и получить цепочку ?. Непосредственная выводимость цепочки ? из цепочки ? обозначается как: ? ?.

19 Цепочки вывода

Цепочки вывода

Цепочка ? называется выводимой из цепочки ? (? * ?) в случае, если выполняется одно из двух условий: ? непосредственно выводима из ? (? ?); существует ? такая, что ? выводима из ?, и ? непосредственно выводима из ? (? ?, ? ?).

20 Пример1

Пример1

Грамматика для языка целых десятичных чисел со знаком

21 Пример2 вывода предложения aaaabbbbcccc для грамматики G языка

Пример2 вывода предложения aaaabbbbcccc для грамматики G языка

Задана грамматика G ({a, b, c}, {B, C, D, S}, P, S) с правилами Таким образом цепочка aaaabbbbcccc выводима из S:

22 Законченная цепочка вывода

Законченная цепочка вывода

Вывод называется законченным (или конечным), если на основе цепочки ?, полученной в результате этого вывода, нельзя больше сделать ни одного шага вывода. Вывод называется законченным, если цепочка ?, полученная в результате этого вывода, пустая или содержит только терминальные символы грамматики. Цепочка ?, полученная в результате законченного вывода, называется конечной цепочкой вывода.

23 Сентенциальная форма грамматики

Сентенциальная форма грамматики

Цепочка символов ? из V* называется сентенциальной формой грамматики G (VT, VN, P, S), V = VT UVN, если она выводима из целевого символа грамматики S: S * ?. Если цепочка ? из VT* получена в результате законченного вывода, то она называется конечной сентенциальной формой.

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

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

Вывод называется левосторонним, если в нём на каждом шаге вывода правило грамматики применяется всегда к крайнему левому нетерминальному символу в цепочке. на каждом шаге вывода происходит подстановка цепочки символов на основании правила грамматики вместо крайнего левого нетерминального символа в исходной цепочке. Вывод называется правосторонним, если в нём на каждом шаге вывода правило грамматики применяется всегда к крайнему правому нетерминальному символу в цепочке. Пример 1 – (1,4), (2,3,4)

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

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

Для грамматик типов 2 и 3 для любой сентенциальной формы всегда можно построить левосторонний или правосторонний вывод. Для грамматик других типов это не всегда возможно, так как по структуре их правил не всегда можно выполнить замену крайнего левого или крайнего правого нетерминального символа в цепочке.

26 Пример2

Пример2

Рассмотренный в примере 2 не является ни левосторонним, ни правосторонним. Грамматика относится к типу 1, и для неё нельзя построить такой вывод, на каждом шаге которого только один нетерминальный символ заменялся бы на цепочку символов.

27 Цепочки вывода

Цепочки вывода

Пример

В грамматике для одной и той же цепочки может быть несколько выводов. Например, для цепочки a+b+a в грамматике G ({a, b, +}, {S, T}, P, S) P: S ? T | T+S; T ? a | b можно построить выводы: 2 – л; 3-п;

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

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

Деревом вывода грамматики G (VT, VN, P, S) называется дерево, которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям: каждая вершина дерева обозначается символом грамматики А из (VT U VN U {?}); корнем дерева является вершина, обозначенная целевым символом грамматики – S; листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой цепочки ?; если некоторый узел дерева обозначен нетерминальным символом А, а связанные с ним узлы – символами b1, b2, …, bn из VT U VN ; n > 0, то в грамматике G существует правило A ? b1 | b2 | … | bn из Р.

29 Классификация грамматик и языков (классификация Хомского)
30 Построение дерева сверху вниз

Построение дерева сверху вниз

При построении дерева вывода сверху вниз построение начинается с целевого символа грамматики, который помещается в корень дерева. Затем в грамматике выбирается необходимое правило, и на первом шаге вывода корневой символ раскрывается на несколько символов первого уровня. На втором шаге среди всех концевых вершин дерева выбирается крайняя, обозначенная нетерминальным символом, для этой вершины выбирается нужное правило грамматики, и она раскрывается на несколько вершин следующего уровня. Построение дерева заканчивается, когда все концевые вершины обозначены терминальными символами В противном случае надо вернуться ко второму шагу и продолжить построение.

31 Построение дерева снизу вверх

Построение дерева снизу вверх

Построение дерева вывода снизу вверх начинается с листьев дерева. В качестве листьев выбираются терминальные символы конечной цепочки вывода, которые на первом шаге построения образуют последний уровень (слой) дерева. Построение дерева идёт по слоям. На втором шаге построения в грамматике выбирается правило, правая часть которого соответствует крайним символам в слое дерева . Выбранные вершины слоя соединяются с новой вершиной, которая выбирается из левой части правила. Новая вершина попадает в слой дерева вместо выбранных вершин. Построение дерева закончено, если достигнута корневая вершина иначе надо вернуться ко второму шагу и повторить его над полученным слоем дерева.

32 Построение дерева

Построение дерева

Если для каждой цепочки символов языка, заданного грамматикой, можно построить единственный левосторонний (и единственный правосторонний) вывод или, построить единственное дерево вывода, то такая грамматика называется однозначной. Иначе грамматика называется неоднозначной.

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

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

Пример 3.

Условный оператор, включённый во многие языки программирования, описывается с помощью грамматики с правилами: S ? if b then S else S | if b then S | a где b – логическое выражение, а а – безусловный оператор. Эта грамматика неоднозначна, т.к. в ней возможны два левых вывода цепочки if b then if b then a else a:

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

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

Пример 3.

Наличие двух различных выводов предполагает две различные интерпретации цепочки if b then if b then a else a: первая из них – if b then (if b then a) else a, вторая – if b then (if b then a else a). При описании языка программирования эту неоднозначность преодолевают, добавляя к семантическим правилам правило вида: «ключевое слово else ассоциируется с ближайшим слева ключевым словом if».

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

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

Неоднозначная грамматика. Пример

Для цепочки if b then if b then a else a можно построить два раз- личных дерева вывода:

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

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

Неоднозначная грамматика. Пример

Разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена: S ? if b then S | if b then S' else S | a S‘ ? if b then S' else S' | a

37 КС- -грамматики

КС- -грамматики

Дерево вывода. Пример

Для КС-грамматик существуют определённого вида правила, по наличию которых во всём множестве правил грамматики можно утверждать, что она является неоднозначной: 1) А ? АА | ? 2) А ? А?А | ? 3) А ? ?А | A? | ? 4) А ? ?А | ?A?A | ? Здесь A из VN; ?, ?, ? из (VN U VT)*.

«Классификация грамматик и языков (классификация Хомского)»
http://900igr.net/prezentacija/russkij-jazyk/klassifikatsija-grammatik-i-jazykov-klassifikatsija-khomskogo-236907.html
cсылка на страницу

Грамота

11 презентаций о грамоте
Урок

Русский язык

100 тем
Слайды
900igr.net > Презентации по русскому языку > Грамота > Классификация грамматик и языков (классификация Хомского)