[编译原理] 学习笔记(二)——文法和语言

本贴最后更新于 2922 天前,其中的信息可能已经物是人非

一、 对程序设计语言的描述从语法、语义和语用三个因素考虑:
a) 语法:对语言结构的定义;
b) 语义:语言的含义;
c) 语用:从使用的角度描述语言。
形式语言理论是编译的理论基础。
二、 字母表:元素的非空有穷集合;
符号/字符:字母表中的元素;
符号串:符号的有穷序列。
三、 符号串运算:
a) 符号串的连接:εx=xε=x;
b) 集合的乘积:AB={xy|x∈A,y∈B};{ε}A=A{ε}=A;
c) 符号串的幂运算:x=abc,x^2=abcabc;
d) 集合的幂运算
e) 正闭包 A+ 与闭包 A*:A*={ε}∪A+
四、 形式语言:字母表上按照某种规则构成的所有符号串的集合,其不考虑语义。描述形式语言的方式有两种:
a) 枚举——当语言为有穷集合时;
b) 文法——描述了无穷集合的语言。
五、 文法:G=(Vn,Vt,P,S)
a) 规则 P:也称为产生式,是一个符号与一个符号串的有序对(A,β)
A→β
i. 一组规则定义了一个语言的语法结构;
ii. 规则中出现的符号分为终结符号和非终结符号
b) Vn 为非终结符(non-terminate);
c) Vt 为终结符(terminate);
d) S 为非终结符号,称为文法的开始符号/识别符号,至少要在一条规则的左部出现。
六、 推导:推导的依据是规则
a) 直接推导:仅使用一次规则;
b) 推导:至少使用一次规则;
c) 广义推导:经过 0 步或若干步的推导。
d) 最右推导又称规范推导,推导出的句型为规范举行;与之对应的最左规约为规范规约。
七、 句型、句子和语言:
a) 句型:S=*>x, x∈(Vn∪Vt)*,其中 S=*>x 为广义推导。
b) 句子:S=*>x, x∈Vt*,其中 S=*>x 为广义推导,x 必须是终结符的闭包(可为 ε)。
c) 语言:L(G[S])={x|S=+>x 且 x 属于 Vt*},其中 S=+>x 为推导,至少使用一次规则。
八、 递归:
a) 递归规则:在规则的左部和右部具有相同非终结符的规则;
i. 规则左递归:A->A…;
ii. 规则右递归:A->…A;
iii. 规则递归:A->…A…;
b) 文法递归:对文法中的任一非终结符,若能建立一个推导过程使得右部再次出现该非终结符,则文法是递归的。如:U->Vx, V->Uy|z,虽然这两个规则都不是递归规则,但组成的文法是递归文法 U->Vx->Uyx。所以含有递归规则的文法一定是递归文法,而递归文法不一定含有递归规则。
九、 短语、直接短语和句柄:都是针对某一句型的
a) 短语:S=*>αAδ 且 A=+>β,则称 β 是相对于非终结符 A 的句型 αAδ 的短语;对应语法树中的子树概念。
b) 直接短语:其中 A=>β 为直接推导;对应语法树中的简单子树。每个直接短语都是某规则的右部。
c) 句柄:是直接短语(即某规则的右部),且具有最左性;对应简单子树中最左的一棵。
十、 文法的二义性:如果一个文法存在某个句子对应两棵不同的语法树 | 包含两个或两个以上的最右(最左)推导(规约),则该文法是二义性的,可以利用文法之间的等价性来消除二义性。
a) 不改变文法中原有的语法规则,进增加一些语法的非形式定义,如优先级;
b) 构造一个等价的无二义性文法。
十一、 文法的分类:
a) 0 型文法/无限制文法:α->β,其中 α∈(Vn∪Vt)*且至少含有一个非终结符,β∈(Vn∪Vt)*。
b) 1 型文法/上下文有关文法:αAβ->αuβ,其中 A∈Vn,α,β∈(Vn∪Vt)*,u∈(Vn∪Vt)+。
c) 2 型文法/上下文无关文法:A->β,其中 A∈Vn,β∈(Vn∪Vt)*。常用于句法分析。
d) 3 型文法/正规文法:常用于词法分析
i. 右线性文法:只能对推出式的右边展开,A->αB|α,A,B∈Vn,α∈Vt*。
ii. 左线性文法:只能对推出式的左边展开,A->Bα|α,A,B∈Vn,α∈Vt*。

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • jsoup

    jsoup 是一款 Java 的 HTML 解析器,可直接解析某个 URL 地址、HTML 文本内容。它提供了一套非常省力的 API,可通过 DOM,CSS 以及类似于 jQuery 的操作方法来取出和操作数据。

    6 引用 • 1 回帖 • 477 关注
  • Electron

    Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。

    15 引用 • 136 回帖 • 1 关注
  • 分享

    有什么新发现就分享给大家吧!

    248 引用 • 1792 回帖
  • Kubernetes

    Kubernetes 是 Google 开源的一个容器编排引擎,它支持自动化部署、大规模可伸缩、应用容器化管理。

    110 引用 • 54 回帖
  • 安装

    你若安好,便是晴天。

    132 引用 • 1184 回帖
  • Linux

    Linux 是一套免费使用和自由传播的类 Unix 操作系统,是一个基于 POSIX 和 Unix 的多用户、多任务、支持多线程和多 CPU 的操作系统。它能运行主要的 Unix 工具软件、应用程序和网络协议,并支持 32 位和 64 位硬件。Linux 继承了 Unix 以网络为核心的设计思想,是一个性能稳定的多用户网络操作系统。

    943 引用 • 943 回帖
  • 知乎

    知乎是网络问答社区,连接各行各业的用户。用户分享着彼此的知识、经验和见解,为中文互联网源源不断地提供多种多样的信息。

    10 引用 • 66 回帖
  • RabbitMQ

    RabbitMQ 是一个开源的 AMQP 实现,服务器端用 Erlang 语言编写,支持多种语言客户端,如:Python、Ruby、.NET、Java、C、PHP、ActionScript 等。用于在分布式系统中存储转发消息,在易用性、扩展性、高可用性等方面表现不俗。

    49 引用 • 60 回帖 • 362 关注
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    12 引用 • 54 回帖 • 65 关注
  • 工具

    子曰:“工欲善其事,必先利其器。”

    286 引用 • 729 回帖
  • 阿里云

    阿里云是阿里巴巴集团旗下公司,是全球领先的云计算及人工智能科技公司。提供云服务器、云数据库、云安全等云计算服务,以及大数据、人工智能服务、精准定制基于场景的行业解决方案。

    89 引用 • 345 回帖
  • 倾城之链
    23 引用 • 66 回帖 • 136 关注
  • 宕机

    宕机,多指一些网站、游戏、网络应用等服务器一种区别于正常运行的状态,也叫“Down 机”、“当机”或“死机”。宕机状态不仅仅是指服务器“挂掉了”、“死机了”状态,也包括服务器假死、停用、关闭等一些原因而导致出现的不能够正常运行的状态。

    13 引用 • 82 回帖 • 51 关注
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    12 引用 • 54 回帖 • 165 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    266 引用 • 665 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 19 关注
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    125 引用 • 588 回帖
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 537 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 628 关注
  • ActiveMQ

    ActiveMQ 是 Apache 旗下的一款开源消息总线系统,它完整实现了 JMS 规范,是一个企业级的消息中间件。

    19 引用 • 13 回帖 • 671 关注
  • etcd

    etcd 是一个分布式、高可用的 key-value 数据存储,专门用于在分布式系统中保存关键数据。

    5 引用 • 26 回帖 • 528 关注
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    47 引用 • 25 回帖
  • Sillot

    Insights(注意当前设置 master 为默认分支)

    汐洛彖夲肜矩阵(Sillot T☳Converbenk Matrix),致力于服务智慧新彖乄,具有彖乄驱动、极致优雅、开发者友好的特点。其中汐洛绞架(Sillot-Gibbet)基于自思源笔记(siyuan-note),前身是思源笔记汐洛版(更早是思源笔记汐洛分支),是智慧新录乄终端(多端融合,移动端优先)。

    主仓库地址:Hi-Windom/Sillot

    文档地址:sillot.db.sc.cn

    注意事项:

    1. ⚠️ 汐洛仍在早期开发阶段,尚不稳定
    2. ⚠️ 汐洛并非面向普通用户设计,使用前请了解风险
    3. ⚠️ 汐洛绞架基于思源笔记,开发者尽最大努力与思源笔记保持兼容,但无法实现 100% 兼容
    29 引用 • 25 回帖 • 85 关注
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    85 引用 • 139 回帖 • 1 关注
  • Eclipse

    Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。

    75 引用 • 258 回帖 • 617 关注
  • 新人

    让我们欢迎这对新人。哦,不好意思说错了,让我们欢迎这位新人!
    新手上路,请谨慎驾驶!

    52 引用 • 228 回帖
  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。

    86 引用 • 122 回帖 • 625 关注