从 Lexer 到 Semantic Analysis：编译器如何理解原始码？

编译器（Compiler）是一种将原始码从一种表示形式转换为另一种表示形式的程式，通常将高阶程式语言转换为机器码、组合语言、位元组码（bytecode）或某种中间表示（Intermediate Representation）。

编译并非单纯的文字替换。原始码必须先被辨识为词法单位，再组织成语法结构，最后检查其中的语义限制。

编译流程可以简化为：

Source Code

↓

Lexical Analysis

↓

Tokens

↓

Parsing

↓

Parse Tree / AST

↓

Semantic Analysis

↓

Validated Representation

实际的编译器可能进一步拆分、合并或增加其他阶段。本文只讨论理解后续内容所需的基本层次。

1. 编译器如何处理原始码？

原始码最初只是一串字元。

result = a + b * 2

字元 → 单位 → 结构 → 语义

score = value + 10

IDENTIFIER("score")

ASSIGN&quot;=&quot;

IDENTIFIER("value")

PLUS("+")

INTEGER(10)

其中：

原始码	Token 类型
`score`	Identifier
`=`	Assignment operator
`value`	Identifier
`+`	Arithmetic operator
`10`	Integer literal

Token 不一定只包含一个字元。例如 score 由多个字元组成，但整体构成一个 token。

Token 主要提供词法类型资讯，尚未完整确定该单位在整体结构中的作用。

3. Lexer 与 Lexical Analysis——从字元到 Token

词法分析（Lexical Analysis）是将原始码中的字元序列分析为 token 的过程。执行此过程的元件通常称为 Lexer 或 Lexical Analyzer。

Characters

↓

Lexer

↓

Tokens

例如：

total = price * 2

IDENTIFIER("total")

ASSIGN

IDENTIFIER("price")

MULTIPLY

INTEGER(2)

Lexer 通常处理：

identifier；
keyword；
operator；
literal；
delimiter。

词法分析并不负责确定 token 之间完整的语法关系。

Lexer 辨识单位；Parser 确定单位之间的结构。

4. Grammar——语言的构造规则

Grammar（文法）是一套形式规则，用于描述一种语言中的合法结构如何形成。

一个简化的 grammar 可以包含以下 production rules：

Expression → Expression + Expression

Expression → Expression * Expression

Expression → Identifier

Expression → Integer

例如：

A → B C

a + b * c

a + (b * c)

/ \

a *

/ \

b c

这与：

(a + b) * c

/ \

+ c

/ \

a b

因此，parser 不只辨识 a、+、b、*、c 的存在，也确定它们之间的层次关系。

6. Parse Tree——语法的层次结构

Parse Tree（剖析树／语法分析树）是表示 token 序列如何依照 grammar 中的 production rules 被分析的树状结构。

例如：

a + b * c

Expression

├── Expression

│ └── Identifiera

├── "+"

└── Expression

├── Expression

│ └── Identifierb

├── "*"

└── Expression

└── Identifierc

Parse tree 表示：

哪些成分互相组合；
它们形成什么中间结构；
更大的结构按照什么层次形成。

线性序列：

a + b * c

├── a

└── *

├── b

└── c

线性顺序与层次结构是两种不同的资讯。

7. AST——Abstract Syntax Tree

抽象语法树（Abstract Syntax Tree，AST）是语法结构的抽象树状表示。

AST 通常会省略只对 parsing 有作用、但后续处理不再需要的节点或细节。

例如 parse tree：

Expression

├── Expression

│ └── Identifiera

├── "+"

└── Expression

├── Expression

│ └── Identifierb

├── "*"

└── Expression

└── Identifierc

可以简化为 AST：

Add

├── Identifiera

└── Multiply

├── Identifierb

└── Identifierc

AST 保留了重要的结构关系：

Multiply(b, c)

Add(a, ...)

a + b * c

(a + b) * c

a + (b * c)

"hello" - 5

Expression → Expression - Expression

Subtract

├── String("hello")

└── Integer(5)

此结构符合 binary expression 的语法形式。

但是，如果该语言规定 - 只能作用于数值类型，则：

String - Integer

Syntax: 合法

Semantic: 不合法

Parser 已完成其语法分析工作。错误是在检查语义限制时才被发现。

一个结构可以成功被 parse，但仍然可能在语义上不合法。

11. Semantic Analysis——检查结构的语义限制

语义分析（Semantic Analysis）是检查已完成语法分析的结构是否符合语义属性与限制的阶段。

依照语言设计，semantic analysis 可以检查：

identifier 是否已宣告；
identifier 的 scope；
资料类型；
类型是否相容；
function arguments；
return type；
operator 是否适用于相应 operand；
其他语义限制。

例如：

x: Integer

x + 10

可以合法。

而：

x: String

x - 10

可能不合法。

两者都可能具有相同的基本语法结构：

BinaryExpression

├── LeftOperand

├── Operator

└── RightOperand

差异存在于各 node 的属性及其语义关系。

12. Type Checking 与 Semantic Constraints

Type checking（型别检查）用于检查一个表达式或操作是否与相关资料类型相容。

假设：

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

更一般的概念是 semantic constraint（语义限制）：一个结构只有在其成分满足特定语义条件时才有效。

因此，一个 node 可以出现在 grammar 所允许的位置，却仍然不符合包含它的结构所要求的 semantic constraint。

13. Syntax 与 Semantic 的差异

Syntax（语法）描述各单位如何组成结构。

Semantic（语义）处理该结构中的属性、关系与限制。

例如：

"hello" - 5

Subtract

├── String

└── Integer

Semantic analysis 则检查：

subtract(String, Integer)

Tokens

↓

Syntactic Structure

↓

Semantic Validation

三个层次不能互相替代。

辨识 token 不足以确定结构；确定结构也不足以确认语义。

14. Programming Language 与 Natural Language

程式语言与自然语言并非以相同机制形成。

程式语言通常具有事先确定的 specification 或规则系统：

Language Specification

↓

Grammar + Semantic Rules

↓

Valid Programs

程式是否有效，由语言规则判定。

自然语言并不主要按照这一方向形成。较适合的简化模型是：

Language Usage

↓

Observed Data

↓

Analysis

↓

Generalization

↓

Grammatical Model

语言使用者不需要先阅读语法学家建立的 grammar，才能使用自己的语言。语言学中的 grammar，主要来自对既有语言现象的观察、描述与概括。

历史语言资料也并不完整。一种结构可能早已存在于口语中，之后才首次出现在现存文献。现存最早的书面证据，不必然代表该结构真正产生的时间。

因此，程式语言的 grammar 主要依据 specification 规定系统中的合法结构；自然语言的描述语法则主要是研究者根据语言资料所建立的分析模型。

15. 为什么 Parser 与 Semantic Analysis 有助于研究自然语言语法？

Compiler 中的概念可以作为一种分析模型，用来区分三个不同问题：

辨识单位

↓

确定结构

↓

检查语义关系

这三个问题同样存在于自然语言分析中。

同一个词语序列可能具有不同的层次分析。一个结构可能符合某种表层 pattern，却不能正确保存句中各成分的语义关系。一个成分也可能符合某个语法位置，却不符合另一成分对它施加的语义限制。

这种对照并不表示：

Natural Language = Programming Language

语法分析 = Compiler

Source

↓

Lexer

↓

Tokens

↓

Parser

↓

Parse Tree / AST

↓

Semantic Analysis

↓

Validated Representation

其中三个核心层次为：

Token

↓

Structure

↓

Meaning / Constraints

Lexer 辨识词法单位。

Parser 确定各单位之间的层次结构。

Semantic Analysis 检查该结构中的语义属性与限制。

一个 pattern 可以产生一个 candidate structure。一个 candidate structure 能够被表示为树状结构，并不等于该分析必然有效。

17. 延伸阅读：从 Parser 到层次分析

下一篇将把上述概念与自然语言的语法分析进行对照：

《从 Parser 到层次分析：语法结构与语义关系》

主要讨论：

Pattern

↓

Candidate Structure

↓

Hierarchical Analysis

↓

Semantic Relations

并以现代汉语结构说明两个不同问题：形式上能否构成某种结构，以及该结构能否正确反映句中各成分的语义关系。