Tutorial 10

Question 1

Hint: Make the following rules:

• String type and evaluation

• Identifier type and evaluation

• Let expression type & evaluation

• Coerce int to string

• String concatenation

• In the rule $e ::= n | s | id | e + e | \cdots|\text{let id = e in e end}$ observe that in the last alternative

  • The two e’s can be of different types - need to handle this case.

Rule 5 - String Value

$\text{syms}\vdash\text{s : String}$

Rule 6 - String Evaluation

$\text{syms}\vdash\text{S}\overset{e}{\rightarrow}\text{S}$

Rule 7 - Identifier Type

$$\text{id}\in\text{dom(syms)}\\ \text{syms(id)}=\text{ConstEntry(T)}\\ \overline{ \text{syms}\vdash\text{typeof(id)=T} }$$

Rule 8 - Identifier Evaluation

$\text{syms}\vdash\text{id : T}$

Rule 9 - Let Expression Type

$$\text{syms}\vdash\text{id : T}\\ \text{syms}\vdash\text{e : T}\\ \overline{ \text{syms}\vdash }$$

Rule 5 - String type and evaluation

$$\text{syms}\vdash\text{s}\overset{e}{\rightarrow}\text{s}\\ \text{syms}\vdash\text{s : String}$$

Rule Identifiers

$$\text{id}\in\text{dom(syms)}\\ \text{syms(id)}=\text{ConstEntry(T,V)}\\ \overline{ \text{syms}\vdash\text{id}\overset{e}{\rightarrow}V}\\ \text{syms}\vdash\text{id : T}$$

Rule Let

$$\text{syms}\vdash\text{e1 : T1}\\ \text{syms}\vdash\text{e2 : T2}\\ \text{syms} + \{id \rightarrow\text{ConstEntry(T1, V1)}\} + \text{e2 : T2}\\ \text{syms}\vdash\text{\{id\}}\rightarrow\text{ConstEntry(T1,V1)\}+ e2}\overset{e}\rightarrow V2\\ \overline{ \text{syms}\vdash\text{let id = e1 in e2 : T2}\\ } \text{syms}\vdash\text{let id = e1 in e2}\overset{e}{\rightarrow}V2$$

Rule Coerce Int to String

$$\text{syms}\vdash\text{e : int}\\ \text{syms}\vdash\text{e}\overset{e}\rightarrow\text{n}\\ \overline{ \text{syms}\vdash\text{e : string} }\\ \text{syms}\vdash\text{e}\overset{e}\rightarrow \text{intToString(n)}$$

Rule String Concatenation

$$\text{syms}\vdash\text{e1:string}\\ \text{syms}\vdash\text{e2:string}\\ \text{syms}\vdash\text{e1}\overset{e}\rightarrow \text{n1}\\ \text{vdash}\vdash\text{e2}\overset{e}\rightarrow \text{n2}\\ \overline{ \text{syms}\vdash\text{e1 ++ e2} : \text{string} }\\ \text{syms}\vdash\text{e1 ++ e2}\overset{e}\rightarrow \text{n1 \^\ n2}$$

Question 2

SymTab parseTDS(SymTab symsin) {
		match(KW_TYPE);
		SymTab symsOut = parseD1(syms);
		SymTabl symsOut = parseDS(symsOut);
}

SymTab parseDS(SymTab symsIn) {
    if (token.isMatch(D)) {
				SymTab symOut = parse(symsIn);
				SymTab symsOut = parseDS(symsOut);
				return symsOut
		}
		return symsIn;
}

ID EQUALS T SEMICOLON
SymTab parseD(symsIn) {
		String name = token.getName(); // for x = int returns "x"
		match(ID)
		match(EQUALS)
		Type T = parseT(symsIn);
		match(SEMICOLON);
		// CHeck if symbol table already contains the ID - iff throw error
		if (symsIn.contains(name)) {
				error("Identifier " + name + " already defined in the symbol table");
        T = Type.ERROR_TYPE;
		}
		return symsIn.add(name, T);
    
}