编译原理笔记(二)文法和语言

这篇具有很好参考价值的文章主要介绍了编译原理笔记(二)文法和语言。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.文法的直观概念

文法概述:文法是对一种语言的句子的结构描述,是以有穷的集合刻画无穷的集合的一个工具。

2.符号和符号串

字母表的概念:字母表是元素的非空有穷集合,字母表中的元素称为符号,因此字母表也被称为符号集。

符号串的概念

  • 符号串的定义:由字母表中的符号组成的任何有穷序列被称为符号串。
  • 符号串的长度:符号串中包含的符号的个数称为符号串的长度。不包含任何符号的符号串被称为空串,用ε表示,其长度为0。
  • 符号串的头尾、固有头和固有尾
    • 头和尾:如果z=xy是一个符号串,那么x是z的头,y是z的尾;
    • 固有头和固有尾:如何x是非空的,那么y是固有尾;如果y是非空的,那么x是固有头。
  • 符号串的连接:设x和y是符号串,它们的连接xy是把y的符号写在x的符号之后得到的符号串。
  • 符号串的方幂:设x是符号串,把x自身连接n次得到的符号串称为符号串x的方幂。
  • 符号串集合:若集合A中的一切元素都是某个字母表上的符号串,则称A是该字母表上的符号串集合。
    • 符号串集合的乘积:两个符号串集合A和B的乘积为:AB={xy | x∈A且y∈B},也就是AB是满足x属于A,y属于B的所有符号串所组成的集合。
  • 字母表的闭包: 字母表Σ的闭包用Σ*表示,是该字母表上所有有穷长的串的集合。
    • 字母表的正闭包:将字母表Σ的闭包中删除空串ε,则得到的集合被称为字母表的正闭包,记作Σ+

3.文法和语言的形式定义

产生式(规则)的概念

  • 产生式的表示:形如α→β或α::=β的有序对。这里使用的符号读作“定义为”。
  • 左部和右部:α称为产生式的左部,β称为产生式的右部。

文法的概念:文法G定义为一个四元组(Vn,Vt,P,S)

  • 元组内容解释:Vn是非终结符集合,Vt是终结符集合,P是产生式的集合(Vn、Vt和P都要求非空)。S是识别符或开始符,是一个表示推导开始的非终结符,至少需要在一条产生式中作为产生式的左部出现。
  • 对产生式的要求:产生式的左部和右部都是非终结符集合和终结符集合的并集的闭包中的元素,并且要求左部至少包含一个非终结符。
  • 文法的简略表示:很多时候不用将一个文法用四元组的形式表示出来,而是只写出产生式,并约定用大写字母表示非终结符,用小写字母表示终结符。

推导的概念

  • 直接推导和直接归约:设α→β是文法G=(Vn,Vt,P,S)的一条产生式,x和y是V*中的任意符号,如果有符号串v和w满足:v=xαy,w=xβy,则说v直接产生w。称w是v的直接推导,或者说w直接归约到v。
  • 推导和规约:如果v可以通过一系列的直接推导获得w,则称v推导出w,或称w推导出v。连续使用的直接推导次数被称为推导长度。
  • 推导和规约的表示:直接推导使用一个粗箭头表示;推导在直接推导的箭头上增加了一个“+”号;也可以统一在直接推导的粗箭头上方加一个“*”号统一表示直接推导和推导。

句型、句子、语言、文法等价的概念

  • 句型的概念:设G[S]是一个文法,如果符号串x是从识别符号推导出来的,则称x是文法G[S]的句型。
  • 句子的概念:如果一个句型中只由终结符构成,那么这个句型被称为句子。
  • 语言的定义:一个文法G产生的语言是该文法产生的所有句子的集合,记作L(G)
  • 文法的等价:如果两个文法产生的语言完全相同,那么称这两个文法等价。

4.文法的类型

乔姆斯基文法分类:1956年乔姆斯基建立形式语言的描述,将文法分为0型、1型、2型和3型文法。这四类文法的区别在于对产生式施加的限制不同。

四种不同的文法

  • 0型文法

    • 文法别称:0型文法也被称为短语文法。
    • 产生式限制:产生式的左部至少含有一个非终结符。
  • 1型文法

    • 文法别称:1型文法也被称为上下文有关文法。
    • 产生式限制:产生式均满足左部的长度小于等于右部的长度(除了S→ε之外)。
  • 2型文法

    • 文法别称:2型文法也被称为上下文无关文法。
    • 产生式限制:产生式的左部都是一个非终结符。
  • 3型文法

    • 文法别称:3型文法也被称为正规文法。
    • 产生式限制:每一个产生式都是A→aB或A→a的形式。

四种文法之间的关系:四种文法类型的定义是逐渐增加限制的。所有的3型文法都是2型文法,所有的2型文法都是1型文法,所有的1型文法都是0型文法。

四种文法生成的语言:0型、1型、2型和3型文法生成的语言分别被称为0型语言、上下文有关语言、上下文无关语言和正规语言。

5.上下文无关文法及其语法树

上下文无关文法和程序设计语言的关系:上下文无关文法有足够的能力描述现今程序设计语言的语法结构。

语法树(推导树)的概念

  • 语法树的作用:语法树是用于描述上下文无关文法的句型推导的直观工具。
  • 语法树满足的条件
    • 每个结点都有一个标记,此标记是V的一个符号;根的标记为S。
    • 如果一个标记为A的结点有一个除了自己之外的子孙,那么A一定是非终结符。
    • 如果结点n的直接子孙从左到右的顺序为n1 n2 n3…,其标记分别为A1 A2 A3…,那么一定存在一个产生式:A→A1 A2 A3 … AK。
  • 语法树的限制:语法树只表示了在某个推导过程中使用了哪个产生式和施用在哪个非终结符上,并没有明确施用产生式的顺序。

最左推导和最右推导

  • 最左推导:如果在推导过程中的任何一步a直接推导出b,都是对a的最左非终结符进行替换,则称这种推导方式为最左推导。
  • 最右推导:类似于最左推导,如果推导过程中都是对a的最右非终结符进行替换,则称这种推导方式为最右推导。在形式语言中,最右推导也被称为规范推导,所推导得到的句型称为规范句型(右句型)。

注意事项:一个句型对应不止一棵语法树;一个句型也不一定只有一种最左推导或最右推导。

文法和语言的二义性

  • 文法的二义性:如果一个文法中存在某个句子,它有两个不同的最左(最右)推导,则说这个文法是二义的。
  • 语言的先天二义性:如果产生上下文无关语言的每一个文法都是二义的,则说此语言是先天二义的。对于程序设计语言来说,常常希望它的文法是无二义的,因为希望对它的每个语句分析都是唯一的。

6.句型的分析

句型分析概述

  • 句型的分析就是识别一个符号串是否为某个文法的句型,是某个推导的构造过程。
  • 进一步说,当给定一个符号串时,试图按照某个文法的规则为该符号串构造推导或语法树,以此来识别它是否是该文法的一个句型。

编译中的句型分析:编译中的句型分析是指识别一个输入符号串是否为语法上正确的程序的过程。在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序,分析算法又被称为识别算法。可以分为自顶向下分析和自底向上分析两种方法:

  • 自顶向下的分析方法:从文法的开始符号出发,反复使用各个产生式,寻找匹配于输入符号串的推导。
  • 自底向上的分析方法:从输入符号串开始,逐步进行归约,直到归约到文法的开始符号。

短语的概念

  • 短语的定义:设G是一个文法,S是文法的开始符号。如果对于文法中的一个句型,且该句型中包含有一个非终结符A,而该非终结符A可以推导出一个句型B,那么就称B是该句型相对于非终结符A的短语。
  • 直接短语(简单短语)的定义:对于短语而言,如果非终结符A是直接推导出一个句型B,那么就称B是该句型相对于非终结符A的直接短语。
  • 句柄的定义:一个右句型的直接短语称为该句型的句柄。句柄的概念只适用于右句型。

7.有关文法实际应用的一些说明

有害规则和多余规则:在实际应用中,应该限制文法中不应该含有有害规则和多余规则。文章来源地址https://www.toymoban.com/news/detail-434343.html

  • 有害规则:左部和右部相同的产生式。之所以说这样的产生式有害,是因为它只会引起文法的二义性。
  • 多余规则:文法中所有句子的推导都用不到的产生式。分为两种形式进行出现。
    • 文法中有些非终结符不在任何规则的右部出现,这种非终结符被称为不可到达的。
    • 文法中存在不能推导出任何终结符的非终结符,这种非终结符被称为不可终止的。

到了这里,关于编译原理笔记(二)文法和语言的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 音视频开发之旅——音频基础概念、交叉编译原理和实践(LAME的交叉编译)(Android)

    本文章已授权微信公众号郭霖(guolin_blog)转载。 本文主要讲解的是 音频基础概念 、 交叉编译原理和实践(LAME的交叉编译) ,是基于 Android平台 ,示例代码如下所示: AndroidAudioDemo 另外, iOS平台 也有相关的文章,如下所示: 音视频开发之旅——音频基础概念、交叉编译

    2024年04月25日
    浏览(85)
  • 正规文法、正规表达式、有限自动机及其之间的转换(笔记)

    The Equivalent Transforming among RG, RE and FA A Grammar G is a quadruple (四元组):G = (V N , V T , S, P ) Where, V N is a finite set of nonterminals. V T is a finite set of terminals. S is the start symbol, S ∈ in ∈ V N . P is a finite set of productions (产生式). Regular Grammar (RG) (正规文法): α∈V N and β ∈V T ∪V T V N Regular Exp

    2024年02月08日
    浏览(40)
  • 【译】大型语言模型的直观解释

    原作:史蒂夫·纽曼 引子:我没有深入研究数学,而是解释了“为什么”它们被构建为“预测下一个单词”引擎,并提出了为什么它们会出现概念性错误的理论。   有很多文章解释了 ChatGPT 等大型语言模型 (LLMs) 的工作原理。然而,他们往往会深入研究那些与大多数用户无关

    2024年01月21日
    浏览(48)
  • 编译原理课程设计--C语言编译器

    源程序1: 源程序1词法分析结果: 与程序1语法分析结果(部分) 源程序1四元式: 源程序1优化后的四元式: action-goto表(部分) 文件目录: (1)掌握语义分析过程,即语法制导翻译过程。 (2)在语法分析的LR分析程序中的基础上添加程序,进行语义分析,生成源程序的四

    2024年02月08日
    浏览(56)
  • MarkDown学习笔记 直观全面详细

    为什么我们要学习 Markdown 呢?因为 Markdown 简单易学易上手,可以以纯文本格式编写文档,然后转换成有效的HTML文档,并且以导出 HTML 、Word、图像、PDF、Epub 等多种格式的文档,许多网站平台的文章、博客、论文均可用Markdown编写文章。 使用#号标记,可以表示1-6级标题, 随

    2024年01月22日
    浏览(46)
  • C语言枚举类型enum(全面详细直观)

    维基百科的理解: 枚举类型用于声明一组命名的常数,当一个变量有几种可能的取值时,可以将它定义为枚举类型。 定义:是指将变量的值一一列出来,变量的值只限于列举出来的值的范围内。 我的理解: 枚举类型就是将一些比较固定的值一一列举出来 ,比如一年有十二个

    2024年02月06日
    浏览(78)
  • 编译原理笔记(一)引论

    学习总结 :这一部分是编译原理的绪论部分内容,对编译程序的整体框架流程进行了介绍。内容均为概念,没有能够出大题的内容,个人认为考试前只需要对这些概念有一个基本的了解即可,而非将本章作为复习重点。 编译程序的地位 : 编译程序是现代计算机系统的基本组

    2024年02月05日
    浏览(36)
  • C 语言->编译和链接实现原理

    ✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉 🍎个人主页:橘橙黄又青-CSDN博客 今天学习 :浅学编译和链接内部实现原理 前提:本文是在gcc编译环境下学习,目前只是浅学习 在ANSI C的任何⼀种实现中,存在两个不同的环境。 第1种 是翻译环

    2024年01月20日
    浏览(41)
  • 编译原理1.1习题 语言处理器

    图源:文心一言 编译原理习题整理~🥝🥝 作为初学者的我,这些习题主要用于自我巩固。由于是自学,答案难免有误,非常欢迎各位小伙伴指正与讨论!👏💡 第1版:自己的解题,与AI老师的判卷~🧩🧩 编辑: 梅头脑🌸  审核: 文心一言 题源: 龙书《编译原理》 Alfre

    2024年01月17日
    浏览(40)
  • 大语言模型的预训练[1]:基本概念原理、神经网络的语言模型、Transformer模型原理详解、Bert模型原理介绍

    预训练属于迁移学习的范畴。现有的神经网络在进行训练时,一般基于反向传播(Back Propagation,BP)算法,先对网络中的参数进行随机初始化,再利用随机梯度下降(Stochastic Gradient Descent,SGD)等优化算法不断优化模型参数。而预训练的思想是,模型参数不再是随机初始化的

    2024年02月17日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包