Т-грамматика с подпрограммами

Рассмотрим Т-грамматику для условных операторов. Граммати­ка описывает перевод сокращенных и полных условных операто­ров в ПОЛИЗ, например оператора вида if A then В else С; в ПОЛИЗ вида А т₁УПЛ В m₂БП m₁:С т₂, где А — логическое выражение, Z и С — любые операторы, в том числе и условные. Ясно, что элементы А, В и С в ПОЛИЗ оператора также будут запи­саны в ПОЛИЗ.

Представим грамматику G = (V_T, Vn,P, S) условного опера­тора некоторого языка программирования правилами (табл. 4.2). Это входная грамматика, в которой V_T= {if then, else, z, p, ;}, V_N= {U,K,H,M,O}, S = U- аксиома. Для обозримости иллю­страций полагаем, что логическое выражение р и не условный оператор z описываются в других грамматиках и считаются уже разобранными синтаксическими конструкциями. Поэтому они включены в множество терминалов V_N.

Таблица 5.1 Правила грамматики условного оператора

Номер правила	Входная грамматика G	Транслирующая грамматика GT
	U->if K	U->if K
	К->рН	K->p[xo]H
	Н -> then О М;	H->then[x1]O M [x3];
	М -> else О	М -> else [X2] О
	M->	М ->
	O->U	O->U
	0->z	O->z [x0]

Теперь запишем Т-грамматику, пополнив входную грамма­тику операционными символами. Операционные символы под­берем, исходя из сравнения форм исходных операторов и соот­ветствующих им форм ПОЛИЗ. Возможный вариант правил R для Т-грамматики G_T = (V_T, V_N, , Р, S) показан в табл. 5.2.1. В этой грамматике = {[х₀], [х₁], [х₂], [х₃]}, a V_T, V_N и U имеют тот же смысл, что и во входной грамматике. Операционные символы по сути своей являются подпрограммами, которые выполняют­ся в темпе синтаксического анализа и осуществляют следующие действия:

- [x₀] - копирует текущий входной символ (терминал) в вы­ходную строку;

- [x₁] - создает очередную метку m_j, дописывает в выходную строку цепочку m_j УПЛ и помещает m_j. в вершину стека меток;

- [x₂] - создает очередную метку m_j+1, дописывает в выходную строку цепочку m_j+1БПm_j:, где т_j— метка в вершине стека меток, и замещает в стеке метку m_i: меткой m_j+1:;

- [х₃] - выталкивает метку т_k из вершины стека меток в выходную строку.

Транслирующая грамматика G_T описывает активные цепоч­ки. Так, входному оператору if a then b else с; будет соответство­вать активная цепочка if a [x₀] then[x₁] b[x₀] else[x₂] c[x₀] [x₃].