下载文档原格式
第三章词法分析本章要点1•词法分析器设计，2.正规表达式与有限自动机，3•词法分析器自动生成。
本章目标：1•理解对词法分析器的任务，掌握词法分析器的设计；2.掌握正规表达式与有限自动机；3•掌握词法分析器的自动产生。
本章重点：1. 词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。
应重点掌握词法分析器的任务与设计，状态转换图等内容。
2 •掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。
（1）非形式描述的语言正规式（2）正规式NFA （非确定的有限自动机）（3）NFADFA （确定的有限自动机）（4）DFA最简DFA本章难点（1）非形式描述的语言正规式（2）正规式NFA （非确定的有限自动机）（3）NFADFA （确定的有限自动机）（4）DFA最简DFA作业题、单项选择题(按照组卷方案，至少15道) 1•程序语言下面的单词符号中，一般不需要超前搜索a.关键字b.标识符c.常数d.算符和界符2. 在状态转换图的实现中，一般对应一个循环语句a.不含回路的分叉结点b.含回路的状态结点c.终态结点d.都不是3. 用了表示字母，d表示数字，={1，d}，则定义标识符的正则表达式可以是：。
(a)ld* (b)ll* (c)l(l | d) * (d)ll* | d*4. 正规表达式(e |ajb表示的集合是(a){ , ab, ba, aa, bb} (b){ab , ba, aa, bb}(c){a , b, ab, aa, ba, bb} (d){,込b, aa, bb, ab, ba}5. 有限状态自动机可用五元组( V T , Q , & q o , Q f)来描述，设有一有限状态自动机M的定义如下：V T={0 , 1}, Q={q 0 , q1 , q2}, Q f={q 2}, 3 的定义为:氷 q o , 0) =q1 3 (q1, 0) =q23(q2 , 1) =q2 3 (q2 , 0) =q2M所对应的状态转换图为。
编译原理词法分析编译原理是计算机科学中的一个重要领域，它研究的是如何将高级语言编写的程序转换成目标机器能够执行的指令序列。
而词法分析则是编译原理中的一个重要环节，它负责将源程序中的字符流转换成有意义的词素序列，也就是词法单元。
在这篇文档中，我们将重点讨论编译原理中的词法分析，包括其基本概念、主要任务和实现方法。
词法分析的基本概念是将源程序中的字符流转换成有意义的词素序列，也就是词法单元。
词法单元是编程语言中的基本构造块，它可以是关键字、标识符、常量、运算符等。
词法分析器的主要任务就是识别源程序中的词法单元，并将其转换成相应的记号，以便后续的语法分析和语义分析。
词法分析的实现方法主要有两种，手工编写词法分析器和使用词法分析器生成器。
手工编写词法分析器需要程序员自己定义词法单元的模式，并编写相应的识别程序。
而使用词法分析器生成器则是通过定义词法单元的模式和对应的动作，然后由生成器自动生成词法分析器的识别程序。
两种方法各有优缺点，选择哪种方法取决于具体的需求和实际情况。
在词法分析中，最常用的方法是有限自动机。
有限自动机是一种抽象的数学模型，它可以用来描述词法单元的识别过程。
有限自动机可以分为确定性有限自动机（DFA）和非确定性有限自动机（NFA），它们分别对应着不同的识别算法。
在实际应用中，通常会先构造NFA，然后将其转换成DFA，以便更高效地进行词法分析。
除了有限自动机，正则表达式也是词法分析中的重要工具。
正则表达式是一种描述字符串模式的形式语言，它可以用来描述词法单元的模式。
在词法分析中，通常会使用正则表达式来定义词法单元的模式，然后通过正则表达式引擎来进行匹配和识别。
总的来说，词法分析是编译原理中的一个重要环节，它负责将源程序中的字符流转换成有意义的词素序列。
词法分析的实现方法有手工编写词法分析器和使用词法分析器生成器两种，而在实际应用中，有限自动机和正则表达式是词法分析中的重要工具。
通过本文的介绍，相信读者对编译原理中的词法分析有了更深入的了解。
第二章P36-6(1)L G ()1是0~9组成的数字串(2)最左推导:N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒0010120127334556568最右推导:N ND N ND N ND N D N ND N D N ND N ND N D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒77272712712701274434886868568P36-7G(S)O N O D N S O AO A AD N→→→→→1357924680|||||||||||P36-8文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiE EFT+T F FTiii*i+i+ii-i-ii+i*i*****************/P36-9句子iiiei 有两个语法树：S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ⇒⇒⇒⇒⇒⇒⇒⇒P36-10/**************)(|)(|S T TTS S →→***************/P36-11/*************** L1:ε||cC C ab aAb A ACS →→→ L2:bcbBc B aA A ABS ||→→→ε L3:εε||aBb B aAb A ABS →→→ L4:AB B A A B A S |01|10|→→→ε ***************/第三章习题参考答案P64–7(1)101101(|)*1 ε ε 1 0 1 1确定化：0 1 {X} φ {1,2,3} φ φ φ {1,2,3} {2,3} {2,3,4} {2,3} {2,3} {2,3,4} {2,3,4} {2,3,5} {2,3,4}{2,3,5} {2,3} {2,3,4,Y} {2,3,4,Y}{2,3,5}{2,3,4,}1 00 0 1 1 00 1 0 1 1 1 最小化：X 1 2 3 4 Y5 XY60 12 35 4{,,,,,},{}{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}{,,,},{},{},{}{,,,}{,01234560123451350123451246012345601234135012345601231010==== 3012312401234560110112233234012345610101}{,,,}{,,}{,},{,}{},{},{}{,}{}{,}{,}{,}{}{,}{}{},{},{,},{},{},{}===== 0 10 0 1 00 1 0 1 1 1P64–8(1)01)0|1(*(2))5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*(3)******)110|0(01|)110|0(10P64–12(a)aa,b a 确定化：a b {0} {0,1} {1} {0,1} {0,1} {1} {1} {0} φ φφφ给状态编号：a b 0125 01 2 4 3 011 12 2 03 333aaa b b bba 最小化：{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}012301101223032330123a ba b ====a ab bab (b)b b aa baa bb aa a 已经确定化了,进行最小化 最小化：{{,}, {,,,}}012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}{,}{}{,}{,}{,}a b a b a b a b a b a =============={,}{,}{,}{,}{,}{,}{,}10243535353524 b a b0 1 2 3 01 2 0 2 3 14 5b b aa b aP64–14(1) 01 0 (2):(|)*0100 1 ε ε0 确定化：0 1 {X,1,Y} {1,Y} {2} {1,Y} {1,Y} {2} {2} {1,Y} φ φφφ 给状态编号：0 1 0 1 2 1 1 2 2 1 3 33 30 1 01 1 10 最小化：0 1 2 01YX YX2 1 0 2 13{,},{,}{,}{}{,}{}{,}{,}{,}{}{,},{},{}0123011012231323301230101====1 1 1 0第四章P81–1(1) 按照T,S 的顺序消除左递归ε|,)(||^)(T S T T S T T a S S G '→''→→'递归子程序： procedure S; beginif sym='a' or sym='^' then abvance else if sym='(' then begin advance;T;if sym=')' then advance; else error; end else error end;procedure T; begin S;'T end;procedure 'T ; beginif sym=',' then begin advance; S;'T end1 3其中:sym:是输入串指针IP 所指的符号 advance:是把IP 调至下一个输入符号 error:是出错诊察程序 (2)FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST('T )={,,ε} FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW('T )={)} 预测分析表a^() , # S S a →S →^S T →()TT ST →' T ST →' T ST →''T'→T ε '→'T ST ,是LL(1)文法P81–2文法：|^||)(|*||b a E P F F F P F T T T F T E E E T E →'→''→→''→+→''→εεε(1)FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#}考虑下列产生式:'→+'→'→'→E E T T F F P E a b ||*|()|^||εεεFIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. (3)+ * ( ) a b ^ # EE TE →'E TE →' E TE →' E TE →'E' '→+E E'→E ε'→E εTT F T →' T F T →' T F T →' T F T →'T' '→T ε '→T T '→T ε '→T T '→T T '→T T '→T εF F P F →' F P F →' F P F →' F P F →'F' '→F ε '→'F F * '→F ε '→F ε '→F ε '→F ε '→F ε '→F εPP E →() P a → P b → P →^(4)procedure E; beginif sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' end else error endprocedure E'; beginif sym='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T; beginif sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' end else error endprocedure T';if sym='(' or sym='a' or sym='b' or sym='^' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' endelse errorendprocedure F';beginif sym='*'then begin advance; F' endendprocedure P;beginif sym='a' or sym='b' or sym='^'then advanceelse if sym='(' thenbeginadvance; E;if sym=')' then advanceelse errorendelse errorend;P81–3/***************(1)是，满足三个条件。
