kN_編譯原理_2

大學(xué)期間的筆記補(bǔ)全卒蘸。編譯原理內(nèi)容太多分幾次雌隅。
課本《編譯原理》第三版，陳火旺等編著悬秉。
筆記總目錄：
一澄步、引論
二、高級(jí)語(yǔ)言及其語(yǔ)法描述
三和泌、詞法分析
四村缸、語(yǔ)法分析——自上而下分析
五、語(yǔ)法分析——自下而上分析
六武氓、屬性文法和語(yǔ)法制導(dǎo)翻譯
七梯皿、語(yǔ)義分析和中間代碼生成
八、優(yōu)化
九县恕、目標(biāo)代碼生成

四东羹、語(yǔ)法分析——自上而下分析

不是正規(guī)文法是畫不出來有限自動(dòng)機(jī)的。語(yǔ)法一般都不是正規(guī)文法（是上下文無關(guān)文法）忠烛。

4.1 語(yǔ)法分析器的功能

語(yǔ)法分析的任務(wù)：對(duì)任一給定 $w ∈ V_T^*$ 属提，判斷 $w ∈ L(G)$ ?
語(yǔ)法分析器：按照產(chǎn)生式規(guī)則，做識(shí)別 $w$ 的工作美尸。
語(yǔ)法分析方法：
- 自上(頂)而下分析：從文法的開始符號(hào)出發(fā)冤议，反復(fù)使用各種產(chǎn)生式，尋找與輸入符號(hào)匹配的最左推導(dǎo)师坎。
  
  難點(diǎn)：一個(gè)終結(jié)符可能有多個(gè)候選式恕酸。
  
  exp: 若終結(jié)符 $b$ 可以由非終結(jié)符 $B,C,D$ 均能推導(dǎo)，則符號(hào) $b$ 的推導(dǎo)只能逐一實(shí)驗(yàn)胯陋，失敗需要回頭重新回溯推導(dǎo)蕊温。
- 自下(底)而上分析：從輸入符號(hào)串開始，逐步進(jìn)行歸約(最右推導(dǎo)的逆過程)遏乔，直至歸約到文法的開始符號(hào)义矛。

4.2 自上而下分析的方法概述

從文法的開始符號(hào)出發(fā)，向下推導(dǎo)盟萨，推出句子凉翻。
對(duì)任何的輸入串(單詞符號(hào))，試圖用一切可能的辦法, 從文法的開始符號(hào)出發(fā)鸯旁，自上而下地為輸入串建立一棵語(yǔ)法樹噪矛，即為輸入串尋找一個(gè)最左推導(dǎo)。
帶回溯自上而下出現(xiàn)的問題：
- 文法的左遞歸問題
  - 一個(gè)文法是含有左遞歸的铺罢，如果存在非終結(jié)符 $P$ ： $P ?^+Pα$
  - 含有左遞歸的文法將使自上而下的分析過程陷入無限循環(huán)艇挨。
- 虛假匹配問題
- 回溯：回溯會(huì)引起時(shí)間和空間的大量消耗
- 報(bào)告分析不成功時(shí)，難于知道輸入串中出錯(cuò)的確切位置韭赘。
實(shí)際上采用了一種窮盡一切可能的試探法缩滨，因此效率很低，代價(jià)很高泉瞻。

4.3 LL（1）分析方法

概念：從左(Left)到右掃描輸入串脉漏，構(gòu)造最左(Leftmost) 推導(dǎo)，分析時(shí)每步向前看一個(gè)(1)字符袖牙。
目的：構(gòu)造不帶回溯的自上而下分析算法侧巨。
- 左遞歸的消除
- 消除回溯，提左因子
- FIRST集合鞭达，F(xiàn)OLLOW集合
- LL(1)分析條件
- LL(1)分析方法
消除左遞歸：
左遞歸文法：

一個(gè)文法含有下列形式的產(chǎn)生式時(shí)司忱，
- 直接遞歸
  - $A→A\beta,\ \ \ \ A∈V_N, \beta ∈V^*$
- 間接遞歸
  - $A→B\beta,B→A\alpha\ \ \ \ \ \ \ \ \ A,B∈V_N,\ \ \alpha,\beta ∈V^*$
稱為左遞歸文法。

如果一個(gè)文法是左遞歸時(shí)畴蹭，則不能采用自頂向下分析法坦仍。
- 直接左遞歸消除：
  
  直接左遞歸消除
- 間接左遞歸消除算法：
  
  間接左遞歸消除算法
回溯問題
- 回溯原因
  
  若當(dāng)前符號(hào) $= a$ ，下一步要展開 $A$ 叨襟，而 $A → α_1|α_2|...|α_n$ 繁扎，怎樣選擇 $α_i$ ?
  
  (1)以 $a$ 為頭的 $α_i$ 如果只有一個(gè)，則替換唯一;
  
  (2)若以 $a$ 為頭有多個(gè) $α_i$ 的糊闽，則替換不唯一梳玫，需要回溯，這是文法的問題墓怀，應(yīng)該變換文法汽纠。
- 文法的要求
  1. 不含左遞歸
  2. 對(duì)每個(gè)終結(jié)符的候選式，其任何推導(dǎo)的頭符號(hào)（終結(jié)符）集合兩兩不相交
  3. 若 $A$ 的候選首符集中包含 $ε$ 傀履，則 $FIRST (A)∩ FOLLOW (A) = Φ$
- 回溯解決方法：提公因子法
  
  提取公共左因子虱朵，將文法改造成任何非終結(jié)符的所有候選首符集兩兩不相交。
  目的：消除歧義钓账！不能由不同的推導(dǎo)路徑得出同一個(gè)首符
  
  提公因子法
FIRST問題
- 符號(hào)串 $α$ 的終結(jié)首符集 $FIRST(α)$ 定義為：
  
  $FIRST(α) = \lbrace a│ \alpha ?^* a… , a∈V_T \rbrace$
  
  特別地碴犬，若 $α ?^* ε$ ，則規(guī)定 $ε∈FIRST(α)$ 梆暮。
- 計(jì)算 $FIRST(X)$ 集：
  - 若 $X∈V_T$ , $FIRST(X)=\lbrace X\rbrace$
  - 若 $X∈V_N$ , $FIRST(X)=\lbrace a|X→a…,a∈V_T\rbrace$
  - 若 $X∈V_N$ , 且有產(chǎn)生式 $X →ε$ 服协，則 $\lbrace ε\rbrace ∈ FIRST(X)$
  - 若, 且有產(chǎn)生式，且
    - 當(dāng) $Y1 啦粹，Y2 偿荷， … 窘游， Y_{i-1} ? ε$ ，則 $FIRST(Y_1)-\lbrace ε\rbrace$ , $FIRST(Y_2)-\lbrace ε\rbrace$ … $FIRST(Y_{i-1})-\lbrace ε\rbrace$ , $FIRST(Y_i)$ 都包含在 $FIRST(X)$ 中
    - 當(dāng) $Y_i ? ε(i=1,2…n)$ ,將 $\lbrace ε\rbrace$ 并入 $FIRST(X)$ 中
FOLLOW問題
- 設(shè) $S$ 是文法 $G$ 的開始符號(hào)跳纳，對(duì) $G$ 的任何非終結(jié)符 $A$ 忍饰，定義 $A$ 的后繼終結(jié)符號(hào)集為：
  
  $FOLLOW(A) ＝ \lbrace a│S ?^* … Aa… , a∈V_T \rbrace$
- 特別地,若 $S ?^*…A$ ，則規(guī)定 $Ｋ伦∈FOLLOW(A)$ 艾蓝。
  
  $FOLLOW(A)$ 是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或“ $＃$ ”《诽粒“ $＃$ ”可認(rèn)為是一個(gè)句子的終止符赢织。
當(dāng)非終結(jié)符 $A$ 面臨輸入符號(hào) $a$ ，且 $a \notin FIRST(α_i)$ (對(duì)任意 $i$ )時(shí)馍盟，如果 $A$ 的某個(gè)候選首符集包含 $ε$ （即 $ε∈FIRST(A)$ ）于置，那么，當(dāng) $a∈FOLLOW(A)$ 時(shí)朽合，就允許 $A$ 自動(dòng)匹配（即選用 $A→ε$ 工作）俱两，否則，認(rèn)為 $a$ 的出現(xiàn)是一種語(yǔ)法錯(cuò)誤曹步。
LL(1)分析方法
- LL(1)文法：
  
  如果文法G滿足以下條件：
  
  （1）文法消除了左遞歸宪彩；
  
  （2）文法中每個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交，即：若 $A→α_1│α_2│… │α_n$ 讲婚，則 $FIRST(α_i)∩FIRST(α_j) = Φ尿孔，（i ≠ j）$ ；
  
  （3）對(duì)文法中的每個(gè)非終結(jié)符 $A$ 筹麸，若它存在某個(gè)候選首符集中包含 $ε$ 活合，則 $FIRST(A)∩ FOLLOW(A) = Φ$ ；
  
  則稱該文法 $G$ 為 $LL(1)$ 文法物赶。
- 對(duì)一個(gè) $LL (1)$ 文法白指，可以對(duì)某個(gè)輸入串進(jìn)行有效的無回溯的自上而下分析。
- 設(shè)面臨的輸入符號(hào)為 $a$ 酵紫，要用非終結(jié)符 $A$ 進(jìn)行匹配告嘲，且 $A→α_1│α_2│… │α_n$ ，則可如下分析:
  1. 若 $a∈FIRST (α_i)$ 奖地，則指派 $α_i$ 執(zhí)行匹配任務(wù)橄唬；
  2. 否則
    - 若 $ε∈FIRST(A)$ ，且 $a∈FOLLOW (A)$ 参歹，則讓 $A$ 與 $ε$ 自動(dòng)匹配仰楚；
    - 否則， $a$ 的出現(xiàn)是一種語(yǔ)法錯(cuò)誤。

4.4 分析方法：遞歸下降分析程序

條件：滿足上述 $LL(1)$ 文法的條件
構(gòu)成
- 一組遞歸過程
- 每個(gè)遞歸過程對(duì)應(yīng) $G$ 的一個(gè)非終結(jié)符
基本思想

從文法開始符號(hào)出發(fā)僧界，在語(yǔ)法規(guī)則(文法產(chǎn)生式)的支配下進(jìn)行語(yǔ)法分析侨嘀。逐個(gè)掃描源程序中的字符(單詞符號(hào))，根據(jù)文法和當(dāng)前輸入字符分析到下一個(gè)語(yǔ)法成分 $A$ 時(shí)捂襟，便調(diào)用識(shí)別和分析A的子程序(或其自身)飒炎，如此繼續(xù)下去。
程序形式

程序形式_1

程序形式_2

4.5 分析方法：預(yù)測(cè)分析程序

遞歸下降分析器的局限性：需要具有能夠?qū)崿F(xiàn)遞歸過程的語(yǔ)言和編譯系統(tǒng)
預(yù)測(cè)分析程序：使用一個(gè)分析表和符號(hào)棧進(jìn)行聯(lián)合控制笆豁，是實(shí)現(xiàn) $LL(1)$ 分析的另一種有效方法。
程序流程：

預(yù)測(cè)分析程序流程

LL(1)分析表M赤赊，行為非終結(jié)符闯狱，列為終結(jié)符，每一個(gè)M[A,a]表示非終結(jié)符A應(yīng)該用什么產(chǎn)生式得出以a打頭的表達(dá)式（若M[A,a]為空表示無法產(chǎn)生抛计，報(bào)錯(cuò)）哄孤。

LL(1)分析表構(gòu)造算法

五、語(yǔ)法分析——自下而上分析

自下而上分析法就是從輸入串開始吹截，逐步進(jìn)行“歸約”瘦陈，直至歸約到文法的開始符號(hào)。

從語(yǔ)法樹的末端波俄，步步向上“歸約”晨逝，直到根結(jié)。

5.1 自下而上分析基本問題

歸約
- 移進(jìn)-歸約法：使用一個(gè)符號(hào)棧懦铺，把輸入符號(hào)逐一移進(jìn)棧捉貌，當(dāng)棧頂形成某個(gè)產(chǎn)生式右部時(shí)，則將棧頂?shù)倪@一部分替換（歸約）為該產(chǎn)生式的左部符號(hào)冬念。
基本問題：
- 如何找出或確定可規(guī)約串趁窃？
- 對(duì)找出的可規(guī)約串替換為哪一個(gè)非終結(jié)符號(hào)？

5.2 規(guī)范規(guī)約

短語(yǔ)
- 令 $G$ 是一個(gè)文法急前， $S$ 是文法的開始符號(hào)醒陆，若 $αβδ$ 是文法 $G$ 的一個(gè)句型，如果有：
  
  $S ?^* αAδ$ 且 $A ?^+ β$
  
  則稱 $β$ 是句型 $αβδ$ 相對(duì)于非終結(jié)符 $A$ 的短語(yǔ)裆针。（多步規(guī)約）
  
  特別地刨摩，若 $A ? β$ ，則稱 $β$ 是句型 $αβδ$ 關(guān)于產(chǎn)生式 $A→β$ 的直接短語(yǔ)据块。（一步規(guī)約）
- 一個(gè)句型的最左直接短語(yǔ)稱為句柄码邻。
  
  二義文法的句柄不止一個(gè)。
從樹的角度考慮：

短語(yǔ)：句型語(yǔ)法樹中每棵子樹（某個(gè)結(jié)點(diǎn)連同它的所有子孫組成的樹）的所有葉子結(jié)點(diǎn)從左到右排列起來形成一個(gè)相對(duì)于子樹根的短語(yǔ)另假。

直接短語(yǔ)：只有父子兩代的子樹形成的短語(yǔ)像屋。

句柄：語(yǔ)法樹中最左那棵只有父子兩代的子樹形成的短語(yǔ)。

概念舉例
規(guī)范規(guī)約

設(shè) $α$ 是文法 $G$ 的一個(gè)句子边篮，若序列 $α_n, α_{n-1}, …, α_0$ 己莺，滿足：

（1） $α_n = α$ 奏甫；
（2） $α_0 = S$ ；
（3）對(duì)任意 $i$ 凌受， $0< i ≤n$ , $α_{i-1}$ 是從 $α_i$ 將句柄替換成相應(yīng)產(chǎn)生左部符號(hào)而得到的

則稱該序列是一個(gè)規(guī)范歸約阵子。
符號(hào)棧的使用：

實(shí)現(xiàn)移進(jìn)-歸約分析的一個(gè)方便途徑是用一個(gè)棧和一個(gè)輸入緩沖區(qū)，用#表示棧底和輸入的結(jié)束胜蛉。

符號(hào)棧
語(yǔ)法分析的操作
- 移進(jìn)：下一輸入符號(hào)移進(jìn)棧頂挠进，讀頭后移；
- 歸約：檢查棧頂若干個(gè)符號(hào)能否進(jìn)行歸約誊册，若能领突，就以產(chǎn)生式左部替代該符號(hào)串，同時(shí)輸出產(chǎn)生式編號(hào)案怯；
- 接收：移進(jìn)－歸約的結(jié)局是棧內(nèi)只剩下棧底符號(hào)和文法開始符號(hào)君旦，讀頭也指向語(yǔ)句的結(jié)束符；
- 出錯(cuò)：發(fā)現(xiàn)了一個(gè)語(yǔ)法錯(cuò)誤嘲碱，調(diào)用出錯(cuò)處理程序金砍。

5.3 算符優(yōu)先分析方法

算符優(yōu)先分析法是自下而上進(jìn)行句型歸約的一種分析方法。

定義終結(jié)符（即: 算符）的優(yōu)先關(guān)系，按終結(jié)符（算符）的優(yōu)先關(guān)系控制自下而上語(yǔ)法分析過程（尋找“可歸約串”和進(jìn)行歸約）。

不是規(guī)范歸約搞乏，但分析速度快，適于表達(dá)式的語(yǔ)法分析谱俭。

算符文法

一個(gè)文法，如果它的任一產(chǎn)生式右部都不含兩個(gè)相繼（并列）的非終結(jié)符宵蛀，即不含如下形式的產(chǎn)生式右部：

$… QR … , Q, R ∈ V_N$

則稱該文法為算符文法昆著。
算符優(yōu)先關(guān)系
- 優(yōu)先運(yùn)算符
  
  任何兩個(gè)可能相繼出現(xiàn)的終結(jié)符 $a$ 和 $b$ （它們之間可能插有一個(gè)非終結(jié)符）的優(yōu)先關(guān)系：
  - $a < b$ $a$ 的優(yōu)先級(jí)低于 $b$
  - $a = b$ $a$ 的優(yōu)先級(jí)等于 $b$
  - $a > b$ $a$ 的優(yōu)先級(jí)高于 $b$
  注：這三種關(guān)系不同于數(shù)學(xué)中的 $<,=,>$ 關(guān)系。在以上場(chǎng)景中表示有產(chǎn)生式 $...ab...$ 或 $… aQb…$
- 算符優(yōu)先關(guān)系
  
  設(shè) $G$ 為算符文法且不含 $ε-$ 產(chǎn)生式术陶， $a, b∈ V_T$ , 算符間的優(yōu)先關(guān)系定義為：
  - $a=b$ 當(dāng)且僅當(dāng) $G$ 含有產(chǎn)生式 $P →… ab…$ 或 $P →… aQb…$
  - $a < b$ 當(dāng)且僅當(dāng) $G$ 含有產(chǎn)生式 $P →… aR …$ 且 $R ? b…$ 或 $R ? Qb…$
  - $a > b$ 當(dāng)且僅當(dāng) $G$ 含有產(chǎn)生式 $P →… Rb…$ 且 $R ? … a$ 或 $R ? … aQ$
  生成樹中凑懂，節(jié)點(diǎn)越深（層數(shù)越大，越偏向葉節(jié)點(diǎn)）梧宫，算符的優(yōu)先級(jí)越大接谨。
算符優(yōu)先文法

如果一個(gè)算符文法 $G$ 中的任何終結(jié)符對(duì) $(a, b)$ 至多滿足下述關(guān)系之一：

$a=b$ ， $a < b$ 塘匣， $a > b$

則稱 $G$ 為算符優(yōu)先文法脓豪。
優(yōu)先關(guān)系表的構(gòu)造
- FIRSTVT(P)和LASTVT(P)
  
  設(shè) $P∈V_N$ ，定義：
  
  $FIRSTVT (P) = \lbrace a│P?a …$ 或 $P?Qa … , a ∈V_T , Q ∈V_N \rbrace$
  
  $LASTVT (P) =\lbrace a│P?… a$ 或 $P ?… aQ , a ∈V_T , Q∈V_N \rbrace$
- 構(gòu)造
  - FIRSTVT (P) 構(gòu)造
    
    規(guī)則1: 若 $P→a …$ 或 $P→Qa …$ , 則 $a ∈FIRSTVT(P)$ ;
    
    規(guī)則2: 若 $a ∈FIRSTVT(Q)$ , 且 $P→Q …$ , 則 $a ∈FIRSTVT(P)$ 忌卤。
  - LASTVT (P) 構(gòu)造
    
    規(guī)則1: 若 $P→ … a$ 或 $P→ … aQ$ , 則 $a ∈LASTVT(P)$ ;
    
    規(guī)則2: 若 $a ∈LASTVT(Q)$ , 且 $P→ … Q$ , 則 $a ∈LASTVT(P)$ 扫夜。
    
    布爾矩陣與符號(hào)棧
算符優(yōu)先分析算法
- 將輸入串依此逐個(gè)存入符號(hào)棧 $S$ 中，直到符號(hào)棧頂元素 $S_k$ 與下一個(gè)待輸入的符號(hào) $a$ 有優(yōu)先關(guān)系 $S_k>a$ 為止；
- 至此笤闯，最左素短語(yǔ)尾符號(hào) $S_k$ 已在符號(hào)棧 $S$ 的棧頂堕阔，由此往前在棧中找最左素短語(yǔ)的頭符號(hào) $S_{j+1}$ ，直到找到第一個(gè) < 為止颗味；
- 已找到最左素短語(yǔ) $S_{j+1}…S_k$ 超陆，將其歸約為某個(gè)非終結(jié)符 $N$ 及做相應(yīng)的語(yǔ)義處理。
  最左素短語(yǔ)：在最左側(cè)的浦马，不包含更小短語(yǔ)的短語(yǔ)时呀。在算符優(yōu)先分析方法中，最左素短語(yǔ)一定要包含算符晶默。
  
  素短語(yǔ)的概念：它是個(gè)短語(yǔ)退唠，并且至少含有一個(gè)終結(jié)符，并且荤胁，除它自身之外不再含任何更小的素短語(yǔ)，所謂最左素短語(yǔ)就是處于句型最左邊的素短語(yǔ)屎债。
  
  分析過程
  - 在算法的工作過程中仅政，若出現(xiàn) $j$ 減1后的值小于等于0時(shí)，則意味著輸入串有錯(cuò)盆驹。在正確的情況下圆丹，算法工作完畢時(shí)，符號(hào)棧 $S$ 應(yīng)呈現(xiàn)：# N #躯喇。
  - 由于非終結(jié)符對(duì)歸約沒有影響辫封，因此，非終結(jié)符根本可以不進(jìn)符號(hào)棧 $S$ 廉丽。
  概念辨析：
  
  最左素短語(yǔ)：只關(guān)注算符（終結(jié)符）倦微，所有的非終結(jié)符都記為N，終結(jié)符規(guī)約為非終結(jié)符時(shí)也一律規(guī)約為N正压。最左素短語(yǔ)一定會(huì)出現(xiàn)在產(chǎn)生式右側(cè)欣福，但是會(huì)忽略所有非終結(jié)符的符號(hào)，一律視為N焦履。
  
  句柄（最左直接短語(yǔ)）：
  
  直接短語(yǔ)：只有父子兩代的子樹形成的短語(yǔ)拓劝。
  
  算符分析法中規(guī)約的目標(biāo)是：尋找最左素短語(yǔ)，逐步規(guī)約

5.4 LR分析法

LR分析表舉例

表達(dá)式

LR分析表

根據(jù)LR分析表的分析過程需要兩個(gè)棧嘉裤，一個(gè)狀態(tài)棧存狀態(tài)郑临，一個(gè)數(shù)據(jù)棧存算符和非終結(jié)符。
- s5: 指shift 5屑宠，將指針?biāo)傅姆?hào)壓入數(shù)據(jù)棧厢洞，將5壓入狀態(tài)棧。
- r6: 指reduce 6，將當(dāng)前數(shù)據(jù)棧中的符號(hào)按照第6個(gè)產(chǎn)生式規(guī)約（此例中為F->i）犀变。經(jīng)過規(guī)約操作之后妹孙，需要將數(shù)據(jù)棧棧頂彈出，將數(shù)據(jù)棧棧頂?shù)?strong>規(guī)約結(jié)果壓棧获枝，同時(shí)將狀態(tài)棧棧頂狀態(tài)彈出蠢正。
- 1: 指狀態(tài)遷移1，如狀態(tài)棧棧頂為舊狀態(tài)（比如(0,E)=1省店，舊狀態(tài)為0）嚣崭，將舊狀態(tài)彈出，壓入新狀態(tài)為棧頂懦傍。
分析流程雹舀，狀態(tài)棧壓0，數(shù)據(jù)棧壓#粗俱。將指針指向的第一個(gè)符號(hào)壓入數(shù)據(jù)棧说榆，根據(jù)狀態(tài)棧棧頂（0）跟數(shù)據(jù)棧棧頂找出對(duì)應(yīng)分析表中的內(nèi)容并執(zhí)行相應(yīng)操作，循環(huán)判斷直到對(duì)應(yīng)表中內(nèi)容為acc（成功）或空（失敶缛稀）签财。

分析過程
LR分析法
- 在自下而上的語(yǔ)法分析中，算符優(yōu)先分析算法只適用于算符優(yōu)先文法偏塞，還有很大一類上下文無關(guān)文法可以用LR分析法分析唱蒸。
- LR分析法中的L表示從左向右掃描輸入串， R表示構(gòu)造最右推導(dǎo)的逆灸叼。LR分析法是嚴(yán)格的規(guī)范規(guī)約神汹。
- 不足：LR分析法手工構(gòu)造分析程序工作量相當(dāng)大。
- 總控程序: 所有的LR分析器相同
- 分析表: 是自動(dòng)生成語(yǔ)法分析器的關(guān)鍵
  - LR (0) 表：基礎(chǔ)古今、有局限性
  - SLR表：簡(jiǎn)單LR表屁魏，實(shí)用
  - 規(guī)范LR表：能力強(qiáng)、代價(jià)大
  - LALR表：向前LR表捉腥，介于SLR和規(guī)范LR之間
- 分析表的內(nèi)容：LR分析器的核心是一張分析表
  - ACTION[s, a]：當(dāng)狀態(tài)s面臨輸入符號(hào)a時(shí)蚁堤，應(yīng)采取什么動(dòng)作.
    
    每一項(xiàng)ACTION[s, a]所規(guī)定的四種動(dòng)作:
    
    \1. 移進(jìn) 把(s, a)的下一狀態(tài) 和輸入符號(hào) 推進(jìn)棧，下一輸入符號(hào)變成現(xiàn)行輸入符號(hào).
    
    \2. 歸約指用某產(chǎn)生式進(jìn)行歸約. 假若的長(zhǎng)度為但狭，歸約動(dòng)作是：去除棧頂個(gè)項(xiàng)披诗，使?fàn)顟B(tài) 變成棧頂狀態(tài)，然后把的下一狀態(tài) 和文法符號(hào) 推進(jìn)棧.
    
    \3. 接受宣布分析成功立磁，停止分析器工作.
    
    \4. 報(bào)錯(cuò)
  - GOTO[s, X]：狀態(tài)s面對(duì)文法符號(hào)X時(shí)呈队，下一狀態(tài)是什么
  GOTO[s, X]定義了一個(gè)以文法符號(hào)為字母表的DFA
LR文法
- 對(duì)于一個(gè)文法，如果能夠構(gòu)造一張LR分析表, 使得它的每個(gè)入口均是唯一確定唱歧，則該文法稱為L(zhǎng)R文法宪摧。
  - 在進(jìn)行自下而上分析時(shí)粒竖，一旦棧頂形成句柄，即可歸約几于。
- LR(k)文法：對(duì)于一個(gè)文法蕊苗，如果每步至多向前檢查 k個(gè)輸入符號(hào)，就能用LR分析器進(jìn)行分析沿彭。則這個(gè)文法就稱為L(zhǎng)R(k)文法朽砰。
  - 大多數(shù)程序語(yǔ)言，符合LR(1)文法
LR(0) 文法
- k ＝0喉刘，即只要根據(jù)當(dāng)前符號(hào)和歷史信息進(jìn)行分析瞧柔，而無需展望。
- 假若一個(gè)文法G的拓廣文法G￠的活前綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)（項(xiàng)目集）不存在下述情況：
  
  （1）既含移進(jìn)項(xiàng)目又含歸約項(xiàng)目睦裳；
  （2）含有多個(gè)歸約項(xiàng)目
  
  則稱G是一個(gè)LR(0)文法造锅。
  
  即是：LR(0)文法規(guī)范族的每個(gè)項(xiàng)目集不包含任何沖突項(xiàng)目
- 構(gòu)造
  - 令每個(gè)項(xiàng)目集 $I_k$ 的下標(biāo) $k$ 作為分析器的狀態(tài)。
  - 包含項(xiàng)目 $S'→·S$ 的集合 $I_k$ 的下標(biāo) $k$ 為分析器的初態(tài)廉邑。
SLR分析表

LR(0)文法太簡(jiǎn)單哥蔚，沒有實(shí)用價(jià)值.

假定一個(gè)LR(0)規(guī)范族中含有如下的一個(gè)項(xiàng)目集(狀態(tài)) $I$ ＝{ $X→a·b\beta ，A→a·蛛蒙，B→a \ ·$ }糙箍。FOLLOW(A)和FOLLOW(B)的交集為 $\emptyset$ ，且不包含b宇驾，那么，當(dāng)狀態(tài)I面臨任何輸入符號(hào) $a$ 時(shí)猴伶，可以
- 若 $a=b$ 课舍，則移進(jìn)；
- 若 $a\in FOLLOW(A)$ 他挎，用產(chǎn)生式 $A→a$ 進(jìn)行歸約筝尾；
- 若 $a\in FOLLOW(B)$ ，用產(chǎn)生式 $B→a$ 進(jìn)行歸約办桨；
- 此外筹淫，報(bào)錯(cuò)。
SLR存在的問題：計(jì)算FOLLOW集合所得到的超前/后繼符號(hào)集合可能大于實(shí)際能出現(xiàn)的超前/后繼符號(hào)集呢撞。FOLLOW集合提供的信息太泛损姜！
規(guī)范LR分析表

https://blog.csdn.net/qq_40147863/article/details/93253171
- 我們需要重新定義項(xiàng)目，使得每個(gè)項(xiàng)目都附帶有 $k$ 個(gè)終結(jié)符殊霞。每個(gè)項(xiàng)目的一般形式是 $[A→a·\beta ,\ a_1a_2…a_k]$ 摧阅，這樣的一個(gè)項(xiàng)目稱為一個(gè) $LR(k)$ 項(xiàng)目。項(xiàng)目中的 $a_1a_2…a_k$ 稱為它的向前搜索符串(或展望串)绷蹲。
- 向前搜索符串僅對(duì)歸約項(xiàng)目 $[A→a·棒卷，\ a_1a_2…a_k]$ 有意義顾孽。對(duì)于任何移進(jìn)或待約項(xiàng)目 $[A→a·\beta,\ a_1a_2…a_k]$ , $\beta \neq ε$ ，搜索符串 $a_1a_2…a_k$ 沒有作用比规。
- 動(dòng)作ACTION和狀態(tài)轉(zhuǎn)換GOTO構(gòu)造
  
  構(gòu)造方法
- 按上述算法構(gòu)造的分析表若厚，若不存在多重定義的入口(即，動(dòng)作沖突)的情形蜒什，則稱它是文法G的一張規(guī)范的LR(1)分析表测秸。
- 使用這種分析表的分析器叫做一個(gè)規(guī)范的LR分析器。
- 具有規(guī)范的LR(1)分析表的文法稱為一個(gè)LR(1)文法吃谣。
- LR(1)狀態(tài)比SLR多：LR(0) $\subset$ SLR $\subset$ LR(1) $\subset$ 無二義文法
LR(0), SLR, LR(1)三種分析表僅僅在reduce操作有區(qū)別乞封；

其中LR(0)，SLR分析表的構(gòu)建方式相同岗憋；LR(1)不同肃晚。
LR(0) & LR(1) 分析（分析表構(gòu)成）算法的區(qū)別：
- LR(0)：
  
  LR(0)部分算法
- LR(1)：
  
  LR(1)部分算法

LALR分析法
- 研究LALR的原因規(guī)范LR分析表的狀態(tài)數(shù)偏多
- LALR特點(diǎn)
  - LALR和SLR的分析表有同樣多的狀態(tài)，比規(guī)范LR分析表要小得多
  - LALR的能力介于SLR和規(guī)范LR之間
  - LALR的能力在很多情況下已經(jīng)夠用
- LALR分析表構(gòu)造方法：通過合并規(guī)范LR(1)

在四種LR分析里仔戈，LR(0)對(duì)文法的要求最高（限制最多）关串，LR(1)要求最低（限制最少）

LR(0)文法判定：

如果文法對(duì)應(yīng)的自動(dòng)機(jī)中不存在移進(jìn)-歸約沖突和歸約-歸約沖突則為 LR(0)文法。換句話說LR(0)文法分析不能解決這兩種沖突监徘，所以范圍最小晋修。移進(jìn)-歸約沖突就是在同一個(gè)項(xiàng)集族中同時(shí)出現(xiàn)了可以移進(jìn)的產(chǎn)生式和可以歸約的產(chǎn)生式。歸約-歸約沖突類似凰盔。

SLR文法判定：

SLR文法不存在歸約-歸約沖突墓卦，有可能存在移進(jìn)-歸約沖突，但是如果可以用 follow集解決則是 SLR文法户敬。換句話說落剪，SLR文法分析過程可以解決歸約-歸約沖突，但是不一定能解決移進(jìn)-歸約沖突尿庐。用 follow集來處理即出現(xiàn)移進(jìn)-歸約沖突的兩條產(chǎn)生式忠怖，如果其 follow集相交為空則為 SLR文法，反之不是抄瑟。

LALR文法判定：

有個(gè)結(jié)論是合并同心集不會(huì)產(chǎn)生新的移進(jìn)-歸約沖突凡泣，但是會(huì)產(chǎn)生新的歸約-歸約沖突，如果沒產(chǎn)生沖突就是 LALR 文法皮假，反之不是鞋拟。

LR(1)文法判定：

因?yàn)?LR(1)文法的范圍比較大，所以文法幾乎都是 LR(1)的（只要LR(1)分析表沒有沖突）惹资。當(dāng)合并同心集產(chǎn)生了歸約-歸約沖突時(shí)才只屬于LR(1)文法严卖，而不屬于其他文法。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末布轿，一起剝皮案震驚了整個(gè)濱河市哮笆，隨后出現(xiàn)的幾起案子来颤，更是在濱河造成了極大的恐慌，老刑警劉巖稠肘，帶你破解...
沈念sama閱讀 210,914評(píng)論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件福铅，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡项阴，警方通過查閱死者的電腦和手機(jī)滑黔，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 89,935評(píng)論 2贊 383
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來环揽，“玉大人略荡，你說我怎么就攤上這事∏附海” “怎么了汛兜？”我有些...
開封第一講書人閱讀 156,531評(píng)論 0贊 345
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)通今。經(jīng)常有香客問我粥谬，道長(zhǎng)，這世上最難降的妖魔是什么辫塌？我笑而不...
開封第一講書人閱讀 56,309評(píng)論 1贊 282
?港島之戀（遺憾婚禮）
正文為了忘掉前任漏策，我火速辦了婚禮，結(jié)果婚禮上臼氨，老公的妹妹穿的比我還像新娘掺喻。我一直安慰自己，他們只是感情好储矩，可當(dāng)我...
茶點(diǎn)故事閱讀 65,381評(píng)論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布感耙。她就那樣靜靜地躺著，像睡著了一般椰苟。火紅的嫁衣襯著肌膚如雪抑月。梳的紋絲不亂的頭發(fā)上树叽，一...
開封第一講書人閱讀 49,730評(píng)論 1贊 289
城市分裂傳說
那天舆蝴，我揣著相機(jī)與錄音，去河邊找鬼题诵。笑死洁仗，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的性锭。我是一名探鬼主播赠潦，決...
沈念sama閱讀 38,882評(píng)論 3贊 404
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼草冈！你這毒婦竟也來了她奥？” 一聲冷哼從身側(cè)響起瓮增，我...
開封第一講書人閱讀 37,643評(píng)論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎哩俭，沒想到半個(gè)月后绷跑，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,095評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡凡资，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,448評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年砸捏，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片隙赁。...
茶點(diǎn)故事閱讀 38,566評(píng)論 1贊 339
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡垦藏，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出伞访，到底是詐尸還是另有隱情掂骏，我是刑警寧澤，帶...
沈念sama閱讀 34,253評(píng)論 4贊 328
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布咐扭，位于F島的核電站芭挽，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏蝗肪。R本人自食惡果不足惜袜爪，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,829評(píng)論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望薛闪。院中可真熱鬧辛馆，春花似錦、人聲如沸豁延。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,715評(píng)論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)诱咏。三九已至苔可，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間袋狞，已是汗流浹背焚辅。一陣腳步聲響...
開封第一講書人閱讀 31,945評(píng)論 1贊 264
情欲美人皮
我被黑心中介騙來泰國(guó)打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留苟鸯，地道東北人同蜻。一個(gè)月前我還...
沈念sama閱讀 46,248評(píng)論 2贊 360
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像早处，于是被迫代替她去往敵國(guó)和親湾蔓。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,440評(píng)論 2贊 348