A. 一道《編譯原理》求follow集題目,在線等答案
哥們,你這個問題中的一個產生式E』→+TE』| e,應該是E->+TE』 |ε這樣吧!否則不可能獲得如此結果。
關於求follow集合,龍書中說得很清楚,依據三條規則即可:
1、任何FOLLOW(S)都包含輸入終止符號,其中S是開始符號。
適用該條,因此FOLLOW(E』)中包含終止符號#。
2、如果存在產生式,A->αBβ,則將FIRST(β)中除ε以外的符號都放入FOLLOW(B)中。
該條不適用,因為在上述所有產生式中不存在形如E『->αE』β這樣的產生式。
3、如果存在產生式,A->αB,或A->αBβ,其中FIRST(β)中包含ε,則將FOLLOW(A)中的所有符號都放入FOLLOW(B)中。
適用該條,因為存在這樣的產生式E->+TE』,使得FOLLOW(E』)=FOLLOW(E)成立。而FOLLOW(E)適用上述第二條,根據產生式F→(E)可求得為FOLLOW(E)={#,)}。
綜上,FOLLOW(E』)=FOLLOW(E)={#,)}。
B. 怎麼學習ollydbg原理是什麼基本使用方法是什麼
最簡單的方法是啟動OllyDbg,點擊File|Open,然後選擇你想調試的程序。程序需要命令行參數輸入對話框下方的文本欄。
重新開始調試最後一個程序的快捷鍵是Ctrl+F2,並且OllyDbg使用相同的參數。
你也可以點選歷史記錄。把程序拖入OllyDbg也可以開始調試。
當然,當啟動OllyDbg時,你在命令行中也能指定被調試的程序名和參數。比如:
你可以創建桌面快捷方式指向OllyDbg,選擇屬性,到快捷方式,把程序名加入目
標欄。每次你雙擊這個快捷圖標,OllyDbg自動裝載被調試程序。
你可以attach OllyDbg到某個正在運行的進程。點擊File|Attach,從列表中選擇
該進程。注意:當你關閉OllyDbg,這個進程也會終止。不要試圖attach系統進程
,這很可能使系統完全死機。(事實上,大多數情況下,OS不允許attach敏感進
程)
OllyDbg能作為just-in-time debugger。這需要在注冊表中登記。點擊
Options|Just-in-time debugging,在對話框中按「Make OllyDbg just-in-time
debugger」。現在,當一些程序崩潰,你會被詢問是否調試它。這樣,操作系統
可以啟動OllyDbg並直接停在異常發生處。如果你選擇attaching without
confirmation,OllyDbg不會詢問直接啟動。要恢復原來的just-in-time
debugger,在出現的對話框中按相應的按紐就行了。
其它方法還有,把OllyDbg加入可執行文件的彈出式菜單。點擊Options|Add to
Explorer,按「Add OllyDbg to menu in Windows Explorer」。以後你可以右擊
可執行文件點選OllyDbg。這個選項創建注冊表鍵
HKEY_CLASSES_ROOT/exefile/shell/Open with OllyDbg and
HKEY_CLASSES_ROOT/exefile/shell/Open with OllyDbg/command
OllyDbg可以調試控制台(基於文本)程序。
注意:WindowsNT或Windows2000下,你必須有管理員許可權
OllyDbg的help-通用快捷鍵(翻譯)
Golbal shortcuts(通用快捷鍵)
這些快捷鍵在OllyDbg中通用,不依賴於當前活動窗口。
Ctrl+F2---OllyDbg重置,重新開始調試。如果沒有活動程序,OllyDbg裝入歷史列表中的第一個程序。OllyDbg重置會釋放內存移除硬斷點。
Alt+F2--關閉被調試的程序。如果程序還在活動狀態,你會被詢問是否執行該操作。
F3--顯示「Open 32-bit .exe file」對話框,這里可以選擇可執行文件和指定參數
Alt+F5--使OllyDbg顯示在屏幕最前方。如果被調試程序中斷時顯示窗口遮住OllyDbg的一些區域,不繼續運行又不能移動或最小化它。激活OllyDbg按Alt+F5可以解決。如果你再次按Alt+F5,OllyDbg會恢復為普通窗口。OllyDbg的當前狀態顯示在狀態欄。
F7--step into,執行下一條簡單命令。如果該命令是一個函數調用,進入調用函數內部。如果命令有REP前綴,執行該命令的一步操作。
Shift+F7--與F7相同,除了當被調試程序遇到某些異常時,首先嘗試調用程序自己的異常處理過程。
Ctrl+F7--animate into,一步一步執行程序,也進入函數調用(就象你一直按著F7,不過更快)。當你執行一些單步或繼續命令,程序到達有效斷點,一些異常發生時,Animation終止。每步執行,OllyDbg重畫所有窗口。要加速animation,關閉所有窗口而不要只改變現有窗口的大小。終止animation,也可按Esc。
F8-step over,執行下一條簡單命令。如果該命令是一個函數調用,立刻執行完該函數(除非函數內部有斷點或產生異常)如果命令有REP前綴,執行所有重復操作,並停於下一條命令。
Shift+F8--與F8相同,除了當被調試程序遇到某些異常時,首先嘗試調用程序自己的異常處理過程。
Ctrl+F8--animate over,一步一步執行程序,但不進入函數調用(就象你一直按著F8,不過更快)。當你執行一些單步或繼續命令,程序Animation到達有效斷點或異常發生時,Animation終止。每步執行,OllyDbg重畫所有窗口。要加速animation,關閉所有窗口而不要只改變現有窗口的大小。終止animation也可按Esc。
F9--繼續執行程序。
Shift+F9--與F9相同。除了當被調試程序遇到某些異常時,首先嘗試調用程序自己的異常處理過程。
Ctrl+F11--run trace into,一步一步執行程序,要進入函數調用,記錄寄存器內容。Run trace 不重繪CPU窗口.
F12-懸掛所有線程以停止程序執行。最好用繼續鍵和菜單命令(像F9)恢復執行線程,而不要用其它手動方法恢復。
Ctrl+F12--run trace over,一步一步執行程序,不進入函數調用,記錄寄存器內容。Run trace不重繪CPU窗口。
ESC--如果animation或跟蹤正在進行,將被終止。如果CPU窗口顯示跟蹤時的數據,此時轉為顯示實際數據。
Alt+B--打開或恢復Breakpoint窗口。這里可以編輯,刪除和觀察斷點。
Alt+C--打開或恢復CPU窗口。
Alt+E--打開或恢復模塊列表
Alt+E--打開或恢復Call stack窗口。
Alt+L--打開或恢復Log窗口。
Alt+M--打開或恢復Memory窗口。
Alt+O--打開Option對話框
Ctrl+P--打開Patch窗口。
Ctrl+T--打開Pause run trace對話框
Alt+X-中斷OllyDbg。
多數窗口可以使用下列快捷鍵:
Alt+F3--關閉活動窗口。
Ctrl+F4--關閉活動窗口。
F5--最大化或恢復活動窗口。
F6--激活下一個窗口。
Shift+F6--激活前一個窗口。
F10--打開激活窗口或面板的右鍵菜單。
LeftArrow--左移一個字元。
Ctrl+LeftArrow--左移一行。
RightArrow--右移一個字元。
Ctrl+RightArrow--右移一行。
OllyDbg的help-分析模塊介紹(翻譯)
分析
OllyDbg集成了快速超強的代碼分析器。裝載它,可以用彈出式菜單或者CPU窗口
的反匯編欄按Ctrl+A或者在執行模塊選「Analyze all moles」。
分析器非常有用。它在數據中分辨代碼,標記入口點和jump的目標,辨認switch
tables,ASCII和UNICODE字元串,定位過程、循環、高級switch語句和解碼標准
API函數參數(看範例)。OllyDbg的其它部分也廣泛用於數據分析。
這怎麼可能呢?我稍微介紹一下原理。首先,OllyDbg反匯編代碼區所有可能的地
址,記下所有發現的調用及指向的目標。當然,許多這樣的調用不正確,但是未
必會有兩個錯誤的調用指向同一條命令,並且三個或三個以上更不可能。這樣,
三個或更多調用指向同一地址,我就確信該地址是經常使用的子過程入口。從這
個入口開始,我跟蹤所有的跳轉和調用,反復操作。這種方法使我99.9%確定所
有命令。然而,某些位元組不在這條鏈中,我採用大約20個更高效的方法(最簡單
的如:「MOV [RA],Ra"是無效命令).
過程檢測也簡單。過程,從分析器的角度看,就是從入口開始的代碼的連續區域
,(理論上)可以到達其它命令(除NOP或對齊填充外)。你可以指定三種識別級
。Strict級嚴格確認一個入口和至少一個出口。heuristical級,分析器嘗試確認
入口。如果你選擇fuzzy級,或多或少相容的代碼區被分離為過程。現代編譯器把
過程分成幾個部分作公用代碼優化。這種情況下,fuzzy級特別有用!然而,誤解
的概率也相當高。
類似的,loop是一個封閉的連續命令序列,這里最後的命令跳到開頭、一個入口
幾個出口。Loop相當於高級操作語言中的do,while和for。OllyDbg能認識任何復
雜的嵌套循環。在反匯編區,他們用長長的大括弧標記。如果入口不是循環的第
一條命令,OllyDbg用個小三角形作標記。
實現switch語句,多數編譯器把switch變數裝入寄存器,然後減去一部分,像下
面代碼序列一樣:
MOV EDX,<switch variable>
SUB EDX,100
JB DEFAULTCASE
JE CASE100 ; Case 100
DEC EDX
JNE DEFAULTCASE
... ; Case 101
這些序列也可能包含一級或兩級switch表,直接比較,優化,填充等等。如果你
深入研究比較和跳轉樹,很難說哪一條命令是某個case語句。OllyDbg為你代勞。
它標記所有的case語句,包括default,甚至嘗試猜測case的意思,如'A',
WM_PAINT 或者 EXCEPTION_ACCESS_VIOLATION。如果命令序列不修改寄存器(只
由比較命令構成),那麼不大可能是switch語句,但可能是if嵌套:
if (i==0) {...}
else if (i==5) {...}
else if (i==10) {...}
讓OllyDbg解碼if嵌套為switch,選擇Analysis1中相應的選項。
OllyDbg預置超過1900個常用API函數的描述。包括KERNEL32, GDI32, USER32,
ADVAPI32, COMDLG32, SHELL32, VERSION, SHLWAPI, COMCTL32, WINSOCK,
WS2_32 和 MSVCRT。你也可以加入自己的描述。如果分析器遇到已知函數名的調
用(或跳轉到該函數),它嘗試解碼調用跟前的PUSH命令。因此,你可以粗略翻
譯該調用的功能。OllyDbg也內置大約400個標准C函數的描述。如果你利用新庫,
我建議你分析前先掃描對象文件。這種情況下,OllyDbg也會解碼已知的C函數參
數。
如果選項「Guess number of arguments of unknown functions」被設置,分析
器嘗試確認調用過程進棧的雙字數目,並標記他們為參數Arg1,Arg2等等。注意:
如果有寄存器參數,OllyDbg還是不認識也不包括在上面的統計中。分析器採用了
一個安全的方法。例如,它不分辨無參數過程和返回前用POP恢復寄存器代替舍棄
參數的case語句。然而,能分辨出的函數數目相當多,並非常有助於提高代碼的
可讀性。
分析器能跟蹤寄存器的值。現代優化編譯器,特別是面向Pentium的,經常把常量
和地址裝入寄存器便於重復使用或減小內存佔用空間。如果一些常量裝入寄存器
,分析器會注意它,並用於解碼函數及其參數。還能執行簡單的算術計算跟蹤
push和pop命令。
分析器不能區別不同類型的名字。如果你用已有的名字命名一些函數,OllyDbg會
解碼所有該地址的調用為原過程。WinMain,DllEntryPoint和WinProc是特殊的預
定義名。你可以使用這些標號標記主程序入口,DLL入口指針和window過程(注意
:OllyDbg不會檢查用戶定義標號的唯一性)。當然,最好的方法是顯示已定義的
參數。
非常不幸,沒有一般的規則用於100%的准確分析。有些情況下,例如當模塊包含
p-代碼或者代碼區嵌入大量數據,分析器可能認為部分數據是代碼。如果統計分
析顯示代碼可能被打包或加密,分析器會警告你。如果你想用hit跟蹤方式,我建
議你不要用fuzzy分析方式,否則斷點被設置在被誤認為代碼的數據上的幾率很高。
自解壓文件通常在主體代碼外有解壓代碼。如果你選擇SFX選項「Extend code
section to include self-extractor」,OllyDbg會擴大代碼區,形式上允許分
析它並跟蹤。
OllDbg的一般原理(翻譯)部分
我希望你熟悉80x86兼容CPU的內部結構,並且有匯編寫程序的經歷。我也希望你
熟悉Microsoft Windows.
OllyDbg是一個單進程多線程的「機器代碼級」debugger,用於Windows環境下的32位程序。它允許你debug和patch PE格式的可執行程序。OllDbg僅僅使用列入文檔的Win32 API調用,所以可用於下一代32位Windows系統。OllDbg看來也可工作於Windows XP,但是我沒有詳盡的測試,因此不能保證功能完整。
OllyDbg不是面向編譯器。它不含特別的規則顯示某些情況下特定的編譯程序生成哪些代碼序列。因此,你可以一樣對待任何編譯器編譯的,或者匯編書寫的任何代碼。
OllyDbg與被調試的程序同時工作。你可以瀏覽代碼和數據、設置斷點、停止或繼續線程,甚至運行期修改內存(有時這叫作軟調試方式)。當然,如果被請求的操作不是最基本的,OllyDbg就會短時暫停程序,但這對用戶透明。有時不在調試狀態運行的程序會意外崩潰。OllyDbg,這個「及時」debugger,會指出異常發生的位置。
OllyDbg強烈面向模塊。模塊這里指啟動時載入的或動態載入的主執行文件或動態連接庫。在調試區,你可以設置斷點,定義新標號和注釋匯編語句。當一些模塊從內存卸載後,OllyDbg保存這些信息到擴展名為.UDD名字同被調試模塊的文件中。下次當裝載這些模塊時,OllyDbg自動復原所有調試信息,不論程序是否使用這些模塊。比如:你調試使用Mydll的程序Myprog1,並且在Mydll中設置一些斷點。那麼當你調試Myprog2時,也使用Mydll,你會發現所有在Mydll中的斷點還在那裡,不管Mydll是否裝載在不同的位置。
一些調試器把被調試進程的內存視為單個2**32位元組區域。OllyDbg做了別的處理方法。內存由幾個獨立的塊組成。任何內存操作都限制於塊內。在大多數案例中,這工作優良並且容易調試。但是模塊包含幾個執行部分等等,你將不能立刻看到整個代碼。然而這些例外不常見。
OllyDbg是內存消耗大戶。啟動時就要分配3MB內存,甚至更多。每次分析,備份,跟蹤或文件轉儲另外再分配。所以當你調試大工程時消耗40或60M內存很正常。
要有效的調試一些無源代碼的程序,你首先必須理解它是如何工作的。OllyDbg提供了大量的手段使理解更容易
C. 關於編譯原理first follow 和select
首先要明白這三個集的作用和用途,知道了他們是用來做什麼的之後,理解起來就簡單一些
First(A)集的作用是標示在替換非終結符A的時候,替換後的文法的首字母集合,語法分析程序根據這個來判斷給定的語言是否是合法的,是符合規則的。
Follow(A)的作用是標示那些可以出現在A之後的字元,語法分析程序根據這個,在A可以被替換為e(空)的時候來進行判斷,看當前的文法是否是合法的。
這里簡單說明下,比如A->b,A->e(空) 當給定的語言是 bXXXXX的時候,根據第一句文法就可以判定句子合法,但是如果給的語言是cXXXXX的時候,因為A->可以替換為空,這時候就需要一句A的follow集來進行判斷,若A的follow集裡面含有c 則語言是合法的
Select集的作用是將first集和follow集進行合並,如果兩個文法的左端都是A,若他們的select集交集為空,表明他們是兩個無關的,不會產生不確定性的文法,反之,則表明文法不是LL(1)文法
計算的公式很繁雜,理解了意思之後,看就能看出來。。。。
D. 編譯原理試題·
Lex和Yacc應用方法(一).初識Lex
草木瓜 20070301
Lex(Lexical Analyzar 詞法分析生成器),Yacc(Yet Another Compiler Compiler
編譯器代碼生成器)是Unix下十分重要的詞法分析,語法分析的工具。經常用於語言分
析,公式編譯等廣泛領域。遺憾的是網上中文資料介紹不是過於簡單,就是跳躍太大,
入門參考意義並不大。本文通過循序漸進的例子,從0開始了解掌握Lex和Yacc的用法。
一.Lex(Lexical Analyzar) 初步示例
先看簡單的例子(註:本文所有實例皆在RetHat linux下完成):
一個簡單的Lex文件 exfirst.l 內容:
%{
#include "stdio.h"
%}
%%
[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在命令行下執行命令flex解析,會自動生成lex.yy.c文件:
[root@localhost liweitest]flex exfirst.l
進行編譯生成parser可執行程序:
[root@localhost liweitest]cc -o parser lex.yy.c -ll
[注意:如果不加-ll鏈結選項,cc編譯時會出現以下錯誤,後面會進一步說明。]
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:77: undefined reference to `main'
/tmp/cciACkbX.o(.text+0x37b): In function `yylex':
: undefined reference to `yywrap'
/tmp/cciACkbX.o(.text+0xabd): In function `input':
: undefined reference to `yywrap'
collect2: ld returned 1 exit status
創建待解析的文件 file.txt:
title
i=1+3.9;
a3=909/6
bcd=4%9-333
通過已生成的可執行程序,進行文件解析。
[root@localhost liweitest]# ./parser < file.txt
Var : title
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
到此Lex用法會有個直觀的了解:
1.定義Lex描述文件
2.通過lex,flex工具解析成lex.yy.c文件
3.使用cc編譯lex.yy.c生成可執行程序
再來看一個比較完整的Lex描述文件 exsec.l :
%{
#include "stdio.h"
int linenum;
%}
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
進行解析編譯:
[root@localhost liweitest]flex exsec.l
[root@localhost liweitest]cc -o parser lex.yy.c
[root@localhost liweitest]./parser < file.txt
----- Lex Example -----
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
Line Count: 4
這里就沒有加-ll選項,但是可以編譯通過。下面開始著重整理下Lex描述文件.l。
二.Lex(Lexical Analyzar) 描述文件的結構介紹
Lex工具是一種詞法分析程序生成器,它可以根據詞法規則說明書的要求來生成單詞識
別程序,由該程序識別出輸入文本中的各個單詞。一般可以分為<定義部分><規則部
分><用戶子程序部分>。其中規則部分是必須的,定義和用戶子程序部分是任選的。
(1)定義部分
定義部分起始於 %{ 符號,終止於 %} 符號,其間可以是包括include語句、聲明語句
在內的C語句。這部分跟普通C程序開頭沒什麼區別。
%{
#include "stdio.h"
int linenum;
%}
(2) 規則部分
規則部分起始於"%%"符號,終止於"%%"符號,其間則是詞法規則。詞法規則由模式和
動作兩部分組成。模式部分可以由任意的正則表達式組成,動作部分是由C語言語句組
成,這些語句用來對所匹配的模式進行相應處理。需要注意的是,lex將識別出來的單
詞存放在yytext[]字元數據中,因此該數組的內容就代表了所識別出來的單詞的內容。
類似yytext這些預定義的變數函數會隨著後面內容展開一一介紹。動作部分如果有多
行執行語句,也可以用{}括起來。
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
A.規則部分的正則表達式
規則部分是Lex描述文件中最為復雜的一部分,下面列出一些模式部分的正則表達式字
符含義:
A-Z, 0-9, a-z 構成模式部分的字元和數字。
- 指定范圍。例如:a-z 指從 a 到 z 之間的所有字元。
\ 轉義元字元。用來覆蓋字元在此表達式中定義的特殊意義,
只取字元的本身。
[] 表示一個字元集合。匹配括弧內的任意字元。如果第一個字
符是^那麼它表示否定模式。例如: [abC] 匹配 a, b, 和C
的任何一個。
^ 表示否定。
* 匹配0個或者多個上述模式。
+ 匹配1個或者多個上述模式。
? 匹配0個或1個上述模式。
$ 作為模式的最後一個字元時匹配一行的結尾。
{ } 表示一個模式可能出現的次數。 例如: A{1,3} 表示 A 可
能出現1次或3次。[a-z]{5} 表示長度為5的,由a-z組成的
字元。此外,還可以表示預定義的變數。
. 匹配任意字元,除了 \n。
( ) 將一系列常規表達式分組。如:{Letter}({Letter}|{Digit})*
| 表達式間的邏輯或。
"一些符號" 字元的字面含義。元字元具有。如:"*" 相當於 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"後跟有後續表達式,
只匹配模版中"/"前面的部分。如:模式為 ABC/D 輸入 ABCD,
時ABC會匹配ABC/D,而D會匹配相應的模式。輸入ABCE的話,
ABCE就不會去匹配ABC/D。
B.規則部分的優先順序
規則部分具有優先順序的概念,先舉個簡單的例子:
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
%%
此時,如果輸入內容:
[root@localhost liweitest]# cat file1.txt
AAAAAAA
[root@localhost liweitest]# ./parser < file1.txt
THREE
TWO
ONE
Lex分析詞法時,是逐個字元進行讀取,自上而下進行規則匹配的,讀取到第一個A字元
時,遍歷後發現三個規則皆匹配成功,Lex會繼續分析下去,讀至第五個字元時,發現
"AAAA"只有一個規則可用,即按行為進行處理,以此類推。可見Lex會選擇最長的字元
匹配規則。
如果將規則
AAAA {printf("THREE\n");};
改為
AAAAA {printf("THREE\n");};
./parser < file1.txt 輸出結果為:
THREE
TWO
再來一個特殊的例子:
%%
title showtitle();
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
%%
並輸入title,Lex解析完後發現,仍然存在兩個規則,這時Lex只會選擇第一個規則,下面
的則被忽略的。這里就體現了Lex的順序優先順序。把這個例子稍微改一下:
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%
Lex編譯時會提示:warning, rule cannot be matched.這時處理title字元時,匹配
到第一個規則後,第二個規則就無效了。
再把剛才第一個例子修改下,加深下印象!
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
AAAA {printf("Cannot be executed!");};
./parser < file1.txt 顯示效果是一樣的,最後一項規則肯定是會忽略掉的。
C.規則部分的使用變數
且看下面示例:
%{
#include "stdio.h"
int linenum;
%}
int [0-9]+
float [0-9]*\.[0-9]+
%%
{int} printf("Int : %s\n",yytext);
{float} printf("Float : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在%}和%%之間,加入了一些類似變數的東西,注意是沒有;的,這表示int,float分
別代指特定的含義,在兩個%%之間,可以通過{int}{float}進行直接引用,簡化模
式定義。
(3) 用戶子程序部分
最後一個%%後面的內容是用戶子程序部分,可以包含用C語言編寫的子程序,而這些子
程序可以用在前面的動作中,這樣就可以達到簡化編程的目的。這里需要注意的是,
當編譯時不帶-ll選項時,是必須加入main函數和yywrap(yywrap將下後面說明)。如:
...
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行Lex分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
三.Lex(Lexical Analyzar) 一些的內部變數和函數
內部預定義變數:
yytext char * 當前匹配的字元串
yyleng int 當前匹配的字元串長度
yyin FILE * lex當前的解析文件,默認為標准輸出
yyout FILE * lex解析後的輸出文件,默認為標准輸入
yylineno int 當前的行數信息
內部預定義宏:
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字元的
默認動作
內部預定義的函數:
int yylex(void) 調用Lex進行詞法分析
int yywrap(void) 在文件(或輸入)的末尾調用。如果函數的返回值是1,就停止解
析。 因此它可以用來解析多個文件。代碼可以寫在第三段,這
樣可以解析多個文件。 方法是使用 yyin 文件指針指向不同的
文件,直到所有的文件都被解析。最後,yywrap() 可以返回1
來表示解析的結束。
lex和flex都是解析Lex文件的工具,用法相近,flex意為fast lexical analyzer generator。
可以看成lex的升級版本。
相關更多內容就需要參考flex的man手冊了,十分詳盡。
四.關於Lex的一些綜述
Lex其實就是詞法分析器,通過配置文件*.l,依據正則表達式逐字元去順序解析文件,
並動態更新內存的數據解析狀態。不過Lex只有狀態和狀態轉換能力。因為它沒有堆棧,
它不適合用於剖析外殼結構。而yacc增加了一個堆棧,並且能夠輕易處理像括弧這樣的
結構。Lex善長於模式匹配,如果有更多的運算要求就需要yacc了。
E. 編譯原理中正規式(ba|a)*如何轉換成NFA
F. 編譯原理空字元ε與空集區別
不知你說的空集是為何指?據我所猜應該是指某個文法所能推導的語句的集合為空,這里的空集意思是不存在匹配該文法的句子。而ε則是指某個包含非終結符號的文法符號串的推導為空,例如A->ε。咋看上去好像差不多,其實它們卻有本質的區別,空集是面向結果的,即一個文法所有可能推導的最終語句;而ε則是面向定義的,即某個非終結符號可以推導為空,這樣的定義可以在推導過程重復使用。
最後給你來點哲學的。為什麼會存在ε?古代有句話叫,其大無外,其小無內,大小之間轉化的奧秘在編譯原理中真實的被呈現了出來,就看你有沒有發現。可以肯定的說,ε的存在正是應了無窮的需要。例如:A->aA|ε,這里ε既可以A可以表達任意多的a串,又可以動態的將其終止,不至無休止的無限下去。
你終會明白,理解了ε,就是理解了形式語言的整個靈魂。