编译原理 教学课件 作者 王生原 董渊 杨萍 张素琴 LR(0)FSM_for_Reading_Viable_Prefixes.doc

《编译原理 教学课件 作者 王生原 董渊 杨萍 张素琴 LR(0)FSM_for_Reading_Viable_Prefixes.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、证明LR分析过程正确性的一个重要引理：LR(0)FSM可以也只能读进所分析文法的活前缀。需要证明两个方面：命题1所有活前缀一定都可由LR(0)FSM读进，即不会错过合法的归约。命题2LR(0)FSM只能读活前缀。证明思路：首先要了解活前缀是如何产生的。活前缀的集合Prefix可归纳定义如下：（1）设S’是增广文法的开始符号，即有产生式S’®S（S是原文法的开始符号），令SÎPrefix。（2）若vÎPrefix，则v的任一前缀u都是活前缀，即uÎPrefix。（3）若vÎPrefix，且v中至少包含一个非终结符，即可以将v写成aBg，其

2、中B为非终结符。若有产生式B®β，则aβ的任一前缀u都是活前缀，即uÎPrefix。（4）Prefix中的元素只能通过上述步骤产生。命题1可以根据Prefix的定义进行归纳证明。基础：对于由规则（1）产生的活前缀SÎPrefix，由于在LR(0)FSM的初始项目集（状态）I0中含有项目S’®·S，显然S是可以被LR(0)FSM读进的。归纳：若vÎPrefix，且v可以被LR(0)FSM读进，则v的前缀可以被LR(0)FSM读进也是显然的。若vÎPrefix，且可以将v写成aBg，其中B为非终结符并有产生式B®β。设LR(0)FSM在从初

3、态I0读进a后进入状态I。因为v=aBg可以被LR(0)FSM读进，所以在状态I可以读进B，根据LR(0)FSM的构造过程，一定存在项目C®a·Bg’ÎI。由闭包的计算过程，可知一定有B®·βÎI，因此β是从I开始后续的可读串。所以，从初态I0开始，aβ的任一前缀u都是可读进的。命题1证毕。命题2可归纳于LR(0)FSM可读序列的长度n来证明。基础：n=0。显然空序列ε是活前缀。归纳：设aX是LR(0)FSM可读序列，且½aX½=n+1，其中X是某个文法符号。在读过a后，LR(0)FSM一定处于状态I，在此状态下X是可读的。根据LR(0

4、)FSM的构造过程，一定存在项目C®β·XgÎI。该项目或者是基本项目，或者是通过闭包计算得到的项目。下面分这两种情形来讨论。1）C®β·Xg是基本项目。若½β½=0，则该项目只能是S’®·S，此时aX=S显然是活前缀。若½β½=m≠0，则LR(0)FSM从状态I0读进n-m个符号的序列μ后进入状态I’，且必定有C®·βXgÎI’。根据LR(0)FSM的构造过程，一定存在项目B®·Cg’ÎI’。这样在状态I’下，可以读进B。因为½μB½≤n，由归纳假设，可知μB是活前缀。因此，由活前缀集合的归纳定义，得知μβX=aX是活前缀。2）C®β

5、·Xg是通过闭包计算得到的项目。此时，β一定为空序列，而项目C®·Xg一定是由I中的某个基本项目B®μ·C0n直接或间接地通过闭包计算序列得到的：C0®·C1g1，C1®·C2g2，¼，Ck®·Cgk+1。由1）的讨论结果，可知aC0是活前缀。从而aC1，aC2，¼，aCk都是活前缀，aC也是活前缀。所以，aX是活前缀。命题2证毕。（如发现问题，请及时讨论）