-
詞法分析器
鎖定
詞法分析器基本定義
詞法分析的第一階段即掃描器，通常基於有限狀態自動機。掃描器能夠識別其所能處理的標記中可能包含的所有字符序列（單個這樣的字符序列即前面所説的“語素”）。例如“整數”標記可以包含所有數字字符序列。很多情況下，根據第一個非空白字符便可以推導出該標記的類型，於是便可逐個處理之後的字符，直到出現不屬於該類型標記字符集中的字符（即最長一致原則）。
詞法分析器的工作是低級別的分析：將字符或者字符序列轉化成記號。在談論詞法分析時，使用術語“詞法記號”（簡稱記號）、“模式”和“詞法單元”表示特定的含義。
在分析時，一是把詞法分析器當成語法分析的一部分，另一種是把詞法分析器當成編譯程序的獨立部分。在前一種情況下，詞法分析器不斷地被語法分析器調用，每調用一次詞法分析器將從源程序的字符序列拼出一個單詞，並將其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"）的程序。
[2-3]
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） 減輕掃描器實質性處理的負擔；
詞法分析器代碼實現
#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);
}
