退字符 ˉ在超前扫描结束后,还要“回退″字符,即将 超前扫描的字符退回输入缓冲区。 实现回退的数据结构:堆栈 回退:将要回退的字符依次压入堆栈 扫描:检查堆栈是否为空,如果不为空,则从栈顶 读取后续字符,否则从输入字符串读取。 书中P45程序3-1给出了使用堆栈实现多字符 回退的算法 16
16 回退字符 ◼ 在超前扫描结束后，还要“回退”字符，即将 超前扫描的字符退回输入缓冲区。 ◼ 实现回退的数据结构：堆栈 – 回退：将要回退的字符依次压入堆栈。 – 扫描：检查堆栈是否为空，如果不为空，则从栈顶 读取后续字符，否则从输入字符串读取。 ◼ 书中 P45程序3-1给出了使用堆栈实现多字符 回退的算法
3.14源程序的输入及预处理 ■缓冲输入:将磁盘上的源程序分批送入缓冲 区,等待扫描器处理。可以提高读盘效率和 方便扫描器工作。 输入系统:一组完成源程序输入的函数或者 子程序,支持读盘、超前搜索、多字符回退 等操作 ■Lex中的扫描缓冲区实例:P46,图3-2 ■预处理:消除无用空白、回车、换行、制表 注释、区分标号区、续行号( FORTRAN) 17
17 3.1.4 源程序的输入及预处理 ◼ 缓冲输入：将磁盘上的源程序分批送入缓冲 区，等待扫描器处理。可以提高读盘效率和 方便扫描器工作。 ◼ 输入系统：一组完成源程序输入的函数或者 子程序，支持读盘、超前搜索、多字符回退 等操作 ◼ Lex中的扫描缓冲区实例：P46,图3-2 ◼ 预处理:消除无用空白、回车、换行、制表、 注释、区分标号区、续行号（FORTRAN） 等
32正规文法和状态转换图 单词的描述:正规文法定义了3型语言,常见 的单词可由正规文法定义。 单词的识别:状态转换图可用于识别3型语言, 它是设计和实现扫描器的一种有效工具,是有 限自动机的直观图示。 18
18 3.2 正规文法和状态转换图 单词的描述：正规文法定义了3型语言，常见 的单词可由正规文法定义。 单词的识别：状态转换图可用于识别3型语言， 它是设计和实现扫描器的一种有效工具，是有 限自动机的直观图示
3.2.1由正规文法构造状态转换图 ■程序设计语言的单词都能用正规文法描述,例如, 标识符可定义为: <标识符><标识符>字母 <标识符><标识符>数字 <标识符>→字母 ■若把字母、数字视为终结符,则上述产生式为左 线性文法,是正规文法。 若我们用d表示0-9间的数字,则C语言的<无符 号数>的文法是右线性文法,也是正规文法(见 P48) 19
19 3.2.1 由正规文法构造状态转换图 ◼ 程序设计语言的单词都能用正规文法描述，例如， 标识符可定义为： <标识符>→<标识符>字母 <标识符>→<标识符>数字 <标识符> →字母 ◼ 若把字母、数字视为终结符，则上述产生式为左 线性文法，是正规文法。 ◼ 若我们用d表示0-9间的数字，则C语言的<无符 号数>的文法是右线性文法，也是正规文法（见 P48）
状态转换图 状态转换图:由一组矢线连接的有限个结点所 组成的有向图。 每个结点代表在识别分析过程中扫描器所处的状态, 其中含有一个初始状态和若千个终态。在图中,状 态用圆圈表示,终态用双层圆圈表示。 状态之间可用有向边连接,其上标记一字符a∈Σ, 表示从有向边的射出状态出发,识别一字符a后, 将进入箭头所指状态(结点) 凡能用正规文法描述的语言,均可由某种有限 状态算法—状态转换图进行分析
20 状态转换图 ◼ 状态转换图：由一组矢线连接的有限个结点所 组成的有向图。 –每个结点代表在识别分析过程中扫描器所处的状态， 其中含有一个初始状态和若干个终态。在图中，状 态用圆圈表示，终态用双层圆圈表示。 –状态之间可用有向边连接，其上标记一字符a， 表示从有向边的射出状态出发，识别一字符a后， 将进入箭头所指状态（结点） ◼ 凡能用正规文法描述的语言，均可由某种有限 状态算法——状态转换图进行分析