Lexical Analysis

In this lecture, we start from using regular expressions to specify the language. In order to parse the regular expressions, we need to construct the finite automaton corresponding to the regular expressions.

Regular Expressions

Regular Expression	Meaning
$a$	$x = a$
$[ab]$	$x \in \{a, b\}$
$[a-z]$	$x \in \{a, \dots, z\}$
$[a-zA-Z]$	$x \in \{a, \dots, z, A, \dots, Z\}$
$.$	$x \in \Sigma$
$\hat{a}$	$x \in \Sigma \setminus \{a\}$
$\varepsilon$	$x \in \emptyset$
$a?$	$x = a \text{ or } x = \varepsilon$

Construction Method	Regular Expression	Meaning
Union	$S \mid T$	$x \in S \cup T$
Concatenation	$ST$	$x \in \{st \mid s \in S, t \in T\}$
Kleene Closure	$S^*$	$x \in \{s_0 \dots s_n \mid \forall 0 \leq i \leq n, s_i \in S, 0 \leq n < \infty\}$
Positive Closure	$S^+$	$x \in \{s_0 \dots s_n \mid \forall 0 \leq i \leq n, s_i \in S, 1 \leq n < \infty\}$
Range Closure	$S\{ \text{min,max} \}$	$x \in \{s_0 \dots s_n \mid \forall 0 \leq i \leq n, s_i \in S, \text{min} \leq n < \text{max} \}$

Precedence: Closure > Concatenation > Union.

Lexical Specification

Handling conflicts in recognition.

• Keywords vs Identifiers: Keywords have a higher priority than identifiers. For example, the string "if" should be recognized as <IF>, not as <ID (if)>.

• When multiple matching patterns exist, choose the longest match. For example, "<=" should be recognized as <LTE>, and not as two separate tokens <LT><EQ>. The string "ifabc" should be recognized as <ID (ifabc)>, and not as <IF> and <ID (abc)>.

Lexical Parsing

Motivation: We need to convert regular expressions to finite automatons.

Thompson's Construction

Screenshot 2024-09-16 at 21.26.53

Below is an example of converting the regular expression of UNUM to NFA:

Gap: Using an NFA for lexical analysis is impractical due to the numerous possible transition paths.

Converting NFA to DFA

Given an input string, we can simulate an NFA with a DFA by defining the states in the DFA as the reachable states in the NFA.

For a single state $s_i$ in the NFA, the epsilon-closure of $s_i$ refers to the set of states reachable from $s_i$ by epsilon ($\epsilon$) transitions:

$$Cl^\epsilon(s_i) = \{ s_j \mid (s_i, \epsilon) \to^* (s_j, \epsilon) \}$$

This means the set of states $s_j$ that can be reached from $s_i$ by taking zero or more epsilon transitions.

For a set of states $S$ in the NFA, the epsilon-closure of $S$ refers to the set of all states that can be reached from any state in $S$ by epsilon transitions:

$$Cl^\epsilon(S) = \{ q' \mid \forall q \in S, (q, \epsilon) \to^* (q', \epsilon) \}$$

This means the set of all states $q'$ that can be reached from any state $q$ in $S$ through zero or more epsilon transitions.

For a set of states $S$ in the NFA, the transition for an input symbol $\alpha$ refers to the epsilon-closure of the set of all states that can be reached after reading the symbol $\alpha$:

$$\Delta(S, \alpha) = Cl^\epsilon(\{ q' \mid \forall q \in S, (q, \alpha) \to q' \})$$

This means that the transition on symbol $\alpha$ for a set of states $S$ is the epsilon-closure of the set of states that can be reached by taking the transition labeled with $\alpha$ from any state $q$ in $S$.

Powerset Construction

The start state in the DFA corresponds to the start state of the NFA, plus all states reachable via $\epsilon$-transitions.

If a state $q$ in the DFA corresponds to a set of states $S$ in the NFA, then the transition from state $q$ on a character $a$ is found as follows:

• Let $S'$ be the set of states in the NFA that can be reached by following a transition labeled a from any of the states in $S$. (This set may be empty.)
• Let $S''$ be the set of states in the NFA reachable from some state in $S'$ by following zero or more epsilon transitions.
• The state $q$ in the DFA transitions on a to a DFA state corresponding to the set of states $S''$.

DFA Optimization: Merging Equivalent States

For two nodes of the same type, $d_i$ and $d_j$, the condition for merging them is:

$$\forall c \in \Sigma, \delta(d_i, c) = \delta(d_j, c)$$

Hopcroft Partitioning Algorithm:

• The Hopcroft partitioning algorithm iteratively divides the state set $D$ of a DFA (Deterministic Finite Automaton) into subsets to minimize the DFA.
• Initially, the state set $D$ is divided into two subsets: accepting states $D_{ac}$ and non-accepting states $D \setminus D_{ac}$.
• The algorithm continues to partition the states until no further splits can be made.

• The Split(s) function checks if a set of states $s$ can be split based on input characters from the alphabet $\Sigma$. If a split occurs, it returns two new subsets; otherwise, it returns the original set.

Regular Language

Two regular expressions are considered equivalent if, and only if, they generate the same regular set (language).

Pumping Lemma:

• If a language consists of a finite set of lexemes, it is guaranteed to be a regular language.

• For languages with an infinite set of lexemes, the Pumping Lemma can be used to demonstrate that the language is not regular.