Uni /COMP4403/Week 12.2

Week 12.2

CourseCompilers & Interpreters
SemesterS1 2022

Week 12.2

🏷️ Replace this section with some keywords that can be used for searching, tagging and the indexing of this page.

Sections

🌱 Links to all Heading1 Blocks in this page.

  1. Static Semantics of PL0 Declarations

1.0 - Static Semantics of PL0 Declarations

1.1 - PL0 Abstract Syntax

1.1.1 - Abstract Syntax for Declarations

program::=blockblock::=blk(ds,s)ds::=idβ‡Έdd::=const(c)∣     type(t)∣     var(t)∣     proc(block)c::=n | id | op(-_,c)t::=id | [c..c]\def\pmaps{β‡Έ} \begin{aligned} \text{program} ::&= \text{block}\\ \text{block} ::&= \text{blk(ds,s)}\\ \text{ds} ::&= \text{id}\pmaps\text{d}\\ \text{d} ::&= \text{const(c)}\\ &|\ \ \ \ \ \text{type(t)}\\ &|\ \ \ \ \ \text{var(t)}\\ &|\ \ \ \ \ \text{proc(block)}\\ \text{c}::&= \text{n | id | op(-\_,c)}\\ \text{t}::&=\text{id | [c..c]}\\ \end{aligned}

  • The notation idβ‡Έd\text{id} β‡Έ\text{d} stands for a mapping from identifiers to declarations

1.1.2 - Abstract Syntax for Statements

s::=assign(lv,e)∣     write(e)∣     read(lv)∣     call(id)∣     if(e,s,s)∣     while(e,s)∣     list(seq s)lv::=ide::=n | lv | op(unary, e) | op(binary, (e, e))unary::=-_binary::=_ + _ | _ βˆ’ _ | _ βˆ— _ | _/_ | _ = _ | _ 6 β‰  _ |          _ < _ | _ β‰€ _ | _ > _ | _ β‰₯ _\begin{aligned} s ::&= \text{assign(lv,e)}\\ &|\ \ \ \ \ \text{write(e)}\\ &|\ \ \ \ \ \text{read(lv)}\\ &|\ \ \ \ \ \text{call(id)}\\ &|\ \ \ \ \ \text{if(e,s,s)}\\ &|\ \ \ \ \ \text{while(e,s)}\\ &|\ \ \ \ \ \text{list(seq s)}\\ \text{lv}::&=\text{id}\\ \small\text{e}::&= \small\text{n | lv | op(unary, e) | op(binary, (e, e))}\\ \text{unary}::&=\text{-\_}\\ \text{binary}::&=\text{\_ + \_ | \_ βˆ’ \_ | \_ βˆ— \_ | \_/\_ | \_ = \_ | \_ 6 }β‰ \text{ \_ |}\\ &\ \ \ \ \ \ \ \ \ \text{ \_ < \_ | \_ ≀ \_ | \_ > \_ | \_ β‰₯ \_} \end{aligned}

1.1.3 - Example PL0 Program

// Declarations for main procedure
const K = 10;
type  S = [-K..K];
		  W = S;
var   x : S;
      y : W;
procedure q() =
	var x : boolean;
	begin
		x := (y > 0);
		if x then write 1 else write 0
	end; // q
begin // main
	x := 2;
	y := -x;
	call q();
	write x
end // main
  • The code in the main method (enclosed between begin and end) are interpreted with respect to the variables defined at the top of the file
  • The code in the procedure q is interpreted with respect to the symbol table of the main method extended with the variables defined in the procedure itself.
    • The definition of the identifier xx in procedure qq as var x : boolean; masks the definition of x:Sx : S in the scope of the main method

Abstract Syntax Tree

  • Consider the declarations in the program above:

    const K = 10;
type  S = [-K..K];
		  W = S;
var   x : S;
      y : W;
procedure q() =
		...

  • We have the following declarations:

\begin{aligned} \text{ds}={K&\mapsto\text{const(10),}\ S&\mapsto\text{type([op(-_, K)…K])},\ \text{W}&\mapsto\text{type(S)},\ \text{x}&\mapsto\text{var(S)},\ \text{y}&\mapsto\text{var(W)},\ \text{q}&\mapsto\text{proc(blk({x}\mapsto\text{var(boolean)}, list([…]))}} \end{aligned}

- In which, we also have the procedure block defined as follows, in the AST $\text{blk(ds, list([assign(x,2), assign(y, op(-\_, x)), call(q), write(x)]))}$ ### 1.1.4 - Reminder β†’ PL0 Types - Scalar Types - `int` - `boolean` - `subrange(T, lower, upper)`, where T is either int or boolean - Reference types, `ref(T)` for variables store an address. - Product Types $T_1\times T_2$ is type type of pairs $(x,y)$ where $x\in T_1$ and $y\in T_2$, - Function Types $T_1\rightarrow T_2$ is the type of functions with arguments of type $T_1$ and results of type $T_2$, known as the function type - For example, the following are the types of some operators - $-\_:\text{int}\rightarrow\text{int}$ - $\_+\_:\text{int}\times\text{int}\rightarrow\text{int}$ - $\text{\_=\_}:\text{int}\times\text{int}\rightarrow\text{boolean}$ - $\_=\_:\text{boolean}\times\text{boolean}\rightarrow\text{boolean}$ ### 1.1.5 - Symbol Table - The symbol table stores all of the declarations from the PL0 programs. - The symbol is a mapping from symbol identifiers to entries: 

\text{syms}\in\text{id}β‡Έ\text{SymEntry}
$$

  • The symbol table entries contain constants, types, variables and procedures:

    • Observe that the constructor for a constant entry takes a PL0 type and an integer
    • The constructor for a type entry takes a PL0 type.
    • The constructor for a variable entry takes a PL0 type.
    • The constructor for a PL0 entry takes a block (which contains declarations and the procedure code itself)

    SymEntry::= ConstEntry(T,Z) βˆ£TypeEntry(T) |VarEntry(T) |ProcEntry(block)\begin{aligned} \text{SymEntry}::=\ &\text{ConstEntry(T,}\mathbb{Z})\ | \\ &\text{TypeEntry(T) |}\\ &\text{VarEntry(T) |}\\ &\text{ProcEntry(block)} \end{aligned}

1.2 - Static Semantics of Constants

  • From before, we had that constants and types can appear in declarations:

    d::=const(c)∣     type(t)∣     var(t)∣     proc(block)c::=n | id | op(-_,c)t::=id | [c..c]\begin{aligned} \text{d} ::&= \text{const(c)}\\ &|\ \ \ \ \ \text{type(t)}\\ &|\ \ \ \ \ \text{var(t)}\\ &|\ \ \ \ \ \text{proc(block)}\\ \text{c}::&= \text{n | id | op(-\_,c)}\\ \text{t}::&=\text{id | [c..c]}\\ \end{aligned}

  • Since we can determine the value of a constant at compilation time, we can enforce additional constraints on them.

  • We determine the value of constants in the static semantics phase of a compiler.

  • The following rules outline how we evaluate the value of constant expressions during the type checking phase of the compiler.

  1. Integer Constant Rule
  2. Constant Identifier Rule
  3. Negated Constant Rule
  4. Type Identifier Rule
  5. Subrange Type Rule
  6. Constant Declaration Rule
  7. Constant Entry Rule
  8. Type Declaration Rule
  9. Type Entry Rule

Integer Constant Rule

0≀n≀maxintβ€Ύsyms⊒nβ†’en\underline{0\le n \le \text{maxint}}\\ \text{syms}\vdash n\overset e \rightarrow n

0≀10≀maxintβ€Ύsyms⊒10β†’e10\underline{0\le{\color{lightgreen}10}\le\text{maxint}}\\ \text{syms}\vdash {\color{lightgreen}10} \overset e \rightarrow {\color{lightgreen}10}

  • This means that in the context of (any) symbol table, an integer constant evaluates to its value if it is between 0 and maxint\color{lightblue}\text{maxint} (inclusive).

Constant Identifier Rule

id∈dom(syms)syms(id)=ConstEntry(T,v)β€Ύsyms⊒idβ†’ev\text{id}\in\text{dom(syms)}\\ \underline{ \text{syms(id)=ConstEntry(T,v)}\\ }\\ \text{syms}\vdash\text{id}\overset e \rightarrow\text{v}

K∈dom(syms)syms(K)=ConstEntry(int,10)β€Ύsyms⊒Kβ†’e10\text{\color{lightgreen}K}\in\text{dom(syms)}\\ \underline{\text{syms({\color{lightgreen}K})=ConstEntry(int,10)}}\\ \text{syms}\vdash\text{\color{lightgreen}K}\overset e \rightarrow \text{10}

  • An identifier evaluates to a value v\color{lightblue} \text{v} if it is in the domain of the symbol table (dom(syms)\color{lightblue}\text{dom(syms)}) and the entry associated with that identifier in the symbol table is a constant entry (with type T\color{lightblue}\text{T} and value v\color{lightblue}\text{v})

Negated Constant Rule

syms⊒c:intsyms⊒cβ†’evsyms⊒op(-_, c)β†’eβˆ’vβ€Ύ\text{syms}\vdash c : \text{int}\\ \text{syms}\vdash c \overset e \rightarrow \text{v}\\ \overline{\text{syms}\vdash\text{op(-\_, c)}\overset e\rightarrow -\text{v}}

syms⊒K:intsyms⊒Kβ†’evsyms⊒op(-_, K)β†’eβˆ’vβ€Ύ\text{syms}\vdash {\color{lightgreen}\text{K}} : \text{int}\\ \text{syms}\vdash {\color{lightgreen}\text{K}} \overset e \rightarrow \text{v}\\ \overline{\text{syms}\vdash\text{op(-\_, {\color{lightgreen}\text{K}})}\overset e\rightarrow -\text{v}}

  • A constant identifier evaluates to -v\color{lightblue}\text{-v} if the constant expression c\color{lightblue} c is well typed, and of an integer type as well as evaluates to some value v\color{lightblue}\text{v}

Type Identifier Rule

id∈dom(syms)syms(id)=TypeEntry(T)β€Ύsyms⊒typeof(id)=T\text{id}\in\text{dom(syms)}\\ \underline{\text{syms(id)=TypeEntry(T)}}\\ \text{syms}\vdash\text{typeof(id)=T}

S∈dom(syms)syms(S)=TypeEntry(subrange(int, -10, 10)β€Ύsyms⊒typeof(S)=subrange(int,-10,10)\text{S}\in\text{dom(syms)}\\ \underline{\text{syms(S)=TypeEntry(subrange(int, -10, 10)}}\\ \text{syms}\vdash\text{typeof(S)=subrange(int,-10,10)}

  • The type of an identifier is defined if the identifier is in the domain of the symbol table id∈dom(syms)\color{lightblue}\text{id}\in\text{dom(syms)} and the symbol table has a type entry corresponding to the identifier of type T\color{lightblue}\text{T}, then the type of the identifier is T\color{lightblue}\text{T}

Subrange Type Rule

syms⊒c0 : Tsyms⊒c0β†’ev0syms⊒c1 : Tsyms⊒c1β†’ev1v0 β‰€ v1T∈{int, boolean}syms⊒typeof([c0..c1])=subrange(T,v0,v1)β€Ύ\def\eval{\overset e \rightarrow} \text{syms}\vdash\text{c0 : T}\\ \text{syms}\vdash\text{c0}\eval \text{v}0\\ \text{syms}\vdash\text{c1 : T}\\ \text{syms}\vdash\text{c1}\eval\text{v1}\\ \text{v0 }\le\text{ v1}\\ \text{T}\in\text{\{int, boolean\}}\\ \overline{\text{syms}\vdash\text{typeof([c0..c1])=subrange(T,v0,v1)}}

  • If the constant expression c0\color{lightblue}\text{c0} is well typed and has type T\color{lightblue}\text{T} and evaluates to the value v0\color{lightblue}\text{v0} in the context of the symbol table, and

  • If the constant expression c1\color{lightblue}\text{c1} is well typed and has type T\color{lightblue}\text{T} and evaluates to the value v1\color{lightblue}\text{v1} in the context of the symbol table, and

  • We also require that v0≀v1\color{lightblue}\text{v0}\le\text{v1} and that the types of the two constant expressions are the same, and are either an integer or Boolean T∈{int, boolean}\color{lightblue}\text{T}\in\text{\{int, boolean\}}

  • For example, let’s consider the symbol table entry for the subrange type K\color{lightblue}K in our PL0 code above:

    const K = 10;
type  S = [-K..K];

  • Consider its well-formedness:

    syms⊒op(-_, K) : intsyms⊒op(-_, K)β†’e-10syms⊒K : Tsyms⊒Kβ†’e10-10 β‰€ 10int∈{int, boolean}syms⊒typeof([op(-_,K)..10])=subrange(int, -10, 10)β€Ύ\def\eval{\overset e \rightarrow} \text{syms}\vdash\text{{\color{lightgreen}op(-\_, K) : int}}\\ \text{syms}\vdash\text{{\color{lightgreen}op(-\_, K)}}\eval \text{\color{lightgreen}-10}\\ \text{syms}\vdash\text{\color{lightgreen}K : T}\\ \text{syms}\vdash\text{\color{lightgreen}K}\eval\text{\color{lightgreen}10}\\ \text{\color{lightgreen}-10 }\le\text{ \color{lightgreen}10}\\ \text{\color{lightgreen}int}\in\text{\{int, boolean\}}\\ \overline{\text{syms}\vdash\text{typeof([{\color{lightgreen}op(-\_,K)}..{\color{lightgreen}10}])=subrange({\color{lightgreen}int, -10, 10})}}

Constant Declaration Rule

syms⊒cβ†’evsyms⊒c : TT∈{int, boolean}syms⊒WFDeclaration(const(c))β€Ύ\text{syms}\vdash\text{c}\overset e\rightarrow \text{v}\\ \text{syms}\vdash\text{c : T}\\ \text{T}\in\text{\{int, boolean\}}\\ \overline{\text{syms}\vdash\text{WFDeclaration(const(c))}}

  • A constant declaration is well formed in the context of the symbol table iff:
    • The constant expression c\color{lightblue}\text{c} evaluates to some value v\color{lightblue}\text{v}, and
    • The constant expression has some type T\color{lightblue}\text{T}, which is either an integer or Boolean

Constant Entry Rule

syms⊒cβ†’evsyms⊒c : TT∈{int, boolean}entry(syms, const(c)=ConstEntry(T,v)β€Ύ\text{syms}\vdash\text{c}\overset e\rightarrow \text{v}\\ \text{syms}\vdash\text{c : T}\\ \text{T}\in\text{\{int, boolean\}}\\ \overline{\text{entry(syms, const(c)}=\text{ConstEntry(T,v)}}

  • If the above premises hold (same as for the Constant Declaration Rule), we can find out what the constant entry is in the context of the symbol table.
  • We can find the constant entry, with type T\color{lightblue}\text{T} and value v\color{lightblue}\text{v}

Type Declaration

syms⊒typeof(t)=Tsyms⊒WFDeclaration(type(t))β€Ύ\text{syms}\vdash\text{typeof(t)=T}\\ \overline{\text{syms}\vdash\text{WFDeclaration(type(t))}}\\

  • Given a declaration of type t, type(t)\color{lightblue}\text{type(t)}, we know it is well formed in the context of a symbol table, if the type of t in the context of the symbol table is of some PL0 type T
  • We have additional rules which describe how to evaluate what the type T\color{lightblue}\text{T} is.

Type Entry

syms⊒typeof(t)=Tentry(syms,type(t))=TypeEntry(T)β€Ύ\text{syms}\vdash\text{typeof(t)=T}\\ \overline{\text{entry(syms,type(t))=TypeEntry(T)}}

  • If in the context of a symbol table, the type of t\color{lightblue}\text{t} is type T\color{lightblue}\text{T}, then we know that the symbol table entry for the type T\color{lightblue}\text{T} is a TypeEntry(T)\color{lightblue}\text{TypeEntry(T)}

1.3 - Static Semantics Rules for Variable Entries

  1. Variable Declaration
  2. Variable Entry

Variable Declaration

syms⊒typeof(t)=Tsyms⊒WFDeclaration(var(t))β€Ύ\text{syms}\vdash\text{typeof(t)=T}\\ \overline{\text{syms}\vdash\text{WFDeclaration(var(t))}}

  • A variable declaration is well formed, if the type t\color{lightblue}\text{t} exists in the context of the symbol table, and its type evaluates to some PL0 type T\color{lightblue}\text{T}

Variable Entry

syms⊒typeof(t)=Tentry(syms, var(t))=VarEntry(ref(T))β€Ύ\text{syms}\vdash\text{typeof(t)=T}\\ \overline{\text{entry(syms, var(t))=VarEntry(ref(T))}}

  • If the premise from the rule above holds, we can also find the variable entry in the symbol table.
    • The type is ref(T)\color{lightblue}\text{ref(T)} as it is a variable type.

1.4 - Static Semantics Rules for Procedures

  1. Procedure Declaration
  2. Procedure Entry

Procedure Declaration

syms⊒WFBlock(block)syms⊒WFDeclaration(proc(block))β€Ύ\text{syms}\vdash\text{WFBlock(block)}\\ \overline{\text{syms}\vdash\text{WFDeclaration(proc(block))}}

  • This is quite simple at the moment, given that the PL0 compiler doesn’t accept parameters.
  • A procedure declaration is well formed in the context of the symbol table if and only if the block is well formed.

Procedure Entry

syms⊒WFBlock(block)entry(syms, proc(block))=ProcEntry(block)β€Ύ\text{syms}\vdash\text{WFBlock(block)}\\ \overline{\text{entry(syms, proc(block))=ProcEntry(block)}}

  • Given that the above premise holds, we can once again determine the symbol table entry of the procedure.

2.0 - Cycles in Declarations

{k↦const(op(-_,m)),m↦const(op(-_,n)),n↦const(op(-_,k)     }\begin{aligned} \{ \text{k}&\mapsto\text{const(op(-\_,m)),}\\ \text{m}&\mapsto\text{const(op(-\_,n)),}\\ \text{n}&\mapsto\text{const(op(-\_,k)}\ \ \ \ \ \} \end{aligned}

  • The syntax of PL0 allows for cyclic definitions, as shown on the slide.
  • In the static semantics of PL0, we enforce that cyclic definitions are not allowed.

2.1 - Uses Operator

🌱 We define this operator here, so that we can use it in the definition below.

  • We create the uses\text{uses} operator, which specifies the identifiers used in the declaration:

    uses(const(c))=uses(c)uses(type(t))=uses(t)uses(var(t))=uses(t)proc(block)={}\begin{aligned} \text{uses(const(c))}&=\text{uses(c)}\\ \text{uses(type(t))}&=\text{uses(t)}\\ \text{uses(var(t))}&=\text{uses(t)}\\ \text{proc(block)}&=\text{\{\}} \end{aligned}

  • The identifiers used within a constant expression or type are also given by the function uses\text{uses}

    uses(n)={}uses(id)={id}uses(op(-_,c))}=uses(c)uses([c0..c1])=uses(c0)βˆͺuses(c1)\begin{aligned} \text{uses(n)}&=\{\}\\ \text{uses(id)}&=\text{\{id\}}\\ \text{uses(op(-\_,c))\}}&=\text{uses(c)}\\ \text{uses([c0..c1])}&=\text{uses(c0)}\cup\text{uses(c1)} \end{aligned}

  • Note here that n\text{n} denotes a number

    uses(const(10))={}uses(type([op(-_,K),,K)])={K}uses(type(S))={S}uses(var(s))={S}uses(var(W))={W}uses(proc(blk(⋯ ,⋯ )))={}\def\uses{\text{uses}} \begin{aligned} \uses\text{(const(10))}&=\{\}\\ \uses\text{(type([op(-\_,K),,K)])}&=\text{\{K\}}\\ \uses\text{(type(S))}&=\text{\{S\}}\\ \uses\text{(var(s))}&=\text{\{S\}}\\ \uses\text{(var(W))}&=\text{\{W\}}\\ \text{uses(proc(blk(}\cdots,\cdots)))&=\{\} \end{aligned}

2.2 - Static Semantics Rules for Procedure Blocks

  1. Well Formed Block
  2. EntryDecl

Well Formed Block

ds_uses = {id1∈dom(ds); id2∈uses(ds(id1))βˆ™id1↦id2}Β¬βˆƒid∈dom(ds)βˆ™((id↦id)∈ds_uses+)symsβ€²=syms βŠ•{id∈dom(ds)βˆ™id↦entryDecl(syms,ds,ds(id))}βˆ€id∈dom(ds)βˆ™(symsβ€²βŠ’WFDeclaration(ds(id)))symsβ€²βŠ’WFStatement(s)syms⊒WFBlock(blk(ds,s))\begin{array}{cc} \text{ds\_uses = \{id}_1\in\text{dom(ds); id}_2\in\text{uses(ds(id}_1\text{))}\bullet\text{id}_1\mapsto\text{id}_2\}\\ \neg\exists\text{id}\in\text{dom(ds)}\bullet\text{((id}\mapsto\text{id)}\in\text{ds\_uses}^+)\\ \text{syms}'=\text{syms }\oplus \{\text{id}\in\text{dom(ds)}\bullet\text{id}\mapsto\text{entryDecl(syms,ds,ds(id))}\}\\ \forall\text{id}\in\text{dom(ds)}\bullet(\text{syms}'\vdash\text{WFDeclaration(ds(id))})\\ \text{syms}'\vdash\text{WFStatement(s)}\\ \hline \text{syms}\vdash\text{WFBlock(blk(ds,s))} \end{array}

  1. We first know that we want the statements in a procedure block to be well formed.

    • However, we want it to be extended in the context of the symbol table augmented with the definitions defined in ds\color{lightblue}\text{ds} as well

      symsβ€²βŠ’WFStatement(s)\text{syms}'\vdash\text{WFStatement(s)}

  2. We also want the declarations in the procedure definition block to be well formed in the context of the (augmented) symbol table symsβ€²\color{lightblue}\text{syms}'

    βˆ€id∈dom(ds)βˆ™symsβ€²βŠ’WFDeclaration(ds(id)))\forall\text{id}\in\text{dom(ds)}\bullet\text{syms}'\vdash\text{WFDeclaration(ds(id)))}

  3. The extended symbol table is defined by the following formal notation:

    symsβ€²=syms βŠ• {id∈dom(ds)βˆ™id↦entryDecl(syms, ds, ds(id))}\text{syms}'=\text{syms}\ \oplus\ \{\text{id}\in\text{dom(ds)}\bullet\text{id}\mapsto\text{entryDecl(syms, ds, ds(id))\}}

    • That is, the augmented symbol table symsβ€²\color{lightblue}\text{syms}' is given by adding the existing symbol table to the mapping of every identifier in the declarations ds\color{lightblue}\text{ds} to each entry declaration - this is formally denoted as id↦entryDecl(syms,ds,ds)id))\color{lightblue}\text{id}\mapsto\text{entryDecl(syms,ds,ds)id))}

  4. We also add a rule which describes that we aren’t allowed to have cycles in our declarations ds\color{lightblue}\text{ds}.

    ds_uses = {id1∈dom(ds); id2∈uses(ds(id1))βˆ™id1↦id2}Β¬βˆƒid∈dom(ds)βˆ™((id↦id)∈ds_uses+)\color{lightblue}\text{ds\_uses = \{id}_1\in\text{dom(ds); id}_2\in\text{uses(ds(id}_1\text{))}\bullet\text{id}_1\mapsto\text{id}_2\}\\ \neg\exists\text{id}\in\text{dom(ds)}\bullet\text{((id}\mapsto\text{id)}\in\text{ds\_uses}^+)\\

    • We first define a β€œdirectly uses” relationship:

    • For any identifier in our declarations, id1∈dom(ds)\color{lightblue}\text{id}_1 \in\text{dom(ds)}, if there is another identifier that directly uses this (original identifier) id2∈uses(ds(id1))\color{lightblue}\text{id}_2\in\text{uses(ds(id}_1 )) then there exists a mapping between these two identifiers, denoted id1↦id2\color{lightblue}\text{id}_1\mapsto\text{id}_2

    • However, our constraint shouldn’t just be whether a mapping - we need to consider the case where we have transitive dependencies.

    • Therefore, our constraint is:

      Β¬βˆƒid∈dom(ds)βˆ™((id↦id)∈ds_uses+)\color{lightblue}\neg\exists\text{id}\in\text{dom(ds)}\bullet ((\text{id}\mapsto\text{id})\in\text{ds\_uses}^+)

    • Where ds_uses+\color{lightblue}\text{ds\_uses}^+ is the transitive closure of this mapping relationship:

      • Transitive Closure

    • That is, an identifier cannot transitively depend on itself.

    EntryDecl

    🌱 We said before, that each identifier gets an entry in the augmented symbol table. What does this mean, and how is it done?

    symsβ€²=symsβŠ•{id∈(dom(ds)∩uses(d))βˆ™(id↦entryDecl(syms,ds,ds(id))entryDecl(syms,ds,d)=entry(symsβ€², d)\def\syms{\text{syms}} \def\id{\text{id}} \begin{array}{cc} \small\syms'=\syms\oplus\{\id\in\text{(dom(ds)}\cap\text{uses(d))}\bullet(\id\mapsto\text{entryDecl(syms,ds,ds(id))}\\ \hline \text{entryDecl(syms,ds,d)=entry(syms}'\text{, d)} \end{array}

    • The symbol table entry for d\color{lightblue}\text{d}, where d∈ds\color{lightblue}\text{d}\in\text{ds} in the context of the symbol table syms\color{lightblue}\text{syms}, denoted entryDecl(syms,ds,d)\color{lightblue}\text{entryDecl(syms,ds,d)} is given as the entry of d\color{lightblue}\text{d} in the context of the extended symbol table symsβ€²\color{lightblue}\text{syms}'.

    • Note here that the definition of the augmented symbol table symsβ€²\color{lightblue}\text{syms}' has changed - it is only augmented by the identifiers in ds\color{lightblue}\text{ds} that d\color{lightblue}\text{d} directly uses, denoted dom(ds)∩uses(d)\color{lightblue}\text{dom(ds)}\cap\text{uses(d)}

    • Additionally, if this condition is met, the identifier will have an entry declaration (which is defined recursively using this rule)

      id↦entryDecl(syms,ds,ds(id)))\color{lightblue}\text{id}\mapsto\text{entryDecl(syms,ds,ds(id)))}

    • This recursion is acceptable (and will terminates) given that the rule above specifies that

2.3.1 - Example of Using Static Semantics Rules

  • Given the following PL0 code:

    // Declarations for main procedure
const K = 10;
type  S = [-K..K];
		  W = S;
var   x : S;
      y : W;
procedure q() =
	var x : boolean;
	begin
		x := (y > 0);
		if x then write 1 else write 0
	end; // q
begin // main
	x := 2;
	y := -x;
	call q();
	write x
end // main

  • And its corresponding abstract syntax tree,

\begin{aligned} \text{ds}={K&\mapsto\text{const(10),}\ S&\mapsto\text{type([op(-_, K)…K])},\ \text{W}&\mapsto\text{type(S)},\ \text{x}&\mapsto\text{var(S)},\ \text{y}&\mapsto\text{var(W)},\ \text{q}&\mapsto\text{proc(blk({x}\mapsto\text{var(boolean)}, list([…]))}} \end{aligned}

$\text{blk(ds, list([assign(x,2), assign(y, op(-\_, x)), call(q), write(x)]))}$ **We want to static check it:** 1. We begin by going through $\color{lightblue}\text{ds}$ and constructing the symbol table entries 1. $\color{lightblue}\text{K}\mapsto\text{const(10)}$ - We initially have the declaration $\color{lightblue}\text{entryDecl(syms,ds,const(10)})$ in which we note that $\color{lightgreen}\text{const(10)}$ doesn’t depend on any identifiers - By the Constant Entry rule using Rule 5.1 and Rule 3.1, we have $\color{lightblue}\text{ConstEntry(int, 10)}$ 2. $\color{lightblue}\text{type([op(-\_, K)..K])}$ - We initially have the declaration $\color{lightblue}\text{entryDecl(syms,ds,type([op(-\_,K)..K]))}$ - We note that this declaration depends on the identifier $\color{lightgreen}\text{K}$ twice - We therefore must compute the entry of $\color{lightgreen}\text{K}$, and augment the symbol table with this entry (by the EntryDecl Rule) 

        \small\color{lightblue}\text{entry(syms}\oplus\{\text{K}\mapsto\text{entryDecl(syms,ds,const(10))}\}, \text{type([op(-\_, K)..K]))}
        $$
        
    - By our previous calculation, we know that the entry for $\color{lightgreen}\text{K}$ is $\color{lightblue}\text{ConstEntry(int, 10)}$
        
        $$
        \small\color{lightblue}\text{entry(syms}\oplus\{\text{K}\mapsto\text{ConstEntry(int,10)}\}, \text{type([op(-\_, K)..K]))}
        $$
        
    - We now determine what the entry of the subrange type $\color{lightgreen}\text{type([op(-\_, K)..K]))}$, in the context of the augmented symbol table $\color{lightgreen}\small\text{entry(syms}\oplus\{\text{K}\mapsto\text{ConstEntry(int,10)}\}$. We apply the Type Entry rule, as well as Rule 5.5 and 3.2 to get the TypeEntry below:
    
    $$
    \color{lightblue}\text{TypeEntry(subrange(int, -10, 10))}
    $$
    
3. $\color{lightblue}\text{type(S)}$
    - We initially have the declaration $\color{lightblue}\text{entryDecl(syms,ds,type(S))}$.
    - Since this declaration depends on the identifier $\color{lightgreen}\text{S}$, we need to compute the entry of this symbol table with respect to the augmented symbol table. (By the EntryDecl rule)
    - Since the entry depends on $\color{lightgreen}\text{S}$, we augment the symbol table with the type entry declaration for it.
        
        $$
        \color{lightblue}\small\text{entry(syms}\oplus\{\text{S}\mapsto\text{entryDecl(syms,ds,type([(op(-\_, K)..K]))\}}, \text{type(S))}
        $$
        
    - By the previous computation, we know that $\small\color{lightblue}\text{entryDecl(syms,ds,type([(op(-\_,K)..K]))}$ evaluates to $\color{lightblue}\text{TypeEntry(subrange(int, -10, 10))}$
        
        $$
        \color{lightblue}\small\text{entry(syms}\oplus\{\text{S}\mapsto\text{\color{lightblue}\text{TypeEntry(subrange(int, -10, 10))}\}}, \text{type(S))}
        $$
        
    - By applying the Type Entry rule and Type Identifier rule, we derive that the type is given by
        
        $$
        \color{lightblue}\text{TypeEntry(subrange(int, -10, 10))}
        $$
        
4. $\color{lightblue}\text{var(S)}$
    - We initially have the declaration $\color{lightblue}\text{entryDecl(syms, ds, var(S)})$
    - Since this declaration depends on the identifier $\color{lightgreen}\text{S}$, we need to compute the entry of this symbol table with respect to the augmented symbol table. (By the EntryDecl rule)
    - Since the entry depends on $\color{lightgreen}\text{S}$, we augment the symbol table with the type entry declaration for it.
        
        $$
        \color{lightblue}\small\text{entry(syms}\oplus\{\text{S}\mapsto\text{entryDecl(syms,ds,type([(op(-\_, K)..K]))\}}, \text{var(S))}
        $$
        
    - By the previous computation, we know that $\small\color{lightblue}\text{entryDecl(syms,ds,type([(op(-\_,K)..K]))}$ evaluates to $\color{lightblue}\text{TypeEntry(subrange(int, -10, 10))}$
        
        $$
        \color{lightblue}\small\text{entry(syms}\oplus\{\text{S}\mapsto\text{\color{lightblue}\text{TypeEntry(subrange(int, -10, 10))}\}}, \text{var(S))}
        $$
        
    - We then apply the Variable Entry and Type Identifier rule to get the following symbol table entry
        
        $$
        \color{lightblue}\text{VarEntry(ref(subrange(int, -10, 10)))}
        $$
        
5. $\color{lightblue}\text{var(W)}$
    - We initially have the declaration $\color{lightblue}\text{entryDecl(syms, ds, var(W))}$
    - Since this declaration depends on the identifier $\color{lightgreen}\text{W}$, we need to compute the entry of this symbol table with respect to the augmented symbol table.
    - We augment the symbol table with the type entry declaration for it:
        
        $$
        \color{lightblue}\text{entry(syms}\oplus\text{\{W}\mapsto\text{entryDecl(syms,ds,type(S)}\}\text{, var(W))}
        $$
        
    - From the previous computation, we know that this can be expressed as
        
        $$
        \color{lightblue}\text{entry(syms}\oplus\{\text{W}\mapsto\text{TypeEntry(subrange(int, -10, 10))\}, var(W))}
        $$
        
    - By the Variable Entry rule and Type Identifier rule, we have:
        
        $$
        \color{lightblue}\text{VarEntry(ref(subrange(int, -10, 10))})
        $$
        
6. $\color{lightblue}\text{proc(\{x}\mapsto\cdots, \}, \text{list}([\cdots]))$
- We initially have the declaration $\scriptsize\color{lightblue}\text{entryDecl(syms, ds, proc(blk(\{x}\mapsto\text{var(boolean)\}, list([}\cdots]))))$.
- By the EntryDecl rule, the declaration is transformed to the following, noting that procedures have no parameters, and therefore only depend on the identifiers used in the block.
- Therefore, by the EntryDecl rule, we have:
    
    $$
    \color{lightblue}\text{entry(syms, proc(blk(\{x}\mapsto\text{var(boolean)\}, list([}\cdots\text{]))))}
    $$
    
- Additionally, by the Procedure Entry rule, we simplify this to:
    
    $$
    \color{lightblue}\text{ProcEntry(blk(\{x}\mapsto\text{var(boolean)\}, list([}\cdots\text{])))}
    $$

  1. We now concatenate the above derivations together, which will be later used to form the augmented symbol table symsβ€²\color{lightblue}\text{syms}'

\color{lightblue}\begin{aligned} \text{ds}={ \text{K}&\mapsto\text{ConstEntry(int,10)},\ \text{S}&\mapsto\text{TypeEntry(subrange(int, -10, 10))},\ \text{W}&\mapsto\text{TypeEntry(subrange(int, -10, 10))},\ \text{x}&\mapsto\text{VarEntry(ref(subrange(int, -10, 10))),}\ \text{y}&\mapsto\text{VarEntry(ref(subrange(int, -10, 10))),}\ \text{q}&\mapsto\text{ProcEntry(blk({x}\mapsto\text{var(boolean)}, list([}\cdots\text{])))} } \end{aligned}

3. Given that we have worked out the extended symbol table, we can now finish the computation of the rule, which requires the checking of the procedure block. The example specific additions are denoted in $\color{lightgreen}\text{green}$ 

\def\k{\text{K}}
\def\s{\text{S}}
\def\w{\text{W}}
\def\x{\text{x}}
\def\y{\text{y}}
\def\q{\text{q}}
\def\gn{\color{lightgreen}}
\begin{array}{cc}
\text{ds\_uses} = \{{\color{lightgreen}\s\mapsto\k, \w\mapsto\s, x\mapsto\s, \y\mapsto\w}\}\\
\neg\exists\text{id}\in\text{dom(ds)}\bullet\text{((id}\mapsto\text{id)}\in\{{\color{lightgreen}\s\mapsto\k, \w\mapsto\s, x\mapsto\s, \y\mapsto\w, }\\{\color{lightgreen}\w\mapsto\k, \x\mapsto\k, \y\mapsto\s, \y\mapsto\k}\})\\
\begin{aligned}
\text{syms}'=\text{syms }\oplus \{\\\\\\\\\\\\
\end{aligned}
\begin{aligned}
\gn\text{K}&\gn\mapsto\text{ConstEntry(int,10)},\\
\gn\text{S}&\gn\mapsto\text{TypeEntry(subrange(int, -10, 10))},\\
\gn\text{W}&\gn\mapsto\text{TypeEntry(subrange(int, -10, 10))},\\
\gn\text{x}&\gn\mapsto\text{VarEntry(ref(subrange(int, -10, 10))),}\\
\gn\text{y}&\gn\mapsto\text{VarEntry(ref(subrange(int, -10, 10))),}\\
\gn\text{q}&\gn\mapsto\text{ProcEntry(blk(\x}\mapsto\text{var(boolean)\}, list([}\cdots\text{])))}\}\\
\end{aligned}
\\
\forall\text{id}\in\text{\gn\{\k, \s, \w, \x, \y, \q\}}\bullet(\text{syms}'\vdash\text{WFDeclaration(ds(id))})\\
\text{syms}'\vdash\small\text{WFStatement(}{\gn\text{list([assign(x,2), assign(y, op(-\_, x)), call(q), write(x)])}})\\
\hline
\text{syms}\vdash\text{WFBlock(blk(ds,s))}
\end{array}
$$

1. Observe here that the original rule form for computing the extended symbol table was
    
    $$
    \color{lightblue}\text{syms}'=\text{syms }\oplus \{\text{id}\in\text{dom(ds)}\bullet\text{id}\mapsto\text{entryDecl(syms,ds,ds(id))}\}
    $$
    
    Here, we have inserted all of the symbol table entries that we have previously computed.
    
2. Now, we need to check that in the context of the new symbol table, the statements in the procedure block are well formed:
    
    $$
    ⁍
    $$
    
3. We also need to check that all of the identifiers in the declarations $\color{lightblue} \text{ds}$ are well formed in the context of the symbol table:
    
    $$
    \color{lightblue}\forall\text{id}\in{\color{lightgreen}\{\text{K, S, W, x, y, q}\}} \bullet(\text{syms}' \vdash \text{WFDeclaration(ds(id))})
    $$
    
4. We also need to check that we don’t have any circular definitions of identifiers:
    
    $$
    \def\k{\text{K}}
    \def\s{\text{S}}
    \def\w{\text{W}}
    \def\x{\text{x}}
    \def\y{\text{y}}
    \def\q{\text{q}}
    \text{ds\_uses} = \{{\color{lightgreen}\s\mapsto\k, \w\mapsto\s, x\mapsto\s, \y\mapsto\w}\}\\
    \neg\exists\text{id}\in\text{dom(ds)}\bullet\text{((id}\mapsto\text{id)}\in\{{\color{lightgreen}\s\mapsto\k, \w\mapsto\s, x\mapsto\s, \y\mapsto\w, }\\{\color{lightgreen}\w\mapsto\k, \x\mapsto\k, \y\mapsto\s, \y\mapsto\k}\})\\
    $$
    
    The entries in $\color{lightblue}\text{ds\_uses}$ are derived from the declarations $\color{lightblue}\text{ds}$ from before:
    
    - We have $\color{lightblue}\text{S}\mapsto\text{K}$ from the declaration $\color{lightblue}\text{S}\mapsto\text{type([op(-\_, K)..K])}$
    - We have $\color{lightblue}\text{W}\mapsto\text{S}$ from the declaration $\color{lightblue}\text{W}\mapsto\text{type(S)}$
    - We have $\color{lightblue}x\mapsto\text{S}$ from the declaration $\color{lightblue}x\mapsto\text{var(S)}$
    - We have $\color{lightblue}y\mapsto\text{W}$ from the declaration $\color{lightblue}y\mapsto\text{var(W)}$
    
    For each of these, we need to compute their transitive closure. It is given as:
    
    $$
    \def\k{\text{K}}
    \def\s{\text{S}}
    \def\w{\text{W}}
    \def\x{\text{x}}
    \def\y{\text{y}}
    \def\q{\text{q}}
    \neg\exists\text{id}\in\text{dom(ds)}\bullet\text{((id}\mapsto\text{id)}\in\{{\color{lightgreen}\s\mapsto\k, \w\mapsto\s, x\mapsto\s, \y\mapsto\w, }\\{\color{lightgreen}\w\mapsto\k, \x\mapsto\k, \y\mapsto\s, \y\mapsto\k}\})
    $$
    
    - Observe that the transitive closure listed contains all of the items in $\color{lightblue}\text{ds\_uses}$ as well as all of the transitive items that we can derive (e.g. $$

\def\k{\text{K}} \def\s{\text{S}} \def\w{\text{W}} \def\x{\text{x}} \def\y{\text{y}} \def\q{\text{q}} {\color{lightblue}\w\mapsto\s, \s\mapsto\k} \Rightarrow {\color{lightgreen}\w\mapsto\k}

- Given this transitive closure, we then have to compute that no identifier depends on itself (in this example, the check passes) ## 2.3 - Static Semantics Rules for the Main Program The main program is well formed if:

\begin{array}{cc}\text{predefined}\vdash\text{WFBlock(block})\ \hline \text{WFProgram(block)} \end{array}

Wherethesymboltableforthepredefinedidentifiersis Where the symbol table for the predefined identifiers is

\begin{aligned} \text{predefined}={\text{int}&\mapsto\text{TypeEntry(int)}\\text{boolean}&\mapsto\text{TypeEntry(boolean)}\ \text{false}&\mapsto\text{ConstEntry(boolean, 0)}\ \text{true}&\mapsto\text{ConstEntry(boolean, 1)}\ &} \end{aligned}

← All COMP4403 notes