Понятие Т-грамматики

В простых СУ-схемах можно объединить левые и правые части соответствующих правил входной и выход­ной грамматик. Получающиеся таким образом грамматики при­нято называть транслирующими грамматиками (Т-грамматиками). Символы выходного алфавита А в Т-грамматике называют операционными символами. При записи Т-грамматики каждый операционный символ во избежание путаницы каким-либо образом выделяют. Будем заключать такой символ в пря­моугольные скобки.

ПримерОпределение Т-грамматики для перевода инфикс­ных арифметических выражений в ПОЛИЗ: V_T= {+, *, (,), имя}; = {[+], [*], [имя]}; V_N = {S, Е,T, F}; S — аксиома, правила R:

1)S->E 2)E->E+T[+] 3) E->T 4) T->T*F[*]

5) T->F 6) F->(E) 7) F-> имя[имя]

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

Т-грамматика описывает правила образования строк из тер­миналов и операционных символов. Эти строки называют ак­тивными цепочками. Если удалить из активной цепочки операци­онные символы, то получится ее входная часть. Если удалить из активной цепочки терминалы, получится выходная часть, или, иначе, трансляция, перевод входной части. Активную цепочку можно рассматривать как программу управления работой МП - преобразователя, соответствующего Т-грамматике. При этом входной символ можно считать обозначением операции чтения этого символа, а операционный символ — обозначением опера­ции выдачи этого символа.

ПримерАктивная цепочка а[a]+b[b]*с[с][*][+] описывает процесс трансля­ции входной цепочки а + b*с (исключили из активной цепочки операционные символы) в ПОЛИЗ [а] [b] [с] [*][+] (исключили из ак­тивной цепочки терминалы). Действительно, существует вывод (левосторонний)

S => Е => Е+ Т[+] => Т+ Т[+] => F+ T[+] => а[а] + Т[+] =>

a[a] + T*F[*][+] => a[a] + F*F[*][+] => a[a] + b [b]*F [*][+] =>

a[a] + b[b]* с [с ][*][+],

и пара (а + b*c, [a][b][с][*][+]) принадлежит переводу инфикс­ных выражений в ПОЛИЗ. В этом примере каждый операционный символ обозначает просто выдачу соответствующего входного символа в выходную строку.