编译原理课件-第3章.ppt

《编译原理》第三章主要探讨的是词法分析这一关键步骤。词法分析是编译器的第一阶段，它从源程序中逐字符扫描，生成一系列的单词符号，为后续的语法分析提供基础。在此过程中，词法分析不仅要识别并过滤掉注释和空白，还要记录行号以便错误定位，并在需要宏处理的环境中执行预处理，如宏展开。 在词法分析中，单词符号是基本单位，通常分为几大类： 1. 关键字：如`if`, `for`, `while`等，它们在编程语言中有特定含义。 2. 标识符：用于表示常量名、变量名和过程名等。 3. 常数：包括整数、浮点数和布尔值。 4. 运算符：如`+`, `*`, `<=`等。 5. 分界符：如`,`、`;`、`(`、`)`等。 词法分析程序的输出通常是一个二元组，包括单词的类别和单词自身的值，这两部分信息分别用于语法分析和其他编译阶段。例如，对于`while(i>=j)i--`这样的语句，`while`、`i`、`>=`、`j`、`--`会被识别为不同的单词符号。 PL/0语言的词法规则可以通过扩展巴科斯范式（EBNF）来形式化表达，每个单词符号可以看作一个独立的类别。在构造词法分析程序时，通常会经历以下步骤： 1. 将词法规则转换为正规式（正规文法）。 2. 正规式转化为非确定有限状态自动机（NFA）。 3. NFA简化为确定有限状态自动机（DFA）。 4. DFA的最小化以提高效率。 5. 根据最小化的DFA构造词法分析程序。 正规文法是描述单词构成规则的工具，属于乔姆斯基文法的第三类，用于描述编程语言的词法规则。比如，标识符可以由一个字母开始，后面跟着零个或多个字母或数字组成。正规式则是一种更为直观的描述方式，通过“|”表示“或”，“*”表示零个或多个，以及“•”表示连接，可以构建出描述单词的表达式。 通过正规式，我们可以简洁地表示各种复杂的词法规则。例如，无符号数可以用一系列规则描述，包括整数、小数和指数部分。正规式则可以直观地表示这些规则，便于构造词法分析程序。 总结来说，词法分析是编译过程的关键环节，涉及到单词符号的识别和分类，而正规文法和正规式则是描述和实现这一过程的重要工具。通过理解这些概念，我们能够更好地理解和构建编译器的词法分析部分。