热门标签 | HotTags
当前位置:  开发笔记 > 程序员 > 正文

编译原理——第三章

第三章词法分析知识总结:1、词法分析器的基本知识(任务、构造、基本要求)2、状态转换图(表示与构造)示例

第三章   词法分析


知识总结:


1、词法分析器的基本知识(任务、构造、基本要求)



2、状态转换图(表示与构造)

示例:



3、正规式与正规集(定义与正规式性质与等价性)

正规式等价性:若两个正规式U,V所表示的正规集相同,则两者等价


4、有限自动机(DFA与NFA)

DFA定义:一个确定有限自动机(DFA)M是一个五元式:M = (S, ∑, f, s0, F)

NFA定义 :一个非确定有限自动机(NFA)M是一个五元式M = (S, ∑, f, S0, F)

区别:

DFA:f是从 S×∑ →S的单值部分映射

NFA:f是从S×∑*→2S 的部分映射,其中,2S表示S的幂集合(所有S的子集组成的集合)(f是非单值的->M是非确定)

状态集合

表示:矩阵表示与状态图表示


***5、正规表达式与有限自动机

等价性:

定理1:对于任何∑上NFA M都可构造一个∑上的正规式V,使得  L(V) = L(M) 

其中,L(M)是∑上NFA M所能识别的字的全体L(V)是∑上的正规集

由NFA M构造正规表达式V

方法:
(1)在M转换图上加进X结点和Y结点,从X结点用弧ε连接M的所有初态结点,M的所有终态结点用弧ε连接到Y,得到一个NFA M’,且L(M) = L(M’)

(2)使用替换规则逐步消去M’的所有结点,直到只剩下X结点和Y结点,在消去过程中,逐步使用正规式来标记箭弧


定理2. 对于∑上的每一个正规式V,存在一个∑上的DFA M,使得L(M) = L(V) 

由正规式V构造DFA M(***重点***)

方法:

1.根据V,构造一个NFA M’,使得L(M’) = L(V)

       (利用替换规则)

2.将M’确定化,变为DFA M

       (涉及到两个定义)

     

      

        3.化简DFA M

        


知识应用:









                                                                  


应用:正规式转换DFA

第一步:构造正规式相应的NFA  M’,得到状态转换图


第二步:利用子集法将M’确定化


(J集合变化过程)


第三步:把每个子集看成一个状态,得到一个DFA M


第四步:用状态转换图表示


第五步:化简DFA




总结:

     这一章学习起来感觉内容有些晦涩难懂,很多知识不理解,都是通过看例题才能明白说的什么。我认为这一章最重点的一部分是由正规式构造DFA,步骤繁琐,理解后真正做起来并不是很难,但是需要很仔细。总之还是需要多练习巩固知识。


推荐阅读
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • 解决PHP与MySQL连接时出现500错误的方法
    本文详细探讨了当使用PHP连接MySQL数据库时遇到500内部服务器错误的多种解决方案,提供了详尽的操作步骤和专业建议。无论是初学者还是有经验的开发者,都能从中受益。 ... [详细]
  • 本文深入探讨了Linux系统中网卡绑定(bonding)的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡,实现网络冗余、带宽聚合和负载均衡,在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]
  • 解读MySQL查询执行计划的详细指南
    本文旨在帮助开发者和数据库管理员深入了解如何解读MySQL查询执行计划。通过详细的解析,您将掌握优化查询性能的关键技巧,了解各种访问类型和额外信息的含义。 ... [详细]
  • 本文详细介绍了macOS系统的核心组件,包括如何管理其安全特性——系统完整性保护(SIP),并探讨了不同版本的更新亮点。对于使用macOS系统的用户来说,了解这些信息有助于更好地管理和优化系统性能。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • Google最新推出的嵌入AI技术的便携式相机Clips现已上架,旨在通过人工智能技术自动捕捉用户生活中值得纪念的时刻,帮助人们减少照片数量过多的问题。 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 解决微信电脑版无法刷朋友圈问题:使用安卓远程投屏方案
    在工作期间想要浏览微信和朋友圈却不太方便?虽然微信电脑版目前不支持直接刷朋友圈,但通过远程投屏技术,可以轻松实现在电脑上操作安卓设备的功能。 ... [详细]
  • 本文深入探讨了 Java 编程语言的基础,特别是其跨平台特性和 JVM 的工作原理。通过介绍 Java 的发展历史和生态系统,帮助初学者理解如何编写并运行第一个 Java 程序。 ... [详细]
  • C++构造函数与初始化列表详解
    本文深入探讨了C++中构造函数的初始化列表,包括赋值与初始化的区别、初始化列表的使用规则、静态成员初始化等内容。通过实例和调试证明,详细解释了初始化列表在对象创建时的重要性。 ... [详细]
  • PHP 5.5.0rc1 发布:深入解析 Zend OPcache
    2013年5月9日,PHP官方发布了PHP 5.5.0rc1和PHP 5.4.15正式版,这两个版本均支持64位环境。本文将详细介绍Zend OPcache的功能及其在Windows环境下的配置与测试。 ... [详细]
  • 深入理解Java泛型:JDK 5的新特性
    本文详细介绍了Java泛型的概念及其在JDK 5中的应用,通过具体代码示例解释了泛型的引入、作用和优势。同时,探讨了泛型类、泛型方法和泛型接口的实现,并深入讲解了通配符的使用。 ... [详细]
  • libsodium 1.0.15 发布:引入重大不兼容更新
    最新发布的 libsodium 1.0.15 版本带来了若干不兼容的变更,其中包括默认密码散列算法的更改和其他重要调整。 ... [详细]
  • 本文介绍如何在Java项目中使用Log4j库进行日志记录。我们将详细说明Log4j库的引入、配置及简单应用,帮助开发者快速上手。 ... [详细]
author-avatar
刘志樺伟宇佳君
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有