【導(dǎo)讀】自下而上分析及其LR分析概述。token，就把它從輸入移到棧中.w歸約為開始符號(hào)S，分析int+)時(shí)就會(huì)發(fā)生錯(cuò)誤.移進(jìn)歸約分析的棧中出現(xiàn)的內(nèi)容加上余留輸入。β，其中α、β是句型，都是對(duì)α中。最右推導(dǎo)被稱為規(guī)范推導(dǎo)。假定α是G的一個(gè)句子，稱序列αn,αn-1…,α0是α的一個(gè)規(guī)范歸約。而else是下一token歸約還是移進(jìn)？分析器模型和分析算法。ＬＲ分析特征討論。置ip指向輸入串w的第一個(gè)符號(hào)。–elseifACTION[S,a]=rj(第j條產(chǎn)生式為A??令當(dāng)前棧頂狀態(tài)為S’。pushGOTO[S’,A]和A(進(jìn)棧)

　　

【正文】 4 3 S7 6 4 S8 5 r5 r5S9 r5 r5 r5 r5 6 S10 7 r7 r7 r7 r7 r7 S11 r7 8 r1 r1 r1 r1 r1 r1 9 r3 r3 r3 r3 r3 r3 10 r2 r2 r2 r2 r2 r2 11 r4 r4 r4 r4 r4 r4 ?? ? I5: S →ae ． c ? A →e ． ? S`==S==aAd==aed ? S`==S==aec ? I7: S →be ． d ? A →e ． ? S`==S==bAc==bec ? S`==S==bed ? ？ 信息 哪些輸入符號(hào)能跟在句柄之后 R R R R R R R R R R Another example ? G[S]: ? (0) S`→ S (1) S→L=R (2) S→R ? (3) L→ *R (4) L→i (5) R→L ? LR(0)項(xiàng)目集規(guī)范族和 G0函數(shù) ? I1 S’ →S . I6 ? I0 S`→ ． S I2 S→L ． =R S →L= .R L → .*R ? S→ ． L=R R→ L. R→ .L L→ .i ? S→ ． R ? L→ ． *R I3 ? L→ ． i S→R ． ? R→ ． L I4 ? L→* ． R I7 ? I5 R→ ． L L→*R ． ? L→i ． L→ ． *R ? L→ .i I8 R→L ． ? (1)不是 LR(0)文法 ? ∵ I2 S→L ． =R R→ L. 中存在移進(jìn) /歸約沖突 ? （ 2） SLR能否 解決 I2中的沖突 ? ∴ FOLLOW（ R） ={,=}與 {=}交不為空 不是 SLR（ 1） 文法 ? S→L.=R R→L. 若用 R→L 歸約 則形成 ? R=… 而 R=不是活前綴 ?早知此信息 ? 向前搜索符 —— LR（ 1） 方法 ? 若 A ?? .B ? ? I ? 則 B ? . ? （ B ? ? 是一產(chǎn)生式） ? I ? 把 FIRST（ B） 中的符號(hào)作為用 B ? ? 歸約的搜索符 ? LR（ 1） 項(xiàng)目 – [ A ?? . ?， a ] ? LR（ K） 項(xiàng)目 – [ A ?? . ?， a1 a2 …… a K ] 構(gòu)造 LR(1)項(xiàng)目集 規(guī)范族和 G0函數(shù) – closure(I)按如下方式構(gòu)造 ? (1) I的任何項(xiàng)目屬 closure(I)； ? (2)若 [A→ β 1． Bβ 2， a]∈ closure(I)， B→ δ 是一產(chǎn)生式，那么對(duì)于 FIRST(β 2a)中的每個(gè)終結(jié)符 b， 如果 [B→ ． δ ,b]不在 closure(I)中，則把它加進(jìn)去； ? (3)重復(fù)（ 1）（ 2），直至 closure(I)不再增大。 – GO函數(shù)： ? 若 I是一個(gè)項(xiàng)目集， X是一個(gè)文法符號(hào) ? GO(I, X)= closure(J) ? 其中 J={ 任何形如 [A→ α X． β ,a]的項(xiàng)目 ∣ [A→ α .Xβ ,a]∈I} ? LR(I)項(xiàng)目規(guī)范族 C的構(gòu)造算法類同 LR(0)的，只是初始時(shí)： ? C={ closure({[S`→ ． S,]})}。 LR(1)項(xiàng)目集規(guī)范族 ? I0: S`→ ． S, I5: S →ae ． c, ? S → ． aAd, A →e ． ,d ? S → ． bAc, I6: S →bA ． c, ? S → ． aec, I7: S →be ． d, ? S → ． bed, A →e ． ,c ? I1: S` →S ． , I8: S →aAd ． , ? I2: S` →a ． Ad, I9: S →aec ． , ? S →a ． ec, I10: S →bAc ． , ? A → ． e, d I11: S →bed ． , ? I3: S →b ． Ac, ? S →b ． ed, ? A→ ． e,c ? I4: S →aA ． d, LR(1)項(xiàng)目集規(guī)范族 ? I1: S`→S ． , I9 :S→ L=R. , ? I2: I6: S→L= ． R, ? I0: S`→ ． S, S→L ． =R, R→ ． L, ? S→ ． L=R, R→L ． , L→ ． *R, ? S→ ． R, I3: L→ ． i, ? L→ ． *R,=/ S→R ． , ? L→ ． i,=/ I4: I11: ? R→ ． L, L→* ． R,=/ L→* ． R, ? L→ ． *R,=/ R→ ． L, ? I5: L→i ． ,=/ L→ ． i,=/ L→ ． *R, ? R→ ． L,=/ L→ ． i, ? I7 L→*R ． ,=/ I8 R→L ． ,/= I10 I13 ? I12: L→i . R→L ． , L→*R ． , LR(1)分析表的構(gòu)造 ? 若項(xiàng)目 [A→ α ． A]屬于 Ik, 那么 置 ACTION[k, a]為“用產(chǎn)生式A→ α 進(jìn)行規(guī)約 ”，簡(jiǎn)記為“ rj”。其中，假定 A→ α 為文法 G`的第j個(gè)產(chǎn)生式； ? At the heart of the table construction is the notion of an LR(0) configuration or item. A configuration is a production of the grammar with a dot at some ? position on its right side. For example, A – XYZ gives four items: ? A – ?XYZ ? A – X?YZ ? A – XY?Z ? A – XYZ?