编译原理chpt3词法分析及其自动构造ppt课件.ppt

《编译原理chpt3词法分析及其自动构造ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、词法分析程序（扫描器）的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。描述程序设计语言的词法的机制是3型文法和正则表达式，识别机制是有穷状态自动机。第三章词法分析及其自动构造单词的描述工具-正规表达式单词的识别系统-有穷自动机设计词法分析程序,实现词法分析程序的自动构造回顾什麽是词法分析程序实现词法分析（lexicalanalysis）的程序按照构词规则将源程序切分成一系列单词，其输出为二元组：(单词种类，单词自身值)单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。可以是独立的一遍，更一般作为语法分析的一个子程序。源程序词法分析程序语

2、法分析程序Tokengettoken….源程序词法分析程序语法分析程序3.1正规式与正规集正规式（regularexpression）,是定义正规集的数学工具。它是描述单词的模式(pattern)的一种重要的表示法。令={a，b}，上的正规式和相应的正规集的例子abab(ab)(ab)a(ab)(ab)(aabb)(ab){a,b}{ab}{aa,ab,ba,bb}{,a,……任意个a的串}{,a,b,aa……所有由a和b组成的串}{上所有含有两个相继的a或两个相继的b组成的串}正规表达式与正规集（正规语言）设字母表为，辅助字母表`={，，，

3、，，，}。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.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集例3.1令={l，d}，则上的正规式r=l(ld)定义的正规集为:{l,ll,ld,ldd,……},其中

4、l代表字母,d代表数字,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,是多数程序设计语言的标识符的词法规则.例3.2={d，，e，+，-},则上的正规式d(dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。程序设计语言的单词都能用正规式来定义若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。例如：e1=(ab)与e2=bae1=b(ab)与e2=(ba)be1=(ab)与e2=(ab)正规式的描述能力有限，它不能用于描述嵌套的结构正规表达式与正规集的代数规律设r,s,t为正规式

5、，正规式服从的代数规律有：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分配律5.r=r、r=r零一律6.rr=rr=rrr…“或”的抽取律3.2有穷自动机有穷自动机作为一种识别装置，它能准确地识别正规集，即识别正规式所表示的集合。有穷自动机分为两类：确定的有穷自动机(DeterministicFiniteAutomata)和不确定的有穷自动机(NondeterministicFiniteAutomata)。3.2.1确定的有穷自动机D

6、FA一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.Σ是一个有穷字母表，它的每个元素称为一个输入符号；3.f是转换函数，是在K×Σ→K上的映射，就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.S∈K是唯一的一个初态；5.ZK是一个终态集，终态也称可接受状态。一个DFA的例子：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）

7、=Vf（Q，b）=QDFA的状态图和矩阵表示bSUVQaaaba，bb字符状态0001∑*上的符号串t被DFAM接受例：证明t=baab被下图的DFA所接受。f（S，baab）=f（f（S，b），aab）=f（V，aab）=f（f（V，a），ab）=f（U，ab）=f（f（U，a），b）=f（Q，b）=QQ属于终态。得证。bSUVQabba,baa结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。