第2章 高级语言及其语法描述ppt课件.ppt

《第2章 高级语言及其语法描述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章高级语言及其语法描述2.1程序语言的定义2.2程序语言的语法描述22021/8/27软件学院2.1程序语言的定义一个程序设计语言是一个记号系统，其完整的定义应包括语法和语义两个方面语言的语法是指一组规则，用它可以形成和产生一个合适的程序上下文无关文法语法只定义什么样的符号序列是合法的，与这些符号的含义毫无关系PASCAL语言中：A:=B+C合乎语法规则，A:=B+不合乎语法规则阐明语法的一个工具是文法，这是形式语言理论的基本概念之一32021/8/27软件学院2.2程序语言的语法描述基本概念字母表、符号、符

2、号串、闭包等文法的定义文法的分类Chromsky对文法的分类文法和语言推导、归约、句型、句子、语言语法分析树和二义性42021/8/27软件学院基本概念字母表元素的非空有限集，记为。例：={a，b，c}字母表中的元素称为符号。例：a，b，c，字母表包含了语言中所允许出现的所有符号符号串符号的有穷序列。例：a,aa,ac,abc，..，无任何符号的符号串称为空符号串，记为ε52021/8/27软件学院不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε例如:设∑={a，b}，则∑*={ε

3、,a,b,aa,ab,ba,bb,aaa,...}注：约定用a,b,c,…表示符号；用,,,…表示符号串；用A,B,C,…表示其集合。62021/8/27软件学院基本概念符号串运算符号串长度x为符号串,其长度

4、x

5、等于组成该符号串的符号个数。例：x=string，则

6、x

7、=6,

8、ε

9、=0符号串连接若x、y是定义在Σ上的符号串，则xy称为x和y的连接，xy也是Σ上的符号串εx＝xε=x72021/8/27软件学院基本概念符号串集合的乘积令A、B为符号串集合，定义符号串集合乘积AB＝{xy

10、x∈A,y∈B}符号

11、串集合的方幂符号串集合A，定义A0={ε},A1=A,A2=AA,A3=A2A,…,An＝An-1A=AAn-1，n>0符号串集合的正闭包A+=A1∪A2∪…∪An…符号串集合的自反闭包A*={ε}∪A+设：U＝{a,aa}那么：U*={,a,aa,aaa,aaaa,…}U＋={a,aa,aaa,aaaa,…}软件学院2.3.1上下文无关文法文法：描述语言的语法结构的形式规则Hegavemeabook.<句子><主语><谓语><间接宾语><直接宾语><主语><代词><谓语><动词><间接宾语><代词><

12、直接宾语><冠词><名词><代词>He<代词>me<名词>book<冠词>a<动词>gave软件学院<句子><主语><谓语><间接宾语><直接宾语><主语><代词><谓语><动词><间接宾语><代词><直接宾语><冠词><名词><代词>He<代词>me<名词>book<冠词>a<动词>gave<句子><主语><谓语><间接宾语><直接宾语><代词><谓语><间接宾语><直接宾语>He<谓语><间接宾语><直接宾语>He<动词><间接宾语><直接宾语>Hegave<间接宾语

13、><直接宾语>Hegave<代词><直接宾语>Hegaveme<直接宾语>Hegaveme<冠词><名词>Hegavemea<名词>Hegavemeabook软件学院上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)*开始符S至少必须在某个产生式的左部出现一次。软件学院例，定义只含+，*的算术表达式

14、的文法G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列产生式组成：EiEE+EEE*EE(E)软件学院几点规定：“”也可以用“::="表示，这种表示称为巴科斯范式(BNF)P1P2可缩写为P1

15、2

16、

17、nPn其中，“

18、”读成“或”，称为P的一个候选式。表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：G(E)：Ei

19、E+E

20、E*E

21、(E)例，定义只含+，*的算术表达式的文法G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列产生式组成：EiE

22、E+EEE*EE(E)软件学院定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)*。如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。对文法G(E)：Ei

23、E+E

24、E*E

25、(E)E(E)(E+E)(i+E)(i+i)软件学院通常，用表示：从