编译原理第2章.ppt

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