Грамматический разбор. Распознаватели. (Лекция 3) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Грамматический разбор. Распознаватели. (Лекция 3), слайд №1

Грамматический разбор. Распознаватели. (Лекция 3), слайд №2

Грамматический разбор. Распознаватели. (Лекция 3), слайд №3

Грамматический разбор. Распознаватели. (Лекция 3), слайд №4

Грамматический разбор. Распознаватели. (Лекция 3), слайд №5

Грамматический разбор. Распознаватели. (Лекция 3), слайд №6

Грамматический разбор. Распознаватели. (Лекция 3), слайд №7

Грамматический разбор. Распознаватели. (Лекция 3), слайд №8

Грамматический разбор. Распознаватели. (Лекция 3), слайд №9

Грамматический разбор. Распознаватели. (Лекция 3), слайд №10

Грамматический разбор. Распознаватели. (Лекция 3), слайд №11

Грамматический разбор. Распознаватели. (Лекция 3), слайд №12

Грамматический разбор. Распознаватели. (Лекция 3), слайд №13

Грамматический разбор. Распознаватели. (Лекция 3), слайд №14

Грамматический разбор. Распознаватели. (Лекция 3), слайд №15

Грамматический разбор. Распознаватели. (Лекция 3), слайд №16

Грамматический разбор. Распознаватели. (Лекция 3), слайд №17

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Грамматический разбор. Распознаватели. (Лекция 3). Доклад-сообщение содержит 17 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Лекция 03. Проблема грамматического разбора. Распознаватели.

Слайд 2

Описание слайда:

Разбор цепочек. Задача разбора Задача разбора в общем виде: на основе имеющейся грамматики некоторого языка построить распознаватель для этого языка Цепочка принадлежит языку, порождаемому грамматикой, только в том случае, если существует ее вывод из аксиомы этой грамматики. Процесс построения такого вывода (а, следовательно, и определения принадлежности цепочки языку) называется разбором.

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Пример. Выводы Для цепочки a+b+a в грамматике G = ({a,b}, {S,T}, {S  T | T+S; T  a|b}, S) можно построить выводы: Левый ST+ST+T+ST+T+Ta+T+Ta+b+Ta+b+a Правый 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

Слайд 5

Описание слайда:

Дерево вывода для цепочки a+b+a Определение: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка a  L(G), для которой может быть построено два или более различных деревьев вывода. В противном случае грамматика называется однозначной.

Слайд 6

Описание слайда:

Пример неоднозначной грамматики G = ({if, then, else, a, b}, {S}, P, S), где P = {S  if b then S else S | if b then S | a}. В этой грамматике для цепочки if b then if b then a else a можно построить два дерева вывода. Неоднозначность – свойство грамматики, а не языка S  if b then S | if b then S’ else S | a S’  if b then S’ else S’ | a

Слайд 7

Описание слайда:

Еще раз вернемся к неоднозначным грамматикам G({+,-,*,/,(,),a,b},{S},P,S): Р: S  S+S | S-S | S*S | S/S | (S) | а | b Для цепочки а*b+а возможны два левых вывода: (1) S  S+S  S*S+S  a*S+S  a*b+S  a*b+a (2) S  S*S  a*S  a*S+S  a*b+S  a*b+a

Слайд 8

Описание слайда:

Построение эквивалентной однозначной грамматики G'({+,-,*./,(,),a,b},{S,Т,E},P',S); Р‘ = {S  S+T | S-T | Т ; Т  Т*Е | Т/Е | Е ; Е  (S) | а | b} Для цепочки а*b+а возможен только один левый вывод: S  S+T  Т+Т  Т*Е+Т  Е*Е+Т  а*Е+Т  a*b+T  a*b+E  a*b+a

Слайд 9

Описание слайда:

Распознаватели

Слайд 10

Описание слайда:

Распознаватели. Условная схема распознавателя

Слайд 11

Описание слайда:

Компоненты распознавателя лента, содержащая исходную цепочку входных символов, и считывающая головки, обозревающей очередной символ в этой цепочке; устройство управления (УУ), которое координирует работу распознавателя, имеет некоторый набор состояний и конечную память (для хранения своего состояния и некоторой промежуточной информации); внешняя (рабочая) память, которая может хранить некоторую информацию в процессе работы распознавателя и в отличие от памяти УУ может иметь неограниченный объем Алфавит распознавателя – ленты + внутренний Операции распознавателя – чтение/запись

Слайд 12

Описание слайда:

Работа распознавателя состоит из последовательности тактов В начале каждого такта состояние распознавателя определяется его конфигурацией. В процессе работы конфигурация меняется. Конфигурация определяется: содержимым входной цепочки символов и положением считывающей головки в ней; состоянием УУ; содержимым внешней памяти. Всегда задается начальная конфигурация. И несколько конечных конфигураций

Слайд 13

Описание слайда:

Работа распознавателя. Язык, определенный распознавателем В начальной конфигурации: считывающая головка на первом символе входной цепочки, УУ находится в заданном начальном состоянии, внешняя память пуста. В конечной конфигурации считывающая головка - за концом исходной цепочки Распознаватель допускает входную цепочку а, если, находясь в начальной конфигурации и получив на вход эту цепочку, он может проделать последовательность шагов, заканчивающуюся одной из его конечных конфигураций. Язык, определяемый распознавателем, — это множество всех цепочек, которые допускает распознаватель.

Слайд 14

Описание слайда:

Виды распознавателей По видам считывающего устройства двусторонние и односторонние По видам устройства управления детерминированные и недетерминированные По видам внешней памяти: распознаватели без внешней памяти; распознаватели с ограниченной внешней памятью; распознаватели с неограниченной внешней памятью.

Слайд 15

Описание слайда:

Классификация распознавателей по типам языков Для языков с фразовой структурой (тип 0) необходим распознаватель, равномощный машине Тьюринга недетерминированный двусторонний автомат, с неограниченной внешней памятью. Практического применения не имеет Для контекстно-зависимых языков (тип 1) двусторонние недетерминированные автоматы с линейно ограниченной внешней памятью. Экспоненциальная сложность Для контекстно-свободных языков (тип 2) односторонние недетерминированные автоматы с магазинной внешней памятью — МП-автоматы. Полиномиальная сложность Детерминированные КС-языки – ДМП-автоматы Для регулярных языков (тип 3) детерминированные автоматы без внешней памяти — конечные автоматы (КА). Линейная сложность

Слайд 16

Описание слайда:

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