【编译原理】高级语言及其语法描述

  • 日期:03-15
  • 点击:(1237)


本文列举了高级语言宫及其语法描述(1)高级语言的定义(2)高级语言的一般特征(1),高级语言的分类(2),数据类型和操作(3),语句和控制结构(3)程序语言的语法描述(1),几个重要的概念(2),上下文无关语法(3),语法树和语法的歧义

高级语言宫及其语法描述

(1)程序语言的定义

编译器为了正确翻译程序,有必要对程序设计进行定义和描述语言的描述从三个方面考虑(简而言之):

语法:它是语言结构的定义(什么样的符号序列是合法的);定义语言形态和语法的形式规则;

语义:描述语言的意义;定义单词符号的含义和语言的语法单位;

语用学:它从用法的角度描述语言。定义使用语言组件的编程技术和方法。它将语言的基本概念与语言的外部世界联系起来(如数学概念或计算机对象和操作)。

例如,赋值语句s=2* 3.1416* r* (r h)的非形式描述如下:

语法:赋值语句由一个变量组成,后跟赋值号“=”,后跟表达式;

语义:首先计算语句右边的表达式的值,然后将结果发送到左边的变量中;

语用学:赋值语句可以用来计算和保存表达式的值。

programming language的定义是实现语言编译器的基础,也是语言用户的用户手册。程序语言是一种符号语言,即符号系统,主要由语法、语义和语用三个方面来定义。

1。语法

任何语言程序都可以被视为一个特定的字符串(有限序列)。

语言定义了程序的形式结构。语法规则指的是一组规则,一个正式的(合法的)程序可以通过这些规则形成和生成。这些规则中的一些被称为词汇规则,另一些被称为语法规则(或生成规则)。

字母表是一个有限的字符集。字符集中的字符是可能出现在语言程序中的字符。它们是语言程序中单词的组成部分。

词汇规则定义了语言程序中单词符号的形成规则。也就是说,什么样的字符串是合法的单词。例如标识符、数值常数、运算符等。描述词汇规则和词汇分析的有效工具是形式语法、形式语法和有限状态自动机理论。

语法规则定义了语言程序中语法单元的形成规则。通用语言的语法单位包括表达式、语句、子程序、函数、过程和程序。描述语法规则和解析的一个有效工具是上下文无关语法。

语法规则和词汇规则定义了程序的形式结构,定义语法单元的意义是一个语义问题。

2。语义

对于一种语言,不仅要给出它的词汇和语法规则,还要定义它的单词符号和语法单位的意义。这是语义问题。没有语义,语言只是符号的集合。

language的语义指的是这样一组规则,它们可以用来定义程序的含义。这些规则被称为语义规则。

程序语言的每个组成部分(语法范畴)都有两层含义:抽象逻辑和计算机实现。前者描述了数学中的逻辑意义,而后者关注的是它在计算机中表示和实现的可能性和效率。

语义可以用两种方式来描述。一种是自然语言描述,但它存在隐性错误、模糊性和不完整性的缺陷。另一种是正式描述。

形式语义学有许多分支,如操作语义学、代数语义学、公理语义学、指称语义学等。它们使用不同的形式系统来描述语义问题,但目前还没有公认的形式系统,因此没有实用的自动语义分析方法。

编译器中常用的语义分析方法是基于属性语法的语法导向翻译。

指语法分析中确定的语法单位的语义分析和翻译。描述语法时,将它们的属性计算规则添加到定义的语法类别中。属性可以是信息,例如t

高级语言可以分为以下几类:

1。命令式语言,也称为过程式语言,具有命令驱动和面向语句的特点。例如,C和pascal属于这种语言。

2。应用语言(也称为功能语言)关注程序所表达的功能。该程序的开发过程是从现有的函数构造更复杂的函数。程序的执行是函数的嵌套或递归调用。例如,LISP和ML就属于这种语言。

3。基于规则的语言也称为逻辑编程语言。程序的执行过程是检查某些条件(谓词逻辑表达式),并在满足这些条件时执行适当的操作。例如,序言就属于这种语言。

4。面向对象语言支持抽象、封装、继承、多态和动态绑定。编程的方法是将数据和操作封装在一起以形成对象,扩展和继承简单对象以构造更复杂的对象,并通过向对象发送消息来获得动作的执行。例如,C、Java和C#都属于这种语言。

2,数据类型和操作

数据类型通常包括以下三个元素:

用于区分不同类型的数据对象;

这种类型的数据对象可以有;

可以作用于类型的数据对象。

编程语言从初始到复杂:

1。基本数据类型

数字数据、逻辑数据(布尔类型)、字符数据、指针类型。

2。数据结构

数组:由相同类型的数据组成的n维矩形结构。它可以分为定式数组和变量数组。数组的内部信息向量包括:第一个地址、维度、每个维度的上限和下限以及元素类型。

Record:由已知类型(可能不同)的数据组成的结构。记录中每个字段的偏移量是其相对于记录头地址的地址偏移量。

字符串、表、堆栈和队列:对数组或记录组合具有受限访问的复合结构。

关于标识符和名称:

虽然名称和标识符在形式上很难区分,但这两个概念本质上是不同的。例如,对于“PI”,我们有时说它是一个名称,有时说它是一个标识符。标识符是一个无意义的字符序列,但名称有明确的含义和属性。圆周率作为一个标识符只不过是两个字母的并置,但圆周率作为一个名称经常被用来表示圆周率。在{ level language }中,通常使用“本地名称”和“全局名称”,但是“本地标识符”和“全局标识符”之间几乎没有区别。

3。语句和控制结构

除了提供数据表示、构造和操作机制,编程语言还具有可执行语句。控制结构定义了语句的执行顺序。一种语言提供的控制结构集对可读和可维护软件的编写有很大的影响。

(1)表达式

表达式由操作数和运算符组成。操作数,也称为操作数,可以是数据引用或函数调用;运算符包括算术运算符、逻辑运算符、关系运算符等。运算符之间有特定的优先级和组合规则。

(2)语句

1,赋值语句:变量名=表达式

2,控制语句:无条件转移语句,条件语句,循环语句,过程调用语句,返回语句

3,描述语句:用于定义名称的性质。

4,简单句和复合句:句子1;报表2;报表3;(3)程序语言

1和几个重要概念

的语法描述为以下内容铺平了道路。

(1)字母表和符号串

1。字母表)

2。符号)

3。符号串

(2)符号串

1的运算。符号串

2的连接。集合

3的乘积。符号串

4的电源操作。设定

5的电源操作。集合A的正闭包A和闭包A*

按以下顺序看这些内容:

(1)字母表

(1)字母表

字母表是一个非空的有限元素集合

[,例如] ∑={a,b,c}

∑是一个由三个元素A,b,c组成的字母表

字母表至少包含一个元素。字母表中的元素可以是字母、数字或其他符号。

不同的语言有不同的字母。

英语字母表由26个字母、数字和标点符号组成。C语言的字母表由字母、数字和一些特殊符号组成。

(2)符号(字符)符号

字母表中的元素称为符号或字符。

[,例如] ∑={a,b,c}

a,b,c是字母表中的符号∑。

(3)字符串符号(单词)字符串

符号的有限序列称为字符串。

例如[]用字母表∑={a,b,c},

有符号串a,b,ab,ba,CBA,ABC,

(a、b、ab、ba、CBA、ABC等。是字母表上的所有符号串吗?)

符号串总是建立在特定的字母表上,并且只能由字母表上的有限符号组成。

符号串中符号的顺序非常重要,例如,ab和ba是字母表∑上两个不同的符号串。

不包含任何符号的符号字符串称为空符号字符串,由(ε)表示,即空符号字符串由0个符号组成,其长度|ε|=0

请看下面符号字符串的操作

符号字符串的连接

如果X和Y是符号字符串,则字符串xy称为它们的连接。也就是说,xy是通过在X符号串之后写入Y符号串而获得的符号串。

例如[]让x=ABC,y=10a。

那么xy=ABc10a

那么yx=10abc

是特殊的。对于任何符号串x,都有:

ε x=x ε=x

(2)集合积积

设A和B是符号串的集合,那么A和B的积定义为:

AB={xy | x ∈ A,y ∈ B}

也就是说,集合AB中的符号串由A和B的符号串连接起来,

例如[]假设A={a,B},B={c,d}

然后ab={AC,ad,BC, BD}

对于任何符号串x:

ε x=x ε=x

因此,对于任何集合a,都有{epsilon} a=a {epsilon}=a

这里应该说

phi表示空集合

phi={ }

注意:epsilon是符号串,不是集合{epsilon}表示由空符号串ε组成的集合,但是这样的集合不是空集合phi,即phi不包含空串。 ε ∈ φ的幂

(3)符号串

(4)集合的幂

(5)正闭包A和闭包A*

正闭包:正闭包

闭包:星形闭包

2

每种正式语言都是由所有符号串组成的集合,这些符号串是根据某个字母表上的某些规则形成的。任何字母表上的符号串集合都可以定义一种形式语言。

[(例如]

C语言是字母表上带有基本符号的符号串的集合。每个C语言程序都是基本符号的符号串。描述

形式语言有两种方法:

第一种方法是当语言是有限集合时,使用枚举来表示语言。

[示例]用字母表A={a,b,c},然后

L1={a,b,c}

L2={a,aa,ab,AC}

L3={c,cc}

都表示字母表A上的一种形式语言。

由于这三种语言都是有限符号串的集合,所以它们的所有句子都可以被枚举来表示该语言。

第二种是当语言是无限集合时,需要设计语法来描述无限集合的语言。

grammar是一个形式规则

(2)grammar

1的形式定义,rule

该规则的作用是告诉如何在规则中使用符号字符串来生成语言中的序列。一套规则定义了一种语言的语法结构。

production: non-terminator中的符号

non-terminator(也称为语法变量)用于表示语法类别。例如,“算术表达式”、“布尔表达式”、“x值语句”、“子程序”、“过程”等是当今编程语言中常见的语法类别。出现在生产公式可以导出符号或符号串的符号中,即每个非终止符代表一个特定的符号串。使用大写字母或尖括号括起非终止符。

终端:不属于非终端的符号。它们是构成语言的基本符号。它们是一种语言不可分割的基本符号,只出现在生产形式的正确部分。通常用小写字母。

2。语法

VT可以理解为一组符号,就像英语单词一样。

VN可以理解为一组语法单位,如英语语法单位,如主语和谓语。

S是语法的起始符号

每条规则都是一种生成类型,所有规则的集合都被记录为p.

production(也称为生成规则或缩写规则)是定义语法类别的书写规则。

简化书写惯例:

3.语言的形式定义

(1)直接派生

(2)派生

4,广义派生

直接派生长度为1,派生长度大于或等于1,广义派生长度大于或等于0

5,句型和句子

句型仅包含结束符号为句子。语法G产生的整个句子是一种语言。

6,Language

7,规范推导和规范约简

任何由语法定义的句子类型和句子都可以根据语法进行推导,但是相同的句型(句子)可以通过不同的推导序列进行推导,因为在推导过程中选择的非终止符的顺序是不相关的。

最左边的派生意味着直接为派生序列中的每个步骤派生α=β,并替换α中最左边的非终止符。

最右边的派生意味着直接为派生序列中的每个步骤派生α=β,并替换α中最右边的非终止符。

最右边的派生也称为规范派生,从规范派生中派生的句型称为规范句型。

每个句子都有标准派生词,但是这个结论对句型来说并不正确。

reduction是演绎的逆过程,reduction是与演绎相反的概念,reduction是用规则的右边部分替换句子模式中的非结尾的过程,reduction是用非结尾替换句子模式中的子串的过程。

范数导出的逆过程称为最左约简,也称为范数约简。

8。递归规则和递归语法

递归规则是指在规则的左边和右边有相同的非终止符的规则。

如果语法中有规则A → A …就叫规则左递归

如果语法中有规则A→A,就叫规则右递归

如果语法中有规则A→A…就叫规则递归

语法递归。它指的是语法中任何非终结的递归。如果可以建立派生过程,并且非终结符本身出现在派生的符号字符串中,则语法是递归的,否则是非递归的。在

语法中使用递归规则,因此可以用有限的规则定义无限多的语言集。

以下情况非常特殊

语法使用递归规则,这使得用有限的规则描述无限集合语言成为可能。

如果您不使用递归规则来定义语法,您需要使用无限多的规则来表示无限集合的语言。

当一种语言是无限集合时,定义该语言的语法必须是递归的。

编程语言是无限集合,所以描述它们的语法必须是递归的。

9,短语,直接短语和句柄

短语,直接短语和句柄是以下章节的内容。如果你在这里不理解它们也没关系。

首先看看短语和直接短语

短语是句型的一部分

handle

句型最左边的直接短语称为句型的句柄。

句柄功能:

(1)它是一个直接短语,即规则的右边部分

(2)它有最左边的字符。

注意:

短语、直接短语和句柄都是特定的句子类型,尤其是句型中的符号串可以构成短语和直接短语。如果没有特定的句型,谈论短语、直接短语和句柄是没有意义的。

3。语法树和语法

1的歧义。派生树的生成

(1)语法树的生成

语法树的构造是从语法的开始符号开始的派生过程。因为语法的每个句型(句子)都有一个派生词,所以语法的每个句型(句子)都有一个对应的语法树。

例如:

Method 1:

将标识符号作为根节点,并为从其直接派生的每一步向下绘制一个分支。分支节点的标记是在直接派生中被替换的非终端的名称。根据这种方法,向下一步一步地画出对应于直接派生的每个步骤的分支,直到在语法树上没有分支可画,并且构造过程结束。

Method 2:

语法树中从左到右的结束节点形成由语法树表示的推导符号串。

句型(三)* I-I最左边和最右边的派生得到相同的语法树。

换句话说,一个合成器

语法树的子树是由一个节点和所有分支组成的部分。

参考派生树

(3)简单子树

语法树简单子树是指只有一级分支的子树。

4)子树和短语的关系

根据子树的概念,短语、直接短语和句型句柄的直观解释如下:

短语:子树的末端节点形成的符号串是相对于子树的根的短语。

direct短语:由简单子树的结束节点形成的符号串是相对于简单子树的根的直接短语。

Handle:最左边的简单子树的结束节点形成的符号字符串就是句柄。对于语法G[E],使用语法树查找短语、直接短语和句型句柄(t I) * I-f.

2,语法

的歧义对应于语法G中任何句子类型的派生序列,并且语法树总是可以构造的。

grammar g[e]:e→e | e ~ e |(e)| I

这个语法的一个句子I * I I I有两个不同的最左边的派生词,对应于两个不同的语法树。

如果一个语法有一个句子对应于两个不同的语法树,这个语法被认为是不明确的。换句话说,如果一个语法有一个句子,它有两个不同的最左边的派生词或两个不同的最右边的派生词,那么这个语法就是歧义的。

含糊的语法会导致编译器执行中的问题。对于语法不明确的句子,当编译器对其结构进行语法分析时,会产生两种或两种以上不同的理解。语法结构的不确定性将不可避免地导致语义加工的不确定性。

解决方法之一:使用语法对等来消除语法歧义。

3。消除语法歧义

(1)原语法规则不变,只增加了一些非形式语法规则。语法g:e→e | e ~ e |(e)| I

不改变现有的四条规则,只增加运算符的优先顺序和组合规则,即*优先,*服从左组合。

这样,语法[E]中的第一*三句只有一个语法树,从而避免了语法的歧义。

(2)构造一个等价的非歧义语法;也就是说,排除歧义,重写原始语法。

例如,语法g:e→e | e ~ e |(e)| I

1,试图使一个规则弱于绑定;让它出现在派生序列的前面(语法树的上层);

2,要进行规则绑定;让它出现在派生序列之后(语法树的下层);

Specific Practice:引入非终结符的歧义性

Language意味着没有没有歧义的语法G,使L(G)成为语言本身。

注:语法歧义和语言歧义是两个不同的概念。G和G’可能有两种不同的语法,其中一种是模棱两可的,另一种是模棱两可的,但有L(G)=L(G’)。

对于一种程序语言,人们通常希望它的语法是模糊的,因为人们希望对每个语句的分析是唯一的。

歧义是不可确定的。也就是说,没有算法可以在有限的步骤中确定语法是否模糊。

4。“语法和语言的分类”乔姆斯基在1956年建立了形式语言理论。形式语言理论发展迅速。

对计算机科学有深远的影响;特别是,它在以下几个方面起着重要的作用:

编程语言设计

乔姆斯基将语法分为四种类型,即类型0、类型1、类型2和类型3。这些语法类型之间的区别在于,对产出形式的限制从0类增加到3类,但它们表达语言的能力反过来被削弱了。

0-类型语法(无限制语法,短语语法)

乔姆斯基将语法分为四种类型,即类型0、类型1、类型2和类型3。这些语法类型之间的区别在于,对产出形式的限制从0类增加到3类,但它们表达语言的能力反过来被削弱了。

0-类型语法(无限制语法,短语语法)

从定义中可以看出,α和β是由语法的终结符和非终结符组成的符号串,β可以为空,而α不能为空,也就是说,| α | | β |

类型0语法也称为无限制语法,因为它没有强加任何限制,相应的语言称为无限制语言。

非终结符A永远不会消失,也不能终止。键入

1语法(与上下文相关的语法)

在推导过程中,连续的N A总是最前面的,连续的N B和后面的N C不能生成,但可以生成彼此隔开的N B和C。

使用规则cB→Bc向前移动所有插入的C中的B。

然后使用规则bB→bb删除所有b。最左边的

aaabbbccc

派生过程:

rule CB→cc和bB→bc是用c

ruleca替换b→AC是在插入的c中向前移动a,

最后使用规则bA→bb删除所有a并用b替换它。键入

2语法(上下文无关语法)

can当规则将A替换为β时,它与A的上下文无关,即没有必要考虑A在上下文中的出现。

也称为上下文无关语法,相应的语言称为上下文无关语言。

通常定义编程语言的语法是上下文无关语法,所以上下文无关语法和相应的语言是我们的主要研究对象。

A和B

和A

or:S→Ab | BaA→A | aS | SaB→B | Bs | Sb

3-类型语法(常规语法)

右行语法和左行语法都称为类型3语法或常规语法,由类型3语法描述的语言称为类型3语言或常规语言。

通常定义编程语言词汇规则的语法是规则语法。

通过几个特殊的例子来体验语言和语法之间的关系。

将语法和转换

上下文无关语法用作程序语言的限制。以下几点仅限于它们:

第二点限制的解释

2 ')

每个非终结符P都必须是有用的。一方面,它意味着一定有一个含有P的句型;也就是说,从起始符号S开始,在推导S αPβ

之后讨论的语法假设满足上述两个条件。这种语法叫做简化语法。

如果编程语言的语法包含冗余规则,那么一定有错误,所以检查语法是否包含冗余规则是非常重要的。

最后附上发音表。