詞法分析（lexical analysis）是計算機科學中將字元序列轉換為單詞（Token）序列的過程。進行詞法分析的程式或者函式叫作詞法分析器（Lexical analyzer，簡稱Lexer），也叫掃描器（Scanner）。詞法分析器一般以函式的形式存在，供語法分析器調用。
基本介紹
基本定義,有限狀態自動機,語法分析器,Lex詞法分析器,詞法分析器的設計,輸入緩衝區,兩個緩衝區的輸入模式,代碼實現,
基本定義
詞法分析的第一階段即掃描器，通常基於有限狀態自動機。掃描器能夠識別其所能處理的標記中可能包含的所有字元序列（單個這樣的字元序列即前面所說的“語素”）。例如“整數”標記可以包含所有數字字元序列。很多情況下，根據第一個非空白字元便可以推導出該標記的類型，於是便可逐個處理之後的字元，直到出現不屬於該類型標記字元集中的字元（即最長一致原則）。
詞法分析器的工作是低級別的分析：將字元或者字元序列轉化成記號。在談論詞法分析時，使用術語“詞法記號”（簡稱記號）、“模式”和“詞法單元”表示特定的含義。
在分析時，一是把詞法分析器當成語法分析的一部分，另一種是把詞法分析器當成編譯程式的獨立部分。在前一種情況下，詞法分析器不斷地被語法分析器調用，每調用一次詞法分析器將從源程式的字元序列拼出一個單詞，並將其Token值返回給語法分析器。後一種情況則不同，詞法分析器不是被語法分析器不斷地調用，而是一次掃描全部單詞完成編譯器的獨立一遍任務。
有限狀態自動機
有限狀態自動機（FSM "finite state machine" 或者FSA "finite state automaton" ）是為研究有限記憶體的計算過程和某些語言類而抽象出的一種計算模型。有限狀態自動機擁有有限數量的狀態，每個狀態可以遷移到零個或多個狀態，輸入字串決定執行哪個狀態的遷移。有限狀態自動機可以表示為一個有向圖。有限狀態自動機是自動機理論的研究對象。
有限狀態自動機是具有離散輸入和輸出的系統的一種數學模型。
其主要特點有以下幾個方面：
– (1)系統具有有限個狀態，不同的狀態代表不同的意義。按照實際的需要，系統可以在不同的狀態下完成規定的任務。
– (2)我們可以將輸入字元串中出現的字元匯集在一起構成一個字母表。系統處理的所有字元串都是這個字母表上的字元串。
– (3)系統在任何一個狀態下，從輸入字元串中讀入一個字元，根據當前狀態和讀入的這個字元轉到新的狀態。
– (4)系統中有一個狀態，它是系統的開始狀態。
– (5)系統中還有一些狀態表示它到目前為止所讀入的字元構成的字元串是語言的一個句子。
形式定義
· 定義：有限狀態自動機(FA—finite automaton)是一個五元組：
– M=(Q, Σ, δ, q0, F)
· 其中，
– Q——狀態的非空有窮集合。∀q∈Q，q稱為M的一個狀態。
– Σ——輸入字母表。
– δ——狀態轉移函式，有時又叫作狀態轉換函式或者移動函式，δ：Q×Σ→Q，δ(q,a)=p。
– q0——M的開始狀態，也可叫作初始狀態或啟動狀態。q0∈Q。
– F——M的終止狀態集合。F被Q包含。任給q∈F，q稱為M的終止狀態。
語法分析器
在計算機科學和語言學中，語法分析（英：Syntactic analysis，也叫Parsing）是根據某種給定的形式文法對由單詞序列（如英語單詞序列）構成的輸入文本進行分析並確定其語法結構的一種過程。
語法分析器（Parser）通常是作為編譯器或解釋器的組件出現的，它的作用是進行語法檢查、並構建由輸入的單詞組成的數據結構（一般是語法分析樹、抽象語法樹等層次化的數據結構）。語法分析器通常使用一個獨立的詞法分析器從輸入字元流中分離出一個個的“單詞”，並將單詞流作為其輸入。實際開發中，語法分析器可以手工編寫，也可以使用工具（半）自動生成。
語法分析器的任務主要是確定是否可以以及如何從語法的起始符號推導出輸入符號串（輸入文本），主要可以通過兩種方式完成：
自頂向下分析：根據形式語法規則，在語法分析樹的自頂向下展開中搜尋輸入符號串可能的最左推導。單詞按從左到右的順序依次使用。
自底向上分析：語法分析器從現有的輸入符號串開始，嘗試將其根據給定的形式語法規則進行改寫，最終改寫為語法的起始符號。
Lex詞法分析器
在計算機科學裡面，lex是一個產生詞法分析器（lexical analyzer，"掃瞄器"（scanners）或者"lexers"）的程式。 Lex常常與yacc 語法分析器產生程式（parser generator）一起使用。Lex(最早是埃里克·施密特和邁克·萊斯克製作）是許多UNIX系統的標準詞法分析器（lexical analyzer）產生程式，而且這個工具所作的行為被詳列為POSIX標準的一部分。
Lex讀進一個代表詞法分析器規則的輸入字元串流，然後輸出以C語言實做的詞法分析器原始碼。
雖然傳統上是商業軟體，但是有些根據原本AT&T代碼這些版本的Lex可以以公開原始碼的形式獲得，並被視為某些系統的一部分，例如說OpenSolaris和貝爾實驗室九號項目。另一個有名的Lex公開原始碼版本是flex，代表"快速的詞法分析器"（fast lexical analyzer）。
詞法分析器的設計
以下是源詞法分析器的設計與實現程式的輸入與預處理步驟：
輸入緩衝區
成對且對半互補的輸入緩衝區模式。
n: 取2的整次冪；每個半區的末尾設定標誌“ eof ” 表示讀入該半區的源程式的結束；
B：單詞w開始指針； F：掃描w的指針。
兩個緩衝區的輸入模式
預處理程式： （作用）
1） 減少記憶體空間占用；
2） 減輕掃描器實質性處理的負擔；
預處理程式主要任務： 1） 濾掉源程式中的非單詞成分(如無用空格；換行符等)；2） 其他的預處理工作:濾掉注釋；宏替換；檔案包含的嵌入；條件編譯的嵌入。
代碼實現
#include<stdio.h>#include<string.h>#include<iostream.h>char prog[80],token[8];char ch;int syn,p,m=0,n,row,sum=0;char *rwtab[6]={"begin","if","then","while","do","end"}; void scaner(){ /* 共分為三大塊，分別是標示符、數字、符號，對應下面的 if else if 和 else */ for(n=0;n<8;n++) token[n]=NULL; ch=prog[p++]; while(ch==' ') { ch=prog[p]; p++; } if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) //可能是標示符或者變數名 { m=0; while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) { token[m++]=ch; ch=prog[p++]; } token[m++]='\0'; p--; syn=10; for(n=0;n<6;n++) //將識別出來的字元和已定義的標示符作比較， if(strcmp(token,rwtab[n])==0) { syn=n+1; break; } } else if((ch>='0'&&ch<='9')) //數字 { { sum=0; while((ch>='0'&&ch<='9')) { sum=sum*10+ch-'0'; ch=prog[p++]; } } p--; syn=11; if(sum>32767) syn=-1; } else switch(ch) //其他字元 { case'<':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='>') { syn=21; token[m++]=ch; } else if(ch=='=') { syn=22; token[m++]=ch; } else { syn=23; p--; } break; case'>':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='=') { syn=24; token[m++]=ch; } else { syn=20; p--; } break; case':':m=0;token[m++]=ch; ch=prog[p++]; if(ch=='=') { syn=18; token[m++]=ch; } else { syn=17; p--; } break; case'*':syn=13;token[0]=ch;break; case'/':syn=14;token[0]=ch;break; case'+':syn=15;token[0]=ch;break; case'-':syn=16;token[0]=ch;break; case'=':syn=25;token[0]=ch;break; case';':syn=26;token[0]=ch;break; case'(':syn=27;token[0]=ch;break; case')':syn=28;token[0]=ch;break; case'#':syn=0;token[0]=ch;break; case'\n':syn=-2;break; default: syn=-1;break; }}int main(){ p=0; row=1; cout<<"Please input string:"<<endl; do { cin.get(ch); prog[p++]=ch; } while(ch!='#'); p=0; do { scaner(); switch(syn) { case 11: cout<<"("<<syn<<","<<sum<<")"<<endl; break; case -1: cout<<"Error in row "<<row<<"!"<<endl; break; case -2: row=row++;break; default: cout<<"("<<syn<<","<<token<<")"<<endl;break; } } while (syn!=0);}