Attribute grammar for generating MacScheme machine assembly code from a quirk20 source program. [Version 0] For simplicity the attribute grammar is defined over abstract syntax trees that have been type checked. This code generator ignores types. Syntactic categories (nonterminals of the attribute grammar). P program C class declaration A class body declaration F function declaration D local declaration S statement E expression L literal expression B binary operation U unary operation Attributes. D.sleaf precomputed (see note below) D.dleaf precomputed (see note below) F.sleaf precomputed (see note below) F.dleaf precomputed (see note below) E.n1 precomputed (see note below) E.n2 precomputed (see note below) E.inits precomputed (see note below) P.code synthesized C.name synthesized C.code synthesized A.class inherited A.code synthesized D.class inherited D.env inherited D.stkenv inherited D.regenv inherited D.reg inherited D.stk inherited D.maxstk synthesized D.name synthesized D.code synthesized F.class inherited F.env inherited F.name synthesized F.code synthesized S.sleaf inherited S.tail inherited S.class inherited S.rtn inherited S.env inherited S.stkenv inherited S.regenv inherited S.reg inherited S.stk inherited S.maxstk synthesized S.code synthesized E.lhs inherited E.tail inherited E.class inherited E.env inherited E.stkenv inherited E.regenv inherited E.reg inherited E.stk inherited E.maxstk synthesized E.code synthesized L.code synthesized B.reg inherited B.code synthesized U.reg inherited U.code synthesized D.sleaf, D.dleaf, F.sleaf, F.dleaf, E.n1, E.n2, and E.inits are used but not specified by this attribute grammar. (They are computed by earlier phases of the compiler.) D.sleaf and F.sleaf are true iff D or F is a function declaration that contains no local function declarations. If D is a function declaration F, then D.dleaf and F.dleaf are true iff D or F contains no non-tail calls. For a NewRecordExp E, E.n1 is the number of dynamic fields within the record to be created. For a FieldExp E, E.n1 is the offset of the field. For a NewRecordExp or NewArrayExp E, E.inits encodes the initial values for each field or element. S.sleaf is a boolean attribute that is true iff S is within a function declaration that contains no local function declarations. For any syntactic category X, X.code is the sequence of MacScheme machine assembly code generated for X. For a class, class body, local, or function declaration X, X.name is the name of the class, constant, variable, or function that is declared by the declaration. S.rtn is an integer that represents the label of the current return code. E.lhs is true iff the expression is being evaluated for its L-value. S.tail and E.tail are booleans that tells whether a statement or expression is in a tail position. X.class is an identifier that names the class in which a declaration, statement, or expression X appears. X.env is a compile-time environment for variables that are allocated on the heap. X.stkenv is a compile-time environment for variables that are allocated in the current stack frame. X.regenv is a compile-time environment for variables that are allocated in registers. X.reg is an integer that records the highest-numbered register that is in use. X.stk is an integer that records the highest-numbered stack slot that is in use. If no stack frame has been allocated, then X.stk is -1. X.maxstk is an integer that represents the highest-numbered stack slot that is required by the code generated for X. Notation. If env is a compile-time environment, then env [I1: n1] abbreviates extend (env, I1, n1). More generally, env [I1: n1, ...] abbreviates extend (env, I1, n1) [...]. returnif(false, L) stands for the empty sequence of MacScheme machine assembly code. returnif(true, L) stands for skip L Attribute grammar. P --> C1 ... Cn let L = new label R = C1.name in P.code = [C1.code] ... [Cn.code] save 0 store 0,0 global command-line-arguments setrtn L invoke 0 L: load 0,0 setreg 1 global R.main pop 0 invoke 1 C --> class R { A1 ... An } A1.class = ... = An.class = R; C.name = R; C.code = [A1.code] ... [An.code] A --> constant T I = L; let R = A.class in A.code = [L.code] setglbl R.I A --> static T I = L; let R = A.class in A.code = [L.code] setglbl R.I A --> T I; A.code = nop A --> F let R = A.class I = F.name in F.class = R; F.env = empty(); A.code = lambda [F.code],0,#f setglbl R.I D --> constant T I = L; D.maxstk = D.stk; D.code = L.code. D --> T I = E; E.lhs = false; E.tail = false; E.class = D.class; E.env = D.env; E.stkenv = D.stkenv; E.regenv = D.regenv; E.reg = D.reg; E.stk = D.stk; D.maxstk = E.maxstk; D.code = E.code. D --> F F.class = D.class; F.env = beginScope (D.env); D.maxstk = D.stk; D.code = lambda [F.code],0,#f F --> proc T0 I0 (T1 I1, ..., Tn In) S F.name = I0; S.sleaf = F.sleaf if F.sleaf and F.dleaf then let L1 = new label in S.tail = true; S.class = F.class; S.rtn = L1; S.env = F.env; S.stkenv = empty(); S.regenv = empty() [I1: 1, ..., In: n]; S.reg = n; S.stk = -1; F.code = [S.code] L1: return else if F.sleaf then let L1, L2, L3 = new labels in S.tail = true; S.class = F.class; S.rtn = L2; S.env = F.env; S.stkenv = empty() [I1: 1, ..., In: n]; S.regenv = empty(); S.reg = 0; S.stk = n; let k = S.maxstk in F.code = skip L3 L1: [S.code] L2: pop k return L3: save k store 0,0 store 1,1 ... store n,n skip L1 else let L1, L2, L3 = new labels env1 = beginScope (F.env) in S.tail = true; S.class = F.class; S.rtn = L2; S.env = env1 [I1: 1, ..., In: n]; S.stkenv = empty(); S.regenv = empty(); S.reg = 0; S.stk = 0; let k = S.maxstk in F.code = lexes n,#f setreg 0 skip L3 L1: [S.code] L2: pop k return L3: save k store 0,0 skip L1 S --> skip; S.maxstk = S.stk; S.code = nop S --> E; E.lhs = false; E.tail = S.tail; E.class = S.class; E.env = S.env; E.stkenv = S.stkenv; E.regenv = S.regenv; E.reg = S.reg; E.stk = S.stk; S.maxstk = E.maxstk; S.code = E.code. S --> if (E1) S1 else S2 let L1, L2 = new labels in E1.lhs = false; E1.tail = false; S1.sleaf = S2.sleaf = S.sleaf; S1.rtn = S2.rtn = S.rtn; S1.tail = S2.tail = S.tail; E1.class = S1.class = S2.class = S.class; E1.env = S1.env = S2.env = S.env; E1.stkenv = S1.stkenv = S2.stkenv = S.stkenv; E1.regenv = S1.regenv = S2.regenv = S.regenv; E1.reg = S1.reg = S2.reg = S.reg; E1.stk = S1.stk = S2.stk = S.stk; S.maxstk = max (E1.maxstk, S1.maxstk, S2.maxstk); S.code = [E1.code] branchf L1 [S1.code] skip L2 L1: [S2.code] L2: S --> while (E1) S1 let L1, L2 = new labels in E1.lhs = false; S1.sleaf = S.sleaf; S1.rtn = S.rtn; E1.tail = S1.tail = false; E1.class = S1.class = S.class; E1.env = S1.env = S.env; E1.stkenv = S1.stkenv = S.stkenv; E1.regenv = S1.regenv = S.regenv; E1.reg = S1.reg = S.reg; E1.stk = S1.stk = S.stk; S.maxstk = max (E1.maxstk, S1.maxstk); S.code = L1: [E1.code] branchf L2 [S1.code] branch L1 L2: S --> return E; E.lhs = false; E.tail = true; E.class = S.class; E.env = S.env; E.stkenv = S.stkenv; E.regenv = S.regenv; E.reg = S.reg; E.stk = S.stk; S.maxstk = E.maxstk; let L = S.rtn in S.code = [E.code] skip L S --> { D1 ... Dm S1 ... Sn } if not S.sleaf let k0 = S.stk + 1 env0 = beginScope (S.env) env1 = env0 [D1.name: 1] env2 = env1 [D2.name: 2] ... envm = env{m-1} [Dm.name: m] in D1.class = ... = Dm.class = S.class; if D1 is a function declaration then D1.env = env1 else D1.env = env0; ... if Dm is a function declaration then Dm.env = envm else Dm.env = env{m-1}; D1.stkenv = ... = Dm.stkenv = S.stkenv; D1.regenv = ... = Dm.regenv = S.regenv; D1.reg = ... = Dm.reg = S.reg; D1.stk = ... = Dm.stk = k0; S1.sleaf = ... = Sn.sleaf = S.sleaf; S1.tail = ... = S{n-1}.tail = false; Sn.tail = S.tail; S1.class = ... = Sn.class = S.class; S1.rtn = ... = Sn.rtn = S.rtn; S1.env = ... = Sn.env = envm; S1.stkenv = ... = Sn.stkenv = S.stkenv; S1.regenv = ... = Sn.regenv = S.regenv; S1.reg = ... = Sn.reg = S.reg; S1.stk = ... = Sn.stk = k0; S.maxstk = max (S.stk, D1.maxstk, ..., Dm.maxstk, S1.maxstk, ..., Sn.maxstk); S.code = store 0,k0 lexes m,#f setreg 0 [D1.code] setlex 0,1 ... [Dm.code] setlex 0,m [S1.code] ... [Sn.code] load 0,k0 else if S.stk >= 0 let k1 = S.stk + 1 ... km = S.stk + m env0 = S.stkenv env1 = env0 [D1.name: k1] ... envm = env{m-1} [Dm.name: km] in D1.class = ... = Dm.class = S.class; D1.env = ... = Dm.env = S.env; D1.stkenv = env0; D2.stkenv = env1; ... Dm.stkenv = env{m-1}; D1.regenv = ... = Dm.regenv = S.regenv; D1.reg = ... = Dm.reg = S.reg; D1.stk = S.stk; D2.stk = k1; ... Dm.stk = k{m-1}; S1.sleaf = ... = Sn.sleaf = true; S1.tail = ... S{n-1}.tail = false; Sn.tail = S.tail; S1.class = ... = Sn.class = S.class; S1.rtn = ... = Sn.rtn = S.rtn; S1.env = ... = Sn.env = S.env; S1.stkenv = ... = Sn.stkenv = envm; S1.regenv = ... = Sn.regenv = S.regenv; S1.reg = ... = Sn.reg = S.reg; S1.stk = ... = Sn.stk = km; S.maxstk = max (D1.maxstk, ..., Dm.maxstk, S1.maxstk, ..., Sn.maxstk); S.code = [D1.code] setstk k1 ... [Dm.code] setstk km [S1.code] ... [Sn.code] else let k1 = S.reg + 1 ... km = S.reg + m env0 = S.regenv env1 = env0 [D1.name: k1] ... envm = env{m-1} [Dm.name: km] in D1.class = ... = Dm.class = S.class; D1.env = ... = Dm.env = S.env; D1.stkenv = ... = Dm.stkenv = S.stkenv; D1.regenv = env0; D2.regenv = env1; ... Dm.regenv = env{m-1}; D1.reg = S.reg; D2.reg = k1; ... Dm.reg = k{m-1}; D1.stk = ... = Dm.stk = S.stk; S1.sleaf = ... = Sn.sleaf = true; S1.tail = ... S{n-1}.tail = false; Sn.tail = S.tail; S1.class = ... = Sn.class = S.class; S1.rtn = ... = Sn.rtn = S.rtn; S1.env = ... = Sn.env = S.env; S1.stkenv = ... = Sn.stkenv = S.stkenv; S1.regenv = ... = Sn.regenv = envm; S1.reg = ... = Sn.reg = km; S1.stk = ... = Sn.stk = S.stk; S.maxstk = max (D1.maxstk, ..., Dm.maxstk, S1.maxstk, ..., Sn.maxstk); S.code = [D1.code] setreg k1 ... [Dm.code] setreg km [S1.code] ... [Sn.code] E --> E1 = E2 E1.lhs = true; E2.lhs = false; E1.tail = E2.tail = false; E1.class = E2.class = E.class; E1.env = E2.env = E.env; E1.stkenv = E2.stkenv = E.stkenv; E1.regenv = E2.regenv = E.regenv; E1.reg = E2.reg = E.reg; E1.stk = E2.stk = E.stk; E.maxstk = max (E1.maxstk, E2.maxstk); E.code = [E2.code] [E1.code] E --> E1 || E2 let L1, L2 = new labels in E1.lhs = E2.lhs = false; E1.tail = false; E2.tail = E.tail; E1.class = E2.class = E.class; E1.env = E2.env = E.env; E1.stkenv = E2.stkenv = E.stkenv; E1.regenv = E2.regenv = E.regenv; E1.reg = E2.reg = E.reg; E1.stk = E2.stk = E.stk; E.maxstk = max (E1.maxstk, E2.maxstk); E.code = [E1.code] branchf L1 const #t skip L2 L1: [E2.code] L2: E --> E1 && E2 let L1, L2 = new labels in E1.lhs = E2.lhs = false; E1.tail = false; E2.tail = E.tail; E1.class = E2.class = E.class; E1.env = E2.env = E.env; E1.stkenv = E2.stkenv = E.stkenv; E1.regenv = E2.regenv = E.regenv; E1.reg = E2.reg = E.reg; E1.stk = E2.stk = E.stk; E.maxstk = max (E1.maxstk, E2.maxstk); E.code = [E1.code] branchf L1 [E2.code] skip L2 L1: const #f L2: E --> E1 B E2 E1.lhs = E2.lhs = false; E1.tail = E2.tail = false; E1.class = E2.class = E.class; E1.env = E2.env = E.env; E1.stkenv = E2.stkenv = E.stkenv; E1.regenv = E2.regenv = E.regenv; E1.reg = E.reg; E2.reg = E.reg + 1; E1.stk = E2.stk = E.stk; E.maxstk = max (E1.maxstk, E2.maxstk); let k1 = E.reg + 1 k2 = E.reg + 2 in B.reg = k2; E.code = [E1.code] setreg k1 [E2.code] setreg k2 reg k1 [B.code] E --> U E1 E1.lhs = false; E1.tail = false; E1.class = E.class; E1.env = E.env; E1.stkenv = E.stkenv; E1.regenv = E.regenv; E1.reg = E.reg; E1.stk = E.stk; E.maxstk = E1.maxstk; U.reg = E.reg; E.code = [E1.code] [U.code] E --> L E.maxstk = E.stk; E.code = L.code. L --> null L.code = const () L --> true L.code = const #t L --> false L.code = const #f L --> 'c' (where c is any character) L.code = const #\c L --> "..." (where ... is any string) L.code = const "..." L --> n (where n is any int literal) L.code = const n L --> x (where x is any float literal) L.code = const x E --> new R () let n = E.n1 inits = { L0, ..., Ln-1 } k1 = E.reg + 1 k2 = E.reg + 2 k3 = E.reg + 3 in E.maxstk = E.stk; E.code = const 0 setreg k3 const n op2 make-vector,k3 setreg k1 const L0 | setreg k3 | const 0 | setreg k2 | reg k1 | op3 vector-set!,k2,k3 | ... const Ln-1 | setreg k3 | const n-1 | setreg k2 | reg k1 | op3 vector-set!,k2,k3 | reg k1 E --> new T [ E1 ] let inits = { L0 } k1 = E.reg + 1 in E1.lhs = false; E1.tail = false; E1.class = E.class; E1.env = E.env; E1.stkenv = E.stkenv; E1.regenv = E.regenv; E1.reg = k1; E1.stk = E.stk; E.maxstk = E1.maxstk; E.code = const L0 setreg k1 [E1.code] op2 make-vector,k1 E --> R.I If E.lhs then E.maxstk = E.stk; E.code = setglbl R.I else E.maxstk = E.stk; E.code = global R.I E --> I E.maxstk = E.stk; If 0 = lookupRib (E.regenv, I) then if E.lhs then let k = lookupOffset (E.regenv, I) in E.code = setreg k else let k = lookupOffset (E.regenv, I) in E.code = reg k else if 0 = lookupRib (E.stkenv, I) then if E.lhs then let k = lookupOffset (E.stkenv, I) in E.code = setstk k else let k = lookupOffset (E.stkenv, I) in E.code = stack k else if lookupRib (E.env, I) >= 0 then if E.lhs then let m = lookupRib (E.env, I) k = lookupOffset (E.env, I) in E.code = setlex m,k else let m = lookupRib (E.env, I) k = lookupOffset (E.env, I) in E.code = lexical m,k else if E.lhs then let R = E.class in E.code = setglbl R.I else let R = E.class in E.code = global R.I E --> E1.I If E.lhs then let n1 = E.n1 k1 = E.reg + 1 k2 = E.reg + 2 k3 = E.reg + 3 in E1.lhs = false; E1.tail = false; E1.class = E.class; E1.env = E.env; E1.stkenv = E.stkenv; E1.regenv = E.regenv; E1.reg = k1; E1.stk = E.stk; E.maxstk = E1.maxstk; E.code = setreg k1 [E1.code] setreg k2 const n1 setreg k3 reg k2 op3 vector-set!,k3,k1 else let n1 = E.n1 in E1.lhs = false; E1.tail = false; E1.class = E.class; E1.env = E.env; E1.stkenv = E.stkenv; E1.regenv = E.regenv; E1.reg = E.reg; E1.stk = E.stk; E.maxstk = E1.maxstk; E.code = [E1.code] op2imm vector-ref,n1 E --> E1 [ E2 ] If E.lhs then let k3 = E.reg + 1 k1 = E.reg + 2 k2 = E.reg + 3 in E1.lhs = E2.lhs = false; E1.tail = E2.tail = false; E1.class = E2.class = E.class; E1.env = E2.env = E.env; E1.stkenv = E2.stkenv = E.stkenv; E1.regenv = E2.regenv = E.regenv; E1.reg = k3; E2.reg = k1; E1.stk = E2.stk = E.stk; E.maxstk = max (E1.maxstk, E2.maxstk); E.code = setreg k3 [E1.code] setreg k1 [E2.code] setreg k2 reg k1 op3 vector-set!,k2,k3 else let k1 = E.reg + 1 k2 = E.reg + 2 in E1.lhs = E2.lhs = false; E1.tail = E2.tail = false; E1.class = E2.class = E.class; E1.env = E2.env = E.env; E1.stkenv = E2.stkenv = E.stkenv; E1.regenv = E2.regenv = E.regenv; E1.reg = E.reg; E2.reg = k1; E1.stk = E2.stk = E.stk; E.maxstk = max (E1.maxstk, E2.maxstk); E.maxstk = max (E1.maxstk, E2.maxstk); E.code = [E1.code] setreg k1 [E2.code] setreg k2 reg k1 op2 vector-ref,k2 E --> E0 (E1, ..., En) if E.tail and E.stk < 0 then let k0 = E.reg + 1 k1 = k0 + 1 ... kn = k0 + n in E0.lhs = E1.lhs = ... = En.lhs = false; E0.tail = E1.tail = ... = En.tail = false; E0.class = E1.class = ... = En.class = E.class; E0.env = E1.env = ... = En.env = E.env; E0.stkenv = E1.stkenv = ... = En.stkenv = E.stkenv; E0.regenv = E1.regenv = ... = En.regenv = E.regenv; E0.reg = E.reg; E1.reg = k0; E2.reg = k1; ... En.reg = k{n-1}; E0.stk = E1.stk = ... = En.stk = E.stk; E.maxstk = max (E0.maxstk, E1.maxstk, ..., En.maxstk); E.code = [E0.code] setreg k0 [E1.code] setreg k1 ... [En.code] setreg kn reg k0 movereg k1,1 ... movereg kn,n invoke n else if E.tail then let k0 = E.stk + 1 k1 = k0 + 1 ... kn = k0 + n in E0.lhs = E1.lhs = ... = En.lhs = false; E0.tail = E1.tail = ... = En.tail = false; E0.class = E1.class = ... = En.class = E.class; E0.env = E1.env = ... = En.env = E.env; E0.stkenv = E1.stkenv = ... = En.stkenv = E.stkenv; E0.regenv = E1.regenv = ... = En.regenv = E.regenv; E0.reg = E1.reg = ... = En.reg = E.reg; E0.stk = E.stk; E1.stk = k0; E2.stk = k1; ... En.stk = k{n-1}; E.maxstk = max (kn, E0.maxstk, E1.maxstk, ..., En.maxstk); E.code = [E0.code] setstk k0 [E1.code] setstk k1 ... [En.code] setstk kn stack k0 load 1,k1 ... load n,kn popstk invoke n else let L1 = new label k0 = E.stk + 1 k1 = k0 + 1 ... kn = k0 + n m = E.reg j0 = kn + 1 j1 = j0 + 1 ... jm = j0 + m in E0.lhs = E1.lhs = ... = En.lhs = false; E0.tail = E1.tail = ... = En.tail = false; E0.class = E1.class = ... = En.class = E.class; E0.env = E1.env = ... = En.env = E.env; E0.stkenv = E1.stkenv = ... = En.stkenv = E.stkenv; E0.regenv = E1.regenv = ... = En.regenv = E.regenv; E0.reg = E1.reg = ... = En.reg = E.reg; E0.stk = E.stk; E1.stk = k0; E2.stk = k1; ... En.stk = k{n-1}; E.maxstk = max (jm, E0.maxstk, E1.maxstk, ..., En.maxstk); E.code = [E0.code] setstk k0 [E1.code] setstk k1 ... [En.code] setstk kn store 0,j0 store 1,j1 ... store m,jm stack k0 load 1,k1 ... load n,kn setrtn L1 invoke n L1: .cont load 0,j0 load 1,j1 ... load m,jm B --> iEq let k = B.reg B --> iEq_bool in B --> iEq_char B.code = op2 eq?,k B --> iNe let k = B.reg B --> iNe_bool in B --> iNe_char B.code = op2 eq?,k op1 not B --> iEq_int let k = B.reg in B.code = op2 =,k B --> iNe_int let k = B.reg in B.code = op2 =,k op1 not B --> iLt_int let k = B.reg in B.code = op2 <,k B --> iGt_int let k = B.reg in B.code = op2 >,k B --> iLe_int let k = B.reg in B.code = op2 <=,k B --> iGe_int let k = B.reg in B.code = op2 >=,k B --> iEq_double let k = B.reg in B.code = op2 =,k B --> iNe_double let k = B.reg in B.code = op2 =,k op1 not B --> iLt_double let k = B.reg in B.code = op2 <,k B --> iGt_double let k = B.reg in B.code = op2 >,k B --> iLe_double let k = B.reg in B.code = op2 <=,k B --> iGe_double let k = B.reg in B.code = op2 >=,k B --> iPlus_int let k = B.reg in B.code = op2 +,k B --> iMinus_int let k = B.reg in B.code = op2 -,k B --> iTimes_int let k = B.reg in B.code = op2 *,k B --> iDivide_int let k = B.reg in B.code = op2 quotient,k B --> iPlus_double let k = B.reg in B.code = op2 +,k B --> iMinus_double let k = B.reg in B.code = op2 -,k B --> iTimes_double let k = B.reg in B.code = op2 *,k B --> iDivide_double let k = B.reg in B.code = op2 /,k U --> iMinus_int U.code = U --> iMinus_double op1 -- U --> iNot U.code = op1 not