2.2 語(yǔ)法分析器生成器YACC,分析器的構(gòu)造步驟： 產(chǎn)生式識(shí)別活前綴的DFA分析表（驅(qū)動(dòng)器）,2.2.1 YACC概述 工作方式：,2.2.1 YACC概述,2YACC生成的語(yǔ)法分析器框架,利用YACC進(jìn)行語(yǔ)法分析器設(shè)計(jì)的關(guān)鍵，也是如何編寫(xiě)YACC源程序。 下邊首先介紹YACC源程序的基本結(jié)構(gòu)，然后著重討論YACC的產(chǎn)生式、YACC解決產(chǎn)生式?jīng)_突的方法、以及YACC對(duì)語(yǔ)義的支持和對(duì)錯(cuò)誤的處理等。,2.2.2 YACC源程序的基本結(jié)構(gòu),聲明（declarations） % 翻譯規(guī)則(translation rules) % 用戶(hù)定義子程序（user defined routines）,與LEX的區(qū)別： 至少一條翻譯規(guī)則,2.2.2 YACC源程序的基本結(jié)構(gòu)（續(xù)1）,例2.10 簡(jiǎn)單的YACC源程序。,% #include #include % %token num %left - %left *,% LS ：LS E n printf(“%dn“，$2)； | E n printf(“%dn“，$1)； ; E ：E - E $=$1-$3； | E * E $=$1*$3； | num ;,% int yylex() int c; while (c=getchar()= ); if (isdigit(c) ungetc(c, stdin); scanf(yytext,“%d“;$yylval); return num; return c main() parser(); ,用戶(hù)編寫(xiě)的詞法分析器應(yīng)與LEX產(chǎn)生的詞法分析器有相同的界面，以供語(yǔ)法分析器使用，它們包括：yylex()、yylval、yytext和yyleng等。, 聲明, C語(yǔ)言部分 “%“ “%“ Yacc的說(shuō)明部分 目的是為翻譯規(guī)則服務(wù)。 文法的開(kāi)始符號(hào)： %start n_name （默認(rèn)第一個(gè)產(chǎn)生式的左部是開(kāi)始符號(hào)） 終結(jié)符： 直接表示：-和*等； （無(wú)需說(shuō)明） 名字： %token t_name （內(nèi)部編碼，LEX中使用） 說(shuō)明終結(jié)符的優(yōu)先級(jí)與結(jié)合性：（非終結(jié)符下節(jié)討論） 結(jié)合性： 左結(jié)合%left 右結(jié)合%right 無(wú)結(jié)合性%nonassoc 優(yōu)先級(jí)：從上到下依次遞增 %left + - %left * / 重新定義語(yǔ)義棧類(lèi)型（下節(jié)討論）。, 用戶(hù)定義子程序,這部分與LEX的第三部分作用相同，所有語(yǔ)義動(dòng)作中的C源程序均可定義在此。如例2.10中的yylex()，若采用LEX生成yylex()，則可編寫(xiě)LEX源程序如下： % nt； 0-9+ scanf(yytext，“%d“，&yylval)； return NUMBER； . return yytext0； 而例2.10中yylex()的定義相應(yīng)改為#include “l(fā)ex.yy.c“即可。, 翻譯規(guī)則,規(guī)則 非終結(jié)符 : 候選項(xiàng)集 ; 候選項(xiàng)集 | 候選項(xiàng) | 候選項(xiàng)集 | 候選項(xiàng) 候選項(xiàng) 文法符號(hào)序列 右部語(yǔ)義動(dòng)作 文法符號(hào)序列 | 文法符號(hào)序列 文法符號(hào) 文法符號(hào) 終結(jié)符 | 非終結(jié)符 | 嵌入語(yǔ)義動(dòng)作 右部語(yǔ)義動(dòng)作 |C語(yǔ)言語(yǔ)句序列 嵌入語(yǔ)義動(dòng)作 C語(yǔ)言語(yǔ)句序列,E ：E - E $=$1-$3； | E * E $=$1*$3； | num ;,2.2.3 YACC程序設(shè)計(jì), YACC解決沖突的方法（二義文法時(shí)產(chǎn)生的沖突）,分析表中的兩類(lèi)沖突 移進(jìn)/歸約沖突：在一個(gè)狀態(tài)中，面對(duì)相同的下一文法符號(hào)，可以同時(shí)有移進(jìn)和歸約兩個(gè)動(dòng)作與其匹配； 歸約/歸約沖突：在一個(gè)狀態(tài)中，面對(duì)相同的下一文法符號(hào)，有兩個(gè)或兩個(gè)以上的產(chǎn)生式可以進(jìn)行歸約。 YACC的默認(rèn)解決方案 移進(jìn)/歸約沖突時(shí)，執(zhí)行移進(jìn)動(dòng)作，即移進(jìn)先于歸約； 歸約/歸約沖突時(shí)，用YACC源程序中第一個(gè)出現(xiàn)的產(chǎn)生式進(jìn)行歸約。 用戶(hù)解決方案：規(guī)定優(yōu)先級(jí)和結(jié)合性,例2.11 對(duì)于如下產(chǎn)生式：,%left + - %left * / %right uminus E ：E + E $=$1+$3； | E - E $=$1-$3； | E * E $=$1*$3； | E / E $=$1/$3； | - E %prec uminus $=-$2； | num $=$1； ；,產(chǎn)生式的優(yōu)先級(jí)和結(jié)合性與產(chǎn)生式右部最右邊的終結(jié)符一致。若不一致時(shí)，采用占位符(place holder)的方法解決。如上邊的%prec uminus。 如果不說(shuō)明%prec uminus，則產(chǎn)生式E:-E對(duì)于輸入序列-3*6，處理結(jié)果是-(3*6)，即在-的情況下遇到*時(shí)先移進(jìn)。而說(shuō)明之后，處理結(jié)果是(-3)*6。, YACC對(duì)語(yǔ)義的支持,分析器工作原理：,語(yǔ)義棧對(duì)語(yǔ)法制導(dǎo)翻譯提供直接支持。語(yǔ)義棧的類(lèi)型決定了文法符號(hào)的屬性，語(yǔ)義棧類(lèi)型表示能力的強(qiáng)弱決定了YACC的能力。, YACC默認(rèn)的語(yǔ)義值類(lèi)型,YACC語(yǔ)義棧與yylval同類(lèi)型，并以終結(jié)符的yylval值作為棧中的初值。因?yàn)閥ylval的默認(rèn)類(lèi)型為整型，所以，當(dāng)用戶(hù)所需文法符號(hào)的語(yǔ)義類(lèi)型是整型時(shí)，無(wú)需定義它的類(lèi)型。如在下述表達(dá)式的產(chǎn)生式中：,E ：E + E $=$1+$3； | E * E $=$1*$3； | num ；, 所需語(yǔ)義值不是整型,用 #define YYSTYPE new_type沖去默認(rèn)的int類(lèi)型，然后通過(guò)YACC所生成分析器中的變量聲明語(yǔ)句使yylval獲得新的類(lèi)型。例如： YYSTYPE yylval; 使得yylval具有new_type類(lèi)型。,例2.11,#define YYSTYPE treeptr typedef struct tnode int data； struct tnode *left； struct tnode *right； treenode，*treeptr； E ：E + E $ = node(+，$1，$3)； | E * E $ = node(*，$1，$3)； | num $ = leaf($1)； ；,就會(huì)為E構(gòu)造一棵語(yǔ)法樹(shù), 所需語(yǔ)義值不止一個(gè)類(lèi)型,YACC源程序中文法符號(hào)的語(yǔ)義值往往需要具有不止一種類(lèi)型，通過(guò)C語(yǔ)言提供的union機(jī)制來(lái)解決這一問(wèn)題。 定義不同的語(yǔ)義值類(lèi)型： %union int ival； double dval； treeptr tval； 在聲明文法符號(hào)的同時(shí)說(shuō)明它們的語(yǔ)義值類(lèi)型： %token num %token real %token id %type E (非終結(jié)符的說(shuō)明用%type),注意: %type 用于說(shuō)明非終結(jié)符的語(yǔ)義值類(lèi)型 %prec 用于說(shuō)明非終結(jié)符的優(yōu)先級(jí)與結(jié)合性, YACC源程序的一般書(shū)寫(xiě)習(xí)慣,設(shè)計(jì)YACC的產(chǎn)生式時(shí)，盡量采用左遞歸形式。由于左遞歸意味著歸約先于移進(jìn)，所以左遞歸產(chǎn)生式構(gòu)造的分析器可以使移進(jìn)/歸約分析棧的內(nèi)容總是保持最少，而右遞歸意味著移進(jìn)先于歸約，所以右遞歸產(chǎn)生式構(gòu)造的分析器，在極端的輸入情況下，會(huì)使分析棧溢出。 充分利用優(yōu)先級(jí)和結(jié)合性，而不是引進(jìn)非終結(jié)符來(lái)解決文法中的沖突，以減少產(chǎn)生式個(gè)數(shù)。特別是盡量避免形如ET的單非產(chǎn)生式，以提高分析速度。 終結(jié)符和非終結(jié)符在書(shū)寫(xiě)上最好有明確區(qū)分，例如分別用大、小寫(xiě)來(lái)表示非終結(jié)符和終結(jié)符，以便于程序的閱讀。,lex與yacc實(shí)例（看演示）, YACC對(duì)語(yǔ)法錯(cuò)誤的處理,沒(méi)有處理語(yǔ)法錯(cuò)誤功能的語(yǔ)法分析器對(duì)含有語(yǔ)法錯(cuò)誤的輸入序列進(jìn)行分析時(shí)，遇到第一個(gè)語(yǔ)法錯(cuò)誤時(shí)分析器就會(huì)停止分析。這給用戶(hù)帶來(lái)極大不便，同時(shí)也是不實(shí)用的。因此，YACC提供處理語(yǔ)法錯(cuò)誤的機(jī)制，它采用的方法是所謂的出錯(cuò)產(chǎn)生式方法。, 不引入出錯(cuò)產(chǎn)生式的情況,在沒(méi)有適當(dāng)?shù)恼Z(yǔ)法錯(cuò)誤處理的情況下，YACC生成的語(yǔ)法分析器對(duì)輸入序列進(jìn)行分析時(shí)，遇到語(yǔ)法錯(cuò)誤時(shí)會(huì)由于在棧頂形不成該語(yǔ)言的活前綴（形不成產(chǎn)生式的右部），而找不到適當(dāng)?shù)漠a(chǎn)生式與之匹配，從而造成棧中元素被連續(xù)彈出，直到棧被彈空，迫使分析過(guò)程終止。,一條沒(méi)有出錯(cuò)處理機(jī)制的產(chǎn)生式,%left + % E : E + E | num;,(b) 分析表的正文形式,(c) 圖形表示的DFA,(d) 在DFA上分析3+5,棧頂內(nèi)容 剩余輸入 分析器動(dòng)作 # 0 3+5# 移進(jìn)num，轉(zhuǎn)向state 2 # 0 num 2 +5# 按(2) “E : num”歸約，goto state 1 # 0 E 1 +5# 移進(jìn) +，轉(zhuǎn)向3 # 0 E 1 + 3 error+5# 輸入序列中插入error，彈出state 3 # 0 E 1 error+5# 彈出state 1 # 0 error+5# 彈出state 0 # error+5# ?,2005年3月4日, 引入出錯(cuò)產(chǎn)生式的情況,加入出錯(cuò)產(chǎn)生式： E : E + E | num | error; 圖形表示的DFA：,為了解決這一問(wèn)題，YACC引入了對(duì)特殊終結(jié)符error的處理，利用它在適當(dāng)?shù)牡胤郊尤肴舾伞俺鲥e(cuò)產(chǎn)生式“，即含有特殊終結(jié)符error的產(chǎn)生式。,此時(shí)有了error的狀態(tài)轉(zhuǎn)移！,引入出錯(cuò)產(chǎn)生式的情況（續(xù)）,棧頂內(nèi)容 剩余輸入 分析器動(dòng)作 # 0 3+5# 移進(jìn) num，轉(zhuǎn)向state 3 # 0 num 3 +5# 按(2)“E : num”歸約，goto State 1 # 0 E 1 +5# 移進(jìn) +，轉(zhuǎn)向State 4 # 0 E 1 + 4 error+5# 移進(jìn)error，轉(zhuǎn)向 state 2 # 0 E 1 + 4 error 2 +5# 按(3)“E : error”歸約，goto State 5, # 0 E 1 + 4 E 5 +5# 按(1)“E : E+E”歸約，goto State 1 # 0 E 1 +5# 移進(jìn) +，轉(zhuǎn)向State 4 # 0 E 1 + 4 5# 移進(jìn) num，轉(zhuǎn)向 State 3 # 0 E 1 + 4 num 3 # 按(2)“E : num”歸約，goto State 5 # 0 E 1 + 4 E 5 # 按(1)“E : E+E”歸約，goto State 1 # 0 E 1 # 接受,再分析3+5, YACC生成的分析器處理錯(cuò)誤的一般原則,當(dāng)認(rèn)為當(dāng)前有錯(cuò)時(shí)（棧頂不匹配，即找不到下一個(gè)可匹配的終結(jié)符），就插入一個(gè)error到輸入中，并從棧中彈出若干狀態(tài)對(duì)（也可能無(wú)需彈出），直到找到含有項(xiàng)目 A . error 的狀態(tài)（如狀態(tài)4），此時(shí)移進(jìn) error （可能為空，例如狀態(tài)4下E. error）；（移進(jìn)） 按Aerror .歸約后，拋棄若干輸入字符（可能無(wú)需拋棄，最多可能拋棄3個(gè)），直到發(fā)現(xiàn)一個(gè)能回到正常分析的終結(jié)符（稱(chēng)為同步記號(hào)）為止。（歸約） 是否彈棧和是否拋棄若干輸入，視輸入序列而定。 一般模式： 出錯(cuò)插入error在當(dāng)前輸入彈出棧中若干對(duì)（也可能不彈出），直到與error匹配歸約后拋棄若干輸入（也可能不拋棄）分析繼續(xù)進(jìn)行。, YACC生成的分析器處理錯(cuò)誤的一般原則（續(xù)1）,4. 分析5 5+5，既從棧中彈出若干狀態(tài)對(duì)，又在歸約后拋棄若 干字符。,棧頂內(nèi)容 剩余輸入 分析器動(dòng)作 # 0 5 5+5# s2 # 0 num 2 5+5# r2，goto State 1 # 0 E 1 error 5+5# pop(E, 1) # 0 error 5+5# s2 # 0 error 2 5+5# r3，goto State 1 # 0 E 1 5+5# 拋棄5 # 0 E 1 +5# s4 # 0 E 1+4 5# s3 # 0 E 1+4 num 3 # r2, goto state 5 # 0 E 1+4 E 5 # r1, goto state 1 # 0 E 1 # $end, accept, YACC生成的分析器處理錯(cuò)誤的一般原則（續(xù)2）,為使分析器盡快從錯(cuò)誤中恢復(fù)過(guò)來(lái)，YACC提供一個(gè)過(guò)程yyerrok，執(zhí)行它后，分析器不再拋棄輸入序列中的終結(jié)符，使分析器回到正常操作方式。在使用yyerrok時(shí)應(yīng)注意，如果產(chǎn)生式形如Aerror，其后語(yǔ)義動(dòng)作中加入yyerrok時(shí)，會(huì)使分析器不再拋棄終結(jié)符，而這時(shí)分析器也不會(huì)移進(jìn)任何終結(jié)符，從而使分析器陷入死循環(huán)。, 如何設(shè)計(jì)出錯(cuò)產(chǎn)生式, 初學(xué)者感覺(jué)困難的原因 語(yǔ)法錯(cuò)誤出現(xiàn)的隨機(jī)性和文法的復(fù)雜性，使得在文法中加入出錯(cuò)產(chǎn)生式去預(yù)置對(duì)語(yǔ)法錯(cuò)誤的處理帶有一定的盲目性； 處理機(jī)制沒(méi)有統(tǒng)一標(biāo)準(zhǔn)； 過(guò)多地加入error會(huì)人為造成沖突，使得有些出錯(cuò)產(chǎn)生式不能同時(shí)加入。, 如何設(shè)計(jì)出錯(cuò)產(chǎn)生式（續(xù)1）,例2.12 對(duì)于下述產(chǎn)生式：,% LS ：LS E n printf(“%dn“，$2)； | E n printf(“%dn“，$1)； | error yyerror(“l(fā)ines: error”); (從一行中恢復(fù)) ; E ：E - E $=$1-$3； | E * E $=$1*$3； | num | error yyerror(“expr: error”); (從一個(gè)表達(dá)式中恢復(fù)) ; %,考慮輸入序列： 23*34-5-2*3 23*4-23*2+5-6*2 23*4-23*2-6+5*3-4,保留第一個(gè)出錯(cuò)產(chǎn)生式，執(zhí)行的結(jié)果為： 711 lines ：error lines ：error,保留第二個(gè)出錯(cuò)產(chǎn)生式，執(zhí)行的結(jié)果為： 711 expr ：error 34 expr ：error -22, 如何設(shè)計(jì)出錯(cuò)產(chǎn)生式（續(xù)2）, 出錯(cuò)產(chǎn)生式加入的位置與語(yǔ)法分析的關(guān)系： 越接近終結(jié)符（如E ：error），錯(cuò)誤定位越精確； 越接近開(kāi)始符號(hào)（如LS : error）分析棧越低。, 加入出錯(cuò)產(chǎn)生式的一般原則： 避免產(chǎn)生沖突； 盡量接近文法的開(kāi)始符號(hào)（使分析棧盡可能低）； 盡量接近終結(jié)符（使出錯(cuò)定位較精確）； 最好不要加在產(chǎn)生式最右邊（即A error 中，最好不為空）； 為關(guān)鍵結(jié)構(gòu)（如條件、循環(huán)等）引入出錯(cuò)產(chǎn)生式。,2.2.4 YACC源程序舉例（略，可參閱“解答”）,2.3 其他語(yǔ)言識(shí)別器生成工具簡(jiǎn)介,詞法分析器生成器和語(yǔ)法分析器生成器，就其真實(shí)作用來(lái)講，并不僅僅用于編譯器的編寫(xiě)，凡是需要語(yǔ)言識(shí)別的應(yīng)用軟件，均可以利用它們來(lái)構(gòu)造。 因此更確切地講，它們是一類(lèi)語(yǔ)言識(shí)別器生成工具。由于LEX和YACC的廣泛應(yīng)用，似乎給人造成了這樣的錯(cuò)覺(jué)，語(yǔ)言識(shí)別器生成工具就是LEX和YACC及其類(lèi)似產(chǎn)品。 但實(shí)事并不是這樣，根據(jù)生成器的目標(biāo)語(yǔ)言、功能需求、基于的文法、以及生成器之間的耦合程度等不同，形成了它們的多樣性。程序設(shè)計(jì)資源網(wǎng)站： /Programming/Compilers/Lexer_and_Parser_Generators 提供了大量這方面的鏈接，下邊討論中所涉及的各類(lèi)生成器的詳細(xì)資料，亦可從該網(wǎng)站查到。 當(dāng)然被用戶(hù)廣泛接受和應(yīng)用的仍然是LEX和YACC一族。, 不同的目標(biāo)語(yǔ)言,生成器所能自動(dòng)生成的識(shí)別器僅能識(shí)別語(yǔ)言的結(jié)構(gòu)，而對(duì)于識(shí)別出的語(yǔ)言結(jié)構(gòu)的語(yǔ)義處理，仍然需要用戶(hù)用某種程序設(shè)計(jì)語(yǔ)言和借助于生成器提供的某些便利來(lái)實(shí)現(xiàn)。因此這類(lèi)生成器的一個(gè)共同特點(diǎn)是： 語(yǔ)義的描述依賴(lài)于一種（或若干種）程序設(shè)計(jì)語(yǔ)言； 生成的目標(biāo)代碼是這種（或這些）程序設(shè)計(jì)語(yǔ)言的源程序模塊。,由于應(yīng)用需求和開(kāi)發(fā)環(huán)境的多樣性，需要生成器支持多種程序設(shè)計(jì)語(yǔ)言。傳統(tǒng)的方法是固定支持一種特定的程序設(shè)計(jì)語(yǔ)言，如C/C+、Pascal(Delphi)、Java、C#、Python等等。另一種方法是生成一個(gè)獨(dú)立的分析表，然后通過(guò)提供不同的分析器引擎(parser engine)來(lái)達(dá)到支持多種語(yǔ)言環(huán)境的目的。 例如GOLD(Grammar Oriented Language Deverloper)就采用這種方法，這種分析表與分析程序分離的形式顯然是一種具有發(fā)展前景的體系結(jié)構(gòu)。, 詞法分析器的功能擴(kuò)展,擴(kuò)展正規(guī)式。從廣義上講，詞法分析器的作用實(shí)質(zhì)上是對(duì)以正文形式表示的輸入序列進(jìn)行識(shí)別。不但可以識(shí)別程序設(shè)計(jì)語(yǔ)言所需要的、較為簡(jiǎn)單的記號(hào)，也應(yīng)該可以處理更為復(fù)雜的各種類(lèi)型的模式匹配。為此有些詞法分析器生成器對(duì)正規(guī)式集進(jìn)行擴(kuò)展，提供了方便、多樣、靈活的匹配模式供用戶(hù)選擇，典型的例子如TLEX中所提供的or與and模式，以及前綴、后綴、子串等多種模式。,另一擴(kuò)展是支持國(guó)際化。隨著互連網(wǎng)的廣泛應(yīng)用，需要詞法分析器識(shí)別不同國(guó)家的文字，因此要求詞法分析器生成器對(duì)字母的處理范圍從原來(lái)的單字節(jié)擴(kuò)大到雙字節(jié)。當(dāng)前絕大多數(shù)的詞法分析器生成器采取了統(tǒng)一的解決方案，即支持unicode。, 不同文法的語(yǔ)法分析器生成器,語(yǔ)法分析器分為兩大類(lèi)：基于LL文法系列的自上而下分析和基于LR文法系列的自下而上分析。兩類(lèi)分析器均可自動(dòng)生成，并且都得到了廣泛的應(yīng)用。 基于LR文法系列的生成器的典型代表就是LEX/YACC類(lèi)，也是應(yīng)用最為普遍的一類(lèi)。包括：Bison、CUP、Yacc+、Bison+、YaYacc、Thinkage YAY、TP Yacc、Elkhound、Rie等等。這些成果大多集中于北美。 基于LL文法系列的生成器有：Coco/R、CppCC、Grammatica、LLgen、PCCTS、PRECC、Spirit、SLK等等。這方面的研究大多集中于歐洲。, 詞法分析與語(yǔ)法分析的耦合程度,松耦合與緊耦合 緊耦合舉例：（一個(gè)簡(jiǎn)化了的Coco/R源程序 ）,COMPILER Demo CHARACTERS letter = “ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrtsuvwxyz“. digit = “0123456789“. EOL = t. TOKENS ident = letter letter | digit. number = digit digit. COMMENTS FROM “/*“ TO “*/“ NESTED IGNORE EOL PRODUCTIONS Demo = Statement “;“ Statement. Statement (. string x; int y; .) = Ident “=“ Number (.CodeGen.Assign(x, y); .). Ident = ident (. x = t.val; .). Number= number (. n = Convert.ToInt32(t.val); .). END Demo.