[其它]编译原理第2章.ppt

第二章 高级语言及其语法描述 主要内容 2.1 程序语言的定义 2.2 高级语言的分类 2.3 程序语言的语法描述 2.1 程序语言的定义 一个程序语言是一个记号系统。程序语言主要由语法和语义两个方面定义。 语法 任何语言程序都可看成是一定字符集（称为字母表）上的一字符串（有限序列）。但是，什么样的字符串才算是一个合式的程序呢？ 所谓一个语言的语法是指这样的一组规则，用它可以形成和产生一个合式的程序。 这些规则的一部分称为词法规则，另一部分称为语法规则（或产生规则）。 词法规则是指单词符号的形成规则。 语言的单词符号是由词法规则所确定的。词法规则规定了字母表中哪样的字符串是一个单词符号。 单词符号一般包括：各类型的常数、标识符、基本字、算符和界符等。 语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位），换言之，语法规则是语法单位的形成规则。 一般程序语言的语法单位有：表达式、语句、分程序、函数、过程和程序等等。 语言的词法规则和语法规则定义了程序的形式结构，是判断输人字符串是否构成一个形式上正确（即合式）程序的依据。 语义 一个语言的语义是指这样的一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则。 2.2 高级语言的分类 一、强制式语言 二、应用式语言 三、基于规则的语言 四、面向对象语言 2.3 程序语言的语法描述 重点讨论上下文无关文法、语法分析树，以及文法的二义性问题。最后还将对形式语言进行简单概述。 设Σ是一个有穷字母表，它的每个元素称为一个符号。 1、Σ上的一个符号串：是指由Σ中的符号所构成的一个有穷序列。不包含任何符号的序列称为空字，记为ε。用Σ﹡表示Σ上的所有符号串的全体，空字ε也包括在其中。 例如， ∑＝{a,b}，则 ∑﹡={ε,a,b,aa,ab,ba,bb,aaa,…｝。 Ф表示不含任何元素的空集｛｝。 注意：要注意空字ε、{}和{ε}的区别。 2、∑﹡的子集U和V的（连接）积 UV＝｛αβ|α∈Uβ∈V} 即集合UV中的符号串是由U和V的符号串连接而成的。 注意，一般而言，UV≠VU，但(UV)W=U(VW）。 3、V自身的n次（连接）积： 记为 V?=VV……V 规定：V°={ε} 令 V﹡= V0∪V1∪V2∪V 3∪…… 称V*是V的闭包。记V﹢=VV*，称V+是V的正则闭包。 上下文无关文法 文法是描述语言的语法结构的形式规则（即语法规则）。 上下文无关文法所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。 上下文无关文法不宜于描述任何自然语言，但对于现今的程序语言来说，上下文无关文法基本上是够用了。 从一个具体英文例句的分析出发，引进有关上下文无关文法的基本概念。比如，我们写了这样一个句子： He gave me a book． 这是一个语法上正确的句子，因为它满足英语中的基本语法规则。 有下面语法规则： ＜句子＞→＜主语＞＜谓语＞＜间接宾语＞＜直接宾语＞ ＜主语＞→代词 ＜谓语＞→动词 ＜间接宾语＞→＜代词＞ ＜直接宾语＞→＜冠词＞＜名词＞ 代词＞→He ＜代词＞→me ＜冠词＞→a ＜动词→gave ＜名词＞→book ＜句子＞ == ＜主语＞＜谓语＞＜间接宾语＞＜直接宾语＞ == ＜代词＞＜谓语＞＜间接宾语＞＜直接宾语＞ == He＜谓语＞＜间接宾语＞＜直接宾语＞ == He＜动词＞＜间接宾语＞＜直接宾语＞ == He gave＜间接宾语＞＜直接宾语＞ ==He gave＜代词＞＜直接宾语＞ == He gave me＜直接宾语＞ == He gave me＜冠词＞＜名词＞ == H gave me a＜名词＞ == He gave me a book 语法分析树:用一种图示化的方法来表示这种推导 上下文无关文法描述 一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。 终结符号乃是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。从语法分析的角度来看，终结符号是一个语言的不可再分的基本符号。 非终结符号（也称语法变量）用来代表语法范畴。例如，“算术表达式”、“布尔表达式”、“赋值句”、“分程序”、“过程”等。 开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为“句子” 产生式（也称产生规则或简称规则） 是定义语法范畴的一种书写规则。一个产生式的形式是A→α 其中，箭头（有时也用：：＝）左边的A是一个非终结符，称为产生式的左部符号；箭头右边α的是由终结符号或/与非终结符号组成的一符号串