我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 正确性证明 >

证明LR 分析过程正确性的一个重要引理:由构造LR(0)项目集规范族

归档日期:07-05       文本归类:正确性证明      文章编辑:爱尚语录

  首先要了解活前缀是如何产生的。活前缀的集合Prefix 可归纳定义如下:

  (1) 设S’是增广文法的开始符号,既有产生式S’ → S (S 是原文法的开始符号),令

  (3) 若v ∈Prefix ,且v 中至少包含一个非终结符,即可以将v 写成 αBγ,其中B 为

  非终结符。若有产生式B →β,则αβ的任一前缀u 都是活前缀,即u∈Prefix 。

  基础:对于由规则(1)产生的活前缀S ∈Prefix ,由于在DFA的初始项目集(状态)I0 中

  归纳:若v ∈Prefix ,且v 可以被DFA 读进,则v 的前缀可以被DFA 读进也是显然的。

  若v ∈Prefix ,且可以将v写成 αBγ,其中B为非终结符并有产生式B →β。设DFA

  在从初态I0读进 α 后进入状态I。因为v=αBγ 可以被DFA读进,所以在状态I可以

  读进B ,根据DFA的构造过程,一定存在项目C →α?B γ ’ ∈I。由闭包的计算过程,

  可知一定有B →?β∈I,因此β是从I开始后续的可读串。所以,从初态I0开始,αβ

  归纳:设 αX 是DFA 可读序列,且?αX ?= n +1,其中X 是某个文法符号。在读过 α 后,

  DFA 一定处于状态I,在此状态下X 是可读的。根据DFA 的构造过程,一定存在

  项目 C →β? X γ∈I。该项目或者是基本项目,或者是通过闭包计算得到的项目。

  若?β?= 0,则该项目只能是S’ →?S,此时αX = S 显然是活前缀。

  若?β?= m ≠ 0,则DFA从状态I0读进n - m个符号的序列μ后进入状态I ’,且必定

  有C →?βX γ∈I ’。 根据DFA的构造过程,一定存在项目B →?C γ ’ ∈ I ’。这

  样在状态I ’下,可以读进B 。因为?μB ?≤n,由归纳假设,可知μB是活前缀。

  此时,β一定为空序列,而项目C →? X γ一定是由I中的某个基本项目B →μ?

  C ν 直接或间接地通过闭包计算序列得到的:C →?C γ,C →?C γ,…,

  C →?C γ 。由1)的讨论结果,可知 α C 是活前缀。从而 αC ,αC ,…,

本文链接:http://gilbertpromos.com/zhengquexingzhengming/309.html