本文是網(wǎng)易云課堂中國(guó)科學(xué)技術(shù)大學(xué)華保健老師教授的《編譯原理》課程習(xí)題。
1 題目
在這部分中詞法分析器界面圖片，你將使用圖轉(zhuǎn)移算法手工實(shí)現(xiàn)一個(gè)小型的詞法分析器。
2 程序框架 2.1 構(gòu)建表格存儲(chǔ)狀態(tài)轉(zhuǎn)移圖
根據(jù)題意構(gòu)建出轉(zhuǎn)移圖：
詞法分析器首先要將此轉(zhuǎn)移圖存儲(chǔ)在特定數(shù)據(jù)結(jié)構(gòu)中中，為了壓縮表格存儲(chǔ)，先將轉(zhuǎn)移圖中的邊所含有的信息進(jìn)行分類：
根據(jù)上述分類表，轉(zhuǎn)移圖針對(duì)每一個(gè)輸入的字符，查找其所屬類別，然后根據(jù)其類別進(jìn)行狀態(tài)轉(zhuǎn)移，這樣避免將所有的輸入信息存儲(chǔ)在狀態(tài)轉(zhuǎn)移圖的數(shù)據(jù)結(jié)構(gòu)中。狀態(tài)轉(zhuǎn)移表如下所示：
可接受的最終狀態(tài)如下表格所示：
2.2 讀入字符和回滾操作
使用相關(guān)IO函數(shù)，從文件中讀入程序信息，以及在必要的時(shí)候執(zhí)行()操作。本文使用Java實(shí)現(xiàn)，主要使用了API如下：
注意：要實(shí)現(xiàn)高效的詞法分析器，應(yīng)該使用合適的緩沖區(qū)，本文力圖簡(jiǎn)單，直接在文件流中進(jìn)行操作。關(guān)于緩沖區(qū)的具體實(shí)現(xiàn)可以參考文獻(xiàn)[1]。
2.2 執(zhí)行Parse操作
根據(jù)上述轉(zhuǎn)移圖的信息，逐步對(duì)輸入文件執(zhí)行parse操作的偽代碼[1] 如下：
NextWord()
state = s0 ;
lexeme = "";
clear stack;
push(bad);
while (state != se) do
NextChar(char);
lexeme = lexeme + char;
if(state in SA)
then clear stack;
push(state);
cat = CharCat[char];
state = δ[state,cat];
end;
while(state not in SA and state != bad) do
state pop();
truncate lexeme;
RollBack();
end;
if(state in SA)
then return Type[state];
else
return invalid;上述代碼首先進(jìn)行初始化操作，state表示目前所處的狀態(tài)，表示目前累計(jì)讀入的字符串，第一個(gè)while循環(huán)模擬了狀態(tài)轉(zhuǎn)移圖的轉(zhuǎn)移過程:
state存儲(chǔ)在棧中，以便出現(xiàn)Se后進(jìn)行回滾操作。與δ分別表示2.1節(jié)中的分類表和狀態(tài)轉(zhuǎn)移表，讀入字符后，根據(jù)讀入的字符和這兩張表進(jìn)行相關(guān)的狀態(tài)轉(zhuǎn)移，直到狀態(tài)為Se后停止轉(zhuǎn)移。第二個(gè)while根據(jù)最終的狀態(tài)是否是可接受的來決定是否進(jìn)行回滾操作，直到找到可接受的最終狀態(tài)。最后一段代碼返回結(jié)果，如果沒有可接受的最終狀態(tài)詞法分析器界面圖片，那么返回表示已經(jīng)無法解析出合法的Word。
2.3 總體結(jié)構(gòu)
最終實(shí)現(xiàn)的簡(jiǎn)單詞法分析器的具體結(jié)構(gòu)如下：
使用了內(nèi)部類來表示狀態(tài)轉(zhuǎn)移表中的初始狀態(tài)和讀入的字符，并重寫了其()方法和()方法，使其可以存儲(chǔ)在中。
3 代碼
見 。
參考文獻(xiàn)
[1] L, K. A [M]. Inc. 2007.