Исключение цепных правил
| Определение. Правило грамматики вида <A> ®
<B>, где <A>,<B> ОVA, |
| Утверждение. Для КС-грамматики Г, содержащей цепные правила , можно построить эквивалентную ей грамматику Г', не содержащую цепных правил. |
Идея доказательства заключается в следующем. Если схема грамматики имеет вид
R = {...,<A> ®
<B>,...,<B> ®
<C>, ... , <C> ® a<X>
},
то такая грамматика эквивалентна грамматике со схемой
R' = {...,<A> ®
a<X>,...},
поскольку вывод в грамматике со схемой R цепочки a<X> :
<A> Ю<
B> Ю <C>
Ю a<X>
может быть получен в грамматике со схемой R' с помощью правила <A>
® a<X>.
В общем случае доказательство последнего утверждения можно выполнить так.
Разобьем R на два подмножества R1 и R2, включая в R1 все правила вида <A> ® < B>.
Для каждого правила из R1 найдем множество правил S(<Ai>), которые строятся так:
если <Ai> Ю
* <Aj> и в R2 есть правило <Aj>
® a
, где a - цепочка словаря (Vт
ИVA)* ,
то в S(<Ai>) включим правило <Ai> ® a .
Построим новую схему R' путем объединения правил R2 и всех построенных
множеств S(<Ai>). Получим грамматику Г' = {Vт ,Va , I , R'}, которая эквивалентна
заданной и не содержит правил вида <A> ®
<B>.
В качестве примера выполним исключение цепных правил из грамматики
Г1. 9
со схемой :
Г1. 9:
R={<E> ® <E> + <T> | <T>,
< T> ® < T> * <F> | <F>,
<F> ® ( <E> ) | a}.
Вначале разобьем правила грамматики на два подмножества:
R1 = { <E> ®
<T>,<T> ® <F> } ,
R2 = { <E> ®
<E>+<T>, <T> ®
<T>*<F>, <F>® (<E>) | a }
Для каждого правила из R1 построим соответствующее подмножество.
S(<E>) = { <E> ®<
T>*<F>, <E> ® (<E>) | a },
S(<T>) = { <T> ®
(<E>) | a}
В результате получаем искомую схему грамматики без цепных правил в виде:
R2 U S(<E>) U S(<T>) = { <E> ®
--> <T>+<T> | <T>*<F> | (<E>) | a,
<T> ®
<T>*<F> | (<E>) | a,
<F> ®
(<E>) | a }
Последний вид рассматриваемых преобразований связан с удалением из
грамматики правил с пустой правой частью.
|
Определение. Правило вида <A> ® $ называется аннулирующим правилом. |
След.Страница Раздел Содержание
Исключение леворекурсивных правил
| Определение. Правило вида <A> ® a <A>
, где A О VA , a О(Vт ИVA) * , называется праворекурсивным, а правило вида <A> ® <A>a - леворекурсивным. |
| Утверждение. Для каждой КС-грамматики Г, содержащей леворекурсивные правила, можно построить эквивалентную грамматику Г', не содержащую леворекурсивных правил. |
Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика Г содержит
правила:
<A> ®
<A>a 1 | <A>a
2 | ... |<A>a m| ,
где ни одна цепочка b не начинается с <A>
и a1, b1О(Vт ИVA) * .
Введем новый нетерминал <A'> и преобразуем правила так:
<A> ®
b 1 | b
2 |...| b n | b
1<A'> | b 2<A'>|...| b n<A'>,
<A'> ®a
1 | a 2 |...| a
m| a 1<A'> |a
2<A'>|...|a m<A'>.
Заменяя все правила с левой рекурсией в Г описанным способом, получим грамматику Г',
причем L(Г)=L(Г') , поскольку каждая цепочка, выведенная в грамматике Г, может быть
построена в грамматике Г'. Рассмотрим построение выводов в Г и Г'. В грамматике Г вывод
цепочки имеет вид:
< A> Ю <A>a 1 Ю
<A>a 1a
1 Ю <A>a 1a
1a 1 Ю b 1a
1a 1a
1,
в грамматике Г' эта же цепочка выводится так:
<A> Ю
b 1<A'> Ю
b 1a 1<A'>
Ю b
1a 1a
1<A'> Ю
b 1a
1a 1a
1.
Чтобы показать технику преобразования, рассмотрим пример. Требуется преобразовать
грамматику Г1. 9 (рассмотренную ранее), которая задана схемой:
Г1. 9: R={<E> ® <E> + <T> | <T>,
< T> ® <T> * <F> | <F>,
<F> ® ( <E> ) | a}.
Следуя описанному способу, правила <E>
® <E> + <T> | <T> преобразуем в правила
<E>®
<T> | <T><E'> и <E'> ®
+<T> | +<T><E'> , а правила <T> ®
<T> * <F> | <F> преобразуем в правила <T>
® <F> | <F><T'> и <T'> ® *<
F> | * <F><T'>.
В результате получаем грамматику Г'1. 9, имеющую схему:
Г'1. 9 : R'= { <E> ®
< T>,
<E> ®
<T><E'>,
< E'>® + <T>,
<E'> ® + <T><E'>,
<T> ®
<F>,
<T> ®
<F><T'>,
<T'> ® * <F>,
<T'> ® * <F><T'>,
< F> ® a,
<F> ®
(<E>) },
не содержащую леворекурсивных правил.
Пред.Страница
След.Страница Раздел Содержание
Язык, допускаемый магазинным автоматом
| Определение. Цепочка a
называется допустимой для автомата М, если существует последовательность конфигураций, в которой первая конфигурация является начальной c цепочкой a , а последняя - заключительной. (sо, a, hо) |--* (s1, $ , $) , где s1 О F . |
| Определение.Множество цепочек, допускаемых автоматом М, называется языком, допускаемым или определяемым автоматом М, и обозначается L(М). |
L(М)= {a ¦ ( sо, a, hо ) ¦--* ( s', $, $) & s' О F }
Чтобы лучше представить себе работу магазинного автомата, рассмотрим два примера. Пусть задан магазинный автомат М1 в следующем виде:
М1: P = {a , b}; S = {s0 , s1 , s2}; H = {h0 , a}; F = {s0};
f (s0 , a , h0) = (s1 , h0a),
f (s1 , a , a) = (s1 , aa),
f (s1 , b , a) = (s2 , $),
f (s2 , b , a) = (s2 , $),
f (s2 , e
, h0) = (s0 , $).
Этот автомат является детерминированным, поскольку каждому набору аргументов соответствует единственное значение функции. Работу автомата при распознавании входной цепочки aabb можно представить в виде последовательности конфигураций:
(s0,aabb,h0) |-- (s1,abb,h0a) |-- (s1,bb,h0aa) |-- (s2,b,h0a) |-- (s2,$,h0) |-- (s0,$,$) .
Нетрудно проверить, что при задании входной цепочки aabbb автомат не сможет закончить работу. Следовательно эта цепочка не принадлежит языку, допускаемому автоматом M1.
Магазинный автомат М2, заданный следующим описанием:
М2: P = {a , b}; S = {s0, s1 , s2}; H = {h0, a , b}; F = {s2};
(1)f (s0 , a , h0) = (s0, h0a),
(2)f (s0 , b , h0) = (s0, h0b),
(3) f (s0 , a , a) = {(s0,aa) , (s1 , $)},
(4) f (s0 , b , a) = (s0,ab),
(5) f (s0 , a , b) = (s0 , ba),
(6) f (s0 , b , b) = {(s0 , bb) , (s1 , $)},
(7) f (s1 , a , a) = (s1, $),
(8) f (s1 , b , b) = (s1, $),
(9) f (s2 , e
, h0) = (s2 , $),
является недетерминированным автоматом, поскольку одному и тому же набору аргументов, например (sо , a, a), соответствуют два значения функции.
Работу автомата рассмотрим для входной цепочки abba. Если использовать последовательность команд (1),(4),(6.1),(5), то получим последовательность конфигураций:
(s0,abba,h0) |-- (s0,bba,h0a), (1)
|-- (s0,ba,h0ab), (4)
|-- (s0,a,h0abb), (6.1)
|-- (s0,$,h0abba). (5),
которая показывает, что дальнейшая работа невозможна, т.к. входная цепочка прочитана и переход (s0,$,h0abba) не определен. Если же использовать последовательность команд (1),(4),(6.2),(3),(9), то получим заключительную конфигурацию:
(s0,abba,h0) |-- (s0,bba,h0a), (1)
|-- (s0,ba,h0ab), (4)
|-- (s1,a,h0a), (6.2)
|-- (s1,$,h0), (3)
|-- (s2,$,$) . (9).
Т.о. можно сделать вывод о том, что цепочка abba допускается автоматом М2.
В общем случае справедливо следующее утверждение.
Пред.Страница
След.Страница Раздел Содержание
Магазинные автоматы
КС-грамматика определяет структуру цепочек и позволяет строить цепочки определенного языка. Магазинные автоматы, подобно рассмотренным ранее конечным автоматам, позволяют решать для контекстно-свободных языков задачу распознавания, которая заключается в том, что по заданной цепочке необходимо определить принадлежит ли она заданному языку.
В работах, связанных с формальными языками и грамматиками,используется модель магазинного автомата, состоящая из входной ленты, устройства
управления и вспомогательной ленты, называемой магазином
разделяется на клетки (позиции) , в каждой из которых может быть
записан символ входного алфавита. При этом предполагается, что в неиспользуемых клетках входной ленты расположены пустые символы e.
Вспомогательная лента также разделена на клетки, в которых могут располагаться символы магазинного алфавита. Начало вспомогательной ленты называется дном
магазина. Связь устройства управления с лентами осуществляется двумя головками, которые могут перемещаться вдоль лент.
Головка входной ленты может перемещаться только в одну сторону - вправо или
оставаться на месте. Она может выполнять только чтение. Головка вспомогательной ленты способна выполнять как чтение, так и запись, но эти операции связаны с перемещением головки определенным образом:
- при записи головка предварительно сдвигается на одну позицию вверх, а затем символ заносится на ленту,
- при чтении символ, находящийся под головкой считывается с ленты, а затем головка сдвигается на одну позицию вниз,т.о.головка всегда установлена против последнего записанного символа. Позицию, находящуюся в рассматриваемый момент времени под головкой, называют
вершиной магазина.
| Определение.Магазинный автомат М определяется следующей совокупностью
семи объектов: M={P , S , sо , f , F , H , hо }, |
где
P - входной алфавит,
S - алфавит состояний,
sо - начальное состояние,
sо О S ,
F - множество конечных состояний ,F является подмножеством S,
H - алфавит
магазинных символов, записываемых на вспомогательную ленту,
hо- маркер дна, он всегда записывается на дно магазина , hо О H,
f - функция переходов
f : {P И {e
}} x S x H ® S x H* ,
если М-автомат - детерминированный, и
f:{P И {e
}} x S x H ® M(S x H*) ,
если М-автомат - недетерминированный. Функция f отображает тройки ( pi , sj , hk ) в пары ( sr , u
) , где u О
H* и hk - символ в вершине магазина, для детерминированного автомата или в множество пар для недетерминированного автомата.
Эта функция описывает изменение состояния магазинного автомата, происходящее при чтении символа с входной ленты и премещении входной головки.
В дальнейшем при построении магазинных автоматов потребуются две разновидности функций переходов, изменяющих состояние автомата без перемещения входной головки: 1) функция переходов с пустым символом в качестве входного символа:
f0( s, e, h) = ( s', b),
которая, независимо от того какой символ находится под читаюшей гловкой входной ленты, предписывает прочитать символ h
из вершины магазина, изменить состояние автомата на s' и записать цепочку
b в магазин.
2)функция переходов с определенным входным символом:
f*( s, a, h) = ( s', b),
которая предписывает изменение состояния и запись цепочки в магазин при условии, что символ a читается входной головкой, а в вершине магазина находится символ h .
Пред.Страница
След.Страница Раздел Содержание
Определение непроизводящих символов
Рассматривая правила грамматики, можно сделать вывод, что если все символы правой части являются производящими, то производящим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов в следующем виде:
1. Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов.
2. Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части.
3. Если на шаге 2 список больше не пополняется, то получен список всех производящих нетерминалов грамматики, а все нетерминалы не попавшие в него являются непроизводящими.
Анализируя в соответствии с приведенными правилами следующую грамматику :
Г2. 0: R = {<I>®a<I>a,
<I>®b<A>d,
<I>®c,
<A>®c<B>d,
<A>®a<A>d,
<B>®d<A>f },
находим, что здесь непроизводящими являются символы <А> и <В>. После удаления правил, содержащих непроизводящии символы, получаем:
R' = {<I> ®a<I>a, <I>® c}.
Пред.Страница
След.Страница Раздел Содержание
Определения бесполезных символов
Бесполезный символ грамматики можно определить следующим образом:
| Определение. Символ X, который принадлежит VтU Va называется бесполезным
в |
Исключить бесполезные символы из грамматики можно удаляя правила, содержащие вначале непроизводящие, а затем недостижимые символы. В качестве иллюстрации применения приведенных правил выполним преобразование следующей грамматики:
Г2. 2 : R = {<I>®ac,
<I>® b<A>,
<A>® c<B><C>,
<B>® a<I><A>,
<C>® bc,
<C>® d }.
Вначале находим, что <А> и <В> являются непроизводящими символами и, исключая правила с непроизводящими символами , получаем:
R' = {<I>®ac,
<C>® bc,
<C>® d }.
В полученной схеме символ <C> является недостижимым символом. Исключая правила, содержащие этот символ, получаем:
R" = {<I>®ac }.
| Определение. КС-грамматика называется приведенной, если она не содержит бесполезных символов. |
В дальнейшем изложении рассматриваются только
приведенные КС-грамматики. Другие виды преобразований грамматик, описываемые ниже, предназначены для исключения правил определенного вида из схемы грамматики.
Пред.Страница
След.Страница Раздел Содержание
Определения недостижимых символов
| Определение. Символ X
О VтИ VA называется недостижимым в КС-грамматике Г, если X не появляется ни в одной выводимой цепочке. |
Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так:
Образовать одноэлементный список, состоящий из начального символа
Если найдено правило, левая часть которого уже имеется в списке, то включить в список все символы, содержащиеся в его правой части.
Если на шаге 2 новые нетерминалы в список больше не добавляются, то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми.
Например, применяя приведенные правила к следующей грамматике:
Г2. 1 : R = { <I> ®a<I>b,
<I> ®c,
<A>
®b<I>,
<A>
®a },
находим, что A является недостижимым символом.
Пред.Страница
След.Страница Раздел Содержание
Построение магазинного автомата
| Утверждение. Если Г = { Vт
, Va , I , R } является КС-грамматикой, то по ней можно построить такой магазинный автомат М, что L(M) = L(Г). |
В основе доказательства лежит способ построения магазинного автомата по заданной КС-грамматике.Чтобы сделать процесс построения автомата более простым и наглядным, условимся использовать магазинные автоматы с одним состоянием s0. Итак, пусть задана грамматика Г = { Vт , Va , I , R }. Определим компоненты автомата М следующим образом: S = { s0 }, P = Vт , H = VтИ VaИ { h0} , F = { s0 },
в качестве начального состояния автомата примем s0 и построим функцию переходов так:
1. Для всех A О
VA , таких что встречаются в левой части правил
<A> ® a
, построим команды вида:
f0( s 0 , e
, <A> ) = ( s0 , aR
),
где aR
-зеркальное отображение a
.
2. Для всех a ОVт
построим команды вида
f ( s0 , a , a ) = ( s0 , $ )
3. Для перехода в конечное состояние построим команду
f ( s0 , e , h0 ) = ( s0 , $ )
4. Начальную конфигурацию автомата определим в виде:
( s0 , w , h0<I> ),
где w - заданная цепочка, записанная на входной ленте.
Автомат, построенный по приведенным выше правилам, работает следующим образом. Если в вершине магазина находится терминал, и символ, читаемый с входной ленты, совпадает с ним, то по команде типа (2) терминал удаляется из магазина, а входная головка сдвигается. Если же в вершине магазина находится нетерминал, то выполняется команда типа (1), которая вместо терминала записывает в магазин цепочку, представляющую собой правую часть правила грамматики. Следовательно, автомат, последовательно заменяя нетерминалы, появляющиеся в вершине магазина, строит в магазине левый вывод входной цепочки, удаляя полученные терминальные символы, совпадающие с символами входной цепочки. Это означает, что каждая цепочка, которая может быть получена с помощью левого вывода в грамматике Г, допускается построенным автоматом М.
Пред.Страница
След.Страница Раздел Содержание
Преобразование неукорачивающих грамматик
| Определение. Грамматика называется неукорачивающей
или грамматикой без аннулирующих правил, если либо $, где <I> - начальный символ грамматики, и символ I не встречается в правых частях остальных правил грамматики. |
Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.
| Утверждение. Для каждой КС-грамматики Г', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику Г, такую что L(Г')=L(Г). |
Построение неукорачивающей грамматики предполагает увеличение числа правил заданной
грамматики путем построения дополнительных правил, получаемых в результате исключения
нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо
выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики. Если же в грамматике есть правило вида <I> ®
$ и символ <I> входит в правые части других правил грамматики, то следует ввести новый начальный символ <I'> и заменить правило <I> ®
$ двумя новыми правилами: <I'> ®
$ и <I'>®
<I> .
В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие правила из следующей грамматики:
Г2. 3 : R = { <I> ®
a<I>b<I>,
<I> ® b<I>a<I>,
Пример построения автомата
Процедуру построения автомата рассмотрим на примере грамматики:
Г1. 9: R={<E> ®<E> + <T> | <T>,
<T> ® <T>
* <F> | <F>,
<F> ®
( <E> ) | a}.
Для искомого автомата имеем:
M3: P = {a, + , * , ) , ( }, H = {E , T , F , a , + , x , ) , h0 , ( }, S = {s0 }, F = {s0}
Для всех правил грамматики строим команды типа (1):
(1) f0
(s0 , e , E) = {(s0 , T+E) ; (s0 , T)},
(2) f0
(s0 , e , T) = {(s0 , F*T) ; (s0 , F)},
(3) f0
(s0 , e , F) = {(s0 , )E( ) ; (s0 , a)},
Для всех терминальных символов строим команды типа (2):
(4) f ( s0, a, a ) = ( s0, $ ),
(5) f ( s0 , + , + ) = (s0 , $ ),
(6) f ( s0 , * , * ) = (s0 , $ ),
(7) f ( s0 , ( , ( ) = (s0 , $ ),
(8) f ( s0 , ) , ) ) = (s0 , $ ),
Для перехода в конечное состояние построим команду:
(9) f (s0 , e
, h0) = ( s0 , $ ).
Построенный автомат является недетерминированным.
Начальную конфигурацию с цепочкой a + a*a запишем так: (s0 , a+a*a , h0E).
Последовательность тактов работы построенного автомата, показывающая, что заданная цепочка допустима, имеет вид:
(s0 , a+a*a , h0E) |-- (s0 , a+a*a , h0T+E) |--
(s0 , a+a*a , h0T+T) |-- (s0 , a+a*a , h0T+F) |--
(s0 , a+a*a , h0T+a) |-- (s0 , +a*a , h0T+) |--
(s0 , a*a , h0T) |-- (s0 , a*a , h0F*T) |--
(s0 , a*a , h0F*F) |-- (s0 , a*a , h0F*a) |--
(s0 , *a , h0F* ) |-- (s0 , a , h0F) |--
(s0 , a , h0a) |-- (s0 , $ , h0) |--
(s0 , $ , $).
Отметим, что последовательность правил, используемая построенным автоматом, соответствует левому выводу входной цепочки:
E Ю E+T Ю T+T Ю
F+T Ю a+T Ю a+T*F Ю a+F*F Ю a+a*F Ю a+a*a.
Если по такому выводу строить дерево, то построение будет происходить
сверху вниз, т.е. от корня дерева к листьям.
Такой способ построения дерева по заданной цепочке называется нисходящим.
Магазинные автоматы называют часто распознавателями, поскольку они определяют, является ли цепочка, подаваемая на вход автомата, допустимой или нет, и следовательно, отвечают на вопрос, принадлежит ли эта цепочка языку, пораждаемому грамматикой, использованной для построения автомата.
Учитывая характер построения вывода в магазине, автоматы рассмотренного типа называют нисходящими распознавателями.
Еще раз подчеркнем , что доказательство допустимости цепочки нисходящим магазинным автоматом ( НМА) предусматривает поиск определенной последовательности конфигураций.
Такой поиск может существенно увеличить время работы автомата. Детерминированные автоматы не требуют поиска и работают быстрее, поэтому именно такие автоматы применяются на практике. Детерминированные автоматы-распознаватели могут быть построены не для всех, а только для некоторых видов КС-грамматик.
|
Определение. Если язык L допускается детерминированным М-автоматом , то он называется детерминированным языком. |
Учитывая значение детерминированных автоматов для практических применений, посвятим им последующие разделы.
Пред.Страница
След.Страница Раздел Содержание
Приведенные грамматики
Из четырех типов грамматик контекстно-свободные грамматики являются наиболее важными с точки зрения приложений к языкам программирования и компиляции. С помощью КС-грамматики можно определить большую часть структуры языка программирования. При построении грамматик, задающих конструкции языков программирования, часто приходится прибегать к их преобразованию, чтобы порождаемый язык приобрел нужную структуру, поэтому вначале рассмотрим несколько достаточно простых, но важных преобразований КС-грамматик. Первый вид преобразования связан с удалением из грамматики бесполезных символов. Бесполезные символы в грамматике могут оказаться в следующих случаях: а) если символ не может быть получен при выводе,
б) если из символа не может быть получена конечная терминальная цепочка (получается бесконечная цепочка или нет правил,приводящих к терминальной цепочке).
Вначале рассмотрим алгоритм выявления символов, из которых нельзя вывести конечные
цепочки.
Пред.Страница След.Страница Раздел Содержание
Работа магазинного автомата
Чтобы описать как работает автомат, введем понятие конфигурации.
| Определение. Конфигурацией автомата М называют тройку (s, a , g )
О S x P* x H* , |
где s - текущее состояние управляющего устройства,
a -неиспользованная часть входной цепочки a
О P* ,самый левый символ этой цепочки a находится под головкой. Если a =e , то считается, что входная цепочка прочитана.
g -цепочка , записанная в магазине, g
О H* ,самый правый символ цепочки считается вершиной магазина. Если g=
$ , то магазин пуст.
Работа автомата может быть представлена как смена конфигураций. Один такт работы автомата заключается в определении новой конфигурации по заданной. Это записывается так:
( s, aa , g h ) |-- ( s', a , gb )
При этом предполагается, что автомат читает символ a, находящийся под головкой, и символ h,
находящийся в вершине магазина, определяет новое состояние s'
и записывает цепочку b
в
магазин вместо символа h. Если b =$ , то верхний символ оказывается удаленным из магазина.
Такая смена конфигураций возможна, если функция f( s, a, h ) определена и ей принадлежит
значение ( s', b ).
Описанный такт работы выполняется с перемещением головки. Для описания работы автомата нам потребуется другой вид такта, предполагающий изменение состояний и магазина без перемещения входной головки. Если f0(s, e, h) определена и ей принадлежит значение (s', b )
, то он определяет смену конфигураций так:
( s, aa , g
h ) |-- ( s', aa , gb )
Таким образом, могут быть три случая при работе автомата:
f(s, a, h) определена и выполняется такт работы,
f(s, a, h) не определена, но определена функция f0(s, e, h) и выполняется пустой такт.
Функции f(s, a, h) и f0(s, e, h)
не определены, в этом случае дальнейшая работа автомата невозможна.
В общем виде действия, задаваемые функцией переходов и выполняемые автоматом, демонстрирует следующая форма записи:
f(s, <входной символ>, <магазинный символ>)=(s1, <заносимая цепочка>)
При этом следует иметь в виду, что при выполнении такта вначале читается символ в вершине, а затем на его место заносится новый символ или цепочка. Отдельные значения функции переходов часто называют командами магазинного автомата.
Начальной конфигурацией называется конфигурация (sо, a
, hо) , где sо
-начальное состояние и hо
- маркер дна магазина, а заключительной - конфигурация (s, $ , $) , где s принадлежит множеству конечных состояний F.
Для обозначения последовательности сменяющих друг друга конфигураций условимся
использовать знак |--*. Таким образом последовательность
( s1, a 1, g
1 ) |-- ( s2, a 2, g 2) |-- ...|-- ( sn, a n,g
n )
записывается в сокращенном виде так:
(s1,a
1, g 1 ) |--* ( sn, a n,g
n ).
Пред.Страница
След.Страница Раздел Содержание
свободные языки являются более сильным
Контекстно- свободные языки являются более сильным выразительным средством, чем автоматные языки, которые являются подмножеством КС-языков. КС-грамматики, предназначенные для практических применений, не должны содержать бесполезных символов. Такие грамматики называются приведенными. КС-грамматики допускают преобразования, результатом которых может быть исключение цепных, аннулирующих или леворекурсивных правил. Задачу распознавания для КС-языков решают магазинные преобразователи. В общем случае для любой КС-грамматики можно построить магазинный распознаватель, допускающий язык, который порождается заданной грамматикой. Однако, такой распознаватель может оказаться недетерминированным. Работа недетерминированного распознавателя связана с поиском последовательности конфигураций, показывающей допустимость входной цепочки. Поиск увеличивает время работы автомата, поэтому для практических применений предпочитают использовать детерминированные автоматы.
Пред.Страница
След.Страница Раздел Содержание
в следующей грамматике, и, если
1) Определите, есть ли бесполезные символы в следующей грамматике, и, если они есть,постройте приведенную грамматику
Г2. 4
: R = {<I>®
<A> | <B>,
<A>®
a<B> | b<I> | b,
<B>®
<A><B> | <B>a,
<B>®
<A><I> | b }.
2) Постройте для заданной грамматики эквивалентную ей неукорачивающую грамматику.
Г2. 5: R = {<I> ®
<A><B><C> ,
<A>®
<B><B> | $ ,
<B> ®<C><C>
| a ,
<C>®
<A><A> | b}.
3) Для заданной грамматики постройте эквивалентную грамматику без цепных правил.
Г2. 6: R = {<I> ®
a<M> ,
<M>®<A>
,
<A> ®
a<A> | <B> ,
<B> ®
b<B> | b}
4) По заданной грамматике постройте грамматику без леворекурсивных правил.
Г2. 7 : R = {<I> ®
a<A> ,
<I> ®
<I>c ,
<I> ®
<A>b ,
<A>®
d }.
5) Проверьте, являются ли цепочки aaabb и aabbaa допускаемыми автоматом М2.
6) Постройте последовательность конфигураций распознавателя М3 для цепочки (a+a) и левый вывод этой цепочки. Сравните содержимое магазина и промежуточные результаты вывода.
7) Постройте магазинные распознаватели для следующих грамматик и проверьте их работу .
а) Г2. 8 : R = {<I> ®
<A><I> | b , <A> ®
<I><A> | a}.
б) Г2. 9 : R = {<I> ®
<A><I> | a , <A> ®
<B><A> | b , <B> ®
<A>a}.
Пред.Страница
След.Страница Раздел Содержание
Функции ПЕРВ, СЛЕД и множество ВЫБОР
Множество ВЫБОР строится для каждого правила и включает те терминальные символы, при появлении которых под читающей головкой распознаватель должен применять это правило.
Для определения множества ВЫБОР
используются функции ПЕРВ и СЛЕД . Аргументом функции ПЕРВ
может быть любая цепочка полного словаря µ, а значением функции ПЕРВ(µ) является множество терминальных символов, которые могут стоять на первом месте в цепочках, выводимых из цепочки µ.
Пред.Страница
След.Страница Раздел Содержание
Исключение леворекурсивных правил
Возможность построения для LL(1) грамматики детерминированного автомата определяет значение этих грамматик для практических применений. Однако, при построении грамматики для заданного языка не всегда удается получить грамматику, принадлежащую классу LL(1). Это может случиться потому, что неудачно выбраны правила грамматики, или потому, что для заданного языка принципиально нельзя построить LL(1) грамматику. В первом случае полученную грамматику можно попытаться преобразовать таким образом, чтобы она удовлетворяла условиям LL(1) грамматики. Известно несколько приемов преобразований, которые в некоторых случаях, но не всегда, позволяют получить грамматику требуемого вида.
Первый вид преобразований заключается в исключении правил, содержащих левую рекурсию. Необходимость исключения таких правил можно показать с помощью следующих рассуждений.
Допустим, что в схеме заданной грамматики имеются правила: <A>
® <B>
| <A><B>. Первое условие определения LL(1) грамматики говорит о том, что функции ПЕРВ для правил с одинаковой левой частью не должны иметь одинаковых элементов, но для заданной грамматики это не так, поскольку
ПЕРВ(<A><B>) = ПЕРВ(<A>) = ПЕРВ(<B>).
Следовательно, грамматика, содержащая рассматриваемые правила, не является LL(1) грамматикой.
Возьмем другие правила, обеспечивающие получение такого же множества цепочек, что и в первом случае : <A> ®
<A><B> | $.
Первое условие выполняется, но имеем:
СЛЕД ( <A> ) = ПЕРВ (<B>) и ПЕРВ (<A>) = ПЕРВ (<B>),
поскольку A можно заменить $.
Эти равенства показывают, что нарушается второе условие из определения LL(1) грамматики.
Из приведенных рассуждений можно сделать вывод о том, что LL(1) грамматика не должна содержать леворекурсивных правил. Конечно, лучше не использовать леворекурсивные правила еще на этапе построения грамматики, но если уж они появились, то их можно исключить, пользуясь приемом, описанным в предыдущем разделе.
Пред.Страница
След.Страница Раздел Содержание
LL( - грамматики
Разделенные и слаборазделенные грамматики представляют собой подклассы грамматик более общего вида, которые называются LL(1) грамматиками, и которые определяются следующим образом.
| Определение. КС-грамматика является LL(1) грамматикой тогда и только тогда, когда выполняются следующие два условия: 1 . Для каждого нетерминала, являющегося левой частью нескольких правил: <A> ®a 1 | a 2 | ... | a n, i) и ПЕРВ(a j) было |
Из определения следует, что грамматики LL(1), в отличие от разделенных грамматик и слаборазделенных, могут содержать правила, начинающиеся нетерминальными символами. Проверим относится ли рассмотренная ранее грамматика Г43 к классу LL(1).
Для этого необходимо вначале проверить наличие одинаковых значений функций ПЕРВ для правил с одинаковой левой частью. Для правил (1) и (2) имеем
ПЕРВ(<B><C>a) = ПЕРВ(<B>) И
ПЕРВ(<C>) = {a,b,d,c},
ПЕРВ(g<D><B>) = {g},
а для правил (5) и (6) имеем
ПЕРВ(<D>a<B>) = ПЕРВ(<D>) И
ПЕРВ(a<B>) = {a,d},
ПЕРВ(ca) = {c}.
Полученные результаты показывают, что первое условие LL(1) грамматики выполняется.
Второе условие необходимо проверить для правил (3) и (7) рассматриваемой грамматики. Вычисляя функции ПЕРВ и СЛЕД для правила (8), имеем:
ПЕРВ(<B>) = {b} и СЛЕД(<B>) = {a,c,d,g,f}.
Эти функции не имеют одинаковых значений, следовательно грамматика Г43
является грамматикой LL(1).
Рассматриваемый класс грамматик можно определить также с помощью множеств выбора следующим образом:
| Определение . КС-грамматика называется LL(1) грамматикой тогда и только тогда, когда множества ВЫБОР, построенные для правил с одинаковой левой частью, не содержат одинаковых элементов. |
Пред.Страница
След.Страница Раздел Содержание
LR(k)-грамматики
Детерминированные восходящие распознаватели, так же как и нисходящие, могут быть построены не для всякой КС-грамматики, а только для определенных подклассов таких грамматик. Наиболее широким подклассом КС-грамматик являются LR(k)-грамматики. Эти грамматики обеспечивают распознавание цепочки при просмотре слева направо, об этом говорит буква L (Left) в названии грамматики, и позволяют выполнить правостороннее сворачивание, это показывает буква R (Right) в названии. Параметр k говорит о том, что для определения того правила грамматики, которое нужно применить для сворачивания цепочки, потребуется просмотреть не более k еще не прочитанных символов входной цепочки.
В общем случае алгоритмы построения распознавателей дл LR(k)-грамматик оказываются достаточно сложными и трудоемкими, поэтому на практике чаще всего используют подклассы LR(k)-грамматик: LR(0), или SLR(1)—простые (Simple) LR(1)-грамматики, позволяющие относительно просто выполнять построение восходящих распознавателей. При этом для каждого подкласса LR(k)-грамматик используется свой алгоритм построения. Если задана КС-грамматика, то определить ее принадлежность к одному из подклассов грамматик LR(k) можно только путем анализа возможности построения для нее с помощью определенного алгоритма детерминированного распознавателя. Учитывая последнее обстоятельство, условимся называть распознаватели по подклассу соответствующих грамматик: LR(0)-распознаватель или SLR(1)-распознаватель.
Прежде чем перейти к рассмотрению правил построения восходящих распознавателей, введем несколько вспомогательных понятий.
Условимся называть символы полного словаря грамматики грамматическими символами. Каждый грамматический символ может входить в разные правила грамматики и, более того, появляться в одном и том же правиле несколько раз. При этом положение символа в правиле грамматики может показывать, какое действие нужно выполнить: перенос или свертку, а также какие грамматические символы могут за ним следовать.
Это обстоятельство позволяет связать позицию грамматического символа в правиле грамматики с понятием состояния распознавателя. Для удобства дальнейших рассуждений введем понятие грамматического вхождения.
| Определение.Грамматическое вхождение символа грамматики задается номером правила и номером позиции, которая указывает место символа в правой части правила, полагая, что самый левый символ правой части правила является первым. |
Пред.Страница
След.Страница Раздел Содержание
Построение функции СЛЕД(<B>)
Аргументом функции СЛЕД является нетерминальный символ, например <B>, а значение функции СЛЕД(<B>) представляет собой множество терминалов, которые могут следовать непосредственно за нетерминалом <B> в цепочках, выводимых из начального символа грамматики.
Вычисление значения функции СЛЕД(<B>) должно выполняться по следующим правилам:
1) Если в схеме грамматики имеются правила вида <X1> ®
µ1<B>a1, <X2> ®
µ2<B>a2, ... , <Xn>
® µn<B>an,
и все цепочки a i
=/= $ , то СЛЕД(<B>) = ПЕРВ(a
1) И
ПЕРВ(a 2) И
... И
ПЕРВ(a n).
2) Если же среди приведенных выше правил имеется хотя бы одна цепочка ai = $, например пусть a1
= $, то функция вычисляется так: СЛЕД(<B>) = СЛЕД(<X1>) И
ПЕРВ(a 2) И
... И
ПЕРВ(a n).
Выполним вычисление функции СЛЕД для нетерминалов грамматики Г3.2
. Вначале определим функцию для нетерминала <A>, который встречается в правой части правила (9).
СЛЕД(<A>) = ПЕРВ(f) = {f}.
Нетерминал <C> входит в правые части правил (1) и (4), учитывая также, что нетерминал <D> являетя анулирующим, получаем: СЛЕД(<C>) = ПЕРВ(<D>) И
ПЕРВ(<E>) ИПЕРВ(c) = {c,d,g}.
Нетерминал <B> входит в правые части правил (1), (2), (5), поэтому имеем: СЛЕД(<B>) =ПЕРВ(<C>c) И
СЛЕД(<A>) И
СЛЕД(<C>),
подставляя в полученное выражение значения функций, входящих в правую часть, получаем: СЛЕД(<B>) = { a, c, d, }И
{ f } И
U { c, d, g, } = { a, c, d, g, f }.
Для нетерминала <D> , который входит в правила (2), (4) , (5) и (8), с учетом того, что нетерминал <B> является аннулирующим, получаем: СЛЕД(<D>) =ПЕРВ(<B>) И
СЛЕД(<A>) И
ПЕРВ(<E>) И
ПЕРВ(a<B>),
учитывая, что , для нетерминала <E>, входящего в правило (4)
СЛЕД(<E>) = СЛЕД(<B>) = {a,d,c,g,f},
окончательно имеем:
СЛЕД(<D>) = ПЕРВ(<B>)И
СЛЕД(<A>) ИПЕРВ(<E>) И
{a} =
= {b}И
{f} И
{c,g} И
{a} = {a,b,c,g,f}.
Пред.Страница
След.Страница Раздел Содержание
Построение магазинного автомата
Для грамматик, удовлетворяющих условиям LL(1) грамматик, справедливо следующее утверждение.
| Утверждение. Для каждой LL(1) грамматики Г можно построить детерминированный магазинный автомат М , допускающий язык, порождаемый заданной грамматикой: L ( Г ) = L ( М ). |
Задача построения магазинного автомата для заданной LL(1) грамматики формулируется следующим образом.
Задана грамматика Г = {Vт,Va, I, R}, и требуется определить
об'екты, определяющие автомат М = { P , S , s0
, F , H , h0 , f }.
Учитывая, что автомат должен допускать цепочки языка, порождаемого заданной грамматикой, примем P = Vт. Чтобы упростить описание автомата, допустим, что он имеет одно состояние s0, которое является и начальным и заключительным, то есть - S = {s0}и F = {s0}.
В качестве магазинного алфавита примем следующее объединение: H = {Vт И
Va И
{h0}}.
Построение функции переходов выполним с использованием множеств ВЫБОР правил заданной грамматики следующим образом:
1 ) Для каждого правила грамматики, начинающегося терминальным символом вида
<A> ®
b a, построим команду автомата
f ( s0 , b , <A> ) = ( s0
, a
' ) ,
где a
' является зеркальным отображением цепочки
a .
2) Для каждого правила грамматики, начинающегося нетерминальным символом вида
<A>
® <B>
a, построим команду автомата f* ( s0 , x , <A> ) = ( s0
, <B> a
' )
где f* - команда автомата без сдвига входной головки, а a
' является зеркальным
отображением цепочки a
.
Количество команд, которые необходимо построить для заданного правила, определяется числом элементов множества ВЫБОР.
Команды магазинного автомата, работающие без сдвига входной головки, выполняют замену нетерминаала, соответствующего левой части правила, цепочкой, соответствующей правой части этого правила. В этом случае сопоставление терминального символа, получаемого при выводе, и очередного символа входной цепочки не производится, поэтому для таких команд сдвиг входной головки не нужен.
3) Для каждого аннулирующего правила грамматики вида
<A>
® $
построим команды автомата
f* ( s0 , x , <A> ) = ( s0
, $ )
для каждого элемента x из множества ВЫБОР(<A>
® $). Количество таких команд определяется числом элементов множества ВЫБОР.
4) Для каждого терминального символа b, расположенного в середине или на конце правых
частей правил грамматики, построим команду
f ( s0 , b , b ) = ( s0
, $ ).
5) Для перехода в заключительное состояние построим команду
f* ( s0 , e
, h0 ) = ( s0 , $ , $ ).
В качестве начальной конфигурации автомата условимся использовать следующее выражение с заданной входной цепочкой µ :
(s0,µ,h0<I>).
Пользуясь приведенными правилами, построим магазинный автомат для грамматики Г12, схема которой в символических обозначениях может быть записана так
Г3. 5
: R = {<A>
® x | (<B>),
<B>
® <A> <C>,
<C>
® +<A> <C>
| $}.
Вначале построим множества ВЫБОР для каждого из правил и проверим, является ли эта грамматика LL(1) грамматикой. (1) ВЫБОР(<A> ®x) = ПЕРВ(x) = {x}
(2) ВЫБОР(<A> ®
((<B>))) = ПЕРВ((<B>)) = {(}
Построение множества ВЫБОР
Множество ВЫБОР, которое потребуется нам для построения переходов магазинных автоматов,можно определить с помощью функций ПЕРВ и СЛЕД следующим образом: 1) Если правило грамматики имеет вид <B>
- > a и
a не является аннулирующей цепочкой, другими словами не существует вывод a
==>*$, то
ВЫБОР(<B> ®
a ) = ПЕРВ( a ).
2) Для аннулирующих правил грамматики вида <B> ®$, мно-
жество выбора определяется так
ВЫБОР(<B>
® $) = СЛЕД(<B>).
3) Если правило грамматики имеет вид <B> ® µ и µ
яв-
ляется аннулирующей цепочкой, то
ВЫБОР(<B>
® µ) = ПЕРВ(µ) И
СЛЕД(<B>).
Для рассматриваемой грамматики Г3.2 множества ВЫБОР для каждого из правил, построенные описанным выше способом, имеют вид:
ВЫБОР(<A> ®
<B><C>c) = ПЕРВ(<B><C>c) = {a,b,c,d},
ВЫБОР(<A> ®
g<D><B>) = ПЕРВ(g<D><B>) = {g},
ВЫБОР(<B> ®
$) = ПЕРВ($) И
СЛЕД(<B>) = {a,c,d,g,f},
ВЫБОР(<B> ®
b<C><D><E>) = ПЕРВ(b<C><D><E>) = {b},
ВЫБОР(<C> ®
<D>a<B>) = ПЕРВ(<D>a<B>) = {a,d},
ВЫБОР(<C> ®
ca) = ПЕРВ(ca) = {a},
ВЫБОР(<D> ®
$) = ПЕРВ($) И
СЛЕД(<D>) = {a,b,c,g,f},
ВЫБОР(<D> ®
d<D>) = ПЕРВ(d<D>) = {d},
ВЫБОР(<E> ®
g<A>f) = ПЕРВ(g<A>f) = {g},
ВЫБОР(<E> ®
c) = ПЕРВ(c) = {c}.
Пред.Страница
След.Страница Раздел Содержание
Преобразование грамматик к виду LL(
Пример работы расширенного магазинный автомат
В качестве иллюстрации работы расширенного автомата рассмотрим автомат, допускающий язык L={wwR | w О {a, b}*}.
M7.1: P = {a, b}, S = {s0, s1}, H = {a, b, <I>, h0}, F = {s1} ,
d(s0, a, h0) = (s0, h0a), d(s0, a, <I>) = (s0, <I>a),
d(s0, b, h0) = (s0, h0b), d(s0, b, <I>) = (s0, <I>b),
d(s0, a, a) = (s0, aa), d*(s0, a, a<I>a) = (s0, <I>),
d(s0, b, a )= (s0, ba), d*(s0, b, a<I>a) = (s0, <I>),
d(s0, a, b) = (s0, ab), d*(s0, a, b<I>b) = (s0, <I>),
d(s0, b, b) = (s0, bb), d*(s0, b, b<I>b) = (s0, <I>),
d*(s0, a, aa) = (s0, <I>), d*(s0, $, a<I>a) = (s0, <I>),
d*(s0, b, aa) = (s0, <I>), d*(s0, $, b<I>b) = (s0, <I>),
d*(s0, a, bb) = (s0, <I>), d*(s0, $, h0<I>) = (s1, $).
d*(s0, b, bb) = (s0, <I>),
Это недетерминированный автомат. Если на входе задана цепочка abba, то его работу можно представить в виде следующего ряда конфигураций:
| № | Вход | Магазин | Состояние | ||||
| 1. | abba|- | h0 | s0 | ||||
| 2. | bba|- | h0a | s0 | ||||
| 3. | ba|- | h0ab | s0 | ||||
| 4. | a|- | h0abb | s0 | ||||
| 5. | a|- | h0a<I> | s0 | ||||
| 6. | |- | h0a<I>a | s0 | ||||
| 7. | |- | h0<I> | s1 |
Пред.Страница
След.Страница Раздел Содержание
Распознаватели и LL(K) - грамматики
Моделирование работы недетерминированных магазинных
распознавателей связано с поиском последовательности переходов из начального в одно из конечных состояний. Поиск состоит из отдельных шагов, каждый из которых может окончиться неудачно и привести к возврату в исходное состояние для выполнения следующего шага. Такой поиск с возвратом связан со значительными затратами времени, поэтому на практике используют более экономичные детерминированные распознаватели, работающие без возвратов. Эти распознаватели допускают только ограниченные классы КС-языков, которые однако отражают все синтаксические черты языков программирования.
Распознаватели можно разделить на две категории: нисходящие и восходящие. Каждая категория характеризуется порядком, в котором располагаются правила в дереве вывода. Нисходящие распознаватели обрабатывают правила сверху вниз, верхние правила раньше нижних, в то время как восходящие анализаторы используют нижние правила раньше тех, что расположены выше. Чтобы показать возможности детерминированных автоматов и способы их построения, в настоящем разделе рассматриваются нисходящие распознаватели, допускающие языки, порождаемые грамматиками вида LL(K).
| Определение. В общем случае грамматика относится к классу LL(K) грамматик, если для нее можно построить нисходящий детерминированный распознаватель, учитывающий K входных символов, расположенных справа от текущей входной позиции. |
Название LL произошло от слова Left, поскольку анализатор просматривает входную цепочку слева-направо , и слова Leftmost, поскольку он обнаруживает появление правила по одному или группе символов, образующих левый край цепочки. На практике наибольшее применение имеет класс LL(1) грамматик, для которых детерминированный распознаватель работает по дному входному символу, расположенному в текущей позиции. В качестве первого шага изучения нисходящих распознавателей рассмотрим их построение для одного из подклассов LL(1) грамматик.
Пред.Страница
След.Страница Раздел Содержание
Распознавателя
Способ построения распознавателя предусматривает сопоставление каждому правилу грамматики команды распознавателя .
Согласно общему способу построения распознавателей для КС-грамматик, описанному в предыдущем разделе, каждому правилу разделенной грамматики, которые имеют вид:
<A> ® a a , где a
- цепочка символов полного словаря и a принадлежит
терминальному словарю, нужно поставить в соответствие команду
(*) f 0( s0 , e , <A> ) = ( s0
, a
' a) ,
которая задает такт работы без сдвига входной головки и в которой
a ' представляет собой зеркальное отображение цепочки a
. Отметим, что в результате выполнения этой команды, в вершине магазина окажется терминал a. Общий способ построения редусматривает также построение для каждого a
символа грамматики команды:
(**)
f ( s0 , a , a ) = ( s0 , $ )
которая удаляет этот терминал из магазина и сдвигает входную головку.
Учитывая, что в разделенной грамматике каждое правило начинается с терминального символа, и что эти терминалы не повторяются, можно сделать вывод о том , что команда (*) должна выполняться только в том случае, когда под входной головкой находится терминал
a, и после нее всегда должна выполняться команда (**).
Чтобы исключить неопределенность правил вида (*) и уменьшить число тактов работы распознавателя, объединим команды вида (*) и (**) в одну команду. Построение такой команды должно выполняться следующим образом: каждому правилу разделенной грамматики <A> ® a a
поставим в соответствие команду
f ( s0 , a , <A>) = ( s0 , a
') ,
которая определяет такт работы распознавателя со сдвигом входной головки.
Кроме того, следует учесть, что терминальные символы могут быть расположены в правых частях правил не только на самой левой позиции. Для таких терминалов необходимо построить команды вида :
f ( s0 , b , b ) = ( s0
, $ )
Для перехода в заключительное состояние добавим правило:
f ( s0 , $ ,h0 ) = ( s1 , $ ) ,
а в качестве начальной конфигурации распознавателя примем, как
обычно, следующее выражение :
( s0 , a
, h0<I> ) ,
где <I> - начальный символ грамматики, а a - заданная входная цепочка.
Применяя приведенные выше правила, построим распознаватель для разделенной грамматики
Г3. 0
. В результате получаем: М 4 : P = { a , b }, H = { a , b ,<I> , <B> , h0 }, S = {s0}, F= {s0},
f ( s0 , a , <I>) = ( s0
, <B>b )
f ( s0 , a , <B>) = ( s0
, $ )
f ( s0 , b , <I> ) = ( s0
, <I> b <B> )
f ( s0 , b , <B> ) = ( s0
, <B> )
f ( s0 , b , b ) = ( s0
, $ )
f ( s0 , e
, h0 ) = ( s0 , $ )
Работу построенного автомата покажем на примере анализа цепочки bbabab.
( s0 , bbababa , h0<I> ) |---
( s0 , bababa , h0<I>b<B> ) |---
( s0 , ababa , h0<I>b<B> ) |---
( s0 , baba , h0<I>b ) |---
( s0 , aba , h0<I> ) |---
( s0 , ba , h0<B>b ) |---
( s0 , a , h0<B> )
|--- ( s0 , $ , h0
) |--- ( s0 , $ , $ ) .
Приведенная последовательность конфигураций показывает, что в каждой конфигурации может быть применена единственная команда детерминированного распознавателя.
Пред.Страница
След.Страница Раздел Содержание
Расширенный магазинный автомат
Рассмотренный пример показывает, что автомат, выполняющий операцию свертки, в отличие от нисходящего распознавателя, не строит в магазине вывод цепочки, начиная с аксиомы грамматики, который соответствует построению синтаксического дерева цепочки "сверху - вниз", а выполняет сворачивание символов, записанных в магазин. Такой порядок сворачивания символов, записанных в магазин, соответствует правому выводу цепочки, выполняемому "снизу - вверх". Это обстоятельство объясняет, почему такие распознаватели называются восходящими. Подобный распознаватель должен учитывать при переходе не один символ, расположенный в вершине магазина, а цепочку символов. Чтобы устранить отмеченное противоречие, определим новый тип автомата, который назовем расширенным магазиннным автоматом.
| Определение. Формальное определение такого автомата имеет вид: M = {P, S, H, F, s0, h0, d}, где {$}} * H* ® S*H* - функция переходов. |
В функциональном виде функции переходов расширенного автомата можно записать так: d(s, p, ga) = (s, gb),
где a, b, g О
H*, p О (P И
{$}) и s О S.
Приведенное определение показывает, что расширенный автомат допускает замену одной цепочки, находящейся в вершине автомата, другой цепочкой.
Используя введенное ранее определение конфигурации автомата, работу расширенного магазинного автомата можно представить в виде последовательности сменяющих друг друга конфигураций.
При этом начальная и конечная конфигурации имеют вид:
(s0, a,р
h0 ) и (s1, $, h0I ),
где a - заданная цепочка, s1 - одно из заключительных состояний автомата, I - начальная аксиома грамматики.
Цепочку и язык, допускаемые расширенным автоматом, можно определить так.
| Определение. Цепочка допускается расширенным автоматом, если существует последовательность конфигураций, первая из которых является начальной конфигурацией с заданной цепочкой, а последней конфигурацией в последовательности является одна из заключительных конфигураций. ( s0, a,р h0 ) , $|--* ( s1, h0I ), где s1 - одно из заключительных состояний, a - заданная цепочка. Определение. Язык, допускаемый расширенным автоматом, можно определить так: L(M) = { a | (s0, a,р h0 ) |--* ( s1, $,$ ) и s1ОF}. |
с помощью правого вывода, можно
Пред.Страница
След.Страница Раздел Содержание
Каждую цепочку, построенную с помощью правого вывода, можно преобразовать в начальный символ грамматики, последовательно заменяя правые части правил, выделенные в цепочки, левыми частями. Такая операция замены, являющаяся обратной по отношению к операции вывода, называется сворачиванием или сверткой. Восходящий распознаватель работает, последовательно выполняя операции переноса и свертки. Вначале он переносит символы входной цепочки в магазин до тех пор, пока в магазине не образуется правая часть какого-либо правила, а затем он выполняет операцию сворачивания.Формальной моделью восходящего распознавателя является расширенный автомат, допускающий, в отличие от простого автомата, при переходе чтение цепочки, находящейся в вершине магазина.
Детерминированные восходящие распознаватели могут быть построены для LR(k) грамматик, которые являются подклассом контекстно-свободных грамматик. Процедура построения LR(k)-распознавателя оказывается весьма сложной и трудоемкой, поэтому в настоящем пособии рассматриваются грамматики LR(0) и SLR(1), которые включаются в подкласс LR(1) грамматик. Подкласс грамматик SLR(1) грамматик является достаточно широким. Кроме грамматик LR(0) он включает грамматики LL(1) и грамматики слабого предшествования. Диаграмма включения подклассов LR(1) грамматики приведена на рис.3.1.
Принадлежность к подклассу LR(0) или SLR(1) грамматик устанавливается путем проверки возможности построения соответствующего распознавателя. Процедура построения восходящих распознавателей состоит из двух частей: построение таблицы переходов и построение таблицы действий. Первая часть этой процедуры оказывается одинаковой для преобразователей LR(0) и SLR(1). Отличия в процедуре построения проявляются во второй части.
LR(1)
|
|
------------------SLR(1)----------------
| | |
| | |
LR(0) со слабым LL(1)
предшествованием
Рис. 3.1
Слаборазделенные грамматики
Используя введенные понятия, можно дать определение слаборазделенной грамматики.
| Определение. КС-грамматика называется слаборазделенной, если выполняются следующие три условия: правая часть каждого правила представляет собой либо пустую цепочку $, либо начинается с терминального символа, если два правила имеют одинаковые левые части, то правые части правил должны начинаться разными символами, для каждого нетерминала A, такого что A ==>* $ множество начальных символов не должно пересекаться с множеством символов, следующих за A.: ПЕРВ(A) З СЛЕД(A) = $ |
Используя приведенное определение, выясним, является ли следующая грамматика слаборазделенной:
Г3. 3
: R = {(1) <I> ®
a<A> , (2) <I> ®
b ,
(3) <A> ®
c<I>a ,
(4) <A> ®
$ }.
Эта грамматика не содержит правил с одинаковой левой частью, начинающихся одинаковыми терминалами, поэтому нужно проверить только условие (3) для правила (4). Вычисляя функции
ПЕРВ(<A>) = {c} и СЛЕД(<A>) = СЛЕД(<I>) = {a},
находим, что множество значений функции ПЕРВ(<A>) и множество значений функции СЛЕД(<A>) не имеют общих элементов. Следовательно, грамматика Г3.3 является слаборазделенной.
Проверка выполнения условия (3) для грамматики
Г3. 4: R = { <I> ®
a<I><A> | $ , <A>
® a | b }
дает следующие результаты:
ПЕРВ(<I>) = {a} и СЛЕД(<I>) = ПЕРВ(<A>) = {a,b},
которые показывают, что пересечение множеств ПЕРВ(<I>) и СЛЕД(<I>) не пусто. Следовательно грамматика Г3.4
не является слаборазделенной.
Пред.Страница
След.Страница Раздел Содержание
Определить какие из следующих грамматик,
1) Определить какие из следующих грамматик, заданных схемами, относятся к классу LL(1) грамматик.
а) Г3. 6 : R = {<I>
® a<A><I>,
<I> ®
b,
<A> ®
c<A><I>,
<A> ®
$}.
б) Г3. 7 : R = {<I>
® a<I><A>,
<I> ®
$,
<A> ®
b,
<A> ®
$}.
2) Проверить принадлежность к классу LL(1) и построить распознаватель для следующих грамматик:
а) Г3. 8 : R = {<I>
® a<I><I>,
<I> ®
b<I>,
<I> ®c<I><I><I>,
<I> ®
d}
б) Г3. 9 : R = {<I>
® a<B>,
<I> ®
(<I>)<B>,
<B> ®
a<B>,
<B> ®
$}.
в) Г3. 10
: R = {<I> ® <A>b<B>,
<I> ®
d,
<A> ®<C>
<A>b,
<A> ®
<B>,
<B> ®
c<I>d,
<B> ®
$,
<C> ®
a,
<C> ®
ed}
Пред.Страница
След.Страница Раздел Содержание
1) Постройте LR(0)–распознаватели для следующих грамматик:
a)
<I> ® (<I><R>
<I> ® a
<R> ® ,<I><R>
<R> ® )
б)
<I> ® <L>
= <R>
<I> ® <R>
<L> ®*
<R>
<L> ® a
<L> ® <R>
2) Постройте SLR(1) преобразователи для следующих грамматик:
а)
<I> ® a<I>b
<I> ® ab
б)
<I> ® <I><A>
<I> ® a
<A> ® <A><B>
<A> ® b
<B> ® a<A>
в)
<I> ® (<R>)
<R> ® a<Q>
<Q> ® ,a<Q>
<Q> ® $
<I> ® $
3) Показать, что следующая грамматика не входит в подкласс SLR(1)–грамматик.
<I> ®
a<I>b
<I> ®
b<I>a
<I> ®
$
Пред.Страница
След.Страница Раздел Содержание
Восходящие распознаватели
В основе работы восходящего распознавателя лежит операция сворачивания или свертки, которая применяется к цепочке, полученной с помощью правого вывода. Эта операция является противоположной выводу. Она заключается в том, что правая часть правила заменяется левой частью. При работе входящий распознаватель переносит символы входной цепочки в магазин и, когда в магазине оказывается правая часть какого-либо правила, осуществляет операцию свертки. Эту операцию можно определить следующим образом.
| Определение. Пусть задана грамматика Г, в схеме которой имеется правило r =A®y и задана цепочка g = r1A r2. Если правая часть цепочки правила r является частью цепочки , то можно получить цепочку t = r1y r2 , заменяя правую часть правила грамматики левой частью. В этом случае говорят, что цепочка tt получается путем непосредственного сворачивания цепочки g и используют обозначение t <= g . Определение. Если существует множество цепочек W = ( w1, w2, ...wn ), таких, что w1 Ь w2 , w2 Ь w3 , ... , wn-1Ь wn , то говорят, что цепочка wn сворачивается в цепочку w1 и используют обозначение w1 *Ь wn . |
Задача распознавания принадлежности данной цепочки языку, порождаемому грамматикой Г, может быть сформулирована следующим образом. Если из заданной цепочки с помощью операции сворачивания можно получить начальный символ грамматики, то такая цепочка может быть построена с помощью правил заданной грамматики, и, следовательно, она принадлежит языку, порождаемому этой грамматикой.
Например, сворачивание цепочки, полученной с помощью правого вывода и правил следующей грамматики
Г3. 11
:
(1) <I> ®
a,
(2) <I> ®
(<I><R> ,
(3) <R> ®
,<I><R> ,
(4) <R> ®
).
можно представить так: (a,a) Ь 1 (<I>,a) Ь 1 (<I>,<I>) Ь 4
(<I>,<I><R> Ь 3(<I><R> Ь 2 <I>.
Каждый шаг рассмотренной процедуры связан с выделением в цепочке правой части какого-либо правила и заменой его левой частью правила. В последовательности сворачиваний правые части правил называются основой
рассматриваемой цепочки. В общем случае основу можно определить так:
| Определение. Основой цепочки называют вхождение правой части последнего правила, примененного при правом выводе рассматриваемой цепочки. |
| 1. h0 | (a,a)^ | Перенос |
| 2. h0( | a,a)^ | Перенос |
| 3. h0(a | ,a)^ | Свертка(1) |
| 4. h0(<I> | ,a)^ | Перенос |
| 5. h0(<I>, | a)^ | Перенос |
| 6. h0(<I>,a | )^ | Свертка(1) |
| 7. h0(<I>,<I> | )^ | Перенос |
| 8. h0(<I>,<I>) | ^ | Свертка(4) |
| 9. h0(<I>,<I><R> | ^ | Свертка(3) |
| 10. h0(<I><R> | ^ | Свертка(2) |
| 11. h0<I> | ^ | Допустить |
Пред.Страница
След.Страница Раздел Содержание
Выделение общих частей
Второй вид преобразований, который называют выделением общих частей, применяют для устранения правил с одинаковыми левыми частями, правые части которых начинаются одинаковыми последовательностями символов.
Например, рассмотрим грамматику с правилами
<I>
® a<I>,
<I>
® a.
Эта грамматика не является LL(1) грамматикой, т.к. значения функций ПЕРВ(a<I>) и ПЕРВ(a) совпадают. Введем дополнительный нетерминал A и преобразуем грамматику так:
<I>
® a<A>,
<A> ®
<I>|$.
В этой грамматике отсутствуют правила с одинаковой левой частью, поэтому для нее выполняется первое условие определения LL(1) грамматики. В общем случае, если заданная грамматика содержит правила
<A>
® a
µ1 | a µ2 | ... | a
µn ,
то, вводя дополнительный нетерминал <A'>, их можно преобразовать к виду:
<A>
® a
<A'>
<A'>
® µ1
| µ2 | ... | µn.
Полученные правила могут быть использованы для построения LL(1) грамматики.
Покажем возможность применения этого вида преобразования на следующем примере. Пусть дана грамматика .
Г3. 6: R = { <I> ®
b<A><I><B>, <I> ®
b<A>,
<A>
® d<I>ca,
<A>
® f,
<B>
®c<A>a,
<B>
® c }.
Эта грамматика не является LL(1) грамматикой, поскольку нарушено первое условие. Воспользуемся способом выделения общих частей: введем нетерминалы D, E и построим правила:
<D>
® <I><B>
| $
<E>
® <A>a | $ .
В результате включения этих правил в схему грамматики получаем:
<I>
® b<A><D>
<D> ®
<I><B>
<D> ®
$
<A> ®
d<I>ca
<A> ®
f
<B> ®
c<E>
<E> ®
<A>a
<E> ®
$
Для этой грамматики первое условие принадлежности грамматики к классу LL(1) выполняется.
Чтобы проверить второе условие, найдем функции ПЕРВ и СЛЕД для аннулирующих правил. СЛЕД(<D>) = СЛЕД(<I>) = ПЕРВ(<B>) И
ПЕРВ(ca) = {c},
ПЕРВ(<D>) = ПЕРВ(<I>) = {b},
СЛЕД(<E>) = СЛЕД(<B>) = СЛЕД(<D>) = {c},
ПЕРВ(<E>) = ПЕРВ(<A>) = {d,f}.
Полученные значения показывают, что второе условие выполняется, и что построенная грамматика является грамматикой типа LL(1).
Преобразование для грамматики Г 3. 6 закончилось удачно, но так бывает не всегда. Часто исключение правил, нарушающих первое условие, приводит к появлению аннулирующих правил, для которых нарушается второе условие.
Третий вид преобразования предполагает исключение аннулирующих правил и построение неукорачивающей грамматики. Такие преобразования могут оказаться полезными, если нарушается второе условие принадлежности грамматики к классу LL(1).
Пред.Страница
След.Страница Раздел Содержание
Магазинные Преобразователи
Магазинные автоматы, рассмотренные в предыдущем разделе, позволяют определить для цепочки, заданной на входе, ее принадлежность к языку, допускаемому автоматом. Настоящий раздел посвящен другому типу моделей устройств, называемому магазинными преобразователями. Подобные устройства позваляют строить по заданной входной цепочки соответствующую ей выходную цепочку. Множество таких пар цепочек называют переводом или трансляцией, допускаемым магазинным преобразователем. Для того чтобы построить преобразователь необходимо заранее знать какой перевод он должен выполнять. Кроме того, преобразователь можно построить не для любого перевода, а только для такого, который может быть описан с помощью простой СУ-схемы. Для построения детерминированного преобразователя необходимо еще, чтобы входная грамматика заданной СУ-схемы пораждала детерминированный язык.
Пред.Страница След.страница Раздел Содержание
Описание работы магазинного преобразователя
Для описания работы магазинного преобразователя необходимо дать его определение.
| Определение:
Мп={P, S, s0, H, h0, F, W, q}, где P - входной алфавит, состоящий из символов, записываемых на входную ленту; W - выходной алфавит, содержащий символы, записываемые на выходную ленту; H - магазинный алфавит, содержащий символы, записываемые и считываемые из магазина; h0 - маркер дна магазина, он принадлежит H; S - множество состояний преобразователя; s0- начальное состояние из множества S; F - множество конечных состояний, представляющих собой подмножество S; j - функция переходов преобразователя, которая задает отображение, j: Sx{P И {$} x H Ю S x H* x W* . Она может быть записана в функциональном виде: j(s, p, h) = (s', b, e), О H, p О P, b О H*, e О W* и s,s' О S. |
Определим конфигурацию Мп как четверку
(s, ac, rh, d),
где ac
О P*, rh
О H*
и d
О W*.
Если такту работы преобразователя соответствует конфигурация (s, ac, rh , d) и определена функция переходов j(s, a, h) = (s', b, e), то происходит смена конфигурации, которую условимся записывать так:
(s, ac,
rh, d) |-- (s', c, rb,
de).
Последовательность сменяющих друг друга конфигураций, как обычно, обозначим символом |--*. В качестве начальной примем конфигурацию, которой соответствует заданная входная цепочка c
на ленте, цепочка h0I в магазине, начальное состояние s0
и пустая цепочка на выходной ленте:
(s0, c, h0I, $).
Конечной или заключительной конфигурацией назовем четверку (sk, $, $, d), где sk
- одно из заключительных состояний из множества F, а d
- выходная цепочка.
Пред.СтраницаСлед.Страница
Определение магазинного преобразователя
.
Магазинный преобразователь (Мп)
от магазинного автомата наличием дополнительной выходной ленты, на которую записывается выходная цепочка. Схему магазинного преобразователя
можно изобразить следующим образом:
В этой схеме входная головка в каждом такте работы может оставаться на месте или двигаться на одну позицию вправо. Выходная головка также может быть неподвижной или смещаться вправо, а головка магазинной ленты может перемещаться в обоих направлениях, причем такие перемещения связаны с операциями записи и чтения.
Пред.Страница След.Страница Раздел Содержание
Перевод определяемый преобразователем
| Определение. Цепочку d назовем выходом для цепочки c, если существует последовательность Определение. D(Mп) = {(x, y) | (s0, c, h0, $) |--* (s', $', $, y) & s' О F} |
Используя последнее определение, можно определить возможность построения преобразователя, реализующего заданный перевод в виде следующего утверждения.
| Утверждение. Для каждой простой СУ-схемы перевода Т = {Va, Vтвх, Vтвых, Q, I} можно построить такой Мп магазинный преобразователь, что D(Т) = D(Мп). |
| Утверждение. Для каждой простой СУ - схемы перевода Т, входная грамматика которой принадлежит классу LL(1) - грамматик, можно построить такой детерминированный магазинный преобразователь Мп, что перевод, определяемый преобразователем, совпадает с переводом, задаваемым СУ - схемой Т. |
Порядок построения детерминированного магазинного преобразователя
В общем случае, если заданы входной и выходной языки, то порядок построения детерминированного магазинного преобразователя можно представить следующим образом:
Построить грамматику, описывающую цепочки входного языка.
Проверить принадлежность этой грамматики классу LL(1)- грамматик. Если условия LL(1) - грамматики не выполняются, то попытаться выполнить преобразование или вернуться к п.1 и построить другую грамматику.
Построить простую СУ-схему, используя построенную грамматику в качестве входной грамматики СУ - схемы.
Построить транслирующую грамматику для полученной СУ -схемы.
Используя правила построения, найти команды преобразования для разных групп правил транслирующей грамматики.
Убедиться, что построенный преобразователь реализует заданный перевод, выполняя несколько примеров построения выходных цепочек с помощью команд преобразователя.
Пред.СтраницаСлед.Страница Раздел Содержание
Построение преобразователя
Покажем теперь, как по заданной СУ - схеме можно построить детерминированный преобразователь. В начале по заданной СУ - схеме построим транслирующую грамматику Г. Это всегда можно сделать, поскольку заданная СУ - схема должна быть простой. Если входная грамматика заданной СУ - схемы относится к классу LL(1) -грамматик, то и входная грамматика транслирующей грамматики также должна относиться к этому классу, поскольку при построении Т - грамматики входные правила изменениям не подвергались. Учитывая, что искомый преобразователь должен в процессе формирования выхода осуществлять и распознавание входной цепочки, будем его строить по правилам транслирующей грамматики, используя правила построения распознавателя.
Такой преобразователь должен воспроизводить левый вывод входной цепочки в магазине и удалять терминальные символы, на ходящиеся в вершине, при совпадении их с очередным символом на входной ленте. Однако при этом в магазин будут записываться выходные символы, содержащиеся в правилах Т - грамматики, и возникнут неопределенные ситуации при появлении выходного символа в вершине магазина. Чтобы исключить такие ситуации, дополним этот правила построения преобразователя следующим правилом: при появлении выходного символа в вершине магазина он должен передаваться на выход независимо от того, какой символ находится под входной головкой.
Построение функции переходов МП
(1) Для всех правил вида <A>
--> ba, где b О
Vтвх и a О(Vтвх
U Vтвых U Va)*, строим ко-
манды:
j( s0, b, A)=( s0, a', $ ),
где a' - зеркальное отображение цепочки a.
(2) Для всех правил вида <A>
--> <B>a, где B ОVa и a О(Vтвх
U Vтвых U Va)*, строим коман-
ды:
j*( s0, u, A ) = ( s0, aB , $ ),
где u О ВЫБОР(<A> --> <B>aвх) и aвх - цепочка, полученная из a путем удаления из
нее всех выходных символов.
. (3) Для всех правил вида <A>
--> $ строим команды:
j*( s0, u, A ) = ( s0, $, $ ),
где u О
ВЫБОР(<A> --> $).
(4) Для всех символов b, принадлежащих, Vтвх , стоящих на первом месте в правой части правил
транслирующей грамматики, т.е. символов,заносимых в магазин, строим правило:
j( s0, b, b ) = ( s0, $, $ ).
(5) Для всех выходных символов {u}, таких что u О Vтвых U {$}, строим команды:
j*( s0, z, {u} ) = ( s0, $, {u} ),
где z О
Vтвх.
Точнее команды строятся для сочетаний {u}z, таких что z может следовать за {u} в цепочках,
выводимых в за данной грамматике.
(6) Заключительное правило строим так:
j( s0, $, h0 ) = ( s0, $, $ ).
Пред.СтраницаСлед.Страница Раздел Содержание
Построение восходящих преобразователей
Пред.СтраницаСлед.СтраницаРаздел Содержание
4.3.7 Построение восходящих преобразователей.
Построение восходящих преобразователей, так же как в рассмотренном выше случае, выполняется на основе распознавателя путем модификации команд за счет выполнения операции передачи выходных символов. Одно из отличий построения восходящих преобразователей заключается в том, что для их построения должна быть использована транслирующая грамматика в постфиксной форме.
| Определение. Транслирующая грамматика, записанная в форме, когда все символы действия в правых частях распо ложены правее всех терминальных и нетерминальных символов, называется постфиксной транслирующей грамматикой. |
Это определение говорит о том, что правила постфиксной транслирующей грамматики должны иметь вид:
<A> ®
a{ z },
где a О( VT И VА) * и z О VTвых
.
Любая транслирующая грамматика может быть преобразована в постфиксную форму путем разбиения правил грамматики и добавления новых нетерминальных символов. Например, для преобразования правила
<A> ® a{ z }<B>{ w },
введем дополнительный нетерминал и разобьем исходное правило на две части. В результате получаем правило в постфиксной форме:
<D> ® a{ z },
<A> ® <D><B>{w}.
Воспользуемся этим приемом для преобразования к постфиксной форме транслирующей грамматики, которая задает преобразование арифметических выражений без скобок, описываемых грамматикой 4. 2, в постфиксную форму.
Г 4. 2 : <I> ® a{a}<R>,
<R> ® +a{a}{+}<R>,
<R>®-a{a}{-}<R>,
<R>® $.
Добавляем три новых нетерминала <P>, <Q>, <S> и, разбивая правила грамматики, получаем грамматику в постфиксной форме.
Г 4. 3 : <I> ® <S><R>,
<S> ® a{a},
<R> ® <P><R>,
<P> ® +a{a}{+},
<R> ® <Q><R>,
<Q> ® -a{a}{-},
<R> ® $.
Напомним, что при построении восходящих распознавателей обработка каждого правила A
<A> ® ax
с номером k с символом x, занимающим самую правую позицию в правой части правила, связывалась операция Свертка(k). В постфиксной транслирующей грамматике самую правую позицию могут занимать символы действия, поэтому при построении восходящего преобразователя эти символы можно объединить с операцией свертки в одну операцию, которую назовем
Свертка - Действие(k) (СД(k)). Учитывая, что все символы действия постфиксной транслирующей грамматики могут быть объединены с операциями свертки, приходим к заключению, что процедура построения восходящего распознавателя может быть применена для построения восходящего преобразователя при условии, что вместо операции Cвертка (k) будет использоваться операция Свертка - Действие(k) для правил построения постфиксной транслирующей грамматики, содержащая символы действия.
В качестве иллюстрации последнего утверждения рассмотрим построение преобразователя для грамматики Г 4. 3. Выполняя последовательно шаги процедуры построения SLR(1) преобразова-
теля для грамматики с аннулирующими правилами и заменяя операции Свертка(k) для правил 2, 4 и 6 операциями Свертка - Действие(k), получаем таблицы переходов и действий искомого преобразователя в следующем виде.
Таблица 4.1
|
|
I | S | R | P | Q | + | - | a |
| I0 | ||||||||
| S | R1 | P | Q | + | - | |||
| R1 | ||||||||
| a2 | ||||||||
| P | R3 | P | Q | + | - | |||
| R3 | ||||||||
| + | a4 | |||||||
| a4 | ||||||||
| Q | R5 | P | Q | + | - | |||
| R5 | ||||||||
| - | a6 | |||||||
| a6 | ||||||||
| h0 | I0 | S | a2 |
Таблица 4.2
| + | - | a | |-- | |
| I0 | D | |||
| S | П | П | c7 | |
| R1 | c1 | |||
| c1 | CD2 | CD2 | CD2 | |
| P | П | П | c7 | |
| R3 | c3 | |||
| + | П | |||
| a4 | CD4 | CD4 | CD4 | |
| Q | П | П | c7 | |
| R5 | c5 | |||
| - | П | |||
| a6 | CD6 | CD6 | CD6 | |
| a4 | П |
Вход Магазин Действие Выход
1. а + а - а|-- h0 П -
2. + а - а|-- h0 a2 СД2 a
3. + а - а|-- h0 S П a
4. а - а|-- h0 S + П a
5. - а|-- h0 S + a4 СД4 aa +
6. - а|-- h0 S P П aa +
7. а|-- h0 S P- П aa +
8. |-- h0 S P - a6 СД6 aa + a -
9. |-- h0 S P Q С7 aa + a -
10. |-- h0 S P Q R5 С5 aa + a -
11. |-- h0 S PR3 С3 aa + a -
12. |-- h0 S R1 С1 aa + a -
13. |-- h0 I0 Д aa + a -
Приведенная последовательность конфигураций показывает, что выходная цепочка формируется при выполнении операций СД2, СД4 и СД6 соответственно на 2, 5 и 8 шаге.
Пред.Страница След.Страница Раздел Содержание
Пример построения преобразователя
Применение правил построения команд преобразователя рассмотрим на примере транслирующей грамматики Г, которая описывает перевод инфиксных выражений, состоящих из идентификаторов и знаков + и *, в постфиксные польские выражения. Эта грамматика имеет следующую схему:
Г 4. 1 : R = {<E> Ю +<E><E>{+},
<E> Ю x<E><E>{x},
<E> Ю a{a}}
Используя правило построения команд преобразователя (1) для правил грамматики, начинающихся входным терминальным символом, получаем команды преобразователя Мп1:
q(s0, +, <E>) = (s0, {+}<E><E>, $),
q(s0, *, <E>) = (s0, {*}<E><E>, $),
q(s0, a, <E>) = (s0, {a}, $)
Правила построения команд вида (2),(3),(4) к заданной грамматике неприменимы, поэтому с помощью правил вида (5) построим команды, обеспечивающие передачу выходных символов на выход. Эти команды имеют вид:
q*(s0, +, {+}) = (s0, $, +), q*(s0, *, {+}) = (s0, $, +),
q*(s0, a, {+}) = (s0, $, +), q*(s0, $', {+}) = (s0, $, +),
q*(s0, *, {*}) = (s0, $, *), q*(s0, +, {*}) = (s0, $, *),
q*(s0, *, {a}) = (s0, $, *), q*(s0, $', {*}) = (s0, $, *),
q*(s0, a, {a}) = (s0, $, a), q*(s0, +{a}) = (s0, $, a),
q*(s0, *, {a}) = (s0, $, a), q*(s0, $', {a}) = (s0, $, a)
Для перехода в заключительное состояние s1
в соответствии с правилом (6) построим команду:
q(s0, $', h0) = (s1, $, $)
Чтобы посмотреть как работает построенный преобразователь, рассмотрим построение выходной цепочки для входа +a*aa. Последовательность конфигураций, получаемых с помощью команд преобразователя имеет вид:
(s0, +a*aa, h0E, $) |-- (s0, a*aah0{+}EE, $) |--
(s0, *aa, h0{+}T{a}, $) |--
(s0, *aa, h0{+}E, a) |--
(s0, aa, h0{+}{*}T{a}, a) |--
(s0, a, h0{+}{*}E, aa) |--
(s0, $, h0{+}{*}{a}, aa) |--
(s0, $, h0{+}{*}, aaa) |--
(s0, $, h0{+}, aaa*) |--
(s0, $, h0, aaa*+) |--
(s0, $, $, aaa*+).
Результатом работы преобразователя
является выходная цепочка aaa*+, представляющая постфиксную запись заданной входной цепочки.
Пред.СтраницаСлед.Страница Раздел Содержание
