> For the complete documentation index, see [llms.txt](https://osh.fducslg.com/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://osh.fducslg.com/notes/compilers/l02-lexical-analysis.md).

# 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](https://p.ipic.vip/6tsi2f.png)

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

<figure><img src="https://p.ipic.vip/yoy39u.png" alt="Screenshot 2024-09-16 at 21.31.05"><figcaption></figcaption></figure>

**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**:

<figure><img src="https://p.ipic.vip/h5z6l7.png" alt="Screenshot 2024-09-28 at 17.55.43"><figcaption></figcaption></figure>

* 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**.