编译原理与技术课件-词法分析.pptVIP

为什么要采用超前有哪些信誉好的足球投注网站 在程序中有一些单词的识别经常需要多读入一些字符才能知道哪些字符组成一个单词。如： 1 DO99K＝l,10 2 IF（5.EQ.M） I＝10 3 DO99K＝1.10 4 IF（5）＝55 这四个语句都是正确的FORTRAN语句。语句1和2分别是DO和IF语句，它们都是以基本字开头的，语句3和4是赋值句，它们都是以用户自定义标识符开头的。 又如C中： a=a++; a=a+1; 三、 状态转换图 状态转换图是一张有限方向图，是设计词法分析器的有效工具。 1 2 3 X Y 图3.2（a）转换图示例 一个状态转换图可用于识别（或接受)一定的字符串。 §3.3 正规表达式与有限自动机 1 正规式与正规集 正规式也称正则表达式。 正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。 定义（正规式和它所表示的正规集）： 设字母表为?，辅助字母表?`={? ，?，?，?，?，?，? }，1. ?和?都是?上的正规式，它们所表示的正规集分别为{?}和{ }； 2. 对任何a? ?，a是?上的一个正规式，它所表示的正规集为{a}； 3. 假定e1和e2都是?上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1? e2, e1?e2, e1?也都是正规式,它们所表示的正规集分别为L(e1), L(e1)?L(e2), L(e1)L(e2)和(L(e1))?。 4. 仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的集合才是?上的正规集。 注意: 其中“?”、 “? ”、 “?”均为正规式运算符： 2. “? ”读为“连接”； 3. “?”读为“闭包”（即，任意有限次的自重复连接）。 在不致混淆时，括号可省去，但规定算符的优先顺序为“?”、“? ”、“?” 。连接符“? ”一般可省略不写。“?”、“? ”和“?” 都是左结合的。 “?”读为“或” ； 例子 令?={a，b}， ?上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} a?b {a,b} ab {ab} (a?b)(a?b) {aa,ab,ba,bb} a ? {? ,a,a, ……任意个a的串} 正规式 正规集 (a?b)? {? ,a,b,aa,ab ……所有由a 和b组成的串} (a?b)?(aa?bb)(a?b)? {??上所有含有两个相继 的a或两个相继的b组成 的串} 正规式的等价性 若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。 例如： e1= (a?b)， e2 = b?a， e1= e2 又如： e1= b(ab)? , e2 =(ba)?b， e1= e2 e1= (a?b)? , e2 =(a??b?)?， e1= e2 设U,V,W为正规式，正规式服从的代数规律有： 1. U?V=V?U “或”服从交换律 2. U?(V?W)=(U?V)?W “或”的可结合律 3. (UV)W=U(VW) “连接”的可结合律 U(V?W)=UV?UW (V?W)U=VU?WU 分配律 5. ?U=U, U?=U ?是“连接”的恒等元 素零一律 6. U?U=U U?=??U?UU?… 2 有限自动机 有限自动机(也称有穷自动机) 能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有穷自动机分为两类：确定的有限自动机(Deterministic Finite Automata)和不确定的有限自动机(Nondeterministic Finite Automata) 。 关于有限自动机我们将讨论如下题目 确定的有穷自动机DFA 不确定的有穷自动