一、知识总结
(一)、程序语言的定义
程序语言的定义:程序语言主要由语法和语义两个方面定义。
1、语法
一个语言的语法是指这样的一组规则,用它可以形成和产生一个合式的程序。这些规则的一部分称为词法规则,另一部分称为语法规则(或产生规则)。
一般程序语言的语法单位有:表达式、语法、分程序、函数、过程和程序等等。
2、语义
一个语言的语义是指这样的一组规则,使用它可以定义一个程序的意义,这些规则成为语义规则。
(二)、高级语言的一般特性
高级语言的分类:强制性语言(过程式语言)、应用式语言(函数式语言)、基于规则的语言(Prolog)、面向对象语言(封装性、继承性、多态性)。
(三)、程序语言的语法描述
设∑是一个有穷字母表,它的每一个元素称为一个符号。∑上的一个符号串是指由∑中的符号所构成的一个有穷序列。不包含任何符号的序列称为空字,记为ℇ。用∑*表示∑上的所有符号串的全体,空字ℇ也包括在其中。
∑*的子集U和V的(连接)积定义为 UV = {ab|a∈U&b∈V} 即集合UV中的符号串是由U和V的符号串连接而成的。一般, UV≠VU ,但(UV)W=U(VW)。
规定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型文法称正规文法。
二、习题:
6(2)最左推导:
N⇒ND⇒NDD⇒NDDD⇒DDDD⇒0DDD⇒01DD⇒012D⇒0127
N⇒ND⇒DD⇒3D⇒34
N⇒ND⇒NDD⇒DDD⇒5DD⇒56D⇒568
最右推导:
N⇒ND⇒N7⇒ND7⇒N27⇒ND27⇒N127⇒D127⇒0127
N⇒ND⇒N4⇒D4⇒34
N⇒ND⇒N8⇒ND8⇒N68⇒D68⇒568
三、感受:
编译原理的第二章感觉概念性的东西比较多,而且理解上有一定难度。首先需要将概念性的知识点,进行仔细总结归纳理解记忆。其次尤其需要提高课堂效率,及时理解,认真做课后习题,及时将知识点及该章对应题型归纳总结。