第三章编译原理.ppt

1、在本章中，单词的记述工具单词的识别系统设定修订和字句解析程序的实现，首先需要编程语言中的原子单位单词的记述和描写，其次需要单词的识别和某些相关动作的实行。 编程语言词法的机制是正则表达式，识别机制是处于贫困状态的机器人。 回顾词法分析程序是什么，实现词法分析(lexical analysis )的程序将源程序字符一个一个地读入，按照配词规则分割成一系列的单词。 单词是语言中具有独立意义的最小单位，如保留字、标识符、运算符、标点符号和常量。 词法分析是编译中的一个阶段，在语法分析之前进行。 与语法分析结合为一次，语法分析程序也可以调用字句分析程序获取当前单词进行语法分析。词法分析程序和语法分析程

2、序之间的关系、源程序、词法分析程序、语法分析程序、Token、get token、词法分析程序的主要任务：阅读源程序，生成单词符号词法分析程序的其他任务：删除空格删除空格帮助理解常见的术语Token单词、词标、符号lexeme词素、词位pattern模式、样式、术语In general。 thereisasetofstringsintheinputforwhichthesametokenisproducedasoutput.thissetofstringsisdescribedbyarulecalledapatternasso ciatternasso nissaidtomatcheachst

3、ringintheset.alexemeisasequenceofcharactersinthesourceprogramthatismattion bythepatternforatoken.e.g.co 其中的pi是token “identifier”的lexeme，其pattern是letterfollowedbylettersand/or digit . 语篇分析工作独立于语法分析工作的原因：编程语言中的单词是基本语法成分，单词符号语法可以用有效的工具描述，简化设置、提高编译效率、提高编译系统的可能性。 根据这样的记述工具实现字句解析程序的自动构筑的字母的字母是要素的非空的贫穷的集合，

4、字母的要素称为符号，所以字母也称为符号集合。 不同的语言可以有不同的字母。 例如，汉语字母包括汉字、数字、标点符号等。 PASCAL语言的字母由字母、数字、几个专用符号和BEGIN、IF等保留字组成。 符号串在字母表中包括符号的任何贫穷序列被称为符号串，并且例如00 11 10是在字母=0，1上的符号串。 在字母A=a、b、c上的多个符号串是a、b、c、ab、aaca。 在符号串中，符号的顺序是重要的，符号串ab与ba不同，abca和aabc也不同。 符号串可以用字母表示。 例如，x=STR表示“x是符号s、t、r，按此顺序组成的符号串”。 如果在符号串的某个长度的符号串x中有m个符号，则将其

5、长度称为m，表示为x=m，001110的长度是6。 空符号串，即不包含符号的符号串被表示为所述符号，并且其长度为0，即=0。 以介绍有关符号串的一些运算。符号串的开头、尾巴、固有的开头和固有的尾巴：如果z=xy是符号串，则x是z的开头，y是z的尾巴，如果x不是空，则y和固有的尾巴一样，如果y不是空，则x是固有的头部。 假设z=abc，对于：z的开头是a、ab和abc，除了abc之外都是唯一的。 z的尾部是c，bc，abc，z的固有尾部是c，bc。 如果对符号串z=xy的开头感兴趣，而对其伪部分不感兴趣，则采用省略标记法： z=x； 如果只是为了强调x出现在符号串z的某个地方，则z=x； 符号t

6、是符号串z的第一个符号，标记为z=t。、符号串的连接：将x和y设为符号串，这些连接xy是将y符号写在x符号之后的符号串。 例如，在x=ST和y=abu的情况下，连接xy=STabu可以看到其中x=2、y=3和xy=5个符号串的平方根，即，符号串本身通过将n次连接的符号串an连接到aaaa n个a a1=a， 如果定义x=AB，则3360 x0=x1=ab x2=ababx3=abab xn=xxn-1=xn-1 x (n0)；符号串集合：如果集合a中的所有元素都在字母表上，则两个符号串的集合a和b的乘积是否为AB=xy|xA 如果是1，则AB=ab1、ab0、cde0、cde1被定义为由*表示

7、的上述所有符号串(包含)构成的集合。 把由除上面以外的所有符号串构成的集合记作。 叫正闭包。 例如，=a、b *=、a、b、aa、ab、ba、bb、aaa、aab、=a、b、aa、ab、ba，我们编写单词符号。 正规式及其表示的正规集合的递归定义如下所示。 定义(正规表达式及其表示的正规集): 设字母为辅助字母=、 一和都是上面的正规式，它们表示的正规集合分别是和，2。 任意a，a是上面的正规公式，它表示的正规集是a。 三假设e1和e2都是上面的正规式，它们表示的正规集合分别是L(e1)和L(e2)，那么(e1)，e1 e2，e1 e2，e1也是正规式，它们表示的正规集合分别是L(e1)，4。

8、 只有通过有限次使用上述3个步骤而定义的公式是上述的正规公式，只有用这些正规公式表示的集合是上述的正规集合。 中的组合图层性质变更选项。 正规表达式的符号。 其中的“”读成“或”(有的用“”代替)。 将“”读取为“连接”将“”读取为“闭包”(即，任何有限次数的自我复制连接)。 如果不混淆，可以省略括号，但运算符的优先级应为“”、“”、“”。 连接器“”一般可以省略不写。 、都是左键。 作为示例，与上述正规公式对应的正规集合的示例包括正规公式集合a a ab a、b ab ab (ab )、aa、ab、ba、bb a、a、a， 所有的ab包括a和b的串(ab)(aabb)(ab )上包括两个连续

9、的a或连续的b的串都可以是当考虑d时，由上述正规式r=l(l d )定义的正规集合是330，其表示的正规集中的各要素的模式是以字母开头的字母数字串，是Pascal和多个编程语言允许的识别符的字句规则编程语言的单词都可以用正规式定义，如果两个正规式e1和e2表示的正规集相同，则e1和e2等价，写成e1=e2。 例如，假设e1=(ab )、e2=ba还是e1=b(ab )、e2=(ba)b e1=(ab )、e2=(ab )、的RS=Sr“或”遵循交换规则2。 r(st)=(rs)t“或”的可耦合律3。 (rs)t=r(st )连接的可能结合律4。 r(st)=rsrt (st)r=srtr分配规

10、则，5 r=r，r=r是“连接”的恒等元素零一律6。 RR=RR=RRRor”的提取规则是：有穷自动机，有穷自动机(也称为有限自动机)，能够正确识别正规集合，即正规语法中定义的语言和正规表达式表示的集合，导入穷自动机这一理论，为词法分析程序的自动构造寻找特殊穷机器人有确定的穷机器人(Deterministic Finite Automata )和不确定的穷机器人(Nondeterministic Finite Automata )两种。 关于穷人机器人我们探讨了以下主题。 确定了的穷人机器人DFA不确定的穷人机器人NFA NFA的确定化DFA的最小化，确定了的穷人机器人DFA，DFA定义：确定

11、了的穷人机器人(DFA)M是一个五组： M=(K，)2.是穷字母，其各要素被称为输入符号，所以输入DFA定义，其中3.f是变换函数，KK上的映射，即f(ki，a)=kj，(kiK，kjK )，指示当前状态为ki，输入符号为a时下一个变换的4.SK是唯一的初始状态5.Z K是最终状态集合，并且最终状态是可接受的在DFA的实例中，假定DFA M=(S，u，v，q，a，b，f，s，q )其中f包含f(S，a)=U f(V，v DFA M )个状态，且含有n个输入字符，那么此状态图包含m个节点，每个节点最多出现n个弧单击初始状态节点的双箭头“=”或“-”，终止状态节点的双圆形显示或“”。 在DFA状态

12、图中，DFA的行表示状态，列表示输入字符，矩阵元素也可以表示对应的状态行和输入字符串下的新状态，即k行a列表示f(k，a )的值的矩阵。 否则，第一行是初始状态，对应的最终状态行在表的右端显示为1，在非最终状态显示为0。DFA的矩阵表示001、DFA如何用作识别机制，需要理解以下定义。 *上的符号串t对DFA M执行输入符号串t，(以Tt1的形式表示)。 其中，t、t1 * )为DFA M=() t1)其中，QK扩展转换函数f为K*K上的映射，f(ki，)=ki，*上的符号串t为DFA M接受M=(K，f，s，z )，如果是t *，则dfam接受t 得到了f(S，b )=f (u，b，aab)

13、=f(V，a，ab)=f ()的证据。 如上所述，b、a、b、a、a、DFA M可以接受的符号串的总数被标记为L(M )，并且DFA的可靠性确定变换函数f:KK是单值函数，即，任何状态kK以及对输入符号a、f(k，a )唯一地确定下一状态从状态转移图来看，如果字母中含有n个输入字符，则任意一个状态节点最多出现n条弧，每条弧用不同的输入字符表示。DFA的行为是用程序模拟. DFA M=(K，f，s，z )的行为的模拟程序K:=S； c:=getchar； 英国首席执行官k 3360=f (k，c )； c:=getchar； ifkisinzthenreturn (是) else return (否)，review，regularexpressionsonthealphabetaredefinedbythefollowingrecursiverules :1 ) andfisaregularexpression3) if r1andr2areregularexpressions、soare (r1)