程序设计语言基础.ppt

第2章程序语言基础知识
2.1程序设计语言基础知识

2.2编译系统基本原理
2.2.1文法
2.2.2文法分析
2.2.3词法分析

2.3C语言基础2.1程序设计语言概述

低级语言(面向机器的语言)
面向对象程序设计语言(C++，Java，
Smalltalk)
程序设计语言逻辑程序设计语言（Prolog）

高级语言函数式的语言（Lisp）

命令式程序设计语言(C，Pascal)

科学计算语言（Fortran）逻辑式语言
是一类以形式逻辑为基础的语言，其代表就是建立关系理论和一阶谓词理论基础上的Prolog。逻辑式语言有很强的推理能力。用于开发专家系统、自然语言理解等。

函数式语言
是一类以演算为基础的语言，其基本概念来自为人工智能而设计的Lisp语言。这里所谓的函数跟数学中的函数概念是类似的。

命令式语言
命令式语言又称过程式语言，它是一种基于动作的语言，所有的计算被看成工作序列。

例：____语言不是面向对象的程序设计语言。
A.Java
B.C++
C.Smalltalk
D.Fortran2.2编译系统基本原理
2.2.1编译原理基本知识
语言处理程序分为两个大类：翻译程序和解释程序。

翻译程序：把用某种程序设计语言书写的程序翻译成等价的机器语言。

常考点1：程序编译过程
一般情况，编译程序的流程如下图所示：注意：
并非所有的编译程序都分成这几个处理阶段，有些编译程序并不需要生成中间代码，有些编译程序不进行代码优化，有些最简单的编译程序在语法分析的同时产生目标指令代码。例（软设2008年5月上午试题20）：编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段，其中，并不是每种编译器都必需的。

A．词法分析和语法分析
B．语义分析和中间代码生成
C．中间代码生成和代码优化
D．代码优化和目标代码生成2.2编译系统基本原理
2.2.2文法
1．文法定义
文法G定义为四元组（VN，VT，P，S），其中：
（1）VN为非终结符号（或语法实体，或变量）集；
（2）VT为终结符号集；
（3）P为产生式（也称规则）的集合；
（4）S称为识别符号或开始符号，它是一个非终结符。一般约定，第一条产生式的左部是开始符号（识别符号）。

一般情况，大写字母表示非终结符；
小写字母表示终结符。例：文法G=（VN，VT，P，S），其中VN={S}，VT={0，1}，P={S—>0S1，S—>01}.

总结：
一个文法定义的语言是终结符号串的集合，这些终结符号串应能从文法的起始符号出发推导出来。2．∑*：
∑*称为集合∑的闭包。∑*=∑0∪∑1∪∑2∪…∑n∪...
其中，∑n表示∑的方幂。假设∑是个符号串，∑n表示把∑自身连接n次得到的符号串。

例如∑=AB，求∑*。
∑*=∑0∪∑1∪∑2∪…∑n∪...
其中：
∑0=，表示不包含任何符号的符号串，即空符号串，其长度为0。
∑1=AB
∑2=ABAB
……定义：设G[S]是一文法，如果符号串x是从识别符号推导出来的，即有S=>x，则称x是文法G[S]的句型。若x仅有终结符号组成，即S=>x，x属于VT*，则称x为G[S]的句子。2.2.3文法分析
1.文法的类型
（1）0型文法

（2）1型文法或上下文有关文法

（3）2型文法或上下文无关文法
（1）0型文法
定义：设G=（VN，VT，P，S）为一文法，如果它的每个产生式a—>b是这样一种结构：a属于（VN∪VT）*且至少含有一个非终结符，而b属于（VN∪VT）*，则G是一个0型文法。

对0型文法产生式的形式作某些限制，就是1型、2型、3型文法。（2）1型文法或上下文有关文法
定义：设G=（VN，VT，P，S）为一文法，若P中的每一个产生式a—>b均满足|b|≥|a|,仅仅S—>除外，则G是1型文法或上下文有关文法。

（3）2型文法或上下文无关文法
定义：设G=（VN，VT，P，S）为一文法，若P中的每一个产生式a—>b满足：a是一非终结符，b属于（VN∪VT）*，则此文法为2型文法或上下文无关文法。

例：文法G=（{E}，{+，*，i，(，)}，P，E）其中P为：
E—>i
E—>E+E
E—>E*E
E—>(E)

今后，对“文法”一词若无特别说明，则均指上下文无关文法。例（2007年下半年上午第50）：程序语言的大多数语法现象可用上下文无关文法描述。对于一个上下文无关文法G=(N，T，P，S)，其中N是非终结符号的集合，T是终结符号的集合，P是产生式集合，S是开始符号。令集合V=N∪T，那么G所描述的语言是的集合。
A．从S出发推导出的包含V中所有符号的串
B．从S出发推导出的仅包含T中符号的串
C．N中所有符号组成的串