第二章 文法和语言

@东明 许 @软件工程@YA1714180

  • https://blog.csdn.net/weixin_30569001/article/details/95053339
  • https://blog.csdn.net/qq_39495105/article/details/85893564
  • https://www.docin.com/p-1323497964.html

一. 章节笔记

一. 文法的非形式讨论

1.文法

文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”(或称为“语法”)。

所谓文法是在 形式上 对句子结构的定义与描述,而未涉及语义问题。

2.语法规则

我们通过建立一组规则,来描述句子的语法结构。规定用“::=”表示“由……组成”。

例如:

<句子>::=<主语><谓语>

<主语>::=<代词>|<名词>

<代词> ::=你|我|他

<名词>::= 王民|大学生|工人|英语

<谓语>::=<动词><直接宾语>

<动词>::=是|学习

<直接宾语>::=<代词>|<名词>

3.由规则推导句子

有了一组规则之后,可以按照一定的方式用它们去推导或产生句子。

推导方法:从一个要识别的符号开始推导,即用相应规则的右部来替代规则的左部,每次仅用一条规则去进行推导。

<句子> => <主语><谓语>

<主语><谓语> => <代词><谓语>

…… ……

这种推导一直进行下去,直到所有带< >的符号都由终结符号替代为止。

说明

(1) 有若干语法成分同时存在时,我们总是从 最左的语法成分进行推导,这称之为最左推导。类似地还有最右推导(一般推导、规范推导)。

(2) 除了最左和最右推导,还可能存在其它形式的推导。

(3) 从一组规则可推出不同的句子

4.语法树

我们用语法树来描述一个句子的语法结构。语法树的叶子节点是句子的单词,非叶子节点的是语法成分。

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

1.文法的形式定义

文法G =(VN,VT,P,Z)

VN:非终结符号集

VT:终结符号集

P:产生式或规则的集合

Z:开始符号(识别符号) Z∈VN

注:

①V=VN ∪ VT 称为文法的字汇表

②规则:规则是一个有序对(U, x), 通常写为 U ::= x 或U→x(其中U∈VN,x∈V* 因此也有|U| = 1且|x| >= 0)

③给定一个文法,实际只需给出产生式集合,并指定识别符号。(识别符号一般约定为第一条规则的左部符号)

例:无符号整数的文法:

G[<无符号整数>]=(VN,VT,P,Z)

VN={<无符号整数>,<数字串>, <数字>}

VT = { 0, 1, 2, 3, … 9 }

P = {<无符号整数> → <数字串>

<数字串> → <数字串> <数字>

<数字串> → <数字>

<数字> →0

<数字> →1

…………

<数字> →9 }

Z = <无符号整数>

2.推导的形式定义

一步推导

:当符号串已没有非终结符号时,推导就必须终止。因为终结符不可能出现在规则左部,所以将在规则左部出现的符号称为非终结符号。

多步推导

任意步推导

规范推导

直观意义上:规范推导=最右推导

3.语言的形式定义

对于文法G[Z]:

(1)句型x:由开始符号Z经任意步推导得到x,且x∈V*;

(2)句子x:由开始符合Z经1多步推导得到x,且x∈VT*

(3)语言L:所有根据该文法推到得到的句子组成的集合

形式语言理论可以证明以下两点:

(1)G →L(G):已知文法,求语言,通过推导;

(2)L(G)→G1,G2,……,Gn:已知语言,构造文法,无形式化方法,更多是凭经验。

等价文法:G和G’是两个不同的文法,若 L(G) = L(G’) ,

则G和G’为等价文法。

4.递归文法

①递归规则:规则右部有与左部相同的符号

对于 U::= xUy

若x=ε,即U::= Uy,左递归;

若y=ε,即U::= xU,右递归。

②递归文法:文法G,存在U ∈VN

if U=+=>…U…, 则G为递归文法(自嵌入递归);

if U=+=>U…, 则G为左递归文法;

if U=+=>…U, 则G为右递归文法。

③左递归文法的缺点:不能用自顶向下的方法来进行语法分析

④递归文法的优点:可用有穷条规则,定义无穷语言

5.句型的短语、简单短语和句柄

给定文法G[Z], w::=xuy∈V+,为该文法的句型,

若 Z==> xUy, 且U=+=>u, 则u是句型w相对于U的短语;

若 Z==> xUy, 且U==>u, 则u是句型w相对于U的简单短语。

其中U ∈Vn,u ∈V+,x, y ∈V*

短语的直观理解:短语是前面句型中的某个非终结符所能推出的符号串

句柄:任一句型的最左简单短语称为该句型的句柄

给定句型找句柄的步骤:短语-> 简单短语-> 句柄

注意:短语、简单短语是相对于句型而言。一个句型

可能有多个短语、简单短语,但句柄只能有一个。

三. 语法树与二义性文法

1.判断二义性文法

依据:文法所能产生的句子,可以用不同的推导原则(使用产生式顺序不同)将其推导出来。如果文法是非二义性文法,那么语法树的生成规律不同,但最终生成的语法树形状完全相同;如果文法是二义性文法,那么最终生成的语法树形状有可能不相同。

方法1:若对于一个文法的某一句子存在两棵不同的语法树(或两个不同的 规范推导);或者自底向上看,对于同一个规范句型,存在两个不同的句柄。则该文法是二义性文法,否则是无二义性文法。

方法2:即不改变二义性文法,而是确定一种编译算法,使该算法满足无二义性充分条件。

文法二义性的判定??:在理论上已经证明:文法的二义性是不可判定的,即不可能构造出一个算法,通过有限步骤来判定任一文法是否有二义性。解决方法:提出一些限制条件,称为无二义性的充分条件。当文法满足这些条件时,就可以判定文法是无二义性的。

2.子树与短语

子树:子树由语法树中的某个结点(子树的根)连同它向下派生的部分所组成。

关系:某子树的末端结点按自左向右顺序为句型中的符号串,则该符号串为该句型的相对于该子树根的短语。

3.规约:自下而上地修剪子树的末端结点,直至把整棵树剪掉(留根),每剪一次对应一次规约。

规范规约:对句型中最左简单短语(句柄)进行的规约称为规范规约。

:规范规约与规范推导 互为逆过程

规范句型:通过规范推导或规范规约所得到的句型称为规范句型。

四. 文法相关的其它知识

1. 句子的分析

句子的分析是词法分析和语法分析所要做的工作

任务:给定G[Z]: S ∈ VT, 判定是否有S ∈ L(G[E])

2. 文法的实用限制

有害规则:若文法中有如U::=U的规则,则这就是有害规则,它会引起二义性。(我推我自己)

多余规则

(1)在推导文法的所有句子中,始终用不到的规则。即该规则的左部非终结符不出现在任何句型中。(用不到)

(2)在推导句子的过程中,一旦使用了该规则,将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。(死胡同)

若某文法中无有害规则或多余规则,则称该文法是 压缩过的

3. 文法的其他表示法

1.扩充的BNF表示:

BNF的元符号: <, >, ::=, |

扩充的BNF的元符号: <, >, ::=, |, {, }, [, ] (, )

  1. { t }:t可重复连接0到任意多次。如果有限制(上标m,下标n),则可重复连接n到m次。
  2. [ t ]:t可有可无。
  3. ( ):元符号,注意不要与VT混淆。

2.语法图

3.文法和语言的分类

形式语言:用文法和自动机所描述的没有语义的语言。

语言定义:L(G[Z]) = { x | x∈Vt*, Z =+=> x }

文法定义:乔姆斯基将所有文法都定义为一个四元组:

G=(VN,VT,P,Z)

VN:非终结符号集

VT:终结符号集

P:产生式或规则的集合

Z:开始符号(识别符号) Z∈Vn

文法和语言分类

文法和语言分类:0型、1型、2型、3型

这几类文法的差别在于对产生式施加不同的限制。

(1)2型文法与BNF表示相等价。

(2)3型语言(L3)又称正则语言、正则集合

(3)四种语言的关系:

二. 直播课笔记

教学目的、要求:

本章是编译原理课程的理论基础,要求理解文法、语言、规范推导、规范归约和短语、简单短语、句炳的基本概念;掌握语言的求解方法、文法的二义性与递归性的判断方法及句型的分析方法。由于编译程序是将高级语言源程序转换成较低–级的目标程序或机器语言,因此为了构造程序设计语言的编译程序,熟悉高级程序语言的语法和语义是必须的。众所周知,任何一个程序设计语言都包含语法、语义和语用三个方面,而阐明语法的一个工具是文法,这是形式语言理论的基本概念之一一。本次课将介绍文法和语言的直观概念,重点介绍构成文法的基本单位“符号和符号串”的有关问题。

其中用到的EBNF元符号含义如下:

●<>:用尖括号括起来的中文字表示语法构造成分,或称语法单元;而用尖括号括. 起来的英文字表示一类词法单元。 ●::=:表示左部的语法单位由右部定义,可读作“定义为”。

●|:表示“或”,即多选项。

●{}:用花括号括起来的成分可以重复0次到任意多次。

●[]:用方括号括起来的成分为任选项,即出现一次或不出现。

2.1 文法的直观概念

句子“张明是学生”的识别过程:陈述句的语法、句子的识别过程、指出语义的重要性(亦即符合语法的句子未必符合语义)

a) 语法:对语言结构的定义;

b) 语义:语言的含义;

c) 语用:从使用的角度描述语言。 形式语言理论是编译的理论基础。

<句子>::=<主语><谓语>

<主语>::=<名词>|<代词>

<名词>::=张明|学生|工人 //慎用省略号

<代词>::=我|你|他|她|它|她们|他们|它们 ——终结符 //慎用省略号

<谓语>::==<动词><直接宾语>

<动词>::=是|学习 //慎用省略号

<直接宾语>::=<名词>|<代词>

<……>非终结符 a::=β 规则/产生式 <名词> 开始符

‘::=’ 可为 → a→β

———— 规则 有限的 描述无线的句子

::=读作 “定义为”

<句子>=><主语><谓语> => “换成”

=><名词><谓语>

=>王明<谓语>

=>王明<动词><直接宾语>

=>王明是<直接宾语>

=>王明是学生

2.2 符号与符号串

2.2.1 基本概念:

  1. 字母表 : 形式符号的非空有穷集合
  • Σ 形式符号的全体
  • 英文{a,b,c, …,z,A,B,C,…,Z}
  • 中文:笔画–字–词–句
  1. 符号/字符 : 字母表中的元素
  2. 符号串 : Σ 中字符构成的一个有限序列

2.2.2 符号串的运算及性质(单词、字的运算)

  1. 长度 : |α| α中的字符个数 ≥0; 空串 ε
  2. 头、尾、固有头和固有尾(也称为:前缀、后缀、真前缀、真后缀)

[Z=xy x头、前缀 尾、后缀]

Z=xy x是头、前缀;y是尾、后缀:

x≠ε,y是固有尾/真后缀y≠ε ,x是固有头/真前缀

|α|=n,头、尾各有n+1

|α|=n,头、尾各有n+1,固有头 固有尾 各有n个

c. 连接 : a,β是符号串 a·β称为a与β的连接

性质 :

α·(β·γ)=(α·β)·γ ——结合律

α·ε=ε·α=α ——ε是单位元

|α β|=|α|+|β|

d. 幂 : α自身连接n(n≥0)称为α的n次幂

性质 :

e.

2.2.3 符号串集合的运算

  1. 并运算∪ ———集合的∪
  2. 连接 ·

性质:

B={α β|α∈A,β∈B}

A·(B·C)=(A·B)·C ——结合律

A·{ε}={ε}·A=A ——ε是单位元

c. 幂 : 符号串集合A自身连接n(n≥0)称为A的n次幂

性质 :

2.2.4 闭包运算 Σ

  1. Kleene

b. 正闭包

c. 两者的关系

2.3 文法和语言的形式定义

2.3.1 规则(重写规则、产生式、生成式)

  • 一个规则是一个二元组 , 通常写作a::=β或a→β
  • a称为规则的左部,β称为规则的右部,→(:=)读作“定义为”, 这是一条关于a的规则 (产生式)
  • a至少有一个非终结符

2.3.2 定义3.1 : 文法G定义为四元组

例子:

2.3.3 文法的表示形式:

2.3.4 推导

1. 直接推导

,称为V可直接推导出W,也称W可以规约到V,记为

2. 长度≥1的推导

存在一个推导序列:

,称为V可n步(≥1)推导出W,也称W可n步(≥1)规约到V,记为:

3. 长度≥0的推导

如果

,称为V可n步(≥0)推导出W,也称W可n步(≥0)规约到V,记为:

:设

,构造相应的文法

当n=1时,

命题为真

:设

,构造相应的文法

条件

改写为

2.3.5 句型和句子

,若

W是

的一个句型,若

,W是

的一个句子(终结符串):设

,构造相应的文法

,对应的文法:

——抽象:设

,构造相应的文法

对应的文法:

2.3.6 文法的等价性

是两个文法,若

,则称

等价:设

,构造相应的文法

——抽象

修改

限制

2.4 文法的类型

2.5 CFG和语法树

//数 CFG

2.5.1 语法树

设CFG,G[S],T是树,满足:

(1)根的标记是S;

(2)其余结点的标记是V中的符号

(3)若标记为A的结点有子树,且子树的根从左到右依次为

(4)叶结点从左到右连接是G[S]的y一个句型

也称为推导树

2.5.2 最左(右)推导

  • 最左推导:在推导的过程中,每次替换的非终结符都是最左边的,得到的句型“左句型”
  • 最右推导:在推导的过程中,每次替换的非终结符都是最右边的,得到的句型“右句型”,也称为规范句型(规范推导)

(最左推导)

(最右推导)

2.5.3 文法的二义性

  • 若G[S]的一一个句子有两个不同的最左(右)推导(两棵不同的语法树),则称G[S]是二义文法。

如if-else语句的文法是二义性的

  • 消除二义性(不能避免二义性)
  • 约定
  • 改写

修改了文法后,增加了推导的长度,但是我们避免了分析的不确定性

三. 课后作业

© 版权声明
THE END
喜欢就支持以下吧
点赞0赞赏
分享
评论 抢沙发

请登录后发表评论