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

令人头疼的编译原理之文法

提到“编译原理”,大部分人的首要反应就是苦恼。确实,编译原理这一部分的内容在计算机学习中是比较难以理解的一部分。首次接触编译原理,我也感觉很复杂,难以理解。但是当看过几次之后,对于一些简单知识点

提到“编译原理”,大部分人的首要反应就是苦恼。确实,编译原理这一部分的内容在计算机学习中是比较难以理解的一部分。首次接触编译原理,我也感觉很复杂,难以理解。但是当看过几次之后,对于一些简单知识点的理解就有点眉目了。在这里就将有点眉目的知识写一下。


学习编译原理接触的第一个重要的概念就是——文法。那么什么是文法呢?

文法,语言中的每个句子可以用严格定义的规则来构造。通俗的讲就是:根据一些指定的规则,来确定编程语言的语法,从而实现编译器的功能。

 

那么文法是如何表示的呢?

文法是由非终结符(大写字母)和终结符(小写字母)以及“—>”组成的。给出几个例子就容易理解了。

A—> a、B—>dba、S—> Ab、adB—>d

通过上面的几个例子可以看出:非终结符A、B、S,一般是写在左边,而终结符a、dba、b,一般是写在右边的。当然习惯的写法是非终结符用S(Start)表示,写在左边,自然而然的小写的就在右边了,这样也便于我们记忆文法的表示方式。

 

话说,在1956年的春天,一个叫乔姆斯基(Chomsky)的人发明了上述文法,他觉得有些文法存在着相似的形式,于是他就给文法分了一下类。

 

首先有一个前提:设有一个组合G=(Vn,Vt,P,S)。其中Vn是非终结符的集合,Vt是终结符的集合,P是推导式的一个集合,S是开始符。就上面的例子来说,A、B、S是Vn,a、dba、b是Vt,整个的集合为P。

 

0型文法

这是最简单的一个文法。它比较宽容,没有那么多的限制条件。左边必须要包含这些元素或者元素组合中的至少一个非终结符,右边可以是这些元素的任意组合,这样就构成了0型文法。由于限制最少,所以见到的文法至少是一个0型文法。如:A—> a

1型文法(上下文有关文法)

它在0型文法的基础之上,只添加了一个要求:右边的长度>=左边的长度(终结符或非终结符的个数)。A—> a、B—>dba则是1型文法,而adB—>d不符合1型文法要求

注意这里有一个特殊的形式  S—> ∑(∑表示空),也是一个1型文法。

2型文法(上下文无关文法)

它在1型文法的基础上,有增加了一个要求:左边必须是非终结符(个数不限)。

如:AB—>de 属于2型文法,而 Aa—>DE则不是,因为Aa中含有a。

3型文法(正规文法)

它是在2型的基础上提出了要么一个非终结符推出一个终结符,要么一个非终结符推出一个终结符并且带一个非终结符。


而上图中的左线性、右线性是相互独立的。如:A—>b、A—>bD这是3型文法

但是A—>b、A—>bD、A—>Db则不是3型文法。从这里可以看出,对于3型文法,它不是左右线性的“组合”,要么都是右线性,要么都是左线性。


好了,关于文法就说这么对。对于文法还是通过实战来促进理解比较好。

 



推荐阅读
  • 本文总结了2018年的关键成就,包括职业变动、购车、考取驾照等重要事件,并分享了读书、工作、家庭和朋友方面的感悟。同时,展望2019年,制定了健康、软实力提升和技术学习的具体目标。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 深入理解 SQL 视图、存储过程与事务
    本文详细介绍了SQL中的视图、存储过程和事务的概念及应用。视图为用户提供了一种灵活的数据查询方式,存储过程则封装了复杂的SQL逻辑,而事务确保了数据库操作的完整性和一致性。 ... [详细]
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • 解读MySQL查询执行计划的详细指南
    本文旨在帮助开发者和数据库管理员深入了解如何解读MySQL查询执行计划。通过详细的解析,您将掌握优化查询性能的关键技巧,了解各种访问类型和额外信息的含义。 ... [详细]
  • 本文详细介绍了macOS系统的核心组件,包括如何管理其安全特性——系统完整性保护(SIP),并探讨了不同版本的更新亮点。对于使用macOS系统的用户来说,了解这些信息有助于更好地管理和优化系统性能。 ... [详细]
  • Google最新推出的嵌入AI技术的便携式相机Clips现已上架,旨在通过人工智能技术自动捕捉用户生活中值得纪念的时刻,帮助人们减少照片数量过多的问题。 ... [详细]
  • 本文深入探讨了 Java 编程语言的基础,特别是其跨平台特性和 JVM 的工作原理。通过介绍 Java 的发展历史和生态系统,帮助初学者理解如何编写并运行第一个 Java 程序。 ... [详细]
  • 使用Numpy实现无外部库依赖的双线性插值图像缩放
    本文介绍如何仅使用Numpy库,通过双线性插值方法实现图像的高效缩放,避免了对OpenCV等图像处理库的依赖。文中详细解释了算法原理,并提供了完整的代码示例。 ... [详细]
  • XNA 3.0 游戏编程:从 XML 文件加载数据
    本文介绍如何在 XNA 3.0 游戏项目中从 XML 文件加载数据。我们将探讨如何将 XML 数据序列化为二进制文件,并通过内容管道加载到游戏中。此外,还会涉及自定义类型读取器和写入器的实现。 ... [详细]
  • 本文深入探讨了Linux系统中网卡绑定(bonding)的七种工作模式。网卡绑定技术通过将多个物理网卡组合成一个逻辑网卡,实现网络冗余、带宽聚合和负载均衡,在生产环境中广泛应用。文章详细介绍了每种模式的特点、适用场景及配置方法。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • 本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度,而 vector 是一种可扩展的容器,允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景,并提供了代码示例以加深理解。 ... [详细]
  • 解决微信电脑版无法刷朋友圈问题:使用安卓远程投屏方案
    在工作期间想要浏览微信和朋友圈却不太方便?虽然微信电脑版目前不支持直接刷朋友圈,但通过远程投屏技术,可以轻松实现在电脑上操作安卓设备的功能。 ... [详细]
  • C++构造函数与初始化列表详解
    本文深入探讨了C++中构造函数的初始化列表,包括赋值与初始化的区别、初始化列表的使用规则、静态成员初始化等内容。通过实例和调试证明,详细解释了初始化列表在对象创建时的重要性。 ... [详细]
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社区 版权所有