A.3 An Implementation of SDT
A.3.2 An implementation of SDT using AG
Here, we give an implementation of SDT under the frame work of AG.
Example A.3.1 (Example of a semantics for synf n) Inherited Attributes:
(string∗T ype list)
BODY.id list, SF EXP.id list, BOOL EXP.id list Synthesized Attributes:
(string∗T ype) SIGN.id
string∗T ype)list SIGN LIST.id list (string)
identifier.w (T ype)
SDTYPE.type, SMTYPE.type, STYPE.type, BASETYPE.type, TYPE.type (λexpression)
SIGN LIST.exp BODY.exp SF EXP.exp
FUN1ARG.exp
(where T ype=string)
SYNFUN→synfnidentifier(SIGN LIST) :SDTYPE BODY {SIGN LIST[4].pre list= [];
BODY.id list=SIGN LIST[4].id list;
reflect((SDTYPE[7].type,SIGN LIST[4].type),
(λµ:string.SIGN LIST[4].exp)BODY[8].exp)} (3)
SDTYPE→X (whereX ∈D)
{SDTYPE.type =X.w}
SMTYPE→Y (whereY ∈M)
{SMTYPE.type=Y.w}
STYPE→Y (whereY ∈T)
{STYPE.type=Y.w} Note: D ⊂M ⊂T
BASETYPE→STYPE
{BASETYPE.type =STYPE[1].type} BASETYPE→bool
{BASETYPE.type =bool} BASETYPE→char
{BASETYPE.type =char} BASETYPE→string
{BASETYPE.type =string} BASETYPE→tree
{BASETYPE.type =tree} TYPE→ identifier
{TYPE.type=::identifier[2].w} TYPE→BASETYPE
{TYPE.type=BASETYPE[1].type} TYPE→TYPElist
{TYPE.type=TYPE[1].type::list} SIGN→STYPE
{SIGN.type=STYPE[1].type;
SIGN.id= (emptySymbol,STYPE[1].type)} SIGN→STYPE(identifier)
{SIGN.type=STYPE[1].type;
SIGN.id= (identifier[3].w,STYPE[1].type)} SIGN LIST→SIGN
{SIGN LIST.type =SIGN[1].type;
SIGN LIST.id list= [SIGN[1].id];
SIGN LIST.exp
=λπ1(SIGN[1].id) :π2(SIGN[1].id)↑µ} (4) SIGN LIST→SIGN, SIGN LIST
{SIGN LIST.type =SIGN[1].type::SIGN LIST[3].type;
SIGN LIST.id list=SIGN[1].id::SIGN LIST[3].id list;
SIGN LIST.exp=λπ1(SIGN[1].id) :π2(SIGN[1].id).SIGN LIST[3].exp} BODY→begin SF EXP end
{SF EXP[2].id list=BODY.id list;
BODY.exp=SF EXP.exp }
SF EXP→identifier
{SF EXP.exp=getValue(SF EXP.id list,identifier[1].w)} SF EXP→[]
{SF EXP.w =ε;SF EXP.tree= (ε,[])}
SF EXP→ ifBOOL EXPthenSF EXPelseSF EXP {BOOL EXP[2].id list=SF EXP.id list;
SF EXP[4].id list=SF EXP.id list;
SF EXP[6].id list=SF EXP.id list;
SF EXP.exp
=if(BOOL EXP[2].exp,SF EXP[4].exp,SF EXP[6].exp)} SF EXP→FUN1ARG(SF EXP)
{SF EXP[3].id list=SF EXP.id list;
SF EXP.exp=FUN1ARG.exp(SF EXP[3].exp)} SF EXP→(SF EXP)
{SF EXP[2].id list=SF EXP.id list;
SF EXP.exp=SF EXP[2].exp} SF EXP→SF EXP::SF EXP
{SF EXP[1].id list=SF EXP.id list;
SF EXP[3].id list=SF EXP.id list;
SF EXP.exp=concatinate(SF EXP[1].exp,SF EXP[3].exp)} SF EXP→SMTYPE↓SF EXP
{SF EXP[3].id list=SF EXP.id list;
SF EXP.exp=getToken(SMTYPE[1].type, getvalue(SF EXP.id list,
SF EXP[3].exp))} BOOL EXP→empty(SF EXP)
{SF EXP[3].id list=BOOL EXP.id list;
BOOL EXP.exp=empty(SF EXP[3].exp)} BOOL EXP→SF EXP=SF EXP
{SF EXP[1].id list=BOOL EXP.id list;
SF EXP[3].id list=BOOL EXP.id list;
BOOL EXP.exp=equal(SF EXP[1].exp,SF EXP[3].exp)} BOOL EXP→(BOOL EXP)
{BOOL EXP[2].id list=BOOL EXP.id list;
BOOL EXP.exp=BOOL EXP[2].exp} BOOL EXP→notBOOL EXP
{BOOL EXP[2].id list=BOOL EXP.id list;
BOOL EXP.exp=not(BOOL EXP[2].exp)} BOOL EXP→BOOL EXPorBOOL EXP
{BOOL EXP[1].id list=BOOL EXP.id list;
BOOL EXP[3].id list=BOOL EXP.id list;
BOOL EXP.exp=or(BOOL EXP[1].exp,BOOL EXP[3].exp)} BOOL EXP→BOOL EXPandBOOL EXP
{BOOL EXP[1].id list=BOOL EXP.id list;
BOOL EXP[3].id list=BOOL EXP.id list;
BOOL EXP.exp=and(BOOL EXP[1].exp,BOOL EXP[3].exp)} FUN1ARG→head
{FUN1ARG.exp=head} FUN1ARG→rest
{FUN1ARG.exp=rest} FUN1ARG→root
{FUN1ARG.exp=root} FUN1ARG→children
{FUN1ARG.exp=children}
Note: the attributes SF EXP.exp, BOOL EXP.exp and FUN1ARG.exp hold λ expres-sions as their values. It does not means that we treat λ expressions directly, but means that each λ expression expresses a continuation for evaluations of attribute values.
In this example, a continuation of calculation of a symbol sequence which will be the result of SDT is going to be constructed in attributesSF EXP.expand BOOL EXP.exp.
The continuation obtained by the example is to calculate a symbol sequence, not to calculate attribute values for the symbols sequence provided by SDT. A procedure to calculate expected symbol sequence is assigned by system function reflect, i.e. used in (3), to the production rule which is designated by the signature of SDT description.
↑ in expression (4) parses its argument and constructs its parse tree. The result of ↑ is a function from a collection of Inherited Attributes of the root of the parse tree to a collection of Synthesized Attributes of the root, the function which is explained in previous section. On this aspect, out approach is similar to Higher Order Attributted Grammar (HAG) [28].
HAG is a model of multi-pass processes. On first pass, data which has tree structure are calculated in a way of AG frame work. On later passes, using tree structured data as a parse tree, which are calculated on previous pass, and adapting AG frame work again, targer objects are obtained finally. In our implementation scheme for SDT given here, when SDT is parsed, a symbol sequence, which may include some non-terminal symbols, is calculated as a attribute value, then the symbols sequence is parsed again by same parser, and finally parser obtains a collection of Attribution for given SDT.
We can assume that this implementation of SDT indicates that the compiler involves an interpreter for SDT. (Figure A.4)
As an alternative imprementation of SDT, instead that compiler includes SDT inter-preter, we suppose to implement SDT so as to embed SDT processes into target objects.
It is to say SDT compiler. The idea for the implementation is quite simple. To explain
Source
SDT Description
Compiler (with Interpreter for SDT)
Parser
Attribution Evaluator
SDT Interpreter
String Inputs for Parsing
Figure A.4: SDT Interpreter
it with above example, in this implementation, system functions, like if, head,rest, . . ., are not assumed for the functions which evaluate their values immediately, but functions which calculate code streams, i.e. continuations, to evaluate original system functions.
This methodology corresponds to Unfolding process which is discussed in the sphere of program translations. We must note that branches in generated code streams are caused not only by system functionif, but also by a process which concerns to a parsing process caused by ”↑”.