Содержание
- 2. Классификация грамматик Аврам Ноам Хомский (Avram Noam Chomsky , 1928) – американский лингвист, политический публицист, философ
- 3. Классификация грамматик 1-грамматики – Контекстно-зависимые (неукорачивающие) грамматики Контекстно-зависимые грамматики: α1Аα2 ::= α1βα2, где α1, α2 ϵ
- 4. Классификация грамматик 2-грамматики – Контекстно-свободные грамматики Неукорачивающие контекстно-свободные (НКС) грамматики А ::= β, где А ϵ
- 5. Классификация грамматик 3-грамматики – Регулярные грамматики Леволинейные грамматики А ::= Bγ или А ::= γ, где
- 6. Классификация языков Языки классифицируются в соответствии с типами грамматик, с помощью которых они заданы. Один и
- 7. Пример языка 1 Регулярная грамматика? Нет AB ::= bBA КС-грамматика? Нет AB ::= bBA КЗ/Неукорчивающая грамматика?
- 8. Пример языка 2 L(G) = { an bn cn, n >= 1} G: S ::= aSBC
- 9. Пример языка 3 L(G) = {(ac)n (cb)n | n > 0} G: S ::= aQb |
- 10. Вывод в грамматике Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматики. Цепочка
- 11. Отношение вывода С математической точки зрения вывод можно рассматривать как отношение на множестве V*. Оно обладает
- 12. Примеры вывода Грамматика для языка целых десятичных чисел со знаком: G ({0, 1, 2, 3, 4,
- 13. Вывод и сентенциальная форма Вывод называется законченным (или конечным), если на основе цепочки β, полученной в
- 14. Примеры сентенциальных форм В грамматике для языка целых десятичных чисел со знаком: G ({0, 1, 2,
- 15. Левосторонний и правосторонний выводы Вывод левосторонний, если на каждом шаге вывода правило грамматики применяется всегда к
- 16. Эквивалентные выводы Для цепочки a+b+a в грамматике G ({a, b, +}, {S, T}, P, S) P:
- 17. Дерево вывода Деревом вывода (синтаксическим деревом) грамматики G (VT, VN, P, S), называется дерево (граф), которое
- 18. Построение синтаксического дерева сверху вниз Для построения дерева вывода, достаточно иметь только цепочку вывода. Для строго
- 19. Построение синтаксического дерева снизу вверх Построение дерева вывода снизу вверх начинается с листьев дерева. В качестве
- 20. Пример дерева вывода Грамматика для языка целых десятичных чисел со знаком: G ({0, 1, 2, 3,
- 21. Вывод в компиляторах Поскольку все известные языки программирования имеют нотацию записи «слева — направо», компилятор также
- 22. Однозначные и неоднозначные грамматики Рассмотрим грамматику G({+,—,*,/,(,),a,b},{S},P,S): P: S ::= S+S | S—S | S*S |
- 23. Однозначные и неоднозначные грамматики Структура предложения и его значение (смысл) взаимосвязаны. Дерево вывода (или цепочка вывода)
- 24. Однозначные и неоднозначные грамматики Грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой,
- 25. Пример перехода от неоднозначной грамматики к однозначной Если грамматика является неоднозначной, то необходимо попытаться преобразовать ее
- 26. Как проверить, является ли грамматика однозначной? Для доказательства неоднозначности грамматики достаточно найти в заданном ею языке
- 27. Как убедиться, что две грамматики эквивалентны? Проблема эквивалентности грамматик в общем виде формулируется следующим образом: имеется
- 29. Скачать презентацию