Информатика и выч. техника \ Программирование

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

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

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

Скачать файл

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

Введение

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

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

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

Определение

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

Пусть $\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, |z|=0 (z = \varepsilon)$

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

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

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

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

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

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

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

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

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

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

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

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

LR-разборщик

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

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

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

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

Структура

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

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

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

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

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

Алгоритм

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

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

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

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

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

1 2 3

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

ВУЗ:

Неизвестный ВУЗ (НВ)

Предмет:

Программирование

Тип:

Курсовые работы

Категория:

Информатика и выч. техника (Технические предметы)

Размер файла:

1 Mb

Скачали: