ch7.1-7.3lr-slr語法分析(張素琴)

分析概述()分析()分析()分析語法分析器的自動構造工具第章分析法分析概述分析器的邏輯結構及工作過程()分析技術是指從左至右掃描輸入符號串是指構造一個最右推導的逆過程，是指為了作出分析決定而向前看的輸入符號的個數。分析方法是當前最廣義的無回溯的“移進歸約”方法。()分析技術于年首先提出來的。根據棧中的符號串和向右順序查看輸入串中的()個符號，就能唯一確定分析器的動作是移進還是歸約，以及用哪個產生式進行歸約。優點：限制少，適用范圍廣；分析速度快；報錯準確。缺點：構造分析器的工作量很大，不大可能手工構造用軟件工具輸入上下文無關文法的，輸出分析器。一、分析器邏輯結構輸入、輸出、棧、驅動程序和分析表組成驅動程序動作轉移輸出棧狀態文法符號產生式表ＬＲ分析特征:規范的符號棧中的符號是規范句型的前綴分析決策依據―棧頂狀態和現行輸入符號識別規范句型特定前綴(就到句柄為止)的四種技術()()()()不同的語法分析器具有不同的分析表驅動程序都是一樣的()分析器()分析表()分析器()分析表()分析器()分析表()分析器()分析表分析表是分析法的核心，它包含兩部分：動作表（）和狀態轉換表（）動作表動作規定如下：移進和=[]進棧[]=歸約:=[]接受成功，規約到識別符號出錯二、分析器的工作過程主控程序根據輸入串、棧、產生式、分析表進行相應的移近、規約、接受或報錯操作。主控程序動作轉移輸出棧狀態文法符號產生式表()分析→→→→對于產生式→對應的句柄其狀態劃分為：句柄識別態一、分析的基本原理把每個句柄的識別過程劃分為若干個狀態每個狀態下，自左向右地識別了句柄的一部分符號?；钋熬Y定義:規范推導，的所有前綴稱為活前綴。即規范句型的前綴，但右端不超過該句型句柄末端。識別了句柄的一部分就相當于識別了當前規范句型的左起部分，這部分被識別的符號串稱之為規范句型的活前綴。對于文法[]→:→→→:是該文法的一個句子=:=:=:=::其活前綴是:ε::::→:→→→的定義：=（Σδ)其中：狀態集Σ—輸入字母表δ–Σ→的映射函數分析器使用有窮自動機識別各規范句型的活前綴()項目：()項目:用圓點“”表示識別一個產生式右部符號到達的位置，若有規則則有下面四個項目：→→→→移進項目待歸約項目歸約項目’開始項目項目→和→稱為后繼項目’接受項目拓廣文法定義：為了使文法的“接受”狀態易于識別，且唯一，常對文法進行拓廣改造。對于文法，我們構造一個’，引進一個不出現在中的非終結符’和一個產生式’→，’為’的開始符號’不出現在規則右部。對于文法[]→|→|→|文法’[’]’→→|→|→|拓廣文法’→’→→→→→→→→→→→→→對于上述文法’所有()項目如下：→→→→文法’[’]’→→|→|→|歸約項目：、、、、、接收項目：移進項目：、、、、、待約項目：、、、初始項目：每個項目作為的一個狀態。由于’僅在第一個產生式的左部出現，規定項目為初態，其余每個狀態都為活前綴的狀態圓點在最后的項目為句柄識別態，第一個產生式的句柄識別態為句子識別態，用標記。狀態之間的轉換關系確定方法如下：若第個項目為：第個項目為：和項目出自同一個產生式，圓點位置只落后一位，則從狀態到狀態連接一條標記為的有向弧。如果為非終結符，則還會有以為射出到該非終結符為左部的所有產生式圓點在最左部的狀態的弧，弧上標記為二識別活前綴項目集規范的構造’→’→→→→→→→→→→→→→→→→→由項目生成識別活前綴的：文法’[’]’→→|→|→|求出識別活前綴的方法：()由轉換為，第四章子集法；()直接求狀態集：設是文法的一個()項目集合()是從出發用下面三個規則構造的項目集:()中每一個項目都屬于()。()若項目→αβ()且→η則將→η加進()中。()重復執行()直到()不再增大為止。轉移函數：若是的一個()項目集()=()其中=→αβ|當→αβ時()稱為轉移函數。項目→αβ稱為→αβ的后繼項目。:→αβ:→αβ算法計算()和()(:):→αβ→η:=∪→η不再增大()→αβ是項目集的核心項目(:∈∪):::=→αβ:=∪→αβ(())是的后繼項目的閉包()項目集規范的構造():=(→)和∪把()加入到中不在增大=(，，，，）其中：項目集規范，∪=→=()它識別文法的所有活前綴。例題：文法（）()()()()()()’→’→→→→→→→→→→→→→()項目如下：→→→→文法’[’]’→→|→|→|::::::()項目集規范：::::::’→→|→|→|()識別活前綴的三()分析表的構造假設一個識別文法活前綴的中的每個狀態不存在下述情況：、既含移進項目又含歸約項目、或者含有多個歸約項目則稱文法是()文法假設包含項目’→的狀態為分析器初態表和表構造如下：、若項目→∈且(，)=①=∈則置[]=意為把()移進棧②∈則置()=、若項目→∈對于所有∈則置[]=意為用第個產生式→進行歸約、若’→∈則置[]=、凡不能用以上規則填入的入口置“”()識別活前綴的:::::::⑶()分析表如下：文法’[’]’→→→→→→→四()分析過程主控程序根據輸入串、棧、產生式、分析表進行相應的移近、規約、接受或報錯操作。$主控程序動作轉移輸出棧狀態文法符號產生式表若[]=(:)=[]；是規則號，規則右部長度則，)若[]=則分析結束。若[]=則轉出錯處理程序。若[]=則把推進棧三個棧的格局()⑶()分析表如下：文法’[’]()’→()→()→()→()→()→()→步驟狀態棧符號棧輸入串說明是文法[]的句子對輸入串的()分析過程表文法[]為:)構造識別活前綴的)構造它的()分析表)分別給出對輸入符號串和的()分析步驟。課堂練習[]拓廣為:()’()()()():’:’::::::::()分析表步驟狀態棧符號棧輸入符號串說明是文法[]的句子對輸入串的分析過程()’()()()()步驟狀態棧符號棧輸入串出錯說明不是文法[]的句子對輸入串的分析過程[]拓廣為:()’()()()()()分析有的文法，識別活前綴的狀態集中，含有沖突項目。例如：文法[’]’→→→→→→→→ε→ε文法的有效項目集：：’→：’→：→→：→→：→:→→→ε：→：→：→:→:→:→:→:→→→→→→→ε→→ε→→ε識別文法活前綴的：：→→→→ε：→→→→ε:→→→ε：→→→ε這就是移進—歸約沖突歸約歸約沖突→ε和→ε是一個項目倒底該歸約誰呢？規約→還是→ε此時構造的()分析表在(，)入口處也會有多項、、。文法的()分析表如下：文法[’]’→→→→→→→→ε→ε對于而言，若當前輸入符=，則應該執行；若()則應用→歸約；若()則應用→ε歸約。()=()=()=解決方法：向前搜索一個輸入符號：→→→→ε前提：、()和()兩兩不相交一般而言：假設文法的某個項目同時含有個移進項目→αβ→αβ→αβ個歸約項目:→γ→γ→γ若與()()()兩兩不相交，則項目集中的沖突可按如下原則解決：面對當前讀入符號為若則移進。若()則用→γ進行歸約。此外，報錯。這種解決方法是比較簡單的，因此稱作()分析，由此構造的分析表，稱作分析表。識別文法活前綴的：()=()=()=表和表構造如下：、若項目→∈且(，)=①=∈則置[]=意為把()移進棧②∈則置()=、若項目→∈對于∈()則[]=意為用第個產生式→進行歸約、若’→∈則置[]=、凡不能用以上規則填入的入口置“”文法的()分析表如下：()()()()()()()()()例構造如下文法的()分析表集如下：()()(()()(()()(()()()