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


 

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

21034. СЕРЕДОВИЩЕ ТА ОСОБЛИВОСТІ СУЧАСНОГО ЕТАПУ РОЗВИТКУ МІЖНАРОДНИХ ЕКОНОМІЧНИХ ВІДНОСИН 29.74 KB
  Середовище міжнародних економічних відносин – це система умов і факторів існування міжнародних економічних зв’язків. Середовище МЕВ поділяється на внутрішнє і зовнішнє.
21035. ИССЛЕДОВАНИЕ МАГНИТНЫХ ПУСКАТЕЛЕЙ 71.5 KB
  В общим случае МП состоит из трехполюсного контактора переменного тока электротеплового реле ЭТР и кнопок управления. Время токовая или защитная характеристика ЭТР зависимость времени срабатывания tср от тока I МП должна согласовываться с перегрузочной характеристикой электродвигателя зависимость допустимого времени протекания тока tдоп от тока I. К клеммам Х1 и Х2 подключается настольный амперметр для измерения тока в обмотке МП. Промежуточное реле KL1 и трансформатор тока ТА1 расположены за стендом.
21036. Электромагнитные воздушные контакты 56 KB
  Для катушек постоянного тока неблагоприятным условием при срабатывании является подача пониженного напряжения 085Uн на катушку нагретую до установившейся температуры Θдоп максимальным напряжением 105Uн. Иногда испытание на втягивание заключается в определении напряжения Uчс чёткого срабатывания т. напряжения при котором якорь переходит из одного крайнего положения в другое без заметного торможении в промежуточном положении. Поскольку чёткость срабатывания обычно определяется на слух то значение напряжения чёткого срабатывания...
21037. Исследование электрической дуги постоянного тока 134.5 KB
  Целью работы является исследование неподвижной дуги постоянного тока определение вольтамперной характеристики дуги между электродами выполненными из различных материалов исследование влияния длины дуги и шунтирующего сопротивления на характеристики дуги. Одной из основных характеристик дуги является ее вольтамперная характеристика зависимость напряжения на дуге от тока дуги. С ростом тока дуги вследствие разогрева дугового столба ее сопротивление уменьшается быстрее нежели растет ток.
21038. Исследование герконовых реле 552 KB
  Общие положения Отечественной промышленностью выпускаются одно и многоконтактные реле на замыкание размыкание и переключение преимущественно расположением герконов внутри катушки управления и с внешним магнитопроводом [12]. Для реле с одним замыкающим герконом рис.2 описывается выражением 1 и 2 и их соотношением определяются процессы срабатывания и возврата геркона где С приведенная жесткость контактных сердечников КС геркона; δн и δ начальное и текущее значения немагнитного зазора между КС; F магнитодвижущая сила МДС...
21039. ИССЛЕДОВАНИЕ АВТОМАТОВ 76 KB
  Краткие сведения об автоматах Автоматы это аппараты предназначенные для нечастых включений и отключений электрических цепей по команде оператора и автоматического отключения цепей при ненормальных режимах в них. Автоматы изготовляются на номинальные токи до 6000 А а отдельные серии до 2030 кА на номинальные напряжения до 660 В переменного тока и до 440 В постоянного тока. В зависимости от требовании к времени срабатывания и от назначения автоматы подразделяются на: 1 Небыстродействующие постоянного и переменного тока время...
21040. Исследование электромагнитных контакторов 67 KB
  Электромагнитный контактор представляет собой электромагнит постоянного или переменного тока по обмотке которого протекает ток. В качестве приводных электромагнитов постоянного тока обычно применяются клапанные Побразные электромагниты с внешним качающимся якорем рис. Кроме того необходимо иметь гибкое соединение для подвода тока к подвижному контакту. Исполнение дугогасительных систем контакторов зависит от рода и уровня тока коммутируемой цепи.
21041. Исследование герконовых реле 178.5 KB
  Ульянова Электротехнический факультет Кафедра электрических и электронных аппаратов ЛАБОРАТОРНАЯ РАБОТА №64 Исследование герконовых реле Выполнили студенты группы ЭТ2103: Кузнецов А. Лабораторная работа №64 Исследование герконовых реле Цель работы: изучение конструкций герконов и реле на их основе исследование параметров реле и геркона. Отечественной промышленностью выпускаются одно и многоконтактные реле на замыкание размыкание и переключение преимущественно с расположением герконов внутри катушки управления и с внешним...
21042. Виртуальные машины 207.5 KB
  Опять же необходимо указать имя и место сохранения создаваемого диска. Поэтому сразу выберите место для сохранения с учетом достаточности свободного пространства на реальном разделе жесткого диска. Отмечу некоторые особенности: к системе можно подключить три жестких диска. Напоследок рассмотрим процедуру создания нового виртуального жесткого диска.