第3章_词法分析和词法分析程序.ppt

编 译 原 理 第 三 章 词法分析和词法分析程序 Principles of Compiler Design Chapter 3. Lexical Analysis 3.1 设计扫描器时应考虑的问题 词法分析程序亦称为扫描器 任务：扫描程序，识别单词 扫描器的输出是语法分析程序的输入 3.1 How to construct a lexical analyzer A lexical analyzer is also called Scanner The main task of the lexical analyzer is to read the input characters of the source program, and group them into lexemes. The lexical analyzer outputs a sequence of tokens for each lexeme in the source program to the parser for syntax analysis. 3.1.1 词法分析的必要性 描述单词的结构比其它语法结构简单，仅用3型文法就够了； 将单词识别从语法分析识别分离出来，可采用更有效的工具实现； 有些语言的单词识别与前后文相关，不宜将其与语法分析合并； 使编译程序各部分独立出来，有利于设计、调试和维护 3.1.1 Lexical Analysis Versus Parsing The separation of lexical and syntactic analysis often leads to a cleaner overall design. Compiler efficiency is improved. A separate lexical analyzer allows us to apply specialized techniques that serve only the lexical task, not the job of parsing. Compiler portability is enhanced. Input-device-specific peculiarities can be restricted to the lexical analyzer. 3.1.2 单词符号的内部表示 常用的内部表示方法: (class,value) 为便于阅读，常用助记符（或常量标识符、宏定义等）表示class。 单词的分类方法：可一词一类（+、-、begin、end等）或多词一类（如关键字类、操作符类、分隔符类、变量名类、常数类等）。 在识别出变量名、函数（过程）名时，还应进行查填符号表的工作。 3.1.2 Tokens A token is a pair consisting of a token name and an optional attribute value (class,value) The token name is an abstract symbol representing a kind of lexical unit, e.g., a particular keyword, or a sequence of input characters denoting an identifier. The token names are the input symbols that the parser processes. We will often refer to a token by its token name. 3.1.3 识别标识符的若干约定和策略 一般来说，单词的长度是有限制的。 在允许长度下，应按最长匹配原则进行识别 有时需要超前扫描来进行单词识别。 在进行超前扫描时，还应注意“回退”字符，即将多吃掉的字符退还回输入缓冲区。 3.1.3 Token Recognition All tokens have finite length. Tokens are recognized when all possible symbols are scanned. Sometimes we need to look at least one additional character ahead. 3.2 正规文法和状态转换图 3.2 Regular Expressions Transition Diagrams 3.2.1 由正规文法构造状态转换图 程序设计语言的单词都能用正规文法描述 一般说来，凡能用正规文法描述的语言，均可由某种有限状态算法——状态转换图进行分析 状态转换图： 有向图（一个初态