程序设计语言基础.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 JavaB C C SmalltalkD Fortran 2 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 iE E EE E EE E 今后 对 文法 一词若无特别说明 则均指上下文无关文法 例 2007年下半年上午第50 程序语言的大多数语法现象可用上下文无关文法描述 对于一个上下文无关文法G N T P S 其中N是非终结符号的集合 T是终结符号的集合 P是产生式集合 S是开始符号 令集合V N T 那么G所描述的语言是的集合 A 从S出发推导出的包含V中所有符号的串B 从S出发推导出的仅包含T中符号的串C N中所有符号组成的串D T中所有符号组成的串 例 2009年上半年上午第50 设某语言的语法规则用上下文无关文法G N T P S 表示 其中N是非终结符号的集合 T是终结符号的集合 P是产生式集合 S是开始符号 令V N T 那么符合该语言的句子是 A 从S出发推导的 仅包含T中符号的符号串B 从N中符号出发推导的 仅包含T中符号的符号串C 从S出发推导的 包含V中符号的符号串D 从N中符号出发推导的 包含V中符号的符号串 2 上下文无关文法及其语法树 推导树 语法树或推导树 是一种描述上下文无关文法的句型推导的直观方法 通过语法树 可以得到文法G的句型 从下面的例子说明语法树的构造 例 G S A a b P S 其中P为 1 S aAS 2 A SbA 3 A SS 4 S a 5 A ba构造G的语法树 注意 如果在推导的任何一步 都是对其中的最左 最右 非终结符进行替换 则称这种推导为最左 最右 推导 例 软设2008年5月上午试题21 已知某文法G S S 0S0S 1 从S推导出的符号串可用 n 0 描述 A 010 nB 0n10nC 1nD 01n0 例 2008年下半年上午第50 设某上下文无关文法如下 S 11 1001 S0 SS 则该文法所产生的所有二进制字符串都具有的特点是 A 能被3整除B 0 1出现的次数相等C 0和1的出现次数都为偶数D 能被2整除 例 2008年下半年上午第48 给定文法G S 及其非终结符A FIRST A 定义为 从A出发能推导出的终结符号的集合 S是文法的起始符号 为非终结符 对于文法G S S L aL L S S其中 G S 包含的4个终结符号分别为 a 则FIRST S 的成员包括 48 A aB a C a 和 D a 和 2 2 4词法分析考点1 词法分析的功能词法分析阶段的主要功能如下 1 识别出源程序中意义独立的最小词法单位 单词 并且确定其类型 例如表示符 关键字 操作符还是数字等 2 删除无用的空格 回车和其它与输入介质有关的无用符号以及程序注释 3 报告分析时的错误 经过词法分析后 源程序就转换为单词串 例 软设2005年11月上午试题27 编译程序进行词法分析时不能 A 过滤源程序中的注释B 扫描源程序并识别句号C 指出出错的行号D 查出拼错的保留字 考点2 正规式和正规集 正规式和正规集正规式 用正规表达式 简称正规式 可表示程序语言的单词 正规集 正规式表示的集合称为正规集 例 令 a b 上的正规式和相应的正规集的例子有 正规式正规集a a a b a b ab ab a a aa 任意个a的串 a b a b aa ab ba bb 所有a b组成的串 a b a b aa bb 正规文法到正规式的转换规则 表正规文法到正规式的转换规则 例 2007年下半年上午第48 正则表达式1 0 01 表示的集合元素的特点是 A 长度为奇数的0 1串B 开始和结尾字符必须为1的0 1串C 串的长度为偶数的0 1串D 不包含字串011的0 1串 例 2009年上半年上午第49 由a b构造且仅包含偶数个a的串的集合用正规式表示为 A a a b B b ab a C a ba b D a b aa 考点3 自动机有穷自动机分为两类 1 确定的有穷自动机 DeterministicFiniteAutomata 2 不确定的有穷自动机 NondeterministicFiniteAutomata 1 确定的有穷自动机 DFA 一个确定的有穷自动机 DFA M是一个五元组 M K f S Z 其中 1 K是一个有穷集 它的每个元素称为一个状态 2 是一个有穷字母表 它的每个元素称为一个输入字符 所以也称 为输入符号字母表 3 f是转换函数 是在K K上的映像 即 如f ki a kj ki属于K kj属于K 表示当前状态为ki 输入字符在a时 将转换为下一个状态kj 4 S属于K S是唯一的一个初态 5 Z包含与K Z是一个终态集 终态也称为可接受状态或结束状态 例 DFAM S U V Q a b f S Q 其中f定义为 f S a Uf V a Uf S b Vf V b Qf U a Qf Q a Qf U b Vf Q b Q请画出该DFA的状态转换图 补充 对于 中的任何一个串t 若存在一条从某一初态结点到某一个终态结点的道路 且这条道路上所有弧的标记符依序连接成的串等于t 则称t可为DFAM所识别 读出或接受 若M的初态结点同时又是终态结点 则空字可为M所识别 接受 2 不确定的有穷自动机 NFA 一个不确定的有穷自动机 NFA M是一个五元组 M K f S Z 其中 1 K是一个有穷集 它的每个元素称为一个状态 2 是一个有穷字母表 它的每个元素称为一个输入字符 3 f是转换函数 是从K K上子集的映像 4 S属于K S是一个非空的初态集 5 Z包含与K Z是一个终态集 例2 一个NFAM 0 1 2 3 4 a b f 0 2 4 其中f定义为 f 0 a 0 3 f 2 b 2 f 0 b 0 1 f 3 a 4 f 1 b 2 f 4 a 4 f 2 a 2 f 4 b 4 请画出该NFA的状态转换图 补充 对于 中的任何一个串t 若存在一条从某一初态结点到某一个终态结点的道路 且这条道路上所有弧的标记符依序连接成的串等于t 则称t可为NFAM所识别 读出或接受 例2中的NFAM所能识别的是那些含有相继两个a或相继两个b的串 自动机到正规式的转换过程如图所示 对于代之对于代之对于代之 1 2 3 R1 R2 1 3 R1R2 1 2 1 2 3 1 2 1 3 R1 R2 R1R2 R3 R1 R2 R1 R3 R2 例 2006年下半年上午第45 46 下图是一有限自动机的状态转换图 该自动机所识别语言的特点是 1 等价的正规式为 2 1 A 由符号a b构成且包含偶数个a的串B 由符号a b构成且开头和结尾符号都为a的串C 由符号a b构成的任意串D 由符号a b构成且b的前后必须为a的串 2 A a b aa B a a b aC a b D a ba a 例 2009年上半年上午第48 下图所示有限自动机的特点是 A 识别的0 1串是以0开头且以1结尾B 识别的0 1串中1的数目为偶数C 识别的0 1串中0后面必须是1D 识别的0 1串中1不能连续出现 例 2008年上半年上午第50 某确定性有限自动机 DFA 的状态转换图如下图所示 令d 0 1 2 9 则以下字符串中 能被该DFA接受的是 A 3857B 1 2E 5C 123 67D 0 576E10 例 2008年上半年上午第48 有限自动机 FA 可用于识别高级语言源程序中的记号 单词 FA可分为确定的有限自动机 DFA 和不确定的有限自动机 NFA 若某DFAD与某NFAM等价 则 A DFAD与NFAM的状态数一定相等B DFAD与NFAM可识别的记号相同C NFAM能识别的正规集是DFAD所识别正规集的真子集D DFAD能识别的正规集是NFAM所识别正规集的真子集 2 3C语言基础常考点 参数传递方式参数传递有两种方式 传值方式和传引用方式 传值调用 以传值调用方式进行参数传递时 是将实参的值传递给形参 然后执行被调用的函数 被调用的函数执行时对形参的修改不影响实参的值 引用调用 以引用调用方式进行参数传递时 是将实参的地址传递给形参 然后执行被调用的函数 被调用的函数执行时对形参的修改将反映在对应实参变量中 例 函数f g 的定义如下所示 调用函数f时传递给形参a的值为1 若采用传值 callbyvalue 的方式调用g c 则函数f的返回值为 1 若采用传引用 callbyreference 的方式调用g c 则函数f的返回值为 2 f 形式参数a g 形式参数b 供选择的答案 1 A 7B 5C 4D 3 2 A 3B 4C 5D 7 例 2007年上半年上午第49 函数t f 的定义如下所示 若调用函数t时传递给x的值为3 并且调用函数f 时 第一个参数采用传值 callbyvalue 方式 第二个参数采用传引用 callbyreference 方式 则函数t的返回值为 A 35B 24C 22D 11