编译原理陈火旺版PPT课件.pptxVIP

5.3LR分析方法;LR(k)分析方法中L是指自左(Left)向右扫描输入单词串，R指分析过程是最右(Right)推导的逆过程(规范归约)，k是指在决定当前分析动作时需向前察看的输入符号个数。;一、LR分析器的逻辑结构：;LR分析器工作过程简介;(1)在总控程序的控制下，从左到右扫描输入串根据分析栈和输入符号的情况，查分析表确定分析动作；;规范归约的关键是寻找句柄，LR法是根据已“移进”、“归约”的符号串及即将读入的符号串进行分析，以确定是否有句柄可归约。;2.分析表的组成：;(2)状态转换表也用一个二维数组表示，行代表分析栈栈顶状态，列代表文法符号，数组元素Goto[Si,Xj]表示当前栈顶状态为Si,，面对文法符号为Xj时，新的栈顶状态。;二、LR分析过程：;接受:若动作表中对应“acc”，则分析成功；;;分析过程：;三.LR(0)分析表的构造;事实上：LR分析过程中，任意时刻均应保证栈中符号串是规范句型的活前缀，即：栈中绝无句柄之后的任何符号。若输入串为一合法的“句子”，则栈中符号与剩余输入串就构成一个规范句型。;2.例如：

对于产生式:

S?aAcBe;(三)构造识别活前缀的NFA;(5)转换函数f：;2.举例：;可画出NFA的状态图如下:(P106);(四)项目的分类：;(五)识别活前缀的DFA：;S’?E

E?aA|bB

A?cA|d

B?cB|d;返回;①据NFA可以构造DFA的转换矩阵：;②状态转换图表示(P106)：;;2.方法二：求项目集规范族每个项目集对应一个DFA状态，它们的全体称这个文法的项目集规范族，下面给出求各项目集的方法，以便得到识别文法活前缀的DFA.;构造项目集规范族的算法（P107）

Begin

C:={CLOSURE({S’→.S})};

REPEAT

FORC中的每一个项目集I和G’的每个符号XDO

IFGO(I,X)非空且不属于CTHEN

把GO(I,X)放入C族中

UNTILC不再增大

End

;3.构造DFA(举例)：;(六)LR(0)文法：;(七)LR(0)分析表的构造：;例对文法G[S’]

S’?E

E?aA|bB

A?cA|d

B?cB|d;?;;例有文法G:

(0)S’?S

(1)S?aAcBe

(2)A?b

(3)A?Ab

(4)B?d;状态;状态