第二章 高级语言及其语法描述

xiaoxiao2021-03-01  20

一、知识总结

(一)、程序语言的定义

程序语言的定义:程序语言主要由语法和语义两个方面定义。

1、语法

一个语言的语法是指这样的一组规则,用它可以形成和产生一个合式的程序。这些规则的一部分称为词法规则,另一部分称为语法规则(或产生规则)。

一般程序语言的语法单位有:表达式、语法、分程序、函数、过程和程序等等。

2、语义

一个语言的语义是指这样的一组规则,使用它可以定义一个程序的意义,这些规则成为语义规则。

(二)、高级语言的一般特性

高级语言的分类:强制性语言(过程式语言)、应用式语言(函数式语言)、基于规则的语言(Prolog)、面向对象语言(封装性、继承性、多态性)。

(三)、程序语言的语法描述

∑是一个有穷字母表,它每一个元素称为一个符号。∑上的一个符号串是指由∑中的符号构成的一个有穷序列。不包含任何符号的序列称为空字记为ℇ。∑*表示∑上所有符号串的全体空字也包括在其中

∑*的子集U和V的(连接)积定义为 UV = {ab|a∈U&b∈V} 即集合UV中的符号串是由UV的符号串连接而成的。一般 UV≠VU 但(UVW=UVW)。

规定V⁰ = {ℇ} V* = V0 U V1 U V2 U V3… V*是V的闭包V+ = VV*称V+为V的正则闭包

1上下文无关文法

文法是描述语言的语法结构的形式规则所谓上下文无关文法是所定义的语法范畴(或语法单位)是完全独立于这种范畴可能出现的环境的。

一个上下文无关文法G包括四个组成: 一组终结符号、一组非终结符号、一个开始符号、以及一组产生式。     形式上说,一个上下文无关文法G是一个四元式(VT,VN,S,P

终结符号(VT)是组成语言的基本符号,在程序语言中就是单词符号如基本字、标识符、常数等。 从语法分析的角度看是一个语言不可再分的基本符号

非终结符号(VN)(也称语法变量)用来代表语法范畴

开始符号(S) 是一个特殊的非终结符号,它代表所定义的语言中我们最感兴趣的语法范畴

产生式 (P) 是定义语法范畴的一种书写规则。一个产生式的形式是 A→ α

2、语法分析树与二义性

可以用一张图来表示一个句型的推导,这种表示称为语法分析树。

如果一个文法存在某个句子对应两颗不同的语法树,则称这个文法是二义的。

作为描述程序语言的上下文无关文法,对其的限制:

第一、文法中不含任何 P->P 形式的产生式,因为,这种产生式除了引起二义性外没有任何用处。

第二、每个非终结符P必须有用处。

3、形式语言鸟瞰

乔姆斯基把文法分成4种类型 0型、1型、2型、3型。 0型强于1型,1型强于2型,2型强于3型。这几类文法的差别在于对产生式施加不同的限制。0型文法也称短语文法。1型文法也称上下文有关文法。2型文法称上下文无关文法。3型文法称正规文法。

二、习题:

62)最左推导:

NNDNDDNDDDDDDD0DDD01DD012D0127

NNDDD3D34

NNDNDDDDD5DD56D568  

最右推导:

NNDN7ND7N27ND27N127D1270127

NNDN4D434  

NNDN8ND8N68D68568  

三、感受:

编译原理的第二章感觉概念性的东西比较多,而且理解上有一定难度。首先需要将概念性的知识点,进行仔细总结归纳理解记忆。其次尤其需要提高课堂效率,及时理解,认真做课后习题,及时将知识点及该章对应题型归纳总结。

转载请注明原文地址: https://www.6miu.com/read-3350117.html

最新回复(0)