從 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

在這個階段，編譯器尚未取得完整的結構資訊。它必須確定：

詞法單位；
每個單位的類型；
各單位之間的語法關係；
表達式的層次結構；
結構所受到的語義限制。

可以簡化為：

字元 → 單位 → 結構 → 語義

正確辨識單位，不等於正確確定結構。能夠建立語法結構，也不等於該結構在語義上有效。

2. Token——原始碼的基本詞法單位

Token 是編譯器從原始碼中辨識出的詞法單位。

例如：

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

可以由 lexer 轉換為：

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 組成。

Grammar 不只是規定哪些 token 可以出現，也描述較小的單位或結構如何組成更大的結構。

實際的程式語言 grammar 還需要處理運算子優先順序（precedence）、結合性（associativity）、分組（grouping）等問題。

5. Parser——從 Token 序列到語法結構

Parser（語法分析器）根據 grammar 分析 token 序列，以確定程式的語法結構。

例如：

a + b * c

線性的 token 序列是：

a  +  b  *  c

但其結構可以是：

a + (b * c)

以樹狀結構表示：

這與：

(a + b) * c

不同。後者的結構為：

因此，parser 不只辨識 a、+、b、*、c 的存在，也確定它們之間的層次關係。

6. Parse Tree——語法的層次結構

Parse Tree（剖析樹／語法分析樹）是表示 token 序列如何依照 grammar 中的 production rules 被分析的樹狀結構。

例如：

a + b * c

其簡化的 parse tree 可以表示為：

Expression
├── Expression
│   └── Identifier $a$ 
├── "+"
└── Expression
    ├── Expression
    │   └── Identifier $b$ 
    ├── "*"
    └── Expression
        └── Identifier $c$

Parse tree 表示：

哪些成分互相組合；
它們形成什麼中間結構；
更大的結構按照什麼層次形成。

線性序列：

a + b * c

因此可以轉換為層次結構：

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

線性順序與層次結構是兩種不同的資訊。

7. AST——Abstract Syntax Tree

抽象語法樹（Abstract Syntax Tree，AST）是語法結構的抽象樹狀表示。

AST 通常會省略只對 parsing 有作用、但後續處理不再需要的節點或細節。

例如 parse tree：

Expression
├── Expression
│   └── Identifier $a$ 
├── "+"
└── Expression
    ├── Expression
    │   └── Identifier $b$ 
    ├── "*"
    └── Expression
        └── Identifier $c$

可以簡化為 AST：

Add
├── Identifier $a$ 
└── Multiply
    ├── Identifier $b$ 
    └── Identifier $c$

AST 保留了重要的結構關係：

Multiply(b, c)

是：

Add(a, ...)

的一個子結構。

Semantic analysis、optimization 或 code generation 等後續階段，通常會處理 AST 或由 AST 進一步建立的中間表示。

8. Parse Tree 與 AST 有何不同？

Parse tree 與 AST 都表示層次結構，但用途不同。

| 特徵 | Parse Tree | AST | |---|---|---| | 與 grammar 的關係 | 直接 | 經過抽象化 | | 中間 production | 通常保留 | 通常省略 | | 標點與語法細節 | 可以保留 | 可以移除 | | 主要用途 | 表示語法分析結果 | 表示後續處理所需結構 | | 詳細程度 | 較高 | 較低 |

並非所有 compiler 都會分別建立兩棵實體的樹。Parser 也可以直接建立 AST。

因此，Parse Tree 與 AST 是相關但不相同的概念。

9. Candidate Parse 與 Ambiguity——同一個 Input 的多種分析

如果 grammar 沒有提供足夠的限制，一個 token 序列可能具有多種語法結構。

例如：

a + b * c

可以存在兩個 candidate parses：

(a + b) * c

以及：

a + (b * c)

兩種結構形成不同的樹，也可能產生不同的運算結果。

一個 input 可以具有多種語法分析的現象稱為 syntactic ambiguity（語法歧義）。

程式語言通常透過以下機制消除或控制 ambiguity：

precedence；
associativity；
括號；
grammar design；
其他語言規則。

由此可以得到一個基本原則：

表層形式（surface form）本身不足以完整確定底層結構。

10. Syntax 合法不代表 Semantic 合法

假設存在以下表達式：

"hello" - 5

如果 grammar 允許：

Expression → Expression - Expression

parser 仍然可以建立：

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)

不符合已定義的 function signature。

可以表示為：

Expected:
    add(Int, Int)

Received:
    add(String, Int)

Result:
    Type mismatch

更一般的概念是 semantic constraint（語義限制）：一個結構只有在其成分滿足特定語義條件時才有效。

因此，一個 node 可以出現在 grammar 所允許的位置，卻仍然不符合包含它的結構所要求的 semantic constraint。

13. Syntax 與 Semantic 的差異

Syntax（語法）描述各單位如何組成結構。

Semantic（語義）處理該結構中的屬性、關係與限制。

例如：

"hello" - 5

Syntax 可以建立：

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

它只提供一套形式化的概念，用來區分單位、結構與語義。

16. 總結：Token → Structure → Meaning

本文所述的基本流程可以簡化為：

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

並以現代漢語結構說明兩個不同問題：形式上能否構成某種結構，以及該結構能否正確反映句中各成分的語義關係。