编译原理学习笔记(二)语言及其文法

本节主要介绍了字母表、符号串等概念及其运算,还有文法、语言、文法的分类、CFG的分析树、二义性文法等内容

参考自中国大学Mooc网上的哈尔滨工业大学的编译原理课程,用到的图也是从Mooc网中下载的原课程课件

字母表

一个字母表是一个有穷符号集合,符号包括字母、数字、标点符号等,ASCII字符集和Unicode字符集都是字母表。

字母表上的运算

既然是集合,那么就有运算。

字母表上的乘运算:

字母表上的幂运算:

字母表的n次幂等于n个字母表相乘

字母表的正闭包:

字母表的正闭包是该字母表各个正次幂的并集

字母表的克林闭包:

在正闭包的基础上添加一个空串

符号串

串是字母表中符号的一个有穷序列

长度为0的串称为空串。

串上的运算

串的连接运算:

x和y的连接,是把y附加到x后面而形成的串,记作xy

串的幂运算

串s的n次幂,等于将n个s进行连接

文法

文法的定义

当我们要描述一种语言时,需要给出这种语言的所有句子,当句子的数目是有限时,则可以穷举;而当一门语言的句子是不可穷举时,就要给出可以表示它们的结构的描述方法,即 该语言的句子的组成规则。这种规则就是文法

以自然语言为例子,例如英语的一个文法:

文法的形式化定义:

G=(VT, VN, P, S),G代表文法,由终结符集合、非终结符集合、产生式集合和开始符组成。

  • VT 终结符集合

    终结符是文法所定义的语言的基本符号,有时也称为token

  • VN 非终结符集合

    非终结符是用来表示语法成分的符号,有时也称为“语法变量”

  • P 产生式集合

    产生式( production)描述了将终结符和非终结符组合成串的方法

  • S 开始符号

    第一条产生式的左部(该语法钟最大的语法成分)

在不引起歧义的情况下,可以只写产生式。

语言

有了文法(语言规则),如何判定一个词串是否是满足文法的句子?

推导和规约

  • 直接推导:用产生式的右部替换产生式的左部
  • 推导:经过n次直接推导表示n步推导(n=1即直接推导)
  • 规约:推导的逆过程即为规约(用产生式的左部替换产生式的右部)

回答前面的问题,可以有两种途径去判断某一词串是否是满足该文法的句子

  1. 句子的推导(派生)-从生成语言的角度:如果从文法的开始符号可以推导出这个词串,则它是该语言的一个句子。
  2. 句子的规约-从识别语言的角度:如果从这个词串可以规约出文法的开始符号,则它是该语言的一个句子。

句型和句子

如果从开始符S可以推导出a,则a是G的一个句型,如果句型中不包含非终结符,则它是一个句子

语言的形式化定义

由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言,记为L(G)

既然语言是一个集合,那么也有集合的运算:

文法的分类

  • 0型文法

    也称无限制文法/短语结构文法

    对于产生式几乎没有限制,只要产生式左部至少包含1个非终结符就可以了

    生成的语言成为0型语言

  • 1型文法

    也称上下文有关文法(CSG)

    在0型文法的基础上,进一步要求,产生式左部的长度<=产生式右部的长度,并且形如下图,注意a1和a2,用产生式的右部替换产生式的左部需要考虑上下文(a1、a2),这也是1型文法称为上下文有关文法的原因

    image-20200628224207772

    上下文有关文法中不包含空产生式,产生的语言成为上下文有关语言

  • 2型文法

    也称上下文无关文法(CFG)

    要求产生式的左部必须是一个非终结符,形如下图,用产生式的右部替换产生式的左部,不需要考虑上下文的情况

    生成的语言成为上下文无关语言

  • 3型文法

    又成为正则语言(RG)

    • 右线性文法,在2型文法的基础上,进一步对产生式的右部进行约束,每一个产生式的右部,要么是一个终结符号串w,要么是终结符号串w右边添加一个非终结符B

      image-20200628225134555
    • 左线性文法,在2型文法的基础上,进一步对产生式的右部进行约束,每一个产生式的右部,要么是一个终结符号串w,要么是终结符号串w左边添加一个非终结符B

      image-20200628225155906

    生成的语言成为正则语言,正则文法能描述程序设计语言的多数单词,例如下面的文法,描述字母打头的字母数字串(标识符)

    image-20200628225541668

四种文法之间的关系:

image-20200628225721720

CFG的分析树

正则文法虽然可以描述程序设计语言的大多数单词,但是它生成能力有限,它几乎描述不了程序设计语言中的句子构造,而上下文无关文法可以描述大部分程序设计语言的语法构造。

分析树是用来描述句子结构的。分析树的组成成分:根节点、内部节点、叶节点

分析树是推导的图形化表示,给定一个推导过程,对于推导过程中得到的每一个句型a,都可以构造出一个边缘为a的分析树。

image-20200628231032972

(句型的)短语

给定一个句型,其分析树中的每一棵子树的边缘称为该句型的一个短语

如果子树只有父子两代节点,那么这棵子树的边缘称为该句型的一个直接短语

直接短语一定是某产生式的右部,但产生式的右部不一定是给定句型的直接短语

例子:

image-20200628231846668

上图中,高人、民生、活水都是产生式的右部,但并不是该句型的直接短语,该句型的直接短语:提高、人民、生活、水平

二义性文法

如果一个文法可以为某个句子生成多棵分析树,则称这个文法是二义性的。

例如,一个条件语句的文法:

image-20200628232158861

对于句型if E1 then if E2 then S1 else S2,可以构造出两棵分析树:

image-20200628232300937

上面这个句型出现两棵分析树的原因是,句中有两个if,只有一个else,所以这个else既可以和第一个if匹配(分析树2),也可以和第二个if匹配(分析树1)。

因此可以增加一个消岐规则(正如大多数编译器所做的那样):每个else和最近的尚未匹配的if匹配,这样的话,就可以保留分析树1,删除分析树2,消除了二义性。

二义性文法的判定

对于任意一个上下文无关文法,不存在一个算法,判定它是无二义性的;但是可以给出一组充分条件,满足这组充分条件的文法是无二义性的(满足的话肯定无二义性,不满足的话也未必就是有二义性的)

0%