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);
}