詞法分析-編譯原理-03-(二).

1、第三章第三章 詞法分析詞法分析 3 3.1 .1 詞法分析的任務(wù)詞法分析的任務(wù) 1) 1) 單詞符號的表示單詞符號的表示 例例 3-1: 3-1: 單詞符號序列單詞符號序列 while( while( * *p != 0 ) p+; p != 0 ) p+; 2) 2) 詞法分析程序（掃描器）的詞法分析程序（掃描器）的 工作方式工作方式 詞法分析詞法分析 表格管理表格管理 語法分析語法分析 源程序源程序 單詞單詞 符號表符號表 常數(shù)表常數(shù)表 設(shè)計與實現(xiàn)設(shè)計與實現(xiàn) 3.2 3.2 正規(guī)式和正規(guī)文法正規(guī)式和正規(guī)文法 1) 1) 正規(guī)式：另一種描述方法正規(guī)式：另一種描述方法 2) 2) 正規(guī)文法與正

2、規(guī)式正規(guī)文法與正規(guī)式 正規(guī)式轉(zhuǎn)換到正規(guī)文法正規(guī)式轉(zhuǎn)換到正規(guī)文法 3 3）詞法的描述）詞法的描述 3.3 3.3 單詞的識別單詞的識別 狀態(tài)圖狀態(tài)圖 123 L L 或或 D 其他其他 初態(tài)初態(tài)終態(tài)終態(tài) 1234 ab a 12 b 1 a L | D L （IDN，入口），入口） DIGIT DIGIT （NUM，值），值） （ASG，_） = ： + （ADD，_） 利用應(yīng)用狀態(tài)轉(zhuǎn)換圖識別單詞利用應(yīng)用狀態(tài)轉(zhuǎn)換圖識別單詞 例例 3-4 3-4 語言無符號整數(shù)的描述語言無符號整數(shù)的描述 3421 0 0-7 0-7 561 0 1-9 0-9 十進(jìn)制整數(shù)十進(jìn)制整數(shù) 八進(jìn)制整數(shù)八進(jìn)制整數(shù) 有限自動

3、機(jī)：有限自動機(jī)：狀態(tài)圖的形式化狀態(tài)圖的形式化 M = （0,9, 1,6, 1, 4,6, ） 構(gòu)造構(gòu)造 DFA 1 0 8-9 2,6 5,6 2,6 3,41-7 5,6 3,4 3,4 1、從開始狀態(tài)出發(fā)；、從開始狀態(tài)出發(fā)； 2、選擇輸入符號，構(gòu)成目標(biāo)狀態(tài)集、選擇輸入符號，構(gòu)成目標(biāo)狀態(tài)集 3、從新狀態(tài)集出發(fā)，重復(fù)、從新狀態(tài)集出發(fā)，重復(fù)1、2 5,6 5,6 5,6 3,43,4 5,6 DFA M = （0,9, 1,26,34,56, 1, 34,56, ） （OCT，值），值） 合并后的合并后的 狀態(tài)圖狀態(tài)圖 1 0 26 34 0-7 0-7 其他其他 56 1-9 0-9 其他其他（DEC，值），值） 其他 2) 2) 狀態(tài)圖的實現(xiàn)：狀態(tài)圖的實現(xiàn)：詞法分析程序詞法分析程序 掃描器的設(shè)計掃描器的設(shè)計 例例3-3 3-3 狀態(tài)圖的實現(xiàn)算法狀態(tài)圖的實現(xiàn)算法 實現(xiàn)問題實現(xiàn)問題: : 3) 3) 小結(jié)小結(jié)正規(guī)式正規(guī)式 狀態(tài)圖狀態(tài)圖 DFA 識別過程的實現(xiàn)算法識別過程的實現(xiàn)算