编译原理(第2章 词法分析).ppt

1、词汇分析，2012-9-30，本章要回答的问题，词汇分析程序的单词描述技术，词汇分析程序的自动构造原理，目录，词汇分析程序设计，1，正则表达式，有限自动机，词汇分析：输入源程序，从左到右读入字符，扫描字符流，分解字符串，识别一个字符。组成源程序的字符流从左到右读取，并分组到标记中，标记是具有集合意义的字符序列。单词符号一般包括：标识符、保留字、运算符、分隔符、各种常量等。示例：标识符由一个字符序列组成，该序列以字母字符开头，后跟字母和数字。词汇分析，源程序字符串，构词规则，规则有限自动机，单词符号序列，以及词汇分析程序的输出。问：如何理解单词符号的确定性？词法分析器的输出形式，以及单词符号的表

2、达形式：二进制(单词类别，单词值)单词类别。1，一类用整数值表示其属性的词。例如，1代表关键字，2代表标识符，等等。2.每个单词对应一个类别。例如，1代表开始，2代表结束，等等。这个词本身的价值。它可以表示为：常数的二进制表示；常数、变量等的地址码。符号表等。标识符通常属于一种。常数应除以类型(整数、实数、布尔值)。关键词可以被视为一种整体，或一个词一种。可以使用一个运算符，但具有某些共性的运算符也可以被视为一个运算符。(运算逻辑关系)边界字符通常是一个字符。如何分类主要取决于治疗的便利性。如果有一个符号，这个词本身的价值是不必要的。否则，请查阅符号表。问：如何用程序的语言来编码各种各样的单词

3、？词法分析输出表单示例，示例：程序段如果i=5，则x :=y；关键字if (3，“if”)标识符I (1，符号表条目指向I)等号=(4，=)常数(2，5)关键字然后(3，然后)标识符x (1，符号表条目指向x)分配号：=(4，=)标识符y(，)，示例2:程序段，而(I=j)I-；关键字while(while，_)括号(，_)标识符i (id，指向I符号表条目)运算符=(=，_)标识符j (id，指向J符号表条目)括号(，_)标识符I (id，指向I符号表条目)运算符-(-，_)分号；(；_)，一个符号，一个类，这两种输出形式有什么区别？词汇分析和语法分析之间的关系，以及将词汇分析和语法分析分开

4、的优点：简化设计。使编译器的结构更加简洁、清晰和有条理。提高编译效率。专业的字符阅读和分词技术；词汇分析器的自动构建。编译器的可移植性。部分涉及源语言的具体要求。词法分析是一个独立的一次性或独立的子程序，一个词法分析程序的过程，以及其他一些任务：过滤出空格，跳过评论，换行符，跟踪换行符，记录行号，复制错误，源程序宏扩展，输入缓冲区，扫描缓冲区，单词序列，源程序，预处理子程序，扫描仪，解析器，单词识别过程的本质是模式匹配！输入缓冲区：如果一个完整的单词被截断了怎么办？例如：EN GOTO 100，提前搜索，关键字识别：例如，在标准FORTRAN中，1，DO99K=1，10 2，IF(5。等式(M

5、)I=10 3，DO99K=1.10 4，IF(5)=55，其中DO和IF是标识符的一部分。因此，不难识别。常数的识别在某些语言中，常数的识别也需要使用前瞻搜索。示例：科学表示中运算符和边界的识别对于C语言中的“=”、“-”等运算符，有必要提前搜索。你需要向前看来确定符号类型！例如：PL/0程序的词法分析设计，识别字：保留字：标识符如BEGIN、END、if、THEN等。用户定义的变量名、常量名、过程名、常量，如10、25、100等。整数运算符，如：-、*、/、=、#、=、=、(、)等。例：PL/0词法分析程序的设计，词法分析过程中要完成的任务GETSYM: getch过滤空间识别保留字识别标

6、识符拼写识别单字符字拼写双字符字识别其他，识别出的字信息通过三个完整的参数SYM、ID和NUM传输到解析器SYM:存储字的类别、一个符号和一个ID、存储用户定义的标识符NUM的值、存储用户定义的数字、枚举符号NUL、ident、数字、加、减、倍、斜线、奇数符号、eql、nen例如：PL/0词法分析器设计，单词识别使用状态转移图来编译一个对应于每个状态的程序，每个状态调用字符提取程序，根据当前的字符，它转到不同的状态，并做出相应的操作来识别一个单词是最终状态，并且有很多问题和语言。编写不同语言的编译器有可能在明确的规则下快速自动地构建一个词法分析器吗？目录，词法分析程序设计，1，正则表达式，3，

7、有限自动机，正则表达式介绍，正规表达式也称为正则表达式，是定义正规集的数学工具。(“正则集代数”)正则表达式用于描述或匹配符合特定语法规则的一系列字符串。正则表达式的概念最初来自Unix中的工具软件(如sed和grep)。许多编程语言支持正则表达式的字符串操作。由于正则表达式的主要应用对象是文本，所以它也用于各种文本编辑器中。例如：输入的电子邮件地址的格式是否正确，编程语言单词是基本的语法符号，正常的表达式是解释单词模式的重要表示(标记)，也是描述单词符号的好工具。准备知识：集合运算，子集* U，V:产品紫外=| U，而aeof do K:=f(K，a)；/输入字符a是字母a:=getchar

8、；如果K在Z中，则返回(是)；否则返回(否)；结论：DFA M接受的所有符号串都表示为L(M)。结论：当且仅当最后一个符号串集合上有一个确定的有限自动机时，它才是正规的，因此V=L(M)。DFA的确定性是映射f: kk是单值函数。也就是说，对于任何状态sK和输入符号a，f(s，a)唯一地确定一个状态。问：如果允许它是一个多值函数呢？不确定有限自动机NFA，NFA M=K，f，s，Z，其中K是一个有限的非空状态集，一个有限的输入字母表，f是从K *到k (2 K)子集的映射，SK是一个初始状态集，Z K是一个终端状态集。问：它的定义和它的定义有什么区别？例如，NFA M=(S，P，Z，0，1，f

9、，S，P，Z)，其中f(S，0)=P f(S，1)=S，Z f(P，1)=Z f(Z，0)=P f(Z，1)每个节点可以发出几个弧来连接其他节点。每个弧都标有*中的一个词(可以是不同的词或空词)。整个图至少包含一个初始节点和几个最终节点(可以是0)。有些节点可以是初始节点，也可以是最终节点。问：它的状态图和？NFA的矩阵表示被简化为具有转移的NFA，f是从K *到k (2 K)的子集的映射，并且1，2、a、b、c *上的符号串t被NFA M所接受。定义：对于其中的任何串t，如果从某个初始状态有一个结，如果M的某些节点既是初始状态又是最终状态， 或者有一条从初始状态节点到最终状态节点的道路，在这

10、条道路上所有的弧都被标记，那么空的字可以被m接受，000 111 1010001 11000001 00 01100，问：这个图接受的所有字符串是什么？ 它的正常形式是什么？练习：字符串被NFA接受，10，a，2，1，b，3，7，5，6，4，8，9，c。考虑以下NFA如何通过转换接受字符串，NFA确定性：转换为等价的DFA，DFA是NFA的一个特例。每个NFAN都必须有一个密度泛函理论模型，这样L(M)=L(N)。每个NFA N有一个等价的DFA M.有一种算法可以将NFA语转换成接受同一种语言的DFA，而相当于NFA语的DFA并不是唯一的。如何将NFA转化为？定义了状态集I的几个相关运算，状

11、态集-闭包(I):如果状态集I的-闭包是sI，那么s _闭包(I)；如果是sI，那么从s开始通过任何弧可以到达的任何状态s都属于_ CLOSURE)。状态集1A:状态集I的弧转移是NFA M的状态集A的子集。它被表示为移动(I，A)，并被定义为状态集J。其中J是从I中的某个状态通过A弧可以达到的所有状态的整体。Ia=_ CLOSURE)，例：状态集I的运算，I=1，-CLOSE(I)=1，2；I=5，-闭包(I)=5，6，2；移动(1，2，a)=5，3，4 Ia=-闭包(5，3，4)=2，3，4，5，6，7，8；1，2，5，3，4，a，a，-(a)-j-()-ia，子集算法，将字母表中的所有元

12、素列为2n 1示例：=a，b确定初始状态_ closed找出该行的第二个和第三个子集ia和Ib，并查看它们是否出现在表的第一列中。如果它们没有出现，请将它们填入后面空行的第一列。(如果有多个元素，请依次列出)重复处理，直到第二列和第三列子集的所有列都出现在第一列中，并且没有未填充的状态子集。示例：子集算法，I=_ closex是X，5，1。从状态1通过弧a可以达到的整个状态J是5，3，_ CLOSE(J)=5，3，1。因此Ia=5，3，1。0 1 2 3 4 5 6，示例：子集算法，重命名右下图中的所有状态子集，获得左图中的状态转移矩阵，形成以下状态转移矩阵，从而获得相应的DFA。如图所示：摘

13、要：NFA判定，补充练习：P58书中的例子，构造NFA N的状态K的子集的算法：假设构造的子集族是C，即C=(t1，T2，t1，T2，Ti是状态k1的子集。首先，让-闭包(K0)是c语言中唯一的成员，它是无标记的。而(C中还没有标记子集t)标记t；对于每个输入字母a do u :=-闭包(移动(t，a)；如果U不在c中，那么在c中添加U作为一个未标记的子集，以确定有限自动机的简化。有限自动机M的简化是指找到一个状态少于M的有限自动机M，这样L(M)=L(M)。DFA最小化的意义：它没有冗余状态，也没有两个状态彼此等价。没有多余的状态(死状态)没有两个状态彼此等价(无法区分)。两个状态S和T的条

14、件兼容性与最终状态相同，或者与非最终状态传播相同。对于所有的输入符号，状态S和T被转换为等价状态，例如：冗余状态，冗余状态：从自动机的起始状态开始，任何输入字符串都不能到达该状态。或者没有从这个状态到最终状态的路径。示例：等效状态，C和D都是最终状态；在A中读到C和F，C和F都是最终状态，C和F在A中读到C；读数B都达到E；因此：C和D是等价的，B，A，S，B，A，A，A，B，B，B，B，B，B，DFA最小化：分割方法：首先，将M的状态分成两组：最终组3，4，5，6，非最终组。因为0，1，2a1，3既不包含在3，4，5，6中，也不包含在0，1，2中，所以应该对其进行划分。因为状态1通过弧A到达状态3，而状态0，2通过弧A到达状态1，1应该被划分成1，0，2，然后0，2应该被调查。因为，每个组都不能被细分。(演示)，DFA最小化：分段方法，最后让状态3代表3，4，5，6，将所有达到原始状态4，5，6的弧导入到3中，并删除4，5，6，从而得到简化的DFA:还记得这张图片吗？它的输入字符串的完整集合是什么？概要：