29378

Грамматический разбор методом операторного предшествования

Доклад

Информатика, кибернетика и программирование

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

Английский

2013-08-21

68.5 KB

11 чел.

16) Грамматический разбор методом операторного предшествования.

Метод операторного предшествования
Данный метод относится к классу 
восходящих методов синтаксического анализа. Он основан на анализе пар соседних операторов исходной программы с целью определения таких операторов в каждой паре, которые должны быть выполнены и распознаны первыми. 
Пример: в соответствии с правилами арифметики умножение должно выполняться раньше сложения. Для метода в этом случае говорят, что «*» предшествует «+» или «*» имеет более высокий уровень предшествия: * •> + 
A+B*C–D, для целого выражения: + <• * •> – 
Это соотношение указывает, что B*C выполняется первым.
Дерево разбора:

Идея метода: входная цепочка символов просматривается слева направо, пока не будет найдено подвыражение, имеющее более высокий уровень предшествования, чем соседние операторы. Затем оно распознаётся с использованием продукций грамматики языка и заменяется 1 нетерминальным символом. Параллельно строится соответствующий фрагмент дерева разбора. Процедура повторяется до тех пор, пока входная цепочка не будет свёрнута до одного нетерминального символа. Считается, что это корень дерева разбора и процесс завершён успешно. 
Для 
реализации метода необходимо установить отношение предшествования между всеми парами операторов грамматики. При этом оператор – все терминальные символы грамматики.
В общем случае между парой терминальных символов a и b некоторой грамматики возможны следующие виды отношений предшествования: 1) a <• b 2) a •> b 3)a = • b 4) отношения предшествования между a и b не существует. 
1) и 2) показывают, что a и b входят в синтаксические единицы языка, распознаваемые отдельно друг от друга. Третий случай означает, что a и b принадлежат одной синтаксической конструкции и распознаются в результате применения одной продукции грамматики. Четвёртый случай означает, что a и b не могут быть соседними ни в одной грамматически правильной конструкции языка. 
Представления отношений предшествования не являются симметричными. 
При практической реализации таких методов отношения между всеми парами терминальных символов описываются с помощью матрицы предшествования:

EE+T |
TT*M | M
M→(E) | i

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

Если матрица предшествования известна, то метод в целом реализуется так: 
1) Во входной строке определяют самую левую подстроку α, имеющую более высокий уровень предшествования, чем соседние символы. 
2) В описанной грамматике найти продукции вида A→α и заменяют цепочку α одним нетерминальным символом. 
3) Построение соответствующего фрагмента дерева разбора. 
4) Повторяем п.1–3, пока не будет найден разбор входной цепи или обнаружена ошибка во входной строке.
Разбор успешен, если входная цепь свёрнута до одного нетерминального символа.
Пояснение к пункту 1: на каждой итерации, за исключением первой, входная цепь – сентенциальная форма грамматики. Выделяемая подстрока α – основа сентенциальной формы. Основа определяется следующими условиями:

Пояснение к пункту 2: выбор необходимых правил вывода осуществляется с учётом структуры правой части конкретной продукции, обозначения нетерминалов при этом не учитывается т.к. нетерминальный символ в таких грамматик соответствует операндам, вся информация о которых уже сохранена в таблице трансляций, важен только факт наличия операнда, а не его обозначения.
Ошибки обнаруживаются так: 1) Нельзя выделить подстроку α на первом шаге. 2) Нельзя найти правило вывода на втором шаге. 3) Во входной цепи появляется два соседних терминальных символа между которых не существует отношения предшествования


 

А также другие работы, которые могут Вас заинтересовать

40946. Основні положення теорії надійності 667 KB
  Але це не означає що люди не цікавилися і не займалися питаннями надійності створюваної ними техніки до тих пір поки не виникла наука про надійність. Створення і використання такої техніки без спеціальних заходів по забезпеченню її надійності не має сенсу. З розвитком і ускладненням техніки ускладнювалася і розвивалася проблема її надійності. Предмет її досліджень вивчення причин що викликають відмови об'єктів визначення закономірностей яким відмови підкоряються розробка способів кількісного вимірювання надійності методів розрахунку і...
40947. Инструменты и технологии рисования во Flash 3.01 MB
  Заливка фигуры растровым изображением Показать/скрыть все слои (Show/Hide All Layers) - если кликнуть левой клавишей мыши в слое под этой пиктограммой, появится крестик красного цвета, а значок с изображением карандаша будет перечеркнут красной линией. Изображение, находящееся в данном слое исчезнет в рабочем поле.
40948. Создание покадровой анимации в Flash 793.5 KB
  Создание покадровой анимации Во Flsh предусмотрено три различных механизма анимирования объектов: покадровая классическая анимация когда автор сам создает или импортирует из других приложений каждый кадр будущего мультика и устанавливает последовательность их просмотра; автоматическое анимирование так называемая tweenedанимация при использовании которой автор создает только первый и последний кадры мультипликации а Flsh автоматически генерирует все промежуточные кадры; различают два вида tweenedанимации: анимация...
40949. Создание анимации вращения 328 KB
  Более того эта анимация работает корректно только если в начальном и заключительном ее кадрах расположен один и тот же флэшсимвол В технологии Flsh используются самостоятельные объекты называемые флэшсимволами Symbols. поэтому анимация движения способна постепенно изменять все эти свойства от первого кадра к заключительному. В случае когда надо совмещать вращение с перемещением в панели Свойств в начальном ключевом кадре анимации задается вращение. Нарисуйте в первом кадре стрелку используя инструмент Кисть B.
40950. Создание анимации. Движение по заданной траектории 566 KB
  Создание анимации Движение по заданной траектории Это занятие посвящено движению по траектории созданию мувиклипов. Движение по заданной траектории Flsh позволяет задать движение объекта вдоль заданной траектории. Добавьте слой траектории.
40951. Работа со звуком в Flash 939 KB
  Работа со звуком во Flsh Введение Где взять звуки Добавление звука во Flsh Импорт звуков Различные виды синхронизации Применение компрессии к выбранным звукам Применение компрессии ко всем звукам Общие рекомендации по экспорту звука
40952. Создание Flash презентации 807.5 KB
  Создание Flshпрезентации Основные принципы создания презентации Способы создания презентации во Flsh Создание презентации Основные принципы создания презентации Способы создания презентации во Flsh Создание презентации Введение Презентация грамотно разработанная с помощью Flsh будет выгодно выделяться среди шаблонных продуктов рожденных в инкубаторе Microsoft Power Point. Основные принципы создания презентации Очень важно чтобы ваша презентация имела цельный законченный вид. После создания структуры...
40953. Программирование в Flash 785.5 KB
  Программирование во Flsh План Введение Знакомство с панелью Действия ctions Работа с действиями объектов Использование действий Возможности управления сценами с помощью сценариев ctionScript События мыши
40954. Объявление и инициализация переменной типа bool. Вывод данных на консоль 97 KB
  Консолью называется окно операционной системы, в котором пользователи взаимодействуют с операционной системой. Приложение может считывать пользовательский ввод из стандартного входного потока, записывать обычные данные в стандартный выходной поток и записывать данные об ошибках в стандартный поток сообщений об ошибках.