Построение преобразователя
Покажем теперь, как по заданной СУ - схеме можно построить детерминированный преобразователь. В начале по заданной СУ - схеме построим транслирующую грамматику Г. Это всегда можно сделать, поскольку заданная СУ - схема должна быть простой. Если входная грамматика заданной СУ - схемы относится к классу 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, $, $ ).
Пред.СтраницаСлед.Страница Раздел Содержание