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) Во входной цепи появляется два соседних терминальных символа между которых не существует отношения предшествования


 

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

71530. Детали машин общего машиностроения 50 KB
  Задачей курса является научить студента конструировать и рассчитывать детали машин с учётом реальнодействующих сил собирать из этих деталей механизмы и машины. Всякая машина состоит из сборочных единицы и деталей. Всякий механизм состоит из соединительных деталей и соединений.
71531. История педагогики: Курс лекций 1.2 MB
  Цели воспитания он связывал с формированием человека-патриота главными качествами которого должны быть высокая нравственность любовь к науке знаниям трудолюбие бескорыстное служение Родине. Зарождение воспитания школы и педагогической мысли...
71532. ИСТОРИЯ АВТОМАТИЗАЦИИ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ И ПРОИЗВОДСТВ 947 KB
  Специалист по автоматизации должен обладать поистине энциклопедическими знаниями. Современные методы проектирования рабочих машин и механизмов электромеханика силовых приводов электроника и схемотехнические решения систем управления микропроцессорные и компьютерные средства...
71533. ИСТОРИЯ ОБРАЗОВАНИЯ И ПЕДАГОГИЧЕСКОЙ МЫСЛИ 559.5 KB
  Помочь студентам осознать Историю образования и педагогической мысли как часть гражданской истории, отразившую тысячелетний сложный и противоречивый опыт человечества в организации воспитания подрастающего поколения. Подготовить их к правильному пониманию в предстоящем...
71534. ИСТОРИЯ АРХИТЕКТУРЫ. КРАТКИЙ ОБЗОР 95.5 KB
  Понятие «архитектура» происходит от греческого слова «архитектор» - главный строитель. Архитектура – каменная летопись; это часть материальной культуры человечества, которая информирует нас о жизни людей давно минувших эпох. Архитектура – «застывшая музыка».
71535. ИСТОРИЯ ГОСУДАРСТВЕННОГО УПРАВЛЕНИЯ В РОССИИ: КОНСПЕКТ ЛЕКЦИЙ 240 KB
  Складывание централизованного государства и государственное управление в России в конце XV XVIII вв. Внутренние и внешние функции Российского государства. Концепции происхождения и становления государства. Образование Древнерусского государства его важнейшие функции.
71536. Обеспечение радиационной безопасности населения 107 KB
  Одним из главных медико-санитарных мероприятий по обеспечению радиационной безопасности населения является регламентация радиационных воздействий от различных источников ионизирующих излучений. Для всех категорий облучаемых лиц в том числе населения определены следующие классы нормативов...
71537. The History of the English Language 711 KB
  The History of the English Language has been reconstructed on the basis of written records of different periods. The earliest written texts in English are dated in the 7th century. The earliest records in other Germanic languages go back to the 3rd or 4th centuries A.D.
71538. Введение в историю экономики 1.1 MB
  Предмет истории экономики и его эволюция Историко-экономическая наука оформилась как самостоятельная ветвь системы экономических наук в XIX в. Однако на данном этапе под основным назначением истории экономики понималась ее иллюстративная роль.