詞法分析

詞法分析（英語：lexical analysis）是計算機科學中將字符序列轉換為標記（token）序列的過程。進行詞法分析的程序或者函數叫作詞法分析器（lexical analyzer，簡稱lexer），也叫掃描器（scanner）。詞法分析器一般以函數的形式存在，供語法分析器調用。

標記

這裏的標記是一個字串，是構成原始碼的最小單位。從輸入字符流中生成標記的過程叫作標記化（tokenization），在這個過程中，詞法分析器還會對標記進行分類。

詞法分析器通常不會關心標記之間的關係（屬於語法分析的範疇），舉例來說：詞法分析器能夠將括號識別為標記，但並不保證括號是否匹配。

針對如下C語言表達式：

sum=3+2;

將其標記化後可以得到下表內容：

語素	標記類型
sum	標識符
=	賦值操作符
3	數字
+	加法操作符
2	數字
;	語句結束

標記經常使用正則表達式進行定義，像lex一類的詞法分析器生成器就支持使用正則表達式。語法分析器讀取輸入字符流、從中識別出語素、最後生成不同類型的標記。其間一旦發現無效標記，便會報錯。

掃描器

詞法分析的第一階段即掃描器，通常基於有限狀態自動機。掃描器能夠識別其所能處理的標記中可能包含的所有字符序列（單個這樣的字符序列即前面所說的「語素」）。例如「整數」標記可以包含所有數字字符序列。很多情況下，根據第一個非空白字符便可以推導出該標記的類型，於是便可逐個處理之後的字符，直到出現不屬於該類型標記字符集中的字符（即最長一致原則）。

標記生成器

標記化（tokenization）即將輸入字符串分割為標記、進而將標記進行分類的過程。生成的標記隨後便被用來進行語法分析。

例如對於如下字符串： The quick brown fox jumps over the lazy dog

計算機並不知道這是以空格分隔的九個英語單詞，只知道這是普通的43個字符構成的字符串。可以通過一定的方法（這裏即使用空格作為分隔符）將語素（這裏即英語單詞）從輸入字符串中分割出來。分割後的結果用XML可以表示如下：

<sentence>
  <word>The</word>
  <word>quick</word>
  <word>brown</word>
  <word>fox</word>
  <word>jumps</word>
  <word>over</word>
  <word>the</word>
  <word>lazy</word>
  <word>dog</word>
</sentence>

然而，語素只是一類字符構成的字符串（字符序列），要構建標記，語法分析器需要第二階段的評估器（Evaluator）。評估器根據語素中的字符序列生成一個「值」，這個「值」和語素的類型便構成了可以送入語法分析器的標記。一些諸如括號的語素並沒有「值」，評估器函數便可以什麼都不返回。整數、標識符、字符串的評估器則要複雜的多。評估器有時會抑制語素，被抑制的語素（例如空白語素和註釋語素）隨後不會被送入語法分析器。

例如對於某程式語言的源程序片段：

net_worth_future = (assets - liabilities);

在進行語法分析後可能生成以下單詞流（空格被抑制）：

NAME "net_worth_future" 
EQUALS 
OPEN_PARENTHESIS 
NAME "assets" 
MINUS 
NAME "liabilities" 
CLOSE_PARENTHESIS 
SEMICOLON

儘管在某些情況下需要手工編寫詞法分析器，一般情況下詞法分析器都用自動化工具生成。

關聯項目

• 語法分析器
• lex
• flex詞法分析器

參考文獻

• CS164: Programming Languages and Compilers (Class Notes #2: Lexical)
• Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X 624
• Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
• Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6