《编译原理讲义全》由会员分享，可在线阅读，更多相关《编译原理讲义全（86页珍藏版）》请在金锄头文库上搜索。
1、 2013-2014第二学期第二学期 Sun Yat-Sen University 2011 级电子政务 JollinZhu (11331448) 编译原理编译原理 2013-2014 学年度第二学期-中山大学软件学院-软件工程 2011 级电子政务方向-编译原理课程讲义 授课老师：娄定俊 编辑：朱琳 Jolin Zhu 2011 级电子政务 编译原理 1 第一章第一章 引论引论 *问题的提出:没有软件的计算机能执行的语言(指令)是非常低级的语言,即机器语言,例如: 0001 01 00 00100000 0011 01 10 00000010 而面向人的高级语言直观,书写方便,不易出错,例如
2、: IF i j then max := i else max := j end; 三. 正规式(Regular expression) 正规式(正则式)代表一个语言. 1. 定义: 给定字母表,定义上的正规式如下: (1) 是正规式,表示; (2) 如果 a,那么 a 是正规式, 表示a; (3) 假定 r 和 s 都是正规式,分别表示语言 L(r)和 L(s), 那么 a) (r)|(s)是正规式,表示 L(r)L(s); b) (r)(s)是正规式,表示 L(r)L(s); c) (r)*是正规式,表示(L(r)*; d) (r)是正规式, 表示 L(r). 除此以外,其它的不是正规式.
3、 正规式表示的语言叫正规集(regular set). 2. 约定 *优先级最高, 左结合(left associative); 连接(concatenation)优先级其次, 左结合; |优先级最低, 左结合; 可以删除不必要的括号. 例如: (a) | (b)*(c) 可写成 a | b*c 3. 例子: 令=a, b a | b 表示 a, b (a | b)(a | b) 表示 aa, ab, ba, bb, 也可用 aa | ab | ba | bb 表示. *同一语言的正规式表示不唯一. a* 表示 , a, aa, aaa, (a | b)* 表示 , a, b, aa, ab,
4、 ba, bb, aaa, aab, a | a*b 表示 a, b, ab, aab, aaab, 4. 正规式的运算规则 *两个正规式相等,当且仅当它们代表的语言相同. 设 r, s 和 t 是任意正规式. 1) r | s = s | r 2) r | (s | t) = (r | s) | t 3) (rs)t = r(st) 4) r(s | t) = rs | rt (s | t)r = sr | tr 2011 级电子政务 编译原理 7 5) r = r, r= r 6) r* = (r |)* 7) r* = r* 证明举例: 证明(4): 要证 L(r(s|t)=L(rs|r
5、t). L(r(s|t)=L(r)(L(s)L(t) =xy|xL(r)(yL(s)yL(t) =xy|(xL(r)yL(s)(xL(r)yL(t) =xy| xL(r)yL(s)xy| xL(r)yL(t) =L(r)L(s)L(r)L(t) =L(rs|rt) 证明(6): 要证 L(r*)= L(r|)*) x, 设 xL(r*)= 0)(iirL.故 xL(r)k 由于 L(r)L(r|)=L(r)L() L(r)k L(r|)k,故 xL(r|)k, 从而 xL(r|)*)=0)|(iirL. 因而 L(r*)L(r|)*). x,设 xL(r|)*)= iiiiLrLrL)()()
6、|(00. 故 x(L(r)L()k,从而 x = 1w 12w 23 wt(t+1)= w 1w2wt ,其中 1+2+(t+1)+ t = k, wj L(r),j=1,2,t 因而有 xL(r)t,从而 xL(r)*=L(r*).也就有 L(r|)*)L(r*). 因此 L(r*)=L(r|)*). 四. 正规定义(Regular definition) d1r1 d2r2 dnrn 各个 di的名字不同且 di (i=1,2,n).每个 ri是d1,d2,di-1上的正规式. 例: Pascal 语言标识符(identifier)的定义 letterA|B|Z|a|b|z digit0
7、|1|9 idletter(letter|digit)* PASCAL 中无符号数 digit0|1|9 digitsdigit(digit)* optional-fraction.digits | optional-exponent(E(+|-|)digits)| 2011 级电子政务 编译原理 8 numdigits optional-fraction optional-exponent 五. 表示的缩写 1. 一个或多个实例(正闭包) r+ = r r*, r* = r+ | 2. 零个或一个实例(instance) r? = r | 3. 假设= ,a1,a2,an, 那么 a1|a2
8、|an可表示为 a1a2an或a1an. 例如: abc表示 a|b|c, az表示 a|b|z 六. 非正规集 例: wcw | wa,b*. *正规式表示语言的能力是有限的,有些语言不能由正规式表示. 2.42.4 记号的识别记号的识别(Recognition(Recognition ofof tokens)tokens) 例:给定正规定义 ifif thenthen elseelse relop|= idletter(letter|digit)* numdigit+(.digit+)?(E(+|-)?digit+)? 假定单词由空格(或制表符换行符)分开 delimblank|tab|n
9、ewline wsdelim+ * 词法分析器(lexical analyzer)将剥去空格.如果输入与 ws(white space)匹配,词法分析器不返回记号给分析器, 它继续去寻找空格后面的记号,然后返回到分析器(parser). * 上述正规定义描述的是 Pascal 语言中的关键字关系符标识符和数字.C 语言的标识符定义如下: letter_A|B|Z|a|b|z|_ digit0|1|9 idletter_(letter_|digit)* 以下以 Pascal 语言中的定义为例. * 以下表中给出对应每一种正规式,词法分析器返回的记号和属性. (见书 P130) 一、 转换图(Tr
10、ansition diagram) *我们首先产生转换图作为构造词法分析器的第一步. 1. 状态(state) 2. 转换边(edge) 3. 标记(label) 4. 接受状态(accepting states or final states) 5. 开始状态(start state or initial state) 6. 工作原理 2011 级电子政务 编译原理 9 例子: (见黑板) 例 1: 关系符的转换图 (见书 P131) *关于指针的回退(retract) 例 2: 关键字和标识符的识别.(见书 P132) *保留字(reserved words)的识别: 设置一张保存标识符信
11、息的符号表(symbol table),把所有保留字预先存入其中, 符号表中的一个域说明当前 标识符是保留字还是普通标识符. 当词法分析器识别一个标识符后,调用过程 install_id( ), 如果该标识符不在符号表中, 说明它不是保留字, 则 install_id( )在符号表中为它建立条目(entry), 并返回指向该条目的指针. 若该标识符已在符号表中, 但不是 保留字, 则该过程返回该标识符已在符号表中条目的指针. 若该标识符已在符号表中, 并且是保留字, 则 install_id( )返回 0. 过程 gettoken 访问该标识符在符号表中的条目, 根据符号表中的信息, 如果该标
12、识符是保留 字,则返回它的记号, 如果是普通标识符, 则返回记号 id. 例 3: 无符号数的识别.(见书 P133) *最长匹配原则 例 4: 空白的处理.(见书 P134) 二、 实现转换图 例子: 处理关系符的转换图转化为程序. PROCEDURE GetRelop (VAR Token: Record name, att End); VAR state, again : integer; c: char; BEGIN Token.name := relop; state := 0; again := 1; WHILE again = 1 DO CASE state OF 0: BEGI
13、N c := nextchar( ); IF c = THEN state := 6 ELSE BEGIN fail( ); again := 0 END END 1: 8: BEGIN retract( ); Token.att := GT; again := 0 END END; 2011 级电子政务 编译原理 10 2.52.5 有穷自动机有穷自动机(Finite(Finite automata)automata) 一、一、 语言的识别器(language recognizer) 语言的识别器是一个程序,它取串 x 作为输入,当 x 是该语言的句子时,回答“是”,否则回答“不是”. *有
14、穷自动机是更一般化的转换图,是转换图的数学模型. *确定与不确定有穷自动机 *识别正规集. 二、 不确定有穷自动机 NFA(Nondeterministic Finite Automata) 1. 定义: 一个不确定有穷自动机 NFA M 是一个五元组 M=(S, s0 , F) 其中: S: 状态集(非空,有穷) : 输入字母表(非空,有穷) s0: 初始状态, s0S F: 终止状态集, FS 状态转换函数(transition function): : S()2S *解释 (s,a)=t1,t2,tk . 2. 例子: 识别语言(a|b)*abb 的 NFA (见书 P148) 3. 用
15、状态转换表表示(上例表示如下) (见书 P149) 4. 识别一个串 NFA 接受一个输入串 x 当且仅当转换图中存在从开始状态到某个接受状态的路径,该路径上的标记拼成 x. 例如: 上例中的 NFA 接受 aaabb 注意:可能有多于一条路径接受同一个串 5. NFA 识别的语言 一个 NFA 识别的语言是它接受的输入串的集合. 例 1: 上例中 NFA 接受的语言为: (a|b)*abb 例 2: 接受 aa*|bb*的 NFA (见书 P150) 三、 确定有穷自动机 DFA(Deterministic Finite Automata) 1. 定义:一个确定有穷自动机 DFA M 是一个五元组 M=(S, s0 , F) 其中: S, , s0, F 同 NFA, 状态转换函数: : S
