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

1、第二章 高级语言及其语法描述 2.1 程序语言的定义(描述) 2.2 高级语言的一般特性 2.3 程序语言的语法描述2.1 程序语言的定义 语法： 语言的语法是指这样的一组规则，用它可以产生和形成一个合式的程序。 例如：变量的标示符要以非数字开头 语法分为词法规则和语法规则。 词法规则： 指单词符号的形成规则，单词符号包括：各种类型常数、标示符、算符和界符等。 词法分析工具：有正规式和有限自动机理论。 语法规则： 是语法单位的形成规则。 语法单位包括：表达式、语句、子程序、函数等。 语法规则描述工具有上、下文无关文法。 语义： 是指这样的规则，使用它可以定义一个程序的意义。 语义描述的方法：属

2、性文法的语法制导翻译方法。该方法接近形式化方法。 相同语句不同含义的例子： Z=X+Y可以表示整数相加和实数相加等不同的语义。 编译程序的就是要从基本的单词符号和语法单位分析程序的语义。2.2 高级语言的一般特性 高级语言分类： 过程式语言-命令驱动、面向语句，如C语言等。 函数式语言-从功能出发构造函数，如LISP等。 基于规则的语言-检查一定的条件，当他满足直，则执行适当的动作，如Prolog语言。 面向对象的语言-支持封装、继承和多态性等。2.3 程序语言的语法描述 基本概念： ：是一个有穷字母表，它的每个元素称为一个符号。 上的字（符号串）：是指由中的符号所构成的一个有穷序列。 ：不包

3、含任何符号的序列称为空字。 ：表示上所有字的集合，其中包括空字。 : 不包含任何元素的集合 = 集合运算： 集合的积运算：UV=|U&V Vn=VVV 其中V0= 集合的或运算：UV=|U ORV 集合的闭包运算：V=V0V1V2V3 集合的正规闭包：V+=VV2.3.1 上下文无关文法 文法：描述语言的语法结构的形式规则。 特点：这些规则必须是准确的，易于理解的，而且，应当有相当强的描述能力，足以描述各种不同的结构。 例如：- 上下文无关文法： 它所定义的语法范畴是完全独立于这种范畴可能出现的环境的。 一个上下文无关文法G包括四个组成部分： 一组终结符号 一组非终结符号 一个开始符号

4、 一组产生式 终结符号： 是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。 非终结符号： 用来代表语法范畴。如：语句A、表达式B等。 开始符号： 是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为“句子”或是“程序”。 产生式： 是定义语法范畴的一种书规则。 一个产生式的形式是A或A:= A：是非终结符号 ：是由终结符号或与非终结符号组成的一个符号串。 例如：一个简单的算术表达式文法： Ei EE+E EE*E (2-1) E(E) 终结符号：i 非终结符号：E 开始符号：算术表达式 产生式：(2-1)

5、 形式化定义： 一个上下文无关文法是一个四元式（VT ,VN ,S , ）VT是一个非空有限集，它的每个元素称为终结符号； VN是一个非空有限集，它的每个元素称为非终结符号，VTVN=； S是一个非终结符号，称为开始符号；SVN。 是一个产生式集合（有限），每个产生式的形式是P。 其中，PVN ，（VTVN）。开始符号S至少必须在某个产生式的左部出现一次。 P1|2|n。其中，i称为是P的一个候选式。 读作定义，直竖读为“或”,它是元语言元语言符号。 上下文无关文法语言：从文法的开始符号出发，反复使用产生式，对非终结符施行替换和展开。 例子：求解文法2-1的语言？ E (E)(E+E)(i+E

6、)(i+i) 推导：称A直接推出 ，即：A ，仅当A是产生式，且、(VTVN)* 如果11 n，则称序列是一个推导；称1可推出n；n 1表示经一步或若干步可推出表示经0步或若干步推出n*1假定G是一个文法，S是它的开始符号。如果有:则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。L(G)= =|S*&VT* *S 最左推导： 任何一步=都是对中的最左非终结符进行替换的。 最右推导： 任何一步=都是对中的最右非终结符进行替换的。 例2.1、例2.2、例2.32.3.2 语法分析树与二义性 语法树定义： 句型推导的树形表示称为语法树。EE

7、E(根)()i*+EEEii 文法二义性： 文法存在某个句子对应两颗不同的语法树，则称这个文法是二义性文法。 例如：EEE(根)()i*+EEEiiEEE(根)()i+*EEEii 二义性文法特点： 文法的二义性和语言的二义性不同，不同的文法可以有相同的语言，即L(G)=L(G*)，其中G是二义性文法。 文法的二义性证明是NP-Hard问题。 上下文无关文法的限制： 文法中不含任何下面形式的产生式 PP 每个非终结符P必须都有用处。即：必须存在含P的句型，并且对于P不存在永不终结的回路。 无二义性文法推导举例： 文法：TETEFTFT*iEF)(E看作“表达式”，T看作“项”，F看作“因子”，

8、则上述文法可以表示为：表达式-项|表示式+项项-因子|项*因子因子-(表达式)|i表达式项因子(表达式)(表达式+项)(项+项)(项*因子+项)(因子*因子+项)(i*因子+项)(i*i+因子)(i*i+i)2.3.3 形式语言鸟瞰 乔姆斯基（Chomsky）把文法分四类： 0型、1型、2型和3型。其描述能力的强度有下列关系：0型强于1型、1型强于2型、2型强于3型。 0型文法： 设G=（VT,VN,S,），对每个产生式有（VNVT）*且（VNVT）*对0型文法分别施加以下第i条限制，就得到I型文法： 每个产生式为均满足|;仅 S例外，但S不得出现在任何产生式的右部。G为任何产生式为A，AVN

9、 ，（VNVT）。 G的任何产生式为(1) AB 或A (2) AB 或A 其中VT，A、BVN。(1)式右线性文法；(2)式左线性文法 文法说明： 1型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成空串。例如，假若A是1型文G的一个产生式，和都不空，则非终结符A只有在和这样的一个上下文环境中才可以把它替换为。 2型文法也称上下文无关文法。 3型文法也称线性文法，或称为正规文法。文法应用举例 例1：判断文法SaSb|ab的类型，并推断文法语言。 由于S aSb|ab与a、b无关，则是上下文无关文法。 S aSb|ab，有SaSb aaSbb anSbn，文法文法对应的语言为：对应的语言为：L2=anbn|n 1 例2现有文法如下：语句if条件 then 语句| if条件 then 语句 else 语句|其它语句试判断文法的二义性和类型？ 由文法可以推导出下面的二义性句型If C1 then if C2 then S1