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


 

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

26506. Образование и развитие Пятой республики во Франции. Принципы голлизма и их эволюция 52.5 KB
  Основные принципы голлизма: голлизм это своеобразная идеология национального величия; вариант гос. Экономические: жесткое регулирование планирование; налоговая политика; расширение сфер экономики; рост гос. Проект разработан рабочим комитетом из чиновников членов Гос совета во главе с Мишелем Дебре. право назначать премьерминистра и отдельных министров возвращать законопроекты передавать на референдум любой законопроект касающийся организации гос власти или одобрения международных соглашений способных затронуть деятельность...
26507. Основные этапы социально-экономического и политического развития ФРГ 99.5 KB
  Основные этапы социальноэкономического и политического развития ФРГ. Конституционное устройство ФРГ: ФРГ объединила 9 земель каждый из субъектов федерации получил право на свою конституцию представительные и административные органы свое законодательство. Осн этапы соц экон и пол разв ФРГ.23 мая1949г Основ ФРГ.
26508. Интеграционные процессы в западной Европе 1950-2000гг 48 KB
  подписан договор о создании Европейского объединения угля и стали ЕОУС Франция ФРГ Италия Бельгия Нидерланды Люксембург. в Риме подписаны договоры о создании Европейского сообщества по атомной энергии Евратом и Европейского экономического сообщества. политические цели объединение сил западноевропейского капитализма против мирового коммунистического движения соц государств национальноосвободит борьбы колониальных и зависимых стран. Правящие круги США поддерживали создание ЕЭС рассчитывая усилить экономическую базу НАТО и...
26509. Проблемы ограничения вооружения и разоружения в П. стран Европы и Америки 1970 -2000 гг 47 KB
  смягчению 2полюсности мира можно назвать взаимное истощение СССР и США. называемое окно уязвимости которое образовалось якобы в резте ракетноядерного отставания США от СССР. Рейган провозгласил своей целью измотать СССР и ослабить его эк. Бытует мнение что это был глобальный исторический блеф администрации Рейгана попытка спровоцировать СССР на разработку подобной программы.
26510. Основные этапы соц-экон. и полит. разв. стран Центр и Вост.Европы 1945-2000гг 62 KB
  было желание видеть в госве гаранта социальн.социализма оставило лицом к лицу коммунизм и либер. революции нардем социал.
26513. Основные этапы социально-экономического развития Японии 32 KB
  в руках США. цель подписание мирного договора сделанного в США и АНГ. договоры как сепаратные м у США и Я. тут же подписан договор безопасности м у Я и США.
26514. Основные этапы социально-экономического и политического развития Индии в 1950 – 2000 гг. 55 KB
  Существенным элементом внешней политики ИНК стали неприсоединение к военным блокам и стремление к консолидации молодых независимых государств. Критике подверглась позиция ИНК в социальных вопросах. В ИНК существовали различные группировки отражавшие несовпадающие интересы социальных слоев связанных с этой партией от крупных капиталистов и землевладельцев до интеллигенции мелкой буржуазии города и деревни трудящихся масс. В этом многообразии коренились и сила общенациональный авторитет ИНК и его внутренняя слабость.