歷史
- 在1975年之前瑞筐,寫出一個編譯器是很麻煩的事情何缓。 在1975年的時候,有兩篇文章的發(fā)表冒版,簡化了編譯器的編寫液茎。
Lex - A Lexical Analyzer Generator.
Yacc: Yet Another Compiler Compiler. - Lex和YACC的具體實現(xiàn)細(xì)節(jié)可以在2006年的這本書中找到:
Compilers, Principles, Techniques and Tools (2nd edition). Addison-Wesley, Reading, Massachusetts. -
WinFlex和WinBison是Flex和Bison的Windows版本。
image.png
編譯順序
- Lex的輸入:詞法規(guī)則(.l文件)
- Lex的輸出:詞法分析器
- Yacc的輸入:語法規(guī)則(.y文件)
- Yacc的輸出:語法分析器
- 宿主程序使用詞法分析器和語法分析器辞嗡,產(chǎn)生分析結(jié)果捆等。
image.png
規(guī)則格式
Lex匹配規(guī)則
Yacc匹配規(guī)則
Lex文件格式
Lex預(yù)定義變量
Lex代碼示例
ECHO
LineNo
變量名
字符統(tǒng)計
Yacc文法
Yacc的語法是BNF范式的變種。BNF文法可以用來表示上下文無關(guān)文法续室,大多數(shù)的編程語言都可以用BNF來表示栋烤。
文法
文法可以擴(kuò)展的表達(dá)式
自底向上分析。默認(rèn)放一個“.”在棧里面挺狰。shift操作:一個新的標(biāo)識符入棧明郭。reduce操作:使用文法進(jìn)行規(guī)約。
Shift -Reduce沖突
例子中的第6步丰泊,E+E可以進(jìn)行Reduce薯定,但是也可以進(jìn)行Shift。使用符號結(jié)合方向和優(yōu)先級解決瞳购。
Reduce-Reduce沖突
id有兩種Reduce結(jié)果:E或者T话侄。
Yacc語法格式
語法格式
Yacc代碼示例
- lex文件
詞法分析器輸出的Token類型:VARIABLE,INTEGER学赛,-年堆,+,(盏浇,)变丧,=,/绢掰,\n痒蓬,a-z - yacc文件
詞法標(biāo)識:INTEGER,VARIABLE
符號優(yōu)先級與結(jié)合方式
文法標(biāo)識:program滴劲,statement谊却,expr
int sys[26]:a-z 26個變量的數(shù)值 - yytext
詞法分析器匹配到的字符串 - yylval
yytext相關(guān)的數(shù)值,比如:在詞法分析器匹配到數(shù)字的時候哑芹,設(shè)置yylval=atoi(yytext) 炎辨,在語法分析器,就可以通過$1聪姿,$2碴萧,來讀取對應(yīng)的yylval。 - 實際上末购,yacc內(nèi)部有兩個棧破喻,一個是分析棧,一個是內(nèi)容棧盟榴,分別用yytext和yylval來讀取曹质。
-
Lex Yacc (一) 入門 這里說的更加詳細(xì)一些。
Lex文件
Yacc文件
示例使用
幾次輸入輸出
第1次輸入
下載地址
https://github.com/lexxmark/winflexbison