編譯原理自頂向下的語法分析

編譯原理自頂向下的語法分析第1頁，課件共52頁，創(chuàng)作于2023年2月語法分析器的作用第2頁，課件共52頁，創(chuàng)作于2023年2月以語法分析器為核心的編譯器模型語法分析器詞法分析器中間代碼生成器語義分析器一部分中間代碼輸入字符串程序入口初始化工作第3頁，課件共52頁，創(chuàng)作于2023年2月語法分析器所處的位置第4頁，課件共52頁，創(chuàng)作于2023年2月語法分析的例子第5頁，課件共52頁，創(chuàng)作于2023年2月語法分析的類比針對自然語言的語法分析：識別一個句子是不是符合語法規(guī)范&識別每一個成分的功能。第6頁，課件共52頁，創(chuàng)作于2023年2月語法分析器的作用接收詞法分析器提供的記號串檢查記號串是否能由源程序語言的文法產生用易于理解的方式提示語法錯誤信息，并能從常見的錯誤中恢復過來語法分析器詞法分析器符號表前端的其余部分源程序記號取下一個記號語法樹中間表示第7頁，課件共52頁，創(chuàng)作于2023年2月語法分析器工作原理語言的結構是用上下文無關文法描述的，因此，語法分析器的工作本質上就是按照文法的產生式，識別輸入符號串是否為一個句子。語法分析器是從左向右的掃描輸入字符串，每次讀入一個符號，并判斷，看是否能從文法的開始符號出發(fā)推導出這個輸入串。或者，從概念上講，就是要建立一棵與輸入串匹配的語法分析樹。語法分析器分類通用的語法分析方法，用來分析任何文法，生成編譯器時效率太低編譯器使用的語法分析方法—處理文法的一些子類自頂向下（建立分析樹）—LL文法，其分析器常用手工實現(xiàn)自底向上（建立分析樹）—LR文法，其分析器常利用自動生成工具構造第8頁，課件共52頁，創(chuàng)作于2023年2月自頂向下分析面臨的困難第9頁，課件共52頁，創(chuàng)作于2023年2月自頂向下分析面臨的困難自頂向下分析的主旨是，對任何輸入串，試圖用一切可能的辦法，從文法的開始符號（根結）出發(fā)，自頂向下的為輸入串建立一棵語法樹。這種分析過程本質上是一種試探過程，是反復使用不同產生式謀求匹配輸入串的過程。自頂向下分析的一般方法是帶“回溯”的。第10頁，課件共52頁，創(chuàng)作于2023年2月自頂向下分析方法的特點第11頁，課件共52頁，創(chuàng)作于2023年2月自頂向下分析存在的問題左遞歸文法：有如下文法：令P是文法的任一非終結符，文法中有規(guī)則P→P……或者P=>+P……，這個文法是左遞歸的。自頂向下分析的基本缺點是：不能處理具有左遞歸的文法。？？？？？第12頁，課件共52頁，創(chuàng)作于2023年2月自頂向下分析存在的問題假定文法G[S]，以及輸入串x*y（記為α）。S→xAy A→**|*初始化：第一步擴展Sx*yIPSx*yIPyAx第13頁，課件共52頁，創(chuàng)作于2023年2月自頂向下分析的困難假定文法G[S]，以及輸入串x*y（記為α）。S→xAy A→**|*第二步擴展：回溯x*yIPSx*yIPyAx**SyAx*第14頁，課件共52頁，創(chuàng)作于2023年2月遞歸下降分析程序構造前面的巴科斯范式只用到了兩個元符號“→”和“|”擴充的巴科斯范式加入幾個元語言符號：用花括號{α}表示閉包運算α*。用{α}n0表示α可任意重復0次至n次。{α}00={α}0=ε.用方括號[α]表示{α}10，即表示α的出現(xiàn)可有可無（等價于α|ε）。例如，通常的“實數(shù)”可定義為：

decimal→[sign]integer.{digit}[exponent] exponent→E[sign]integer integer→digit[digit] sign→+|-第15頁，課件共52頁，創(chuàng)作于2023年2月遞歸下降分析程序的構造當文法滿足上述兩個文法條件時，我們就可以為它構造一個不帶回溯的自頂向下分析程序，這個分析程序是由一組遞歸過程組成的。每個過程對應文法的一個非終結符。這樣的一個分析程序稱為遞歸下降分析器。E→E+T|TT→T*F|FF→(E)|iE→T{+T}T→F{*F}F→(E)|i第16頁，課件共52頁，創(chuàng)作于2023年2月遞歸下降分析程序構造E→T{+T}T→F{*F}F→(E)|iPROCEDUREE;BEGIN T; WHILESYM=‘+’DO BEGINADVANCE;TENDENDPROCEDURET;BEGIN F; WHILESYM=‘*’DO BEGINADVANCE;FENDEND第17頁，課件共52頁，創(chuàng)作于2023年2月LL(1)分析法第18頁，課件共52頁，創(chuàng)作于2023年2月消除直接左遞歸——改寫成右遞歸直接左遞歸的消除P→Pα|βP→βP’P’→αP’|εE→E+T|TT→T*F|FF→(E)|iE→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i第19頁，課件共52頁，創(chuàng)作于2023年2月消除左遞歸的一般算法如果一個文法不含回路（形如P=>+P的推導），也不含以ε為右部的產生式，那么執(zhí)行下述算法將保證消除左遞歸（但改寫后的文法可能含有ε為右部的產生式）。第20頁，課件共52頁，創(chuàng)作于2023年2月消除左遞歸的算法第21頁，課件共52頁，創(chuàng)作于2023年2月消除左遞歸的例子R→Sa|aQ→Rb|bS→Qc|cR→Sa|aQ→Sab|ab|bS→Sabc|abc|bc|cS→abcS’|bcS’|cS’S’→abcS’|εR→Sa|aQ→Sab|ab|bS→abcS’|bcS’|cS’S’→abcS’|εS→Qc|cQ→Rb|bR→bcaR’|caR’|aR’R’→bcaR’|ε第22頁，課件共52頁，創(chuàng)作于2023年2月回溯問題第23頁，課件共52頁，創(chuàng)作于2023年2月第24頁，課件共52頁，創(chuàng)作于2023年2月消除回溯、提取左因子令Ｇ是一個不含左遞歸的文法，對G的所有非終結符的每個候選α定義它的終結首符集FIRST(α)為：FIRST(α)={a|α=>*a…,a∈VT}若α=>*ε，則規(guī)定ε∈FIRST(α)FIRST(α)是α的所有可能推導的開頭終結符或可能的ε如果非終結符Ａ的所有候選首符集兩兩不相交，即Ａ的任何兩個不同候選αi和αｊFIRST(αi)∩FIRST(αj)=Φ那么當要求Ａ匹配輸入串時，Ａ就能根據它所面臨的第一個輸入符號ａ，準確的指派某一個候選前去執(zhí)行任務。這個候選就是那個終結首符集含ａ的α。第25頁，課件共52頁，創(chuàng)作于2023年2月消除回溯、提取左因子提取左因子的方法假定Ａ的規(guī)則是： Ａ→δβ1|δβ2|…|δβn|γ1|γ2|…|γm

（其中，每個γ不以δ開頭）那么這些規(guī)則可以改寫為：

A→δA’|γ1|γ2|…|γm A’→β1|β2|…|βn經過反復提取左因子，就能夠把每個非終結符（包括新引進者）的所有候選首符集便成為兩兩不相交。我們?yōu)榇艘冻龅拇鷥r是大量引進新的非終結符和ε產生式。第26頁，課件共52頁，創(chuàng)作于2023年2月消除回溯、提取左因子提取左因子的方法假定Ａ的規(guī)則是： Ａ→δβ1|δβ2|…|δβn|γ1|γ2|…|γm

（其中，每個γ不以δ開頭）那么這些規(guī)則可以改寫為：

A→δA’|γ1|γ2|…|γm A’→β1|β2|…|βn經過反復提取左因子，就能夠把每個非終結符（包括新引進者）的所有候選首符集便成為兩兩不相交。我們?yōu)榇艘冻龅拇鷥r是大量引進新的非終結符和ε產生式。第27頁，課件共52頁，創(chuàng)作于2023年2月LL(1)分析條件E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i對輸入串i+i進行自頂向下分析Ei+iIPTE’i∈FIRST(TE’)Ei+iIPTE’i∈FIRST(FT’)FT’Ei+iIPTE’i∈FIRST(i)FT’i第28頁，課件共52頁，創(chuàng)作于2023年2月LL(1)分析條件E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i對輸入串i+i進行自頂向下分析Ei+iIPTE’+不屬于T’的任一候選式的首符集FT’iεETE’FT’iε+TE’εFT’εi第29頁，課件共52頁，創(chuàng)作于2023年2月LL(1)分析條件如果A的某個候選首符集中包含ε怎么辦？假定S是文法G的開始符號，對于G的任何非終結符A，我們定義FOLLOW(A)={a|S=>*…Aa…，a∈VT}FOLLOW(A)是所有句型中出現(xiàn)在緊接A之后的終結符或“#”。開始符號的FOLLOW集初始化時加入“#”。當非終結符A面臨輸入符號a，且a不屬于A的任意候選首符集但A的某個候選首符集包含ε時，只有當a∈FOLLOW(A)時，才可能允許A自動匹配。第30頁，課件共52頁，創(chuàng)作于2023年2月LL(1)分析條件通過上面的討論，我們可以找出滿足構造不帶回溯的自頂向下分析的文法條件。文法不含左遞歸對于文法中每一個非終結符A的各個產生式的候選首符集兩兩不相交。即，若A→α1|α2|…|αn，則FIRST(αi)∩FIRST(αj)=Φ (i≠j)對文法中的每個非終結符A，若它存在某個候選首符集包含ε，則，F(xiàn)IRST(A)∩FOLLOW(A)=Φ如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。這里LL(1)中的第一個L表示從左到右掃描輸入串，第二個L表示最左推導，1表示分析時每一步只需向前查看一個符號。第31頁，課件共52頁，創(chuàng)作于2023年2月LL(1)分析條件對于一個LL(1)文法，可以對其輸入串進行有效的無回溯的自頂向下分析。假設要用非終結符A進行匹配，面臨的輸入符號為a，A的所有產生式為A→α1|α2|…|αn若a∈FIRST(αi)，則指派αi去執(zhí)行匹配任務。若a不屬于任何一個候選首字符集，則：若ε屬于某個FIRST(αi)，且a∈FOLLOW(A)，則讓A與ε自動匹配；否則，a的出現(xiàn)是一種語法錯誤。根據LL(1)文法的條件，每一步這樣的工作都是確信無疑的第32頁，課件共52頁，創(chuàng)作于2023年2月LL(1)分析法第33頁，課件共52頁，創(chuàng)作于2023年2月預測分析程序工作過程實現(xiàn)LL(1)分析的一種有效方法是使用一張分析表和一個棧進行聯(lián)合控制。下面要介紹的預測分析程序就是屬于這種類型的LL(1)分析器。第34頁，課件共52頁，創(chuàng)作于2023年2月預測分析表預測分析表示一個M[A,a]形式的矩陣。其中A為非終結符，a是終結符或‘#’。矩陣元素M[A,a]中存放著一條關于A的產生式，指出當A面臨輸入符號a時所應采用的候選。M[A,a]中也可能存放一個“出錯標志”，指出A根本不該面臨輸入符號a。i+*()#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)第35頁，課件共52頁，創(chuàng)作于2023年2月預測分析過程概述預測分析程序的總控程序在任何時候都是按STACK棧頂符號X和當前的輸入符號a行事的。如下圖所示，對于任何(X,a)，總控程序每次都執(zhí)行下述三種可能的動作之一：若X=a=‘#’，則宣布分析成功，停止分析過程。若X=a≠‘#’，則把X從STACK棧頂彈出，讓a指向下一個輸入符號。若X是一個非終結符，則查看分析表M。若M[X,a]中存放著關于X的一個產生式，那么，先把X彈出STACK棧頂，然后把產生式的右部符號串按反序一一推進STACK棧（若右部符號為ε，則意味著不推什么東西進棧）。在把產生式的右部符號退進棧的同時應該做這個產生式對應的語義動作（目前暫且不管）。若M[X,a]中存放著“出錯標志”，則調用出錯診斷程序ERROR。第36頁，課件共52頁，創(chuàng)作于2023年2月預測分析過程舉例i+*()#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)i1*i2+i3步驟符號棧輸入串所用產生式0#Ei*i+i#1#E’Ti*i+i#E→TE’2#E’T’Fi*i+i#T→FT’3#E’T’ii*i+i#F→i4#E’T’*i+i#5#E’T’F**i+i#T’→*FT’6#E’T’Fi+i#7#E’T’ii+i#F→i8#E’T’+i#9#E’+i#T’→ε10#E’T++i#E’→+TE’11#E’Ti#12#E’T’Fi#T→FT’13#E’T’ii#F→i14#E’T’#15#E’#T’→ε16##E’→ε第37頁，課件共52頁，創(chuàng)作于2023年2月預測分析表的構造第38頁，課件共52頁，創(chuàng)作于2023年2月FIRST集合和FOLLOW集合的定義第39頁，課件共52頁，創(chuàng)作于2023年2月FIRST集合的構造算法第40頁，課件共52頁，創(chuàng)作于2023年2月分析表的構造第41頁，課件共52頁，創(chuàng)作于2023年2月分析表的構造第42頁，課件共52頁，創(chuàng)作于2023年2月分析表的構造第43頁，課件共52頁，創(chuàng)作于2023年2月FIRST集合構造的例子FIRST(E’)={+,ε}FIRST(T’)={*,ε}FIRST(F)={(,i}FIRST(T)={(,i}FIRST(E)={(,i}E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i第44頁，課件共52頁，創(chuàng)作于2023年2月FOLLOW集合構造的例子FOLLOW(E)={),#}FOLLOW(E’)={),#}FOLLOW(T)={+,),#}FOLLOW(T’)={+,),#}FOLLOW(F)={*,+,),#}E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|iFIRST(E’)={+,ε}FIRST(T’)={*,ε}FIRST(F)={(,i}FIRST(T)={(,i}FIRST(E)={(,i}i+*()#EE→TE’E→TE’E’E’→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)第45頁，課件共52頁，創(chuàng)作于2023年2月LL(1)文法第46頁，課件共52頁，創(chuàng)作于2023年2月LL(1)分析中的錯誤處理第47頁，課件共52頁，創(chuàng)作于2023年2月錯誤的出現(xiàn)及基本做法棧頂?shù)慕K結符與當前的輸入符號不匹配。非終結符A處于棧頂，面臨的輸入符號為a，但分析表M中M[A,a]為空?；镜淖龇ň褪翘^輸入串中的一些符號直至遇到“同步符號”為止。這種做法的效果有賴于同步符號集的選擇。第48頁，課件共52頁，創(chuàng)作于2023年2月同步符號集的選擇把FOLLOW(A)中的所有符號放入非終結符A的同步符號集。如果我們跳讀一些輸入符號直至出現(xiàn)FOLLOW(A)中的同步符號，把A從棧中彈出來，這樣就可能使分析繼續(xù)下去。對于非終結符A來說，只用FOLLOW(A)作為它的同步符號集是不夠的。例如，如果分號作為語句的終結符，那么作為語句開頭的關鍵字就可能不在產生表達式的非終結符的FOLLOW集合中。這樣，在一個賦值語句后少一個分號就可能導致作為下一個語句開頭的關鍵字被跳過如果把FIRST(A)中的符號加入非終結符A的同步符號集，那么當FIRST(A)中的一個符號在輸入中出現(xiàn)時，可以根據A恢復語法分析第49頁，課件共52頁，創(chuàng)作于2023年2月同步符號集的選擇如果一個非終結符產生空串，那么推導ε的產生式可以作為缺省的情況，這樣做可以推遲某些錯誤檢查，但不能導致放棄一個錯誤。這種方法減少在錯誤恢復期間必須考慮的非終結符數(shù)