From Lexer to Semantic Analysis: How Does a Compiler Understand Source Code?

Author · Updated Sep 27, 2026 10 views

A compiler is a program that transforms source code from one representation into another, typically from a high-level programming language into machine code, assembly, bytecode, or an intermediate representation.

Compilation is not simple text substitution. Source code must first be recognized as lexical units, organized into syntactic structures, and checked against semantic constraints.

A simplified compilation pipeline can be represented as:

Source Code
↓
Lexical Analysis
↓
Tokens
↓
Parsing
↓
Parse Tree / AST
↓
Semantic Analysis
↓
Validated Representation

Real compilers may split, merge, or introduce additional stages. This article focuses only on the layers required for the concepts discussed here.

1. How Does a Compiler Process Source Code?

Source code initially exists as a sequence of characters.

result = a + b * 2
Characters → Units → Structure → Semantics
score = value + 10
IDENTIFIER("score")
ASSIGN"="
IDENTIFIER("value")
PLUS("+")
INTEGER(10)

| Source | Token type |

|---|---|

| score | Identifier |

| = | Assignment operator |

| value | Identifier |

| + | Arithmetic operator |

| 10 | Integer literal |

A token does not necessarily correspond to a single character. score consists of multiple characters but forms a single token.

Tokens primarily provide information about lexical categories. They do not yet fully determine the structural role of each unit.

3. Lexer and Lexical Analysis — From Characters to Tokens

Lexical analysis is the process of converting a sequence of source-code characters into tokens. The component that performs this process is usually called a lexer or lexical analyzer.

Characters
↓
Lexer
↓
Tokens

For example:

total = price * 2
IDENTIFIER("total")
ASSIGN
IDENTIFIER("price")
MULTIPLY
INTEGER(2)

A lexer commonly recognizes categories such as:

  • identifiers;
  • keywords;
  • operators;
  • literals;
  • delimiters.

Lexical analysis does not determine the complete syntactic relations between tokens.

A lexer identifies units. A parser determines the structure between those units.

4. Grammar — The Structural Rules of a Language

A grammar is a system of formal rules describing how valid structures in a language can be formed.

A simplified grammar may contain production rules such as:

Expression → Expression + Expression
Expression → Expression * Expression
Expression → Identifier
Expression → Integer

A rule of the form:

A → B C
a + b * c
a + b * c
a + (b * c)
+
/ \
a *
/ \
b c

This differs from:

(a + b) * c
*
/ \
+ c
/ \
a b

A parser therefore does more than recognize the presence of a, +, b, *, and c. It determines their hierarchical relationships.

6. Parse Tree — The Hierarchical Structure of Syntax

A parse tree is a tree that represents how a sequence of tokens is analyzed according to the production rules of a grammar.

For:

a + b * c
Expression
├── Expression
│ └── Identifiera
├── "+"
└── Expression
├── Expression
│ └── Identifierb
├── "*"
└── Expression
└── Identifierc

A parse tree represents:

  1. which components combine with one another;
  2. which intermediate structures they form;
  3. how larger structures are built hierarchically.

The linear sequence:

a + b * c
+
├── a
└── *
├── b
└── c

Linear order and hierarchical structure are different types of information.

7. AST — Abstract Syntax Tree

An Abstract Syntax Tree is an abstract tree representation of syntactic structure.

An AST usually omits nodes or details that are necessary for parsing but unnecessary for later stages of processing.

For example, the parse tree:

Expression
├── Expression
│ └── Identifiera
├── "+"
└── Expression
├── Expression
│ └── Identifierb
├── "*"
└── Expression
└── Identifierc

may be reduced to the following AST:

Add
├── Identifiera
└── Multiply
├── Identifierb
└── Identifierc

The AST preserves the important structural relation:

Multiply(b, c)
Add(a, ...)
a + b * c
(a + b) * c
a + (b * c)
"hello" - 5
Expression → Expression - Expression
Subtract
├── String("hello")
└── Integer(5)

This structure satisfies the syntactic form of a binary expression.

However, if the language defines - only for numeric types, then:

String - Integer
Syntax: valid
Semantics: invalid

The parser has completed its syntactic task. The error appears only when semantic constraints are checked.

A structure can be successfully parsed while remaining semantically invalid.

11. Semantic Analysis — Checking Semantic Constraints

Semantic analysis is the stage that checks the semantic properties and constraints of a syntactically analyzed structure.

Depending on the language, semantic analysis may check:

  • whether an identifier has been declared;
  • identifier scope;
  • data types;
  • type compatibility;
  • function arguments;
  • return types;
  • whether an operator is applicable to its operands;
  • other semantic constraints.

For example:

x: Integer
x + 10

may be valid.

In contrast:

x: String
x - 10

may be invalid.

Both expressions may share the same general syntactic structure:

BinaryExpression
├── LeftOperand
├── Operator
└── RightOperand

The difference lies in the properties and semantic relations of the nodes inside that structure.

12. Type Checking and Semantic Constraints

Type checking determines whether an expression or operation is compatible with the relevant data types.

Suppose:

add(Int, Int) → Int
add(1, 2)
add(Int, Int)
add("one", 2)
add(String, Int)
Expected:
add(Int, Int)
Received:
add(String, Int)
Result:
Type mismatch

The more general concept is a semantic constraint: a structure is valid only when its components satisfy the required semantic conditions.

A node may therefore occupy a position permitted by the grammar while still violating a semantic constraint imposed by the surrounding structure.

13. Syntax and Semantics

Syntax describes how units are organized into structures.

Semantics concerns the properties, relations, and constraints associated with those structures.

For example:

"hello" - 5
Subtract
├── String
└── Integer

Semantic analysis then evaluates:

subtract(String, Integer)
Tokens
↓
Syntactic Structure
↓
Semantic Validation

These levels are not interchangeable.

Recognizing tokens is insufficient to determine structure. Determining structure is insufficient to establish semantic validity.

14. Programming Languages and Natural Languages

Programming languages and natural languages do not arise through the same process.

A programming language usually has a specification or a predefined system of rules:

Language Specification
↓
Grammar + Semantic Rules
↓
Valid Programs

Programs are evaluated against those rules.

Natural languages do not primarily develop in this direction. A more appropriate simplified model is:

Language Usage
↓
Observed Data
↓
Analysis
↓
Generalization
↓
Grammatical Model

Speakers do not need a grammar written by linguists before they can use their language. In linguistics, grammatical models are primarily constructed through observation, description, and generalization of existing linguistic phenomena.

Historical linguistic evidence is also incomplete. A construction may have existed in speech before it first appeared in surviving written records. The earliest surviving attestation therefore does not necessarily represent the time when the construction originated.

Programming-language grammar is primarily defined by a specification that determines valid structures within the system. Descriptive grammar of natural language is primarily an analytical model constructed from linguistic data.

15. Why Are Parser and Semantic Analysis Useful for Studying Natural-Language Grammar?

Compiler concepts provide an analytical model for distinguishing three separate problems:

Identifying Units
↓
Determining Structure
↓
Checking Semantic Relations

The same distinction is useful in natural-language analysis.

A sequence of words may permit multiple hierarchical analyses. A structure may match a formal pattern while failing to preserve the semantic relations between its components. A constituent may also occupy a syntactically possible position while failing to satisfy the semantic requirements imposed by another constituent.

This analogy does not imply:

Natural Language = Programming Language
Grammatical Analysis = Compilation
Source
↓
Lexer
↓
Tokens
↓
Parser
↓
Parse Tree / AST
↓
Semantic Analysis
↓
Validated Representation

The three central levels are:

Token
↓
Structure
↓
Meaning / Constraints

A lexer identifies lexical units.

A parser determines the hierarchical structure among those units.

Semantic analysis checks the semantic properties and constraints of that structure.

A pattern may produce a candidate structure. The fact that a candidate structure can be represented as a tree does not by itself establish that the analysis is valid.

17. Further Reading: From Parser to Hierarchical Analysis

The next article applies these concepts comparatively to the grammatical analysis of natural language:

From Parser to Hierarchical Analysis: Syntactic Structure and Semantic Relations

Its central analytical sequence is:

Pattern
↓
Candidate Structure
↓
Hierarchical Analysis
↓
Semantic Relations

Using structures from Modern Chinese, it distinguishes two separate questions: whether a sequence can formally constitute a particular syntactic structure, and whether that structure correctly represents the semantic relations among the components of the sentence.