LR-анализатор. LR(k)-грамматики. Замечание о пополненной грамматике. LR-разборщик. Принцип переноса-свёртки

Страницы работы

12 страниц (Word-файл)

Содержание работы

Введение

LR-анализатор (англ. LRparser) — синтаксический анализатор для исходных кодов программ, написанных на некотором языке программирования, который читает входной поток слева (Left) направо и производит наиболее правую (Right) продукцию контекстно-свободной грамматики. Используется также термин LR(k)-анализатор, где k выражает количество непрочитанных символов предпросмотра во входном потоке, на основании которых принимаются решения при анализе.


LR(k)-грамматики

Восходящий разбор (англ. Bottom-up parsing) предназначен для построения дерева разбора. Мы можем представить себе этот процесс как "свертку" исходной строки w к стартовому нетерминалу грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки w и правой части какого-то правила грамматики, затем происходит замена этой подстроки на нетерминал, являющийся левой частью правила. Восходящий разбор менее интуитивно понятный, чем нисходящий, но зато позволяет разбирать больше грамматик.

Определение

Определение:

Пусть \Gamma =\langle \Sigma, N, E, P \rangle — контекстно-свободная грамматика. Пополненной грамматикой (англ. augmented grammar), полученной из \Gamma, назовем грамматику \Gamma' =\langle \Sigma', N', E_0, P' \rangle, где \Sigma' = \Sigma; N' = N \cup \{E_0\}; E_0 \notin N; P' = P \cup \{E_0 \to E\}

Определение:

Пусть \Gamma' =\langle \Sigma', N', E_0, P' \rangle — пополненная грамматика для КС-грамматики \Gamma. Грамматика \Gamma является LR(k)-грамматикой, если из того, что для любых двух правосторонних выводов верно, что:

§  E_0 \Rightarrow^* \beta A t z \Rightarrow \beta \alpha t z  \Rightarrow^* w, если |t|=k или |t|<k, |z|=0 (z = \varepsilon)

§  E_0 \Rightarrow^* \gamma B t z' \Rightarrow \gamma \xi t z' \Rightarrow^* w', если |t|=k или |t|<k, |z'|=0 (z' = \varepsilon)

следует, что \beta \alpha = \gamma \xi, тогда \beta = \gamma и A = B.

Говоря неформально, мы делаем правостороннюю свёртку нашей строки в стартовый нетерминал. Если по не более чем k символам неразобранной части строки мы можем однозначно определить, во что сворачивается хвост выведенного правила, то грамматика будет LR(k).

LR(k) означает, что:

§  входная цепочка обрабатывается слева направо (англ. left-to-right parse),

§  выполняется правый вывод (англ. rightmost derivation),

§  для принятия решения используется не более k символов цепочки (англ. k-token lookahead).

Замечание о пополненной грамматике

Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Действительно, если грамматика использует E в правых частях правил, то свертка основы в E не может служить сигналом приема входной цепочки. Свертка же в E_0 в пополненной грамматике служит таким сигналом, поскольку E_0 нигде, кроме начальной сентенциальной формы, не встречается.

Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Пусть пополненная грамматика имеет следующие правила:

(0)\ E_0 \to E \\ (1)\ E \to Ea \\ (2)\ E \to a \\

Если игнорировать 0-е правило, то, не заглядывая в правый контекст основы Ea, можно сказать, что она должна сворачиваться в E. Аналогично основа a безусловно должна сворачиваться в E. Создается впечатление, что данная грамматика без 0-го правила есть LR(0)-грамматика. Что на самом деле неверно, в чём можно убедиться, рассмотрев процесс LR(0)-разбор


LR-разборщик

Принцип переноса-свёртки

При LR(k)-анализе применяется метод перенос-свертка (англ. shift-reduce). Суть метода сводится к следующему:

1.  Программа анализатора читает последовательно символы входной строки до тех пор, пока не накопится цепочка, совпадающая с правой частью какого-нибудь из правил. Рассмотренные символы переносим в стек (операция перенос).

2.  Далее все символы совпадающей цепочки извлекаются из стека и на их место помещается нетерминал, находящийся в левой части этого правила (операция свертка).

Структура

Метод перенос-свертка использует следующие компоненты:

§  входная строка,

§  стек (для запоминания рассмотренных символов),

§  управляющая таблица (для выбора следующего действия — перенос или свертка),

§  автомат (для запоминания информации о текущем состоянии стека).

Алгоритм

1.  Программа читает символ из входной цепочки.

2.  Обращается к управляющей таблице.

3.  Совершает соответствующее действие.

4.  Возвращается к первому пункту, пока входная цепочка не закончится.


Программная реализация

Похожие материалы

Информация о работе

Тип:
Курсовые работы
Размер файла:
1 Mb
Скачали:
0