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

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

一、 对程序设计语言的描述从语法、语义和语用三个因素考虑:
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*。

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • CSDN

    CSDN (Chinese Software Developer Network) 创立于 1999 年,是中国的 IT 社区和服务平台,为中国的软件开发者和 IT 从业者提供知识传播、职业发展、软件开发等全生命周期服务,满足他们在职业发展中学习及共享知识和信息、建立职业发展社交圈、通过软件开发实现技术商业化等刚性需求。

    14 引用 • 155 回帖 • 1 关注
  • ZooKeeper

    ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,是 Google 的 Chubby 一个开源的实现,是 Hadoop 和 HBase 的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功能包括:配置维护、域名服务、分布式同步、组服务等。

    59 引用 • 29 回帖 • 3 关注
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    41 引用 • 130 回帖 • 257 关注
  • 正则表达式

    正则表达式(Regular Expression)使用单个字符串来描述、匹配一系列遵循某个句法规则的字符串。

    31 引用 • 94 回帖 • 1 关注
  • Solidity

    Solidity 是一种智能合约高级语言,运行在 [以太坊] 虚拟机(EVM)之上。它的语法接近于 JavaScript,是一种面向对象的语言。

    3 引用 • 18 回帖 • 383 关注
  • 开源

    Open Source, Open Mind, Open Sight, Open Future!

    406 引用 • 3571 回帖
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 45 关注
  • 知乎

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

    10 引用 • 66 回帖
  • FreeMarker

    FreeMarker 是一款好用且功能强大的 Java 模版引擎。

    23 引用 • 20 回帖 • 461 关注
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖
  • Oracle

    Oracle(甲骨文)公司,全称甲骨文股份有限公司(甲骨文软件系统有限公司),是全球最大的企业级软件公司,总部位于美国加利福尼亚州的红木滩。1989 年正式进入中国市场。2013 年,甲骨文已超越 IBM,成为继 Microsoft 后全球第二大软件公司。

    105 引用 • 127 回帖 • 394 关注
  • SQLite

    SQLite 是一个进程内的库,实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。SQLite 是全世界使用最为广泛的数据库引擎。

    5 引用 • 7 回帖
  • Ant-Design

    Ant Design 是服务于企业级产品的设计体系,基于确定和自然的设计价值观上的模块化解决方案,让设计者和开发者专注于更好的用户体验。

    17 引用 • 23 回帖
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 533 关注
  • Google

    Google(Google Inc.,NASDAQ:GOOG)是一家美国上市公司(公有股份公司),于 1998 年 9 月 7 日以私有股份公司的形式创立,设计并管理一个互联网搜索引擎。Google 公司的总部称作“Googleplex”,它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎,它提供了简单易用的免费服务。不作恶(Don't be evil)是谷歌公司的一项非正式的公司口号。

    49 引用 • 192 回帖
  • NetBeans

    NetBeans 是一个始于 1997 年的 Xelfi 计划,本身是捷克布拉格查理大学的数学及物理学院的学生计划。此计划延伸而成立了一家公司进而发展这个商用版本的 NetBeans IDE,直到 1999 年 Sun 买下此公司。Sun 于次年(2000 年)六月将 NetBeans IDE 开源,直到现在 NetBeans 的社群依然持续增长。

    78 引用 • 102 回帖 • 672 关注
  • Laravel

    Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计,是一款崇尚开发效率的全栈框架。

    20 引用 • 23 回帖 • 723 关注
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    238 引用 • 224 回帖
  • Webswing

    Webswing 是一个能将任何 Swing 应用通过纯 HTML5 运行在浏览器中的 Web 服务器,详细介绍请看 将 Java Swing 应用变成 Web 应用

    1 引用 • 15 回帖 • 619 关注
  • 倾城之链
    23 引用 • 66 回帖 • 138 关注
  • abitmean

    有点意思就行了

    30 关注
  • Typecho

    Typecho 是一款博客程序,它在 GPLv2 许可证下发行,基于 PHP 构建,可以运行在各种平台上,支持多种数据库(MySQL、PostgreSQL、SQLite)。

    12 引用 • 65 回帖 • 453 关注
  • Solo

    Solo 是一款小而美的开源博客系统,专为程序员设计。Solo 有着非常活跃的社区,可将文章作为帖子推送到社区,来自社区的回帖将作为博客评论进行联动(具体细节请浏览 B3log 构思 - 分布式社区网络)。

    这是一种全新的网络社区体验,让热爱记录和分享的你不再感到孤单!

    1433 引用 • 10052 回帖 • 484 关注
  • jsoup

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

    6 引用 • 1 回帖 • 482 关注
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 353 关注
  • 资讯

    资讯是用户因为及时地获得它并利用它而能够在相对短的时间内给自己带来价值的信息,资讯有时效性和地域性。

    55 引用 • 85 回帖
  • PWA

    PWA(Progressive Web App)是 Google 在 2015 年提出、2016 年 6 月开始推广的项目。它结合了一系列现代 Web 技术,在网页应用中实现和原生应用相近的用户体验。

    14 引用 • 69 回帖 • 150 关注