编译原理第3章.词法分析.ppt

第三章 词法分析 第三章. 词法分析§3.0 词法分析程序的功能 回忆：词法分析程序的功能：对构成源程序的字符串从左到右进行扫描和分解，并根据语言的词法规则识别出一个个具有独立意义的单词符号。 具体： ①设计成单独一遍扫描。 ②设计成子程序，当语法分析器需要新单词时调用它。 §3.1 词法分析程序的输入输出 一.输入：字符串表示的源程序 二.输出：单词符号或单词符号表示的源程序 1.语言的单词符号：是指语言中具有独立意义的最小语法单位。共分五类： 保留字、标识符、常数、运算符、和界符 2.单词符号的内部表示： 二元组（单词种别码，单词自身值） 继续 单词种别码 保留字： ①一字一种：1－begin 2－end 3－if 4－then ②全体为一种：0 或者 k 标识符： 全体为一种 常数： ①数据类型：整型、实型、字符型、布尔型 ②全体为一种 运算符： ①一符一种 ②全体为一种 界符： ①一符一种 ②全体为一种 返回 单词自身值 ①如果一个种别码对应一个单词符号，则种别码可以代表单词自身。 ②如果一个种别码对应多个单词符号，则单词自身值是单词符号的机内码。 ③用相应符号表项的指针值来区分同类中不同的单词符号。 K表： I表： C表： §3.2 词法分析程序的设计一.输入、预处理 二.单词符号的识别以及超前搜索 词法分析程序在识别单词时,对有些单词需要向源程序中多看若干个字符才能被识别,称为超前搜索。 1.关键字的识别: 有些语言中关键字的识别需要超前搜索。例如:FORTRAN语言中: 1 DO99K=1, 10 2 DO99K=1.10 2.标识符的识别: 以运算符、界符、空格等结束。 3.常数的识别: 需要超前搜索。例如: 5.EQ.M 和 5.E08。 4.运算符和界符的识别: 需要超前搜索。例如: = 三.状态转换图 状态转换图: 是由一组矢线连接的有限个结点所组成的有向图。其作用是识别相应的字符串。 例如: 标识符: I→ l | I l | I d 初态 =① ② ③ 终态 例如: 整数→数字 | 整数数字 =① ④ ⑤ 利用状态转换图识别(或接受)字符串的过程: 从初态出发, 按照与符号串余留部分中最左字符相匹配的原则, 游历状态图, 直至符号串的末端为止。如果这时恰好到达终态, 则符号串为该文法的句子；否则不是。例如：识别 num1、1001 初态 =① ② ③ 终态 ④ ⑤ 大多数程序设计语言的单词符号都可以用状态转换图来识别。可以用一张状态转换图或若干张状态转换图来描述一个语言的所有单词。例如：图3.3是简单语言词法分析的状态转换图。 2.由正规文法构造状态转换图(1).右线性文法 = 状态转换图 已知: G=(VN , VT , P , S ) P : A→aB | a A , B∈VN , a∈VT* 求: 状态转换图M 设: | VN |=k , 则状态转换图M共有k+1个结点 方法: ①初态=S , 增设终态结点F ②对G中形如A→aB 的产生式, 从结点A引一条矢线到结点B , 并用 a 标记。 ③对G中形如A→a 的产生式, 从结点A引一条矢线到终态结点F , 并用 a 标记。 ④对G中形如A→ε 的产生式, 从结点A引一条矢线到终态结点F , 并标记为 ε , 或令A为接受状态。 例如: 文法G[Z] : Z → 0A A → 0A | 0B B → 1A | ε 语言为 : L(G)=0 ( 0 | 01 )* 0 求 : 状态转换图。 (2).左线性文法 = 状态转换图 已知: G=(VN , VT , P , S ) P : A→Ba | a A , B∈VN , a∈VT* 求: 状态转换图M 设: | VN |=k , 则状态转换图M共有k+1个结点 方法:①新增初态=R , S=终态结点 ②对G中形如A→Ba 的产生式, 从结点B引一条矢线到结点A , 并标记为 a 。 ③对G中形如A→B 的产生式, 从结点B引一条矢线到结点A , 并标记为 ε 。 ④对G中形如A→a 的产生式, 从初态R引一条矢线到结点A , 并 标记为 a 。 例如: 文法G[S] : S → S1 | U1 U → U0 | 0 四.状态转换图 = 程序 词法分析程序的设计步骤: