語法分析

整章開篇

• 語法分析分為兩類即自頂向下和自底向上兩種橡疼。

文法和語言

• 語言：對字母表來說趁怔，^*上的任意一個(gè)子集都成為上的一個(gè)語言序目，記為L(L^*)腥泥。
• 句子：該語言的每一個(gè)字符串成為其的一個(gè)語句或句子碎税。
• 文法：文法表示成四元組 G[S] = (V_T,V_N,S,)
  1. V_T是終結(jié)符集尤慰，是非空有限集，它的每個(gè)元素是終結(jié)符雷蹂。
  2. V_N是非終結(jié)符集伟端，是非空有限集，每個(gè)元素是非終結(jié)符匪煌。并且V_TV_N=
  3. S是文法開始符责蝠，是特殊的非終結(jié)符號(hào)（SV_N）
  4. 是產(chǎn)生式的非空有限集 產(chǎn)生式舉例：
  5. (V_TV_N)⁺且至少有一個(gè)非終結(jié)符，不能是空串萎庭，(V_TV_N)^*
  6. 終結(jié)符不可再分霜医，通常是一個(gè)語言的字母表，代表語法的最小元素驳规，是一種個(gè)體記號(hào)肴敛。非終結(jié)符也稱語法變量，代表一個(gè)一定的語法概念（一個(gè)類，一個(gè)集合）医男。文法開始符號(hào)代表語言的目標(biāo)砸狞，其它語法實(shí)體只是構(gòu)造語言目標(biāo)的隨機(jī)變量。（元語言是描述其它語言的語言昨登，產(chǎn)生式右側(cè)的表達(dá)式是產(chǎn)生式左側(cè)的一個(gè)候選式趾代，它與一樣都是元語言符號(hào)（不屬于的字符））
  7. 寫文法的題型暫時(shí)忽略，考試有現(xiàn)場蒙
• 文法產(chǎn)生的語言：A丰辣，則稱A為直接推導(dǎo)
• 形式語言的分類：
  1. 0型文法與0型語言（對應(yīng)圖靈機(jī)）
  2. 1型文法與1型語言（對應(yīng)線性界限自動(dòng)機(jī)，自然語言）
  3. 2型文法與2型語言（對應(yīng)下推自動(dòng)機(jī)禽捆，程序設(shè)計(jì)語言）
  4. 3型文法與3型語言（對應(yīng)有限自動(dòng)機(jī)）

推導(dǎo)與語法樹

• 最右推導(dǎo)：所給句子推導(dǎo)隊(duì)列中每一步推導(dǎo)都是對句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換笙什，最左推導(dǎo)同理。（實(shí)在替不了先別替）最右推導(dǎo)是規(guī)范推導(dǎo)胚想，它的逆過程是規(guī)范規(guī)約（最左規(guī)約）
• 短語：設(shè)是文法G[S]的一個(gè)句型琐凭，有SA且A，則是關(guān)于該句型的一個(gè)短語浊服。有A則為直接短語或簡單短語统屈。兩個(gè)條件缺一不可，短語屬于該句型的組成部分牙躺，不能破壞句型結(jié)構(gòu)的限制愁憔。
• 句柄：一個(gè)句型的最左直接短語叫句柄
• 素短語：含有終結(jié)符性質(zhì)的短語，如果不存在具有相同性質(zhì)的真子串孽拷，則該短語為素短語吨掌。
• 語法樹：根節(jié)點(diǎn)是文法開始符號(hào)S，內(nèi)部節(jié)點(diǎn)一定是非終結(jié)符脓恕，別到處瞎標(biāo)膜宋，它必為葉節(jié)點(diǎn)且是其父節(jié)點(diǎn)的唯一子節(jié)點(diǎn)。
• 根據(jù)語法樹找短語什么的：
  1. 語法樹某個(gè)節(jié)點(diǎn)+其后代是子樹（只含單層分支也就是兩代節(jié)點(diǎn)的樹叫簡單子樹）
  2. 短語：子樹（所有）末端節(jié)點(diǎn)組成的符號(hào)串是子樹相對于子樹根的短語
  3. 直接短語：簡單炼幔。秋茫。。乃秀。肛著。。环形。策泣。。抬吟。萨咕。。火本。危队。聪建。。茫陆。
  4. 句柄：最左簡單金麸。。簿盅。挥下。。桨醋。棚瘟。。喜最。偎蘸。。瞬内。迷雪。。虫蝶。章咧。。秉扑。
  5. 素短語：子樹的末端節(jié)點(diǎn)組成的符號(hào)串含終結(jié)符慧邮，且在該子樹中不再有包含終結(jié)符的更小子樹。
• 二義性：文法的一個(gè)句子能找到兩種不同的最左推導(dǎo)或最右推導(dǎo)舟陆，就是二義性句子误澳，包含該句子的文法就是二義性文法。（比如乘法優(yōu)先或加法優(yōu)先兩種）秦躯，文法二義性不代表語言二義性忆谓。不改變文法中原有的語法規(guī)則，僅加進(jìn)一些語法的非形式規(guī)定踱承。（可以加一些約束條件倡缠，比如乘法優(yōu)先，并且都左結(jié)合）或構(gòu)造一個(gè)等價(jià)的無二義性文法（比如加非終結(jié)符P43）茎活。

自頂向下的語法分析

• 遞歸向下分析法：
  1. 含左遞歸以及回溯使自頂向下分析存在不確定性昙沦。
  2. 消除左遞歸：
     AA|
     改寫：AA'
     A'A'|

例子：

IMG_20190614_203237.jpg

3. 消除回溯:(有則A'哪里產(chǎn)生空)

IMG_20190614_203807.jpg

• LL1分析法（預(yù)測分析法）：自左向右掃描輸入串，最左推導(dǎo)载荔，只向右查看一個(gè)符號(hào)就可決定如何推導(dǎo)

  1. 分析表的構(gòu)造法：求FIRST和FOLLOW盾饮。方法如下：

     IM.jpg
     
     
     IMG_20190614_205410.jpg
     
     

     其實(shí)很簡單：練一下就會(huì)
     比如例題3.8

     
     
     pra.jpg
     
     之后構(gòu)造分析表
     
     new.jpg
     
     
     IMG20190614212631.jpg

  2. 分析一個(gè)輸入串
     方法是：相同同消，不同規(guī)約之后反向壓入棧（只是符號(hào)棧規(guī)約）
     ，兩#分析成功丘损，符號(hào)棧初始?jí)喝?和起始符號(hào)

     
     
     IMG_20190614_213237.jpg

自底向上語法分析

• 是一種“移進(jìn)—規(guī)約”法普办，一旦棧頂符號(hào)形成某個(gè)句型的句柄就進(jìn)行一次規(guī)約。
• 算符優(yōu)先分析法：
• 算符優(yōu)先文法：
  1. 首先定義一個(gè)任何產(chǎn)生式的右部都不含兩個(gè)相繼（并列）的非終結(jié)符的文法為算符文法徘钥。

  2. 定義任何兩個(gè)可能相繼出現(xiàn)的終結(jié)符a與b（它們之間最多插有一個(gè)非終結(jié)符）的優(yōu)先關(guān)系衔蹲。詳情參考圖片（后面+則G[S]是一個(gè)算符優(yōu)先文法）：
     14.jpg
  3. 算符優(yōu)先分析表的構(gòu)造
     FIRSTVT的構(gòu)造：（搞P）
     如果存在產(chǎn)生式Pa...或PQa...
     若有產(chǎn)生式PQ...，則FIRSTVT(Q)FIRSTVT(P)
     LASTVT的構(gòu)造：（搞P）
     如果存在產(chǎn)生式P...a或P...aQ
     若有產(chǎn)生式P...Q呈础，則LASTVT(Q)LASTVT(P)
     循環(huán)求好幾遍即可
     優(yōu)先關(guān)系表的構(gòu)造：
     15.jpg
     
     例題嘗試：
     
     sf.jpg
     
     分析過程
     
     sffx.jpg
• 優(yōu)先函數(shù)

  1. 關(guān)系圖法構(gòu)造優(yōu)先函數(shù)（Bell方法）

     
     
     關(guān)系圖.jpg

規(guī)范歸約的自底向上語法分析方法

LR分析法是自左向右自底向上規(guī)約
記住歷史：
展望未來：

• LR0分析器
  活前綴：（字的前綴指字的首部，比如字abc前綴有而钞，a，ab笨忌，abc俱病」倨＃活前綴就是規(guī)范巨型的一個(gè)前綴，不含句柄之后任何符號(hào)途凫。
• 圓點(diǎn)在最右端是規(guī)約項(xiàng)目溢吻，文法開始符號(hào)的規(guī)約項(xiàng)目是接受項(xiàng)目维费，不再最右端是待約項(xiàng)目。
• 為了使接受狀態(tài)易于識(shí)別促王，將文法進(jìn)行拓廣犀盟。S'S是唯一的接受態(tài)蝇狼。
• 構(gòu)造LR0分析表的過程：
  1. 拓廣文法
  2. 列出LR0的所有項(xiàng)目。
  3. 構(gòu)造項(xiàng)目集規(guī)范族迅耘。先以起始符號(hào)開寫，之后順勢寫纽哥，一項(xiàng)一項(xiàng)移（會(huì)）栖秕。
  4. 構(gòu)造dfa
  5. 構(gòu)造分析表：首先看I_i的發(fā)出I_k箭頭為終結(jié)符，action表I行終結(jié)符列填S_k，非終結(jié)符則是goto填k够滑，I_i中含規(guī)約項(xiàng)目吕世，將產(chǎn)生式標(biāo)記的序號(hào)r_j全填入action第i行，含接受項(xiàng)目在action子表終結(jié)符“#”列欄填入acc命辖。
  6. 練習(xí)：
  lr0.jpg
• SLR(1)分析
  1. 先找出dfa
  2. 找出規(guī)約項(xiàng)目（包括接受項(xiàng)目）
  3. 求FOLLOW集：如果Aa屬于I_k且由I_k發(fā)出的標(biāo)記為a的有向邊落在I_j上尔艇，置ACTION[k,a]為Sj，若待約項(xiàng)目AB终娃。。余佛。窍荧。。蕊退。（同上），GOTO置為j净蚤，規(guī)約項(xiàng)目屬于I_k則僅當(dāng)aFOLLOW(A)時(shí)茉贡，ACTION[k,a]為ri，ACTION有移進(jìn)規(guī)約沖突項(xiàng)目腔丧，都填，goto無此情況愉粤。
  4. 移進(jìn)的FIRSTb和規(guī)約的F O L L O W（S）交集為空則不產(chǎn)生沖突。（與lr0區(qū)別就是r不都填如蚜，就填follow）
  5. 練習(xí)暫時(shí)忽略（因?yàn)榭赡懿豢迹?/em>