Quiz #1 Material Summary

Main phases/functions of compiler#

1. Lexical Analyzer ==> reads the stream of characters and groups them into meaningful sequences
2. Syntax Analyzer ==> using the components produced by the previous phase, creates a tree like intermediate representation that depicts the grammatical structure of the token stream.
3. Semantic Analyzer ==> using the tree, check the semantic consistency of the source program with the language definition. Also gathers type information
4. Intermediate Code Generator ==> constructs intermediate representation of the target code
5. Machine Independent Code Optimzer ==> Optimizes intermediate representation
6. Code Generator ==> generate target machine code from intermediate representation
7. Machine-dependent Code Optimizer ==> optimizes machine code

Compiler Phases#

Compiler Phases with outputs of each phases:#

Context Free Grammar (CFG)#

1. terminals / tokens ==> elementary symbols of the language
2. nonterminals ==> represent string of terminals
3. productions ==> consists of nonterminal (called left side), an arrow, and sequence of terminals and/or nonterminals (called body)
4. a nonterminal designated as the start symbol

Finding FIRST() sets#

Definitions

1. $\alpha$ ==> string of grammar symbolsl (terminals and/or non-terminals)
2. FIRST($\alpha$) ==> set of terminals that appear as the first symols of one or more strings of terminals generated from $\alpha$

How to compute/find FIRST() sets

1. if $X$ is a terminal, then FIRST($X$) = ${X}$
2. if $X$ is a nonterminal and $X \to Y_1 Y_2 \cdots Y_k$ is a production,
   1. FIRST($X$) = FIRST($Y_1$)
   2. If FIRST($Y_i$) contains $\epsilon$ then FIRST($X$) = $\{ FIRST(Y_i) – \epsilon \} \cup \{FIRST(Y_{i+1})\}$, and so on
   3. If FIRST($Y_i$) contains $\epsilon$ for all $i$ = 1 to $n$, then add $\epsilon$ to FIRST($X$).
3. if $X \to \epsilon$ is a production, then add $\epsilon$ to FIRST($X$).

terminals vs nonterminals#

• terminals ==> tokens, unchangeable like 1, 2, 3, if
• non-terminals ==> terms, like <digit>, <stmt>, that can be changed to any valued according to definition

Finite Automatas (FAs)#

Nondeterministic FA (NFA) Definition#

1. A finite of state $S$
2. A set of input symbols $\Sigma$, the input alphabet. It is assumed that $\epsilon$, the empty string is not part of $\Sigma$.
3. A transition function that gives, for each state, and for each symbol in $\Sigma\cup{\epsilon}$ a set of next states.
4. A state $s_0$ from $S$ that is distinguished as the start/initial state
5. A set of states $F$, a subset of $S$, that is distinguished as the accepting/final states

RE to NFA using Thompson’s construction#

NFA to DFA#

Example:

RE: (a|b)*abc

NFA Graph:

Transition table:

Resulting DFA Graph:

Explanation (based on the example)

• What is the contents of the table mean?

• how do I find the equivalent set of the NFA for each DFA state?

  • for the first DFA state, the initial state, the equivalent set is by starting from the initial state of the NFA, unioned with all the states that can be reached from this initial state only from $\epsilon$ transitions, unioned again with all the other states that can be reached from the states in the set, and so on, and so on until no other states can be reached, or in other words: $$ \textit{NFA States Set} = \epsilon\textit{-closure}(0) $$ $$ \textit{NFA States Set} = \textit{NFA States Set} \cup \epsilon\textit{-closure}(\textit{NFA States Set}) $$ $$ \textit{NFA States Set} = \textit{NFA States Set} \cup \epsilon\textit{-closure}(\textit{NFA States Set}) $$ $$ \textit{And so on until no other states can be reached}$$

  note: $\epsilon\textit{-closure}(s)$’s output is all the states that can be reached from $s$ using only $\epsilon\textit{-transitions}$ alone

  • that’s the initial state, how do I find the next NFA States set?
  1. select a a input character, let’s say WIP

usable operations of NFA

WIP

NB: I'm too lazy to write the whole explanation at the moment.
If you really want to understand and the book explanation is too hard to read, just ask me(Ian).

DFA Minimization/Optimization#

Example

DFA graph from the previous example:

Resulting Partition:

$$\Pi = \{A, C\}\{B\}\{D\}\{E\}$$

Resulting Minimized DFA graph

Explanation

Note: Not guaranteed to be correct

based on the transition table of the previous example (with NFA states column removed, it is uselss here),

1. separate accepting state as it’s own group. So state $E$ becomes it’s own group

$$\Pi = \{A, B, C, D\}\{E\}$$

2. group all the states with the same input character transition, like for example, state $A$ and $C$ both transition to state $B$ on input character $b$ and to state $C$ on input character $a$. So, the partition result becomes;

$$\Pi = \{A, C\}\{B\}\{D\}\{E\}$$

3. now turn each group becomes a new state. so for this example, A and C merge into a single state

4. Using the transition table, make the new minimized DFA.

Ambiguous grammar#

a grammar that produces more than one parse tree for some sentence

Example#

Definition: $$E \Rightarrow E + E | E - E | E \times E | E / E | (E) | id$$

Example $E$ statement:

$$ E + E * E$$

Graph showing how the above expression can be intrepreted into 2 different ways: