Вопрос № 27

Вопрос № 26

Тип 1 — контекстно-зависимые

К этому типу относятся контекстно-зависимые (КЗ) грамматики и неукорачивающие грамматики. Для грамматики G(V_T,V_N,P, S), V=V_T∪V_N все правила имеют вид:

αAβ→αγβ, где α, β∈V*, γ∈V+, A∈VN. Такие грамматики относят к контекстно-зависимым.

α→β, где α, β∈V+, |α|≤|β|. Такие грамматики относят к неукорачивающим.

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

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

Тип 2 — контекстно-свободные

К этому типу относятся контекстно-свободные (КС) грамматики. Для грамматики G(V_T,V_N,P, S), V=V_T∪V_N все правила имеют вид:

A→β, где β∈V+ (для неукорачивающих КС-грамматик, β∈V* для укорачивающих), A∈V_N. То есть грамматика допускает появление в левой части правила только нетерминального символа.

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

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

МПА состоит из следующих элементов:

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

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

3. Лента памяти для чтения и записи, доступ к которой организован по принципу стека («последний пришел – первый ушел»). На каждом этапе доступ есть только к элементу, записанному в стек последним (вершине стека). Добавление элементов возможно только в вершину, удаление элементов возможно также только из вершины стека.

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

Текущая конфигурация МПА описывается как (a, q, b), где a – текущий символ входной ленты, q – текущее состояние головки чтения и записи, b – верхний символ магазина.

Программа для МПА состоит из команд вида

(a, q, b) ® (q ¢, b ¢, r),

где q ¢ – новое состояние головки,

b ¢ – символ, который записывается в магазин вместо символа b,

r – правило перемещения головки: если r = 1, выполнить сдвиг на одну клетку вправо, если r = 0, оставаться на месте.

Дата добавления: 2015-04-24