29378

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

Доклад

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

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

Английский

2013-08-21

68.5 KB

10 чел.

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


 

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

35564. Высокие технологии в металлургии. ч.1 Производство цветных металлов 1.14 MB
  Кратко изложена теория и практика современной металлургии меди никеля алюминия магния и титана. Металлургия меди 5 1.2 Свойства меди и области её применения 8 1.3 Сырье для получения меди 9 1.
35565. ТЕОРИЯ ПЕРЕХОДНЫХ ПРОЦЕССОВ. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ЭЛЕКТРОТЕХНИКИ 9.56 MB
  21 Операторные схемы замещения элементов цепи22 Законы Ома и Кирхгофа в операторной форме.38 Численное решение уравнения состояния явный метод Эйлера40 ЛЕКЦИЯ 5 Линейные электрические цепи при импульсных воздействиях Расчет реакции цепи на одиночный импульс воздействия метод наложения.42 Расчет реакции цепи на периодическое импульсное воздействия метод сопряжения интервалов . Дальнейшее состояние цепи называют установившимся процессом.
35566. ЭКСПЛУАТАЦИОННЫЕ СВОЙСТВА АВТОМОБИЛЕЙ 3.43 MB
  АТС и его эксплуатационные свойства4 Вопрос 2. Условия эксплуатации АТС. Тяговоскоростные свойства АТС ТСС АТС. Силы действующие на АТС9 Вопрос 5.
35567. Металлургия черных металлов 1.51 MB
  Дан расчет количества МНЛЗ обращено внимание на выбор типа и основных проектных характеристик МНЛЗ. Типы МНЛЗ и их применение. Расчет количества МНЛЗ для рассматриваемого примера. На обоих предприятиях установлена и внедрена в производство установка внепечной очистки сталей АКВОС на ОАО €Электросталь€ строится 5й СПЦ который планируется оборудовать двумя ДСП20 агрегатами внепечной очистки стали и МНЛЗ.
35568. ТЕХНОЛОГИЯ ПРОИЗВОДСТВА СТАЛИ В ЭЛЕКТРИЧЕСКИХ ПЕЧАХ 1.01 MB
  Курс лекций Технология производства стали в электрических печах ГОУ СПО Красносулинский металлургический колледж г. Данное методическое пособие является кратким курсом лекций по дисциплине Технология производства стали в электрических печах для студентов 3 курса специальности 150108 – Порошковая металлургия композиционные материалы покрытия СОДЕРЖАНИЕ АННОТАЦИЯ. ТЕХНОЛОГИЧЕСКИЕ ПРОЦЕССЫ ПРОИЗВОДСТВА СТАЛИ.
35569. Матанализ Конспект лекций 20.29 MB
  Свойства бесконечно малой последовательности. Теорема. Сумма бесконечно малой есть бесконечно малое. Теорема Произведение бесконечно малого есть бесконечно малое. Теорема о представление последовательности имеющий конечный предел. Теоремы о пределах числовых последовательностей. Теорема о пределе суммы/ Теорема о произведение пределов///
35571. Физика. Конспект лекций 1.43 MB
  Статическое электромагнитное поле электростатика Общие свойства электростатического поля Потенциал разумная выборка Поля создаваемые распределениями зарядов с хорошей симметрией Центральная сферическая симметрия. Поле создаваемое равномерно заряженной плоскостью. Поле создаваемое произвольным распределением заряда.
35572. Описание микропроцессора MC68HC908GP32 56 KB
  МК содержат на кристалле резидентное ПЗУ программ режим адресации внешней памяти у большинства моделей отсутствует. Интеграция на кристалле МК трех типов памяти: памяти программ maskROM FLASH оперативной памяти данных статическое ОЗУ и энергонезависимой памяти данных ЕЕPROM которая программируется и стирается в рабочем режиме МК под управлением программы пользователя без подключения дополнительных источников питания. В первой группе следует выделить команду пересылки данных между двумя ячейками памяти минуя регистры центрального...