ch3 词法分析.ppt

计算机编译原理 计算机编译原理 第三章 词法分析 学习内容 3.1 词法分析的任务 3.2 词法分析程序的设计与实现 3.3 正规式与有穷自动机 3.4 词法分析程序的自动构造工具 学习目标 掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的转换、DFA的化简 理解：正规文法、正规式、DFA的概念、NFA的概念 了解：词法分析程序的自动构造工具 3.1 词法分析的任务 词法分析是编译过程中的第一个阶段，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。 输入：源程序字符串 输出：单词符号（最基本的语法单位） 词法分析程序的功能 词法分析程序主要执行以下功能： 读入源程序字符串，识别开具有独立含义的最小语法单位——单词（符号）； 把单词变换成长度统一的且为定长的属性字； 其他功能： 滤掉空格，跳过注释、换行符 某些预加工处理 词法分析程序的实现方式 1.词法分析单独作为一遍 优点: 结构清晰、各遍功能单一，有利于集中考虑词法分析一些枝节问题。 词法分析程序的实现方式 2.词法分析程序作为单独的子程序 更通常情况，常将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。 词法分析程序的输出 1.单词的种类 单词符号一般可分为下列五种： 基本字（关键字）：begin、end、if、while、var 标识符：常量名、变量名、过程名 常数（量）：25、3.1415、true、“ABC” 运算符：＋、－、*、＜= 界符：逗点、分号、括号 词法分析程序的输出 单词类别：表示单词种类，常用整数编码，它是语法分析需要的 几种常用的单词内部形式： 1）一类一种：按单词种类分类。 2）一字一种：保留字、运算符和分界符采用一符一类，所有标识符为一个编码，所有常数为 一个编码。 词法分析程序的输出 2.单词的输出形式： （单词种别，单词符号的属性值） 单词的属性值：指单词符号的特征，通过属性值把同一种类的单词区别开来。关键字、常数、运算符和分界符的属性值即为自身值，标识符的的属性值为为存放该标识符的符号表入口的指针。 例1（一类一种） 单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，关键字为3，运算符为4，界符为5。 if i=5 then x:=y 关键字　if　　(3, ‘ if’) 标识符　i 　　（1，指向i的符号表入口） 等号　＝　　 （4, ‘= ’） 常数　5　　 （ 2, ‘5’ ） 关键字　then　　 （ 3, ‘then ’ ） 标识符　x　　 （ 4,指向x的符号表入口） … 例2（一字一种） C程序 while (i=j) i--; 输出单词符号： while, - (, - id, 指向i的符号表项的指针 =, - id, 指向j的符号表项的指针 ), - id, 指向i的符号表项的指针 --, - ;, - 若一个种别只有一个单词符号，则种别编码就代表该单词符号。 3.2 词法分析程序的设计与实现 状态图 状态转换图是为了识别正规文法所表示的单词而设计的一种有限方向图。 在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连接，箭弧上的标记（符号）代表在射出结点状态下可能出现的输入符号或符号类。 3.2 词法分析程序的设计与实现 一张状态转换图只包含有限个状态，即有限个结点，其中有一个初态，并由若干终态（用双圆圈表示）。 复习——正规文法 3型文法(正规文法)： 它是2型文法的特例,任一产生式α→β的形式都为 A→aB或 A→a，其中A ，B∈VN ，a∈VT。 在程序设计语言中，3型文法通常用来描述单词的结构。 正规文法又成为右线性文法。 左线性文法：产生式为 A→Ba或 A→a 由正规文法构造状态图 1.对于右线性文法，状态图的构造步骤如下： 步骤1：增加节点Z为终态（假定文法的字母表中不包括符号Z）； 步骤2：将每一个非终结符号设置为一个对应的状态； 步骤3：对于形如A→a的每一个规则，引一条从状态A到Z的弧，弧上标记为a；而对于形如A→aB的每个规则，引一条从状态A到B的弧，标记为a（其中B∈VN ，a∈VT ）。 由正规文法构造状态图 2.对于左线性文法，状态图的构造步骤如下： 步骤1：增加节点S为初态（假定文法的字母表中不包括符号S）； 步骤2：将每一个非终结符号设置为一个对应的状态； 步骤3：对于形如A→a的每一个规则，引一条从状态S到A的弧，弧上标记为a；而对于形如A→Ba的每个规则，引一条从状态B到A的弧，标记为a（其中B∈VN ，a∈VT ）。 例子 假设某语言的标识符用一下正规文法来定义： G[S]: S