编译原理第3章(1).ppt

1、第三章词汇分析和有限自动机、有限自动机是构建词汇分析程序的理论基础。本章主要介绍了司法分析程序的设计原理和构造方法，重点介绍了自动机的基本概念和正规语法、正则表达式、宾子机器人之间的相互关系。第三章词汇分析和有限机器人、词汇分析器功能、词汇分析器编写方法、正规语法和有限机器人、正规表达式和有限机器人、语言单词符号两种定义方法、单词符号和输出单词的形式、词汇分析的任务是从左到右扫描和分解字符串表示的源程序。根据语言的词汇规则确定一个独立，3.1词汇分析器的功能，字符串表示的源程序，语法分析器，单词符号，下一个单词符号，语法分析器，3.2单词符号和输出单词的格式，关键字也称为基本单词。例如，C语言

2、中的if、else、While和标识符表示各种名称，如变量名、常量名称、数组名称和函数名称。语言的单词符号表示在语言中具有独立意义的最小语法单位。3.2单词符号和输出单词的格式、整数常量125、实数常量0.718、布尔常量TRUE等各种类型的常量。可以使用以下运算符：*、/、等。分隔符为、(，)，等。3.2单词符号和输出单词的格式，词汇分析器输出单词的格式，词汇分析器输出的单词符号通常是，(单词类型，单词本身的值)，3.2单词符号和输出单词的格式，单词类型，单词类型表示单词的种类，是进行语法分析所需的信息。为了便于处理，通常将整数编号映射到每个单词。3.2单词符号和输出单词的形式，常数3360

3、可以分类为一个，也可以按类型(整数、实数、布尔等)分类。基本字：可以把整个看作一个整体，也可以用一个字。标识符：通常分类为一个。运算符和边界符号：可以使用一种分隔方法或分类为一种。3.2单词符号和输出单词的格式，单词本身的值，一种仅包含一个单词符号，一种包含多个单词符号，(1)标识符本身的值是标识符本身的字符串。(2)常量本身的值是常量本身的二进制值。值是类别编码、3.2单词符号和输出单词的形式，(3)使用特定类型表格的特定项指针值分隔同一种类的徐璐其他单词。例如，对于标识符，使用符号表中的条目指针作为其自身的值。常量使用常量表中的入口指针作为其自身的值。，3.2单词符号和输出单词的格式，常量

4、本身的值显示为常量本身的值(转换为标准二进制格式)。范例： if(a1)b=100；假设、基本单词、运算符和边界字符都匹配。标识符本身的值显示为自己的字符串。假设3.2单词符号和输出单词的形式，标识符的种类编码为整数10。常数的种类编码为整数11。基本单词if编码为2。指定号码的种类编码为17。较大的种类编码为23。分号的种类编码为26。左括号的种类编码为29。右括号的种类编码为30。程序段：3.2单词符号和输出单词格式，if(a1)b=100；词法分析器扫描后输出的单词符号字符串为，(2，)基本单词if，(29，)左括号(，(10，a)标识符a，(23，)大于，(11，)，3.3定义单词符号

5、的的正则表达式。这是正则集中的空符号字符串，即。3 .ai是的正则表达式。这表示正则集由单个符号ai(即ai)组成。3.3.1正则表达式和正则集，4 .如果E1和E2是常识，则分别表示L(e1)和L(e2)的正则集：(1) E1 | E2是想象中的正则表达式。L(e1e2)=L(e1)L(e2)，(3) (e1)*也是的正则表达式。这是表示l (E1) *)=(l)的正则表达式，其中闭包运算具有最高优先级，连接运算紧随其后或运算最低。链接文字“”通常可以省略，不写。这三个运算符都是左连接。3.3.1正则表达式和正则集，示例1包含字母=a，b。根据正则表达式和正则集的定义，A和B是正则表达式，对

6、应的正则集是2 .a | b是正则表达式，对应的正则集是3。L(ab)=L(a)L(b)=ab=ab，公式和正则集，4 .必须指出的是，(a | b)*是公式，其正则集为：不能将A，b*的子集视为正则集。l (a | b) *)=(l (a | b) *=a，b *=，a，b，aa，ab，ba，bb，5 编程语言部分单词符号可以定义为以下正则表达式：标识符l (l | d)* l表示az中的任何字符，整数常量dd* d表示09中的任何数字，关系运算符=，3.3.1正则表达式和正则集，正则表达式和正则语法的差异和关联：标识符ID=L 3 . 3 . 3 记录为R1R2。，例如(a | b)*=(

7、a* b *)*；B(ab)*=(ba)*b，3.3.1公式和正则集，公式具有以下特性3360，1A | B=B | A(交换方法)，2a | (b | 5(A |)，分析首先提供相应的正则表达式公式(公式中的正则表达式“|”而不是“|”)，如下所示：z=0a (1)，a=0a 0b (2)，b=1a (3)，Z 0A=0A 01A 0(4)，(4)利用分配方法，A=(0 01用(1)表达式中的A替换(6)，可以得到Z=0 (0 01)* 0，R=0 (0 | 01)* 0，3.3.2正则语法和正则表达式。例如：分析首先提供相应的正则表达式公式(在表达式中使用“”代替正则表达式的“|”)，如下

8、所示：a=abbb (1)，b=AC a b (2)，c=ab (3)，3 B=(aa)*(a b) (5)，(5)赋值(使用(4)的解释规则，即正则语法GZ生成语言的正则表达式为z=u0v1 (1)，u=Z1 1(2)，v=z0=R=(10 | 01)(10 | 01) ，(3)如果A和B都是公式，则诸如AaB的规则将转换为Aab和Bb。其中B是新的非终结器。3.3.2正则语法和正则表达式，(4)在转换的语法中，A a*b等规则进一步转换为A aA | b。使用，(5)规则(3)和(4)继续转换，直到每个规则最多包含一个终结器。3.3.2正则语法和正则表达式，示例1将R=(a | b)(aa

9、)*(a | b)转换为相应的正则语法，从而使A成为语法起始符号，根据规则(2)，根据规则(2)，根据a aa、I lt、t lt | dt |、I l | lt、t l | d | lt | dt、3.4正则和有限机器人，有限机器人是具有离散输入和输出系统的抽象数学模型。有限机器人有“确定”和“不确定”两种类型，确定的有限机器人和不确定的有限机器人都可以准确地识别正规集。3.4.1决定贫穷的机器人，决定贫穷的机器人(DFA)，贫穷的机器人M是5元组，Q是贫穷的状态集合，每个元素称为状态。是穷输入字母表，其中每个元素称为输入字符。M=(Q，f，S，Z)表示当前状态为qi，输入字符为a时，自动机切换到下一状态QJ，QJ称为qi的后续状态。f是从q到q的单值映射。m=