рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Грамматики простого предшествования.Отношения предшествования

Грамматики простого предшествования.Отношения предшествования - раздел Программирование, СИНТАКСИЧЕСКИЙ И СЕМАНТИЧЕСКИЙ АНАЛИЗ   Отношения Предшествования Такие Же Отношения, Как И Логически...

 

Отношения предшествования такие же отношения, как и логические конъюнкция, дизъюнкция, и несут смысл определённых операций.

Примечание. Здесь и в дальнейшем будем рассматривать пару рядом стоящих символов R,SÎV=VtÈVn, то есть считать эти символы терминальными или нетерминальными.

Определение 5.3.Говорят, что R предшествует S (R·>S) (то есть R сворачивается раньше, чем S), если R является частью основы синтаксического дерева, а S нет (рис. 5.22).

 

Рис. 5.22. R·>S

Определение 5.4.Говорят, что R сворачивается одновременно с S (RS), если оба символа входят в основу одновременно (рис. 5.23).

Рис. 5.23. RS

 

Определение 5.5.Говорят, что S предшествует R (R<·S), или R сворачивается позже, чем S, если S в основе, а R ещё нет (рис.5.24).

Рис. 5.24. R<·S

Свойства отношения предшествования. Отношения предшествования в отличие от всех основных отношений, не обладают коммутативными свойствами, то есть нельзя применять свойства симметрии к отношениям предшествования. Действительно, если мы говорим что R предшествует S (R·>S), то это совсем не означает, что S<·R. Хотя для определённых символов словаря это имеет место, но только в частном случае.

Сформулируем аналитические определения отношений.

Определение 5.6.Отношение U FIRST S имеет место, тогда и только тогда, когда имеет место выводимость: U®Sa, SÎVN, aÎV*. (Иначе говоря, S – первый нетерминал.)

Определение 5.7. ОтношениеU FIRST+ S имеет место , тогда и только тогда, когда существует итерационная выводимость: UÞ+Sa, SÎVN, aÎV*.

Определение 5.8.ОтношениеU LAST S имеет место, тогда и только тогда, когда имеет место выводимость: U®aS, SÎVN , aÎV*.

Определение 5.9.Отношение U LAST+ S имеет место, тогда и только тогда, когда существует итерационная выводимость: UÞ+aS , SÎVN , aÎV*.

Определение отношений предшествования между символами по заданной грамматике производится в соответсвии со свойствами отношений:

Свойство 1. RS, когда в грамматике существуют следующие отношения:

U®aRSbÎP; причём

a,bÎV*; R,SÎV.

Свойство 2.. R<·S, если в грамматике существуют или имеют место следующие отношения:

U®aRWb; причём

a,bÎV*; W FIRST+ S; R,S,WÎV.

Свойство 3..R·>S, если в грамматике существуют или имеют место следующие отношения:

U®aQWb; причём

a,bÎV*; Q LAST+ R; W FIRST+ S; R,S,W,QÎV.

 

Для иллюстрации рассмотрим грамматику G[Z]:

1. Z ® bMb

2. M ® (L | a

3. L ® Ma)

Легко видеть, что G[Z] является грамматикой простого предшествования. (Легко доказывается!)

Язык, порождаемый данной грамматикой:

L(G[Z])={bab, b(aa)b, b((aa)a)b, . . . .}

Построим сентенциальные деревья из цепочек принадлежащих L(G[Z]) (рис. 5.25…5.27)

 

Рис. 5.25. 1-е сентенциальное дерево

 

Рис. 5.26. 2-е сентенциальное дерево

Рис. 5.27. 3-е сентенциальное дерево

В данном случае отношения предшествования между символами грамматики установлено графически, то же самое можно было бы сделать используя свойства 1,2,3 отношения FIRST, LAST, но аналитически.

Матрица предшествования.

Алгоритм разбора для восходящего распознавателя с использованием грамматик предшествования. Алгоритм Флойда (1963)

 

Матрица предшествования представляется в виде таблицы Q c элементами qij такими, что:

qij=0, если Si и Sj несравнимы;

qij=1, если Si<·Sj;

qij=2, если SiSj;

qij=3, если Si·>Sj.

Сами правила должны находиться в таблице, структура которой позволяет по заданной грамматике (правой части) найти содержимое и правило, а затем указать соответствующую левую часть.

Алгоритм Флойда. Символы входной цепочки просматриваются слева направо и помещаются в стек S до тех пор, пока символ вершины стека Si не окажется в отношении предшествования “·>” с очередным анализируемым символом R, это означает, что верхний символ стека является “хвостом” основы и, следовательно, основа уже в стеке.

Основу находят в списке правил приготовленной таблицы редукций и заменяют нетерминалом U. Процесс повторяется до тех пор, пока в качестве U не окажется Z (рис. 5.28).

 

Рис. 5.28. К алгоритму Флойда

 

 
 

 

 


Рис. 5.29. Блок-схема распознавателя

Блок-схема распознавателя изображена на рис. 5.29.

Здесь S — стек; i — счетчик стека; j — индекс адресации внутренних элементов стека; $t1,...,tn$ — формат анализируемого предложения; U — нетерминал, к которому приводится основа, найденная на шаге разбора; Z — начальный символ грамматики.

Значение блоков:

1,2 — задание начальных условий;

3,4 — выполнение условия: если Si и R не находятся в отношении Si·>R, то не вся основа в стеке, поэтому символ R заносится в стек и поиск продолжается.

5,6,7 — Si предшествует R (Si·>R), следовательно, основа уже в стеке. Необходимо найти “голову” основы (то есть такое j, что Sj-1<·Sj ).

8,9 — проверка цепочки Sj...Si ; если она не является правой частью редукции, то работа закончена с авостом (ошибкой), в противном случае исключить из стека Sj...Si , и занести в стек символ U, который является левой частью (U®Sj ... Si).

 

– Конец работы –

Эта тема принадлежит разделу:

СИНТАКСИЧЕСКИЙ И СЕМАНТИЧЕСКИЙ АНАЛИЗ

На сайте allrefs.net читайте: "СИНТАКСИЧЕСКИЙ И СЕМАНТИЧЕСКИЙ АНАЛИЗ"

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Грамматики простого предшествования.Отношения предшествования

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ПРОЦЕССОР ЧИСЛОВЫХ КОНСТАНТ
Приведем грамматику числовых констант в следующем виде G[<Число>]: 1. <Число> ® [+ | -] <Число Без Знака> 2. <Число Без Знака> ® <Десят

Очистка мусора
Мусором будем называть вспомогательные сиволы, которые не являются носителями смыслового содержания текста. Такими символами являются символы табуляции ‘t’, символы перевода на новую строку

Декомпозиция программы при лексическом анализе
Основным функциональным назначением сканера является декомпозиция программы на её терминальные составляющие: идентификаторы, ключевые слова, числовые константы, знаки операций и так далее. Эти язык

Семантика целого числа при сканировании
Для целого в алгоритме предусмотрен генератор условного кода 2. Под кодом здесь понимается класс целых. Часто, при обработки целых требуется не только их указатель(код) целого числа, но и значение

Лексический анализ идентификатора
Выделение идентификаторов кодом 2 не является полной информацией о каждом идентификаторе в отдельности. На этапе лексического анализа информационной характеристикой идентификатора является кортеж &

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

ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ
Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, констант, имён функций (библиотечных и внеших) и т.д. Определение 5.1. Табли

Структуры линейного формата
Для структур линейного формата существует два способа хранения имен. Первый – хранить символы имени в записях таблицы символов рис. 5.10, второй - в записи для имени размещать только указатель на о

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

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

Неупорядоченный поиск
Неупорядоченный поиск – это простейший способ организации таблицы символов. Он состоит в том, чтобы добавлять элементы для аргументов в порядке их поступления, без каких-либо попыток упорядочения.

Бинарный поиск
Поиск может быть выполнен более эффективно, если элементы таблицы упорядочены (отсортированы) согласно некоторому естественному порядку аргументов. Эффективным методом поиска в упорядоченн

Хеш-адресация
Данный метод в целом более эффективен, чем линейные списки, и используется для таблиц символов в большинстве случаев [13]. Схема открытого хеширования (хеш-таблица размера 211) приведена на рис.5.1

Сравнение способов организации таблиц символов
Прямой поиск прост в реализации, но самый неэффективный, т.к. время поиска прямопропорционально размерности таблицы, а количество сравнений в среднем равно половине элементов таблицы. Бинарный поис

РЕКУРСИВНЫЙ СПУСК
Рассмотрим подкласс КС-грамматик - S-грамматики Определение 5.2. S-грамматики — это подкласс контекстно-свободных грамматик, таких что: 1. Правая часть

ДИАГНОСТИКА И НЕЙТРАЛИЗАЦИЯ СИНТАКСИЧЕСКИХ ОШИБОК
Диагностика — установка места возникновения и типа синтаксической ошибки. Кроме того, обработанная ошибка должна быть визуализирована пользователем в виде, удобном для её обнаружения. Нейт

Метод Айронса
  Основная идея — по контексту без возврата отбрасывать литеры, которые привели к тупиковой ситуации (когда продолжение анализа по грамматике невозможно) и разбор продолжается. Для ил

Алгоритм Айронса по исправлению ошибок
  Пусть xjy — куст исходной программы, где x — построенная часть, jy — недостроенная часть, jÎVT 1. Строим список L из литер недостающих час

Вычисления арифметических записей на основе ПОЛИЗ
Существует два способа записи арифметических выражений: 1) инфиксная (традиционная) и 2) постфиксная (ПОЛИЗ) Таблица 5.1 Инфиксная Постфиксная

ВОСХОДЯЩИЕ МЕТОДЫ АНАЛИЗА
  Анализ методами слева направо является более приоритетным и занимает 60..80% для грамматик определённого класса. Менее популярными являются методы анализа снизу вверх или восходящие

УПРАЖНЕНИЯ
Перевести в ПОЛИЗ инфиксные выражения 1 - 3   1. ( x2

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги