编译原理word版.doc

第三章 复习：程序语言的语法描述 几个概念: 考虑一个有穷 字母表 其中每一个元素称为一个字符 字字符串 不包含任何字符的序列称为空字，记为 用表示∑上的所有字的全体,包含空字ε 复习：程序语言的语法描述 ∑*的子集U和V的连接（积）定义为 UV＝{ | ((U ((V } V自身的 n次积记为 Vn=VV…V 规定V0={}，令 V*=V0V1∪V2∪V3∪… 称V*是V的闭包; 记 V＋＝VV* ，称V+是V的正规闭包。 复习：程序语言的语法描述 上下文无关文法的定义： 一个上下文无关文法G是一个四元式 ，V，S，P)，其中 ：终结符集合(非空) ：非终结符集合(非空)，且V S：文法的开始符号，S(VN P：产生式集合(有限)，每个产生式形式为 P((， ， 开始符S至少必须在某个产生式的左部出现一次。 复习：程序语言的语法描述 定义：称A(直接推出，即 A((((( 仅当A 是一个产生式， 且， (VT ( VN)* 。 如果1 ( (2 ( ( ((n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n 。 复习：程序语言的语法描述 最左推导：任何一步都是对中的最左非终结符进行替换。 最右推导：任何一步都是对中的最右非终结符进行替换。 复习：程序语言的语法描述 用一张图表示一个句型的推导,称为语法树。 复习：程序语言的语法描述 定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。 语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。 复习：程序语言的语法描述 形式语言鸟瞰 0型(短语文法，图灵机)： 产生式形如： 其中： (VT ( VN)*且至少含有一个非终结符； (VT ( VN)* 1型(上下文有关文法，线性界限自动机)： 产生式形如： 其中：|| ( |(|，仅 S 例外。 复习：程序语言的语法描述 形式语言鸟瞰 2型(上下文无关文法，非确定下推自动机)： 产生式形如： A 其中：A VN； (VT ( VN)*。 3型(正规文法，有限自动机)： 产生式形如： A B 或 A 其中： VT*；A，BVN 产生式形如： A B( 或 A 其中： VT*；A，BVN 第三章 词法分析 词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。 词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序 一、词法分析器的功能和输出形式 功能:输入源程序、输出单词符号 单词符号的种类： 基本字：如 begin，repeat， 标识符——表示各种名字：如变量名、数组名和过程名 常数：各种类型的常数 运算符：+，-，*，/， 界符：逗号、分号、括号和空白 输出的单词符号的表示形式: 单词种别，单词自身的值 单词种别通常用整数编码表示。 若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。 若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。 标识符单列一种； 常数按类型分种整、实、布尔等）。 例 C程序 while (i=j) i--; 输出单词符号： while, - (, - id, 指向i的符号表项的指针 =, - id, 指向j的符号表项的指针 ), - id, 指向i的符号表项的指针 --, - ;, - 二、词法分析器作为一个独立子程序 词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？ 作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。 不作为一遍：将其处理为一个子程序。 词法分析器的结构 输入串放在输入缓冲区中。 预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等 扫描缓冲区 二、单词符号的识别:超前有哪些信誉好的足球投注网站 1 基本字识别: 例如: DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55 DO99K=1.10 IF(5)=55 需要超前有哪些信誉好的足球投注网站才能确定哪些是基本字 2 标识符识别: 字母开头的字母数字串，后跟界符或算符 3 常数识别: 识别出算术常数并将其转变为二进制内码表示。有些也要超前有哪些信誉好的足球投注网站。 5.EQ.M 5.E08 4 算符和界符的识别 把多个字符符合而成的算符和界符拼合成一个单一单词符号。 :=， **， .EQ. ， ++，--，= 三、状态转换图 状态转换图是一张有限方