[23.05.11] Лекция №13 (1061999)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция №13 [23.05.11]

Восходящий анализ

- КС-грамматика, - цепочка в объединённом алфавите, и есть цепочка , содержащаяся в цепочке посередине: .

И вот - это основа, - левое крыло вхождения, - правое крыло вхождения.

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

Пример:

, здесь - это , - это , - это

а возьмём , тут цепочка - не является основой, значит, - не выводима из .

Для практического применения необходимо сформулировать дополнительные решающие правила, помогающие определить, является ли данная цепочка основой. Один из подходов заключается в сопоставлении каждому правилу КС-грамматики некоторого бинарного отношения на множестве цепочек в объединённом алфавите . Вхождение правой части некоторого правила является основой тогда и только тогда, когда его крылья принадлежат соответствующему данному правилу бинарному отношению.

Пример:

,

, тут , ,

, тут , ,

и так далее

таким образом, определение основы с использованием введённого бинарного отношения позволяет провести безтупиковую редукцию некоторого палиндрома аксиомы.

Попытка редукции без использования разрешающего отношения приводит в тупик:

-грамматики

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

Обобщённый(расширенный) МП-автомат, состояние , читаем , цепочка символов магазина : , где - заменяемая цепочка

Детерминированный магазинный автомат – если из любой его конфигурации выводится не более чем одна конфигурация.

Язык допускается некоторым ДМП-автоматом тогда и только тогда, когда он порождается некоторой -грамматикой.

Для детерминированных КС-языков может быть реализована стратегия восходящего анализа "перенос-свёртка":

концевой маркер *

- тут пишем в обратную сторону, для удобства, вроде бы

, где:

это или , или

это или , или , или

перенос в магазин входной цепочки

следующие три команды помечены как "свёртка"

, ,

заключительная команда:

Пример:

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций