Lexical Analysis and the Main Structure Used: Finite Automata

In compiler design, the correct answer to the question “Which data structure is mainly used in lexical analysis?” is (iv) Finite automata.3

Lexical analysis is the first major phase of a compiler. It reads the source program character by character and groups sequences of characters into tokens such as identifiers, keywords, numbers, and operators.2 The reason finite automata are central here is that token patterns are usually specified using regular expressions, and regular expressions are implemented efficiently through finite automata, especially deterministic finite automata (DFA).3

A useful exam-oriented conclusion is:

Lexical analyzers are commonly built by converting token regular expressions into an NFA and then into a DFA, because a DFA can scan input one character at a time and determine token membership efficiently.3

Footnotes

1. Lexical analysis - Wikipedia - Explains that scanners are usually based on finite-state machines and that tokens are often defined by regular expressions. ↩ ↩²

2. Lecture 4: Automatic Lexer Generation - McGill University - Describes the standard pipeline from regular expressions to NFA to DFA to generated lexer. ↩ ↩² ↩³

3. Compiler Design – Unit I PDF - Sathyabama University - Covers regular expressions, finite automata, and NFA-to-DFA conversion in compiler design. ↩ ↩² ↩³

4. Introduction of Lexical Analysis - GeeksforGeeks - Summarizes lexical analysis, tokens, and the DFA-based recognition approach. ↩

5. How DFA and NFA help for Tokenization of Regular Expression - GeeksforGeeks - Explains why DFA/NFA are useful for tokenization and why DFA-based execution is efficient. ↩ ↩²

Why finite automata are used in lexical analysis

A lexer must recognize patterns such as identifiers, integers, floating-point literals, operators, and delimiters. These token classes typically form regular languages, which can be recognized by finite automata without needing unbounded memory.3

This is why lexical analysis is fundamentally different from syntax analysis. Syntax analysis often needs richer structure, such as context-free grammars and stack-based parsing, whereas lexical analysis usually works at the regular-language level.2 In practical lexer generators, token descriptions are written as regular expressions and compiled into transition diagrams, NFAs, and finally DFAs for efficient execution.3

A DFA is especially attractive because, for each state and input symbol, there is at most one transition. That makes scanning predictable and fast: the lexer advances through the source while tracking the current state and emits a token when it reaches an accepting configuration.3

$$\text{Regular Expression} \;\rightarrow\; \text{NFA} \;\rightarrow\; \text{DFA} \;\rightarrow\; \text{Lexer}$$

Key implications:

• Token definitions are compactly written as regular expressions.2
• Those expressions are transformed into finite automata.2
• The resulting DFA recognizes valid lexemes in a deterministic way.2

Footnotes

1. Lecture 4: Automatic Lexer Generation - McGill University - Describes the standard pipeline from regular expressions to NFA to DFA to generated lexer. ↩ ↩² ↩³ ↩⁴

2. Compiler Design – Unit I PDF - Sathyabama University - Covers regular expressions, finite automata, and NFA-to-DFA conversion in compiler design. ↩ ↩² ↩³ ↩⁴

3. How DFA and NFA help for Tokenization of Regular Expression - GeeksforGeeks - Explains why DFA/NFA are useful for tokenization and why DFA-based execution is efficient. ↩ ↩² ↩³ ↩⁴

4. Lexical analysis - Wikipedia - Explains that scanners are usually based on finite-state machines and that tokens are often defined by regular expressions. ↩ ↩²

5. Compiler Construction Lecture 2 - Lexical Analysis - Adelphi University - Contrasts finite automata with pushdown automata and highlights the scanner role of finite automata. ↩ ↩² ↩³

Why the other options are not the main answer

Although queues, stacks, and trees are important in computer science, they are not the main structure used to recognize tokens in lexical analysis.3

• A stack is central to pushdown automata and parsing of context-free syntax, not basic token recognition.
• A tree is more closely associated with parse trees, abstract syntax trees, and semantic structure after tokenization.
• A queue may appear in implementation details, but it is not the theoretical basis of lexical scanning.

Thus, if the question asks for the structure mainly used in lexical analysis, the intended compiler-design answer is finite automata.2

Footnotes

1. Lexical analysis - Wikipedia - Explains that scanners are usually based on finite-state machines and that tokens are often defined by regular expressions. ↩ ↩² ↩³

2. Introduction of Lexical Analysis - GeeksforGeeks - Summarizes lexical analysis, tokens, and the DFA-based recognition approach. ↩ ↩²

3. Compiler Construction Lecture 2 - Lexical Analysis - Adelphi University - Contrasts finite automata with pushdown automata and highlights the scanner role of finite automata. ↩ ↩²

4. Lecture 4: Automatic Lexer Generation - McGill University - Describes the standard pipeline from regular expressions to NFA to DFA to generated lexer. ↩

Technical perspective: DFA vs. NFA in scanners

In theory and in compiler tools, both NFA and DFA are used during lexer construction, but the final runtime scanner is often DFA-based for speed and determinism.3 An NFA is convenient during construction because regular expressions can be translated to NFAs systematically. Then subset construction converts the NFA to a DFA, which is simpler to execute while scanning the source stream.2

This explains a subtle but important point:

• During design/construction: regular expression $\rightarrow$ NFA $\rightarrow$ DFA.2
• During execution: the scanner usually behaves like a DFA-based finite-state machine.2

So even when textbooks mention both NFA and DFA, the high-level answer remains the same: lexical analysis is mainly based on finite automata.3

Footnotes

1. Lecture 4: Automatic Lexer Generation - McGill University - Describes the standard pipeline from regular expressions to NFA to DFA to generated lexer. ↩ ↩² ↩³ ↩⁴

2. Compiler Design – Unit I PDF - Sathyabama University - Covers regular expressions, finite automata, and NFA-to-DFA conversion in compiler design. ↩ ↩² ↩³

3. How DFA and NFA help for Tokenization of Regular Expression - GeeksforGeeks - Explains why DFA/NFA are useful for tokenization and why DFA-based execution is efficient. ↩ ↩² ↩³

4. Lexical analysis - Wikipedia - Explains that scanners are usually based on finite-state machines and that tokens are often defined by regular expressions. ↩ ↩²

Final answer for the given question

Question: Which data structure is mainly used in lexical analysis?

Options:
(i) Queue
(ii) Stack
(iii) Tree
(iv) Finite automata

Correct answer: (iv) Finite automata.3

This answer is justified because lexical analyzers recognize token patterns described by regular expressions, and those patterns are implemented through finite automata, especially DFAs in practical scanners.3

Footnotes

1. Lexical analysis - Wikipedia - Explains that scanners are usually based on finite-state machines and that tokens are often defined by regular expressions. ↩ ↩²

2. Lecture 4: Automatic Lexer Generation - McGill University - Describes the standard pipeline from regular expressions to NFA to DFA to generated lexer. ↩

3. How DFA and NFA help for Tokenization of Regular Expression - GeeksforGeeks - Explains why DFA/NFA are useful for tokenization and why DFA-based execution is efficient. ↩ ↩²

4. Compiler Design – Unit I PDF - Sathyabama University - Covers regular expressions, finite automata, and NFA-to-DFA conversion in compiler design. ↩