Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции

• Название: Курс лекций по спецкурсу Методы трансляции
• Анкор: Курсовая Лексический анализатор
• Дата: 29.12.2019
• Размер: 0.64 Mb.
• Имя файла: Краткий курс лекций.doc
• Тип: Курс лекций; #102547
• страница: 12 из 19

Синтаксический анализ предложений для грамматик с
ограниченным контекстом

Грамматики, для которых основа в предложении определяется не более чем m символами, находящимися слева от основы, и не более чем n символами справа от основы называется грамматикой с (m,n) ограниченным контекстом. В частности, грамматики с простым предшествованием представляют собой грамматики с (1,1) ограниченным контекстом (в ходе проверки отношений рассматривается один символ слева от основы и один символ справа от неё).

Грамматики, для которых основа определяется всей находящейся слева от нее частью приводимой строки и не более, чем n расположенными справа терминальными символами, называется LR(n)-грамматикой. Для любой LR(n)-грамматики существует эквивалентная ей LR(1)-грамматика. Алгоритм грамматического разбора для LR(n)-грамматик основан на предварительном переводе грамматик на некоторый метаязык, называемый языком правил подстановки Флойда.

Правила подстановки Флойда для LR(1)-грамматик записываются в следующем формате:

M1

x1...xk

y1...ym

СП

*

M2

где

M₁ – метка правила (может отсутствовать);

x₁...x_k – образец для сравнения с частью приводимой строки. Может содержать символ – любой символ;

y₁...y_m – строка, которая заменяет часть приводимой строки x₁...x_k (может отсутствовать);

СП – имя семантической подпрограммы (может отсутствовать). Это может быть фиксация обнаруженной ошибки, выход по концу разбора и т.п.;

* – знак, предписывающий прочитать следующий символ входной строки (может отсутствовать);

M₂ – метка правила, к которому нужно перейти после успешного применения данного правила (может отсутствовать).

Грамматический разбор предложений для LR(n)-грамматик ведется с использованием стека терминальных и нетерминальных символов. Возможность применения отдельных правил подстановки Флойда определяется совпадением образца x₁...x_k из правила с k верхними символами стека.

Завершение грамматического разбора осуществляется путем вызова специальной семантической подпрограммы – «Выход». Для обеспечения автоматического вызова этой подпрограммы исходная грамматика дополняется правилом вида: Z → S┴, где S – начальный символ исходной грамматики, ┴ – ограничитель, добавляемый к входной строке.