您好，欢迎来到微智科技网。
科技 教育 生活 旅游 时尚 美容 美食 健康 体育 游戏 汽车 家电
搜索
您的当前位置：首页怎样构造识别活前缀的DFA——编译原理

怎样构造识别活前缀的DFA——编译原理

来源：微智科技网

怎样构造识别活前缀的DFA

第一步 拓广文法

第二步 构造LR(0)项目集规范族

  1. 构造第一个状态集合 I 0 I_0 I0​
    • 使 用 拓 广 文 法 中 添 加 的 表 达 式 （ 即 上 文 所 说 的 “ 头 ” ） 作 为 集 合 I 0 中 的 初 始 元 素 使用拓广文法中添加的表达式（即上文所说的 “头”）\\作为集合I_0中的初始元素 使用拓广文法中添加的表达式（即上文所说的“头”）作为集合I0​中的初始元素
    • ∀ a ∈ I （ a 为 表 达 式 ） ， 如 果 a 具 有 以 下 形 式 \forall a \in I（a为表达式），如果a具有以下形式 ∀a∈I（a为表达式），如果a具有以下形式
      A → α ⋅ B β ， A\rightarrow \alpha ·B \beta， A→α⋅Bβ，
      其 中 α 和 β 可 能 为 ： 终 结 符 ， 非 终 结 符 ， 空 串 ϵ B 为 非 终 结 符 且 其中\alpha和\beta 可能为：终结符，非终结符，空串\epsilon \\ B为非终结符且 其中α和β可能为：终结符，非终结符，空串ϵB为非终结符且
      B → γ B\rightarrow \gamma B→γ
      则 将 则将 则将
      B → ⋅ γ B\rightarrow ·\gamma B→⋅γ
      加 入 I 0 加入I_0 加入I0​
  2. 构造其他状态集合 I j I_j Ij​
    • 根 据 I j − 1 中 ⋅ 在 每 个 表 达 式 中 的 位 置 找 到 ⋅ 后 的 所 有 可 能 符 号 （ 包 括 终 结 符 和 非 终 结 符 ） ， 构 成 集 合 P 根据I_{j-1}中·在每个表达式中的位置找到·后的所有可能符号 \\ （包括终结符和非终结符），构成集合P 根据Ij−1​中⋅在每个表达式中的位置找到⋅后的所有可能符号（包括终结符和非终结符），构成集合P
    • ∀ ξ ∈ P ， ∃ ( A → α ⋅ ξ β ) ∈ I j − 1 ， 则 将 \forall \xi \in P，\exists (A\rightarrow\alpha ·\xi \beta) \in I_{j-1}，则将 ∀ξ∈P，∃(A→α⋅ξβ)∈Ij−1​，则将
      A → α ξ ⋅ β A\rightarrow\alpha\xi ·\beta A→αξ⋅β
      加 入 I j 加入I_j 加入Ij​
    • j 从 1 到 n 依 次 按 照 上 述 规 则 递 推 j 从1到n依次按照上述规则递推 j从1到n依次按照上述规则递推

第三步 构造DFA

依据已经构造好的状态集合和转换关系画图即可

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019- 7swz.com 版权所有 赣ICP备2024042798号-8

违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务