Распознаватели КС-языков

R(Q, V, Z, δ, q0, z0, F),

где Q – множество состояний автомата;

V – алфавит входных символов автомата;

– функция переходов автомата, которая отображает множество Q×(V∪{λ})×Z на конечное множество подмножеств P(Q×Z*);

q0 – начальное состояние автомата Q, q0∈Q;

F – множество конечных состояний
автомата, F⊆Q.

Z – специальный конечный алфавит магазинных символов автомата (обычно включает в себя алфавиты терминальных и нетерминальных символов грамматики), V⊆Z;

z0∈Z – начальный символ магазина;

(q, α, ω),

где q – текущее состояние автомата, q∈Q;

α – цепочка еще непрочитанных символов на входе автомата, α∈V*;

ω – содержимое магазина, ω∈Z*.

можно указать пару (β, n),
где β∈V* – вся цепочка входных символов,
n∈N∪{0}, n>0 –положение считывающего
указателя в цепочке

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

Допускаются λ-переходы (λ-такты), при которых входной символ игнорируется (он будет входным символом при следующем переходе).

Автомат не обязательно должен извлекать символ из магазина (при z=λ этого не происходит).

МП-автомат является детерминированным, если из одной и той же его конфигурации возможен не более чем один переход в следующую конфигурацию.

Не для каждого МП-автомата можно
построить эквивалентный ему
детерминированный МП-автомат

Начальная конфигурация МП-автомата: (q0, α, z0), α∈V*;
множество конечных конфигураций – (q, λ, ω), q∈F, ω∈Z*.

МП-автомат допускает (принимает) цепочку символов, если, получив эту цепочку на вход, он может перейти в одну из конечных конфигураций (при окончании цепочки автомат находится в одном из конечных состояний, а стек содержит некоторую определенную цепочку) – тогда входная цепочка принимается (после окончания цепочки автомат может сделать произвольное количество λ-переходов), иначе цепочка символов не принимается.

Расширенный МП-автомат может заменять цепочку символов конечной длины в верхней части стека на другую цепочку символов конечной длины.

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

два варианта реализации:

на каждом шаге работы алгоритм должен запоминать все возможные следующие состояния МП-автомата, выбирать одно из них, переходить в это состояние и действовать так до тех пор, пока либо не будет достигнуто конечное состояние автомата, либо автомат не перейдет в такую конфигурацию, когда следующее состояние будет не определено (если достигнуто одно из конечных состояний, то входная цепочка принята, работа алгоритма завершается, иначе алгоритм должен вернуть автомат на несколько шагов назад, когда еще был возможен выбор одного из набора следующих состояний, выбрать другой вариант и промоделировать поведение автомата с этим условием; алгоритм завершается с ошибкой, когда все возможные варианты работы автомата будут перебраны и ни одно из возможных конечных состояний не было достигнуто) – является наиболее распространенным (называется «разбор с возвратами»);

Время выполнения данного алгоритма
имеет экспоненциальную зависимость
от длины входной цепочки символов.
Необходимый объем памяти имеет
линейную зависимость от длины
входной цепочки символов.

Время выполнения данного алгоритма
имеет линейную зависимость
от длины входной цепочки символов.
Необходимый объем памяти имеет
экспоненциальную зависимость от длины
входной цепочки символов.

Другая особенность в моделировании МП-автомата заключается в том, что алгоритм моделирования работы произвольного МП-автомата в общем случае может не завершиться за конечное число шагов (успешно или неуспешно) – даже после считывания всей входной цепочки символов МП-автомат может совершить произвольное (в том числе и бесконечное) число λ-переходов (если цепочка не принята, это может привести к бесконечному количеству шагов моделирующего алгоритма, который по этой причине никогда не будет закончен).

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

Экспоненциальная зависимость вычислительных затрат
от длины входной почки существенно ограничивает
применимость алгоритмов разбора с возвратами.
Они тривиальны в реализации, но имеют неудовлетворительные
характеристики, поэтому могут использоваться
только для простых КС-языков с малой длиной
входных предложений языка и в реальных компиляторах не применяются.
Для многих классов КС-языков существуют
более эффективные алгоритмы распознавания.

Начальная конфигурация: (q, α, S) – автомат пребывает в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов α∈VT*, в стеке лежит символ, соответствующий целевому символу грамматики S.

Конечная конфигурация: (q, λ, λ) – автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, стек пуст.

Функция переходов МП-автомата строится на основе правил грамматики:
(q, α)∈δ(q, λ, A), A∈VN, α∈(VT∪VN)*, если A→α ∈Р грамматики G;
(q, λ)∈δ(q, a, a) ∀a∈VT.

если на верхушке стека автомата находится символ А∈VN

то А можно заменить на цепочку символов α (если в грамматике языка есть правило A→α) и СГ не сдвигается – этот шаг работы называется «подбор альтернативы»

всеесли

если на верхушке стека находится символ а∈VТ: а=тек_сим_вх_цеп

то а можно выбросить из стека и передвинуть СГ→1 – этот шаг работы называется «выброс».

всеесли

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

Данный МП-автомат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида A→α, следовательно, тогда функция δ(q, λ, A) будет содержать более одного следующего состояния – у автомата будет несколько альтернатив.

Недостаток алгоритма нисходящего разбора с возвратами – значительная временная емкость, так как имеется экспоненциальная зависимость необходимых для работы алгоритма вычислительных ресурсов от длины входной цепочки.

Преимущества данного алгоритма:

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

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

Сам по себе алгоритм разбора с подбором альтернатив,
использующий возвраты, не находит применения
в реальных компиляторах, но его основные принципы
лежат в основе многих нисходящих распознавателей,
строящих левосторонние выводы и
работающих без использования возвратов.

Этот алгоритм может быть напрямую использован для построения распознавателей, но исходная грамматика не должна быть леворекурсивной.

Символ A∈VN в КС-грамматике G(VT, VN, P, S)
называется рекурсивным, если для него существует
цепочка вывода вида А⇒+αАβ, где α, β∈(VT∪VN)*:
если α=λ и β≠λ, то рекурсия называется левой, а грамматика G – леворекурсивной;
если α≠λ и β=λ, то рекурсия называется правой, а грамматика G – праворекурсивной;
если α=λ и β=λ, то рекурсия представляет собой цикл.

Начальная конфигурация: (q, α, λ) – автомат пребывает в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов α∈VT*, стек пуст.

Конечная конфигурация: (q, λ, S) – автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, в стеке лежит символ, соответствующий целевому символу грамматики S.

Функция переходов МП-автомата строится на основе правил грамматики:
(q, А)∈δ(q, λ, γ), A∈VN, γ∈(VT∪VN)*, если A→γ ∈Р грамматики G;
(q, a)∈δ(q, a, λ) ∀a∈VT.

если на верхушке стека автомата находится цепочка символов γ

то γ можно заменить на А∈VN (если в грамматике языка есть правило A→γ) и СГ не сдвигается – этот шаг работы называется «свертка»

всеесли

если СГ обозревает тек_сим_вх_цеп а∈VТ

то а можно поместить в стек и передвинуть СГ→1 – этот шаг работы называется «сдвиг» или «перенос».

всеесли

На каждом шаге работы автомата необходимо решать:
что необходимо выполнять: сдвиг или свертку;
если выполнять свертку, то какую цепочку γ
выбрать для поиска правил
(цепочка γ должна встречаться в правой части правил грамматики);
какое правило выбрать для свертки, если окажется,
что существует несколько правил вида А→γ
(несколько правил с одинаковой правой частью).
Чтобы промоделировать работу этого
расширенного МП-автомата, надо на каждом шаге
запоминать все предпринятые действия, чтобы
иметь возможность вернуться к уже сделанному шагу
и выполнить эти же действия по-другому.
Этот процесс должен повторяться до тех пор,
пока не будут перебраны все возможные варианты.

Этот алгоритм может быть напрямую использован для построения распознавателей, но исходная грамматика не должна допускать циклов и не должна содержать λ-правил (грамматику необходимо предварительно преобразовать к приведенной форме).

Недостаток алгоритма восходящего разбора с возвратами – значительная временная емкость, так как имеется экспоненциальная зависимость необходимых для работы алгоритма вычислительных ресурсов от длины входной цепочки.

Преимущества данного алгоритма:

простота реализации – практически его использовать только тогда, когда известно, что длина исходной цепочки символов заведомо не будет большой (не больше нескольких десятков символов);

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

Сам по себе алгоритм «сдвиг-свертка»,
использующий возвраты, не находит применения
в реальных компиляторах, но его основные принципы лежат
в основе многих восходящих распознавателей,
строящих правосторонние выводы
и работающих без использования возвратов.

Принцип работы заключается в следующем:
искомая цепочка вывода строится не сразу – сначала на основе входной цепочки порождается некоторое промежуточное хранилище информации объема n*n (промежуточная таблица), а потом уже на его основе строится вывод.

Табличные алгоритмы обладают полиномиальными характеристиками требуемых вычислительных ресурсов в зависимости от длины входной цепочки.
Для произвольной КС-грамматики G(VT, VN, P, S) время выполнения алгоритма имеет кубическую зависимость от длины входной цепочки символов, а необходимый объем памяти – квадратичную зависимость от длины входной цепочки символов (она напрямую связана с использованием промежуточного хранилища данных).

самые эффективные универсальные алгоритмы для распознавания цепочек КС-языков с точки зрения требуемых вычислительных ресурсов
(несмотря на это они не находят широкого применения, поскольку полиномиальная зависимость требуемых вычислительных ресурсов от длины входной цепочки символов является неудовлетворительной для компиляторов, поэтому практически всегда используются не универсальные, а более узкие, специализированные алгоритмы распознавателей, которые имеют обычно линейную зависимость требуемых вычислительных ресурсов от длины входной цепочки символов, а к универсальным алгоритмам прибегают только тогда, когда специализированный распознаватель построить не удается).

алгоритм Эрли.

Для однозначных КС-грамматик алгоритм Эрли
имеет квадратичную зависимость времени
выполнения от длины входной цепочки символов,
а для некоторого класса КС-грамматик – линейную
(но для этих классов обычно существуют
более простые алгоритмы распознавания);
также он является более сложным в реализации.

распознаватели с возвратами имеют экспоненциальную зависимость требуемых для выполнения алгоритма разбора вычислительных ресурсов от длины входной цепочки символов;

табличные распознаватели имеют полиномиальную зависимость требуемых для выполнения алгоритма разбора вычислительных ресурсов от длины входной цепочки символов.

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

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

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

Распознаватели КС-языков без возвратов

Нисходящие распознаватели – порождают цепочки левостороннего вывода и строят дерево вывода сверху вниз – используют модификации алгоритма с подбором альтернатив и при их создании применяются методы, которые позволяют однозначно выбрать одну и только одну альтернативу на каждом шаге работы МП-автомата (шаг «выброс» в этом автомате всегда выполняется однозначно);

К этому классу относятся:

распознаватель на основе метода рекурсивного спуска;

распознаватель на основе LL(k)-грамматики;

распознаватель на основе LL(1)-грамматики.

КС-грамматика обладает свойством LL(k), k>0,
если на каждом шаге вывода для однозначного выбора
очередной альтернативы МП-автомату достаточно знать
символ на верхушке стека и рассмотреть первые k символов
от текущего положения считывающей головки
во входной цепочке символов.
LL – left – цепочка читается слева направо,
left – вывод левосторонний

К этому классу относятся:

распознаватель на основе LR(k)-грамматики;

распознаватель на основе LR(0)-грамматики;

распознаватель на основе LR(1)-грамматики;

распознаватель на основе грамматик предшествования.

КС-грамматика обладает свойством LR(k), k≥0,
если на каждом шаге вывода для однозначного
решения вопроса о выполняемом действии в алгоритме
«сдвиг-свертка» расширенному МП-автомату достаточно
знать содержимое верхней части стека и
рассмотреть первые k символов от текущего
положения считывающей головки во входной цепочке символов.
LR – left – цепочка читается слева направо,
right – вывод правосторонний

В процессе анализа входной цепочки расширенный МП-автомат сравнивает текущий символ входной цепочки с одним из символов, находящихся на верхушке стека, проверяя, какое из возможных отношений предшествования существует между ними, и в зависимости от найденного отношения выполняется либо сдвиг (перенос), либо свертка, а при отсутствии его – алгоритм сигнализирует об ошибке.

Распознаватель на основе грамматик предшествования

простого предшествования;

расширенного предшествования;

слабого предшествования;

смешанной стратегии предшествования;

операторного предшествования.

для каждой упорядоченной пары терминальных и нетерминальных символов выполняется не более чем одно из трех отношений предшествования:

Fi=.Fj
(∀Fi, Fj∈V), если и только если ∃ правило A→xFiFjy∈P, где A∈VN, x, y∈V*;

Fi<.Fj
(∀Fi, Fj∈V), если и только если ∃ правило A→xFiDy∈P и вывод D⇒*Fjz,
где A, D∈VN, x, y, z∈V*;

Fi.>Fj
(∀Fi, Fj∈V), если и только если ∃ правило A→xCFjy∈P и вывод C⇒*zFi,
или ∃ правило A→xCDy∈P и выводы C⇒*zFi и D⇒*Fjw, где A, C, D∈VN,
x, y, z, w∈V*;

различные порождающие правила имеют разные правые части.

Распознаватель на основе грамматик предшествования

Отношение предшествования единственно для каждой упорядоченной пары символов, если между какими-либо двумя символами нет отношения предшествования, значит, они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки.

Отношения предшествования зависят от порядка, в котором стоят символы, например, если Fi.>Fj, то не обязательно, что Fi<.Fj.
(поэтому знаки предшествования иногда помечают специальной точкой)

Fi=.Fi+1,
если символы Fi и Fi+1 принадлежат одной основе – «составляют основу»;

Fi<.Fi+1,
если символ Fi+1 есть крайний левый символ некоторой основы –
«предшествует основе»;

Fi.>Fi+1,
если символ Fi есть крайний правый символ некоторой основы – «следует за основой».

Исходя из этих соотношений, выполняется разбор строки для грамматики предшествования.

знак отношений

Для удобства построения матрицы предшествования грамматики используются два дополнительных множества:

множество крайних левых и множество крайних правых символов относительно нетерминальных символов грамматики, которые определяются как:

L(А)={Х| ∃ А⇒*Хz}, А∈VN, Х∈V, z∈V* – множество крайних левых символов относительно нетерминального символа А (цепочка z может быть и пустой цепочкой);

R(А)={Х| ∃ А⇒*zХ}, А∈VN, Х∈V, z∈V* – множество крайних правых символов относительно нетерминального символа А.

Fi=.Fj (∀Fi, Fj∈V), если ∃ правило A→xFiFjy∈P, где A∈VN, x, y∈V*;

Fi<.Fj (∀Fi, Fj∈V), если ∃ правило A→xFiDy∈P и Fj∈L(D), где A, D∈VN, x, y∈V*;

Fi.>Fj (∀Fi, Fj∈V), если ∃ правило A→xCFjy∈P и Fi∈R(C)
или ∃ правило A→xCDy∈P и Fi∈R(C), Fj∈L(D), где A, C, D∈VN, x, y∈V.

Распознаватель на основе грамматик предшествования

⊥н<.Х, ∀ Х∈V, если ∃ S⇒*Хy, где S∈VN, y∈V* или если Х ∈L(S);

⊥к.>Х, ∀ Х∈V, если ∃ S ⇒*yХ, где S∈VN, y∈V* или если Х ∈R(S).

Матрица предшествования служит для работы распознавателя языка, заданного грамматикой простого предшествования.

Данный алгоритм выполняется расширенным МП-автоматом с одним состоянием.
Отношения предшествования служат для того, чтобы определить в процессе выполнения алгоритма, какое действие – сдвиг или свертка – должно выполняться на данном шаге и однозначно выбрать правило при свертке (обеспечивается за счет различия правых частей всех правил грамматики).

Выполнение алгоритма может быть прервано, если на одном из его шагов возникнет ошибка
(ситуация, когда невозможно выполнить очередной шаг, например, не установлено отношение предшествования между двумя сравниваемыми символами или не удалось найти нужное правило для свертки).
Тогда входная цепочка не принимается.

не всякий детерминированный КС-язык может быть задан грамматикой простого предшествования, и поэтому не для каждого детерминированного КС-языка можно построить распознаватель по методу простого предшествования;

при большом количестве терминальных и нетерминальных символов в грамматике матрица предшествования будет иметь значительный объем (значительная часть ячеек которой может оставаться пустой), а следовательно, ухудшится временная характеристика распознавателя.

Грамматика операторного предшествования это операторная КС-грамматика G(VT, VN, P, S), V=VT∪VN, в которой:

для каждой упорядоченной пары терминальных символов выполняется не более чем одно из трех отношений предшествования:

a=.b, если и только если ∃ правило А→xaby∈P
или правило А→xaCby, где a, b∈VT, А, C∈VN, x, y∈V*;

a<.b, если и только если ∃ правило A→xaCy∈P и вывод C⇒*bz
или вывод C⇒*Dbz, где a, b∈VT, A, C, D∈VN, x, y, z∈V*;

a.>b, если и только если ∃ правило A→xCby∈P и вывод C⇒*za
или вывод C⇒*zaD, где a, b∈VT, A, C, D∈VN, x, y, z∈V*;

различные порождающие правила имеют разные правые части.

вторые (правые) терминальные символы

знак отношений

Для построения матрицы предшествования вводятся множества:

множество крайних левых и множество крайних правых терминальных символов относительно нетерминальных символов грамматики, которые определяются как:

Lt(А)= {t | ∃ А⇒*tz или ∃ А⇒*Ctz},
где t∈VT, А, C∈VN, z∈V*;

Rt(А)= {t | ∃ А⇒*zt или ∃ А⇒* ztC},
где t∈VT, А, C∈VN, z∈V*.

a=.b, если ∃ правило А→xaby∈P или правило А→xaCby, где a, b∈VT, А, C∈VN, x, y∈V*;

a<.b, если ∃ правило А→xaCy∈P и b∈Lt(C), где a, b∈VT, А, C∈VN, x, y∈V*;

a.>b, если ∃ правило А→xCby∈P и a∈ Rt(C), где a, b∈VT, А, C∈VN, x, y∈V*.

Предварительно необходимо выполнить построение множеств L(А) и R(А).

⊥н<.a, ∀ a∈VT, если ∃ S⇒*ax или ∃ S⇒*Cax, где S, C∈VN, x∈V*
или если a∈Lt(S);

⊥к.>a, ∀ a∈VT, если ∃ S⇒*xa или ∃ S⇒*xaC, где S, C∈VN, x∈V*
или если a∈Rt(S).

Матрица операторного предшествования служит для работы распознавателя языка, заданного грамматикой операторного предшествования.

Системное программное обеспечение

Распознаватели КС-языков

Распознаватель на основе грамматик предшествования

Схема алгоритма распознавания
для грамматики операторного предшествования

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

Далее строятся множества крайних левых и крайних правых символов L(А), R(А) относительно всех нетерминальных символов грамматики.

S

T

E

S

T

E

, E

(, a, b

, a

, T

T

(

)

T, E, (, a, b

, a

, b

, b

), a, b

E, ), a, b

S, T, E

T, E

(, a, b

), a, b

T, E, (, a, b

E, ), a, b

S, T, E , (, a, b

T, E, ), a, b

P:
S→S+T1|S-T2|T3
T→T*E4|T/E5|E6
E→(S)7|a8|b9

+

+

*

*

, -

+ , -, *, /, (, a, b

(

, /

, a

)

, -

, /

, a

, b

, b

+ , -, *, /, ), a, b

*, /, (, a, b

*, /, ), a, b

(, a, b

), a, b

крайние левые терминальные символы

<.

<.

<.

<.

<.

.>

.>

.>

.>

.>

.>

.>

=.

<.

<.

<.

<.

<.

<.

<.

.>

.>

.>

.>

.>

.>

.>

P:
F→F+F 1|F-F 2|F 3
F→F*F 4|F/F 5|F 6
F→(F)7|a8|b9

P:
F→F+F 1|F-F 2
F→F*F 3|F/F 4
F→(F)5|a6|b7

F→F

Это преобразование не ведет к созданию эквивалентной грамматики и выполняется только после построения всех множеств и матрицы предшествования. Само преобразование выполняется только с целью более эффективного выполнения алгоритма разбора, в который уже заложены необходимые данные о порядке применения правил при создании матрицы предшествования.

Построенная таким образом грамматика называется остовная грамматика, а вывод, полученный при разборе на основе этой грамматики – остовным выводом.

В остовном выводе отсутствуют шаги,
связанные с применением цепных правил,
и не учитываются типы нетерминальных символов,
что сокращает длину цепочки вывода
и размер дерева вывода.

При распознавании исходной цепочки символов последовательность разбора будем записывать в виде последовательности конфигураций расширенного МП-автомата из следующих элементов:

не просмотренная автоматом часть входной цепочки символов;

содержимое стека;

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

Такт автомата обозначен символом ÷:
если на данном такте выполняется сдвиг (перенос) – ÷сд, если свертка – ÷св.

сд

крайние правые терминальные символы (вх.цепочка)

крайние левые терминальные символы (стек)

{-b/a⊥к; ⊥нa; ∅}÷

cв

{-b/a⊥к; ⊥нF; 6}÷

сд

{b/a⊥к; ⊥нF-; 6}÷

сд

{/a⊥к; ⊥нF-b; 6}÷

cв

{/a⊥к; ⊥нF-F; 6, 7}÷

сд

{a⊥к; ⊥нF-F/; 6, 7}÷

сд

{⊥к; ⊥нF-F/a; 6, 7}÷

св

{⊥к; ⊥нF-F/F; 6, 7, 6}÷

св

{⊥к; ⊥нF-F; 6, 7, 6, 4}÷

св

{⊥к; ⊥нF; 6, 7, 6, 4, 2}

– разбор закончен, цепочка принята.

Цепочка вывода (правосторонний вывод):
F⇒2F-F⇒4 F-F/F⇒ 6 F-F/a⇒ 7 F-b/a⇒ 6 a-b/a.

крайние левые терминальные символы (стек)

Входная цепочка: (a-b)/a.

{(a-b)/a⊥к; ⊥н; ∅}÷

сд

{a-b)/a⊥к; ⊥н(; ∅}÷

сд

{-b)/a⊥к; ⊥н(a; ∅}÷

св

{-b)/a⊥к; ⊥н(F; 6}÷

сд

{b)/a⊥к; ⊥н(F-; 6}÷

сд

{)/a⊥к; ⊥н(F-b; 6}÷

св

{)/a⊥к; ⊥н(F-F; 6, 7}÷

св

{)/a⊥к; ⊥н(F; 6, 7, 2}÷

сд

{/a⊥к; ⊥н(F); 6, 7, 2}÷

св

{/a⊥к; ⊥нF; 6, 7, 2, 5}÷

сд

{a⊥к; ⊥нF/; 6, 7, 2, 5}÷

сд

{⊥к; ⊥нF/a; 6, 7, 2, 5}÷

св

{⊥к; ⊥нF/F; 6, 7, 2, 5, 6}÷

св

{⊥к; ⊥нF; 6, 7, 2, 5, 6, 4}

– разбор закончен, цепочка принята.

Цепочка вывода (правосторонний вывод):
F⇒4F/F⇒6F/a⇒5(F)/a⇒2(F-F)/a⇒7(F-b)/a⇒6(a-b)/a.

Матрица предшествования

крайние правые терминальные символы (вх.цепочка)

крайние левые терминальные символы (стек)

Входная цепочка: a-b/.

{ a-b/⊥к; ⊥н; ∅}÷

сд

{-b/⊥к; ⊥нa; ∅}÷

cв

{-b/⊥к; ⊥нF; 6}÷

сд

{b/⊥к; ⊥нF-; 6}÷

сд

{/⊥к; ⊥нF-b; 6}÷

cв

{/⊥к; ⊥нF-F; 6, 7}÷

сд

{⊥к; ⊥нF-F/; 6, 7}÷

cв

Ошибка! – нет правила для выполнения свертки на этом такте.

объединения;

конкатенации;

итерации;

гомоморфизма (изменения имен символов).

Произвольные КС-языки не замкнуты относительно операций:

пересечения;

дополнения.

Детерминированные КС-языки (КС-языки, цепочки которых можно распознавать с помощью детерминированных МП-автоматов) замкнуты относительно операции:

дополнения.

Детерминированные КС-языки не замкнуты относительно операций:

объединения;

пересечения.

Выделяются две основные цели преобразований КС-грамматик:

упрощение правил грамматики;

облегчение создания распознавателя языка.

это преобразования, связанные с исключением из грамматики тех правил и символов, без которых она может существовать;

это преобразования, в результате которых изменяется вид и состав правил грамматики, при этом грамматика может дополняться новыми правилами, а ее словарь нетерминальных символов – новыми символами.

заранее определенный вид правил грамматики
позволяет упростить работу с языком,
заданным этой грамматикой, и облегчает
создание распознавателей для него

Всегда в результате преобразований получается новая КС-грамматика, эквивалентная исходной, то есть определяющая тот же самый язык.

Так как не всегда эти две цели можно совместить,
то в случае с языками программирования
(когда итогом работы с грамматикой
является создание компилятора языка)
вторая цель преобразования является основной
и упрощениями правил пренебрегают,
если при этом удается упростить
построение распознавателя языка.