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


 

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

51477. Определение отклика на гармоническое воздействие 397 KB
  Определить комплексную передаточную функцию КПФ и ее составляющие: модуль Hω и аргумент θω привести полученную КПФ к общему виду КПФ для цепи первого порядка. Схема исследуемого четырехполюсника Исходные данные цепи: Ом мГн Функции воздействия: и Решение Определение комплексной передаточной функции КПФ четырехполюсника Комплексная передаточная функция записывается: По формуле чужого сопротивления находим : Отсюда = Подставим полученное выражения для в формулу нахождения КПФ: Таким образом мы привели полученную КПФ к...
51478. Определение отклика на гармоническое воздействие при подключении и отключении источника 305 KB
  В лабораторной работе определен отклик цепи при подключении и отключении источника, построены необходимые графические изображения и таблицы
51479. Определение отклика на периодическое негармоническое воздействие 346.5 KB
  Построить спектр амплитуд и спектр фаз отклика. Определить действующее и среднее значение отклика мощность выделяемую на сопротивлении нагрузки. Определение отклика цепи Определим отклик.
51480. Кинематика материальной точки 287 KB
  Рассмотрим участок АВ: Согласно II закону Ньютона При проектировании на оси координат получаем величина непостоянная а переменная то ускорение непостоянно. Получаем где выражение это определение скорости. Подставляя полученные значения в исходное выражение получаем. Интегрируем обе части выражения получаем.
51481. Динамика вращательного движения вокруг горизонтальной оси 263 KB
  Система состоящая из диска массой m и радиуса R с прикрепленными к нему тонкими стержнями общей массой m может свободно вращаться вокруг горизонтальной оси. Через обод на диске переброшена тонкая невесомая нерастяжимая нить к концам которой привязаны грузы массой каждый. На ободе диска прикреплен шарик массой пренебрежимо малого размера. На какой наибольший угол повернётся система если на один из висящих на нити грузов положить перегрузок массой .
51482. Отклонить тело из положения равновесия и написать уравнение колебаний 210.5 KB
  Найдем центры масс каждого тела отдельно а затем и всей системы: ; Центр массы стержня 1 лежит на его середине: Центр массы стержня 2 лежит на его середине: Центр массы большого диска 3 лежит в его центре а центр находится на оси OX: Центр массы большой пластины 4 лежит на пересечении ее диагоналей: Центр массы малого диска 5 лежит в его центре: Центр массы малой пластины 6 лежит на пересечении ее диагоналей: Найдем центр масс всей системы: Координаты центра масс: С0.14 Угол на который отклонится центр масс системы от нормали: где ...