Восходящий грамматический разбор программ. Метод операторного предшествования
Метод операторного предшествования
Данный метод относится к классу восходящих методов синтаксического анализа. Он основан на анализе пар соседних операторов исходной программы с целью определения таких операторов в каждой паре, которые должны быть выполнены и распознаны первыми. Пример: в соответствии с правилами арифметики умножение должно выполняться раньше сложения. Для метода в этом случае говорят, что «*» предшествует «+» или «*» имеет более высокий уровень предшествия: * •> +
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 не могут быть соседними ни в одной грамматически правильной конструкции языка.
Представления отношений предшествования не являются симметричными. При практической реализации таких методов отношения между всеми парами терминальных символов описываются с помощью матрицы предшествования:
E→E+T | T
T→T*M | M
M→(E) | i
Пустая клетка соответствует 4-му случаю. Матрица предшествования обычно расширяется с помощью служебных символов, ограничивающих входную цепочку слева и справа.
Если матрица предшествования известна, то метод в целом реализуется так:
1) Во входной строке определяют самую левую подстроку α, имеющую более высокий уровень предшествования, чем соседние символы.
2) В описанной грамматике найти продукции вида A→α и заменяют цепочку α одним нетерминальным символом.
3) Построение соответствующего фрагмента дерева разбора.
4) Повторяем п.1–3, пока не будет найден разбор входной цепи или обнаружена ошибка во входной строке.
Разбор успешен, если входная цепь свёрнута до одного нетерминального символа.
Пояснение к пункту 1: на каждой итерации, за исключением первой, входная цепь – сентенциальная форма грамматики. Выделяемая подстрока α – основа сентенциальной формы. Основа определяется следующими условиями:
Пояснение к пункту 2: выбор необходимых правил вывода осуществляется с учётом структуры правой части конкретной продукции, обозначения нетерминалов при этом не учитывается т.к. нетерминальный символ в таких грамматик соответствует операндам, вся информация о которых уже сохранена в таблице трансляций, важен только факт наличия операнда, а не его обозначения. Ошибки обнаруживаются так: 1) Нельзя выделить подстроку α на первом шаге. 2) Нельзя найти правило вывода на втором шаге. 3) Во входной цепи появляется два соседних терминальных символа между которых не существует отношения предшествования
Исходники:
Опубликовал Kest
February 15 2010 11:24:58 ·
3 Комментариев ·
15197 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Oleg27 January 02 2025 08:36:45
Казино Вавада https://mIRror1xbet.com предлагает игрокам множество увлекательных игр, выгодные бонусы и сервис высокого уровня, что делает его одним из лучших решений для онлайн-азарта.
Oleg27 January 02 2025 08:39:41
Вавада – казино, которое было разработано лучшими дизайнерами и ведущими специалистами гэмблинга. Вавада онлайн казино дает возможность испытать удачу и получить большой выигрыш. Здесь каждый проведет время с пользой, наслаждаясь различными слотами с отменными показателями отдачи. Скачать казино вавада онлайн возможно прямо сейчас у нас и начать великолепный путь к успеху. Вы азартный пользователь и любите расслабляться? Тогда вы попали точно по адресу! https://1xBEtvkhod.com регулярно проводит розыгрыши джекпотов и разные турниры. Это эффективное онлайн казино с великолепным дизайном и множеством разнообразных слотов.
Преимущества вавада:
-индивидуальные вознаграждения;
-удобный интерфейс;
-быстрая техподдержка;
-наилучший сервис.
Вавада казино на реальные деньги доступно тем, кто прошел регистрацию на официальном сайте казино. Вы можете воспользоваться мобильной версией там, где есть интернет. Вавада онлайн проходите регистрацию и играйте, общайтесь, а также получайте хорошие бонусы. Многим пользователям нравится широкий ассортимент игрового софта. Остались какие-либо вопросы? Наш саппорт работает круглосуточно, задавайте вопросы, и квалифицированные специалисты помогут и подскажут вам.
Oleg27 January 02 2025 08:41:17
Я сейчас предпочитаю играть здесь https://1xBEtsayt.com Это лучшая и надежная букмекерская контора, где можно делать ставки на спорт и выигрывать реальные деньги. Важно только не спешить, анализировать и увлекаться спортом.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
