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


 

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

68178. ДЕРЖАВНЕ РЕГУЛЮВАННЯ РОЗВИТКУ МАЛОГО ТА СЕРЕДНЬОГО ПІДПРИЄМНИЦТВА В УМОВАХ ІНФОРМАЦІЙНОГО СУСПІЛЬСТВА 185 KB
  В умовах інформаційного суспільства радикальних змін у відносинах власності проблема становлення й розвитку малого та середнього підприємництва в Україні набуває важливого значення. Актуальність теми дослідження зумовлена недостатньою теоретичною розробкою підходів до обґрунтування...
68179. Теоретико-методичні засади реалізації фізичної компоненти Державного стандарту базової середньої освіти 27.99 MB
  Загальна середня освіта протягом останніх років зазнала суттєвих змін як у напрямі законодавчого і нормативного регулювання, так і у створенні й впровадженні в освітню практику нових методичних систем і педагогічних технологій.
68180. ЗАСТОСУВАННЯ МЕТОДІВ ФІЗІОПУНКТУРИ ДЛЯ ОЦІНКИ ТА КОРЕКЦІЇ ФУНКЦІОНАЛЬНОГО СТАНУ СПОРТСМЕНІВ 322 KB
  Підвищити ефективність профілактики ризику виникнення донозологічних та патологічних станів у осіб, що знаходяться під впливом тривалих психофізичних навантажень, шляхом дослідження можливостей застосування неінвазивних методів фізіопунктури...
68181. ФОРМУВАННЯ ДОСЛІДНИЦЬКОЇ КОМПЕТЕНТНОСТІ МАЙБУТНЬОГО ВЧИТЕЛЯ ХІМІЇ В СИСТЕМІ ВИЩОЇ ОСВІТИ 322.5 KB
  Формування у випускників вищих навчальних закладів освіти вмінь та навичок дослідницької діяльності розглядаємо як одне з основних завдань підготовки майбутнього вчителя. Результати проведеного нами пілотажного дослідження показали недостатню сформованість дослідницької компетентності...
68182. ТЕОРЕТИКО-МЕТОДОЛОГІЧНІ ЗАСАДИ ЗАСТОСУВАННЯ ІННОВАЦІЙНИХ ТЕХНОЛОГІЙ У ПІДГОТОВЦІ ФАХІВЦІВ СОЦІОНОМІЧНИХ ПРОФЕСІЙ У ВИЩІЙ ШКОЛІ 801.5 KB
  Зважаючи на багатоаспектне теоретичне обґрунтування компетентнісного підходу та виокремлення різновидів професійних компетентностей у науці не запропоновано цілісного підходу до зясування та формування базових професійних компетентностей у майбутніх...
68183. Синтез робастної електромеханічної системи із розподіленими параметрами механічної частини об’єкту регулювання 821 KB
  Керування багатьма технічними обєктами і технологічними процесами здійснюється за допомогою подовжених конструкцій що звязують приводний двигун із робочим органом. При керуванні такими протяжними об’єктами необхідно враховувати власні механічні коливання обумовлені пружними властивостями...
68184. Фітоіндикація початкових етапів грунтогенезу на рекультивованих землях Нікопольського марганцеворудного басейну 2.04 MB
  Мета дослідити агроекологічні чинники формування родючості і морфологічних ознак техноземів сформованих із різних за літологічним складом розкривних гірських порід і гумусованого шару зонального ґрунту за тривалого сільськогосподарського використання рекультивованих земель в умовах...
68186. РОЗПОВСЮДЖЕННЯ ЗВУКОВИХ ІМПУЛЬСІВ У ХВИЛЕВОДАХ, ЗАПОВНЕНИХ ІДЕАЛЬНОЮ РІДИНОЮ 1.25 MB
  Наукова новизна отриманих результатів: показана можливість використання моделі нестаціонарної пружної хвилі у вигляді періодичної послідовності часових відрізків синусоїди за відсутністю або наявності частотної модуляції з метою дослідження процесу розповсюдження імпульсу у хвилеводі...