西安交大：词法分析教程——基于有限自动机与正规表达式

在西安交通大学Yinliang Zhao教授的指导下，该PPT聚焦于程序设计中的关键概念——词法分析。词法分析是编程语言处理的第一步，它将源代码分解为更小、有意义的单元，即词汇单元或词法元素。课程内容主要包括以下几个部分： 1. 程序结构：程序由程序首部和分程序组成。程序首部包含`program`标识符，而分程序由复合语句构成，复合语句以`begin`开始，以`end`结束。 2. 语句结构：语句包括赋值语句、复合语句和条件语句。赋值语句用`:=`表示对标识符进行赋值，条件语句则通过`if-then-else`结构根据布尔表达式的值来执行不同的代码块。 3. 表达式和项：表达式由项组成，项又可以是因式。因式包括标识符、无正负号常量（数字）以及操作符应用于表达式的结果。例如，`<项>{(+|-)<项>}`定义了加减运算，`<因式>{(*|/)<因式>}`涵盖了乘除运算。 4. 布尔表达式和关系运算符：布尔表达式是基于两个表达式的关系运算，如等于（=）、小于（<）、大于（>）、大于等于（>=）、小于等于（<=）和不等于（<>）。 5. 词法分析器设计：课程介绍了如何设计和实现词法分析器，包括确定有限自动机和非确定有限自动机的概念，以及它们与正规文法和正规式之间的关系。正规文法用于描述语言的结构，而确定有限自动机则是其机械化的形式，它们之间存在等价性。 6. 正规式与正规集：正规式是字符串模式的描述工具，表示满足特定规则的字符串集合。例如，`ba*`是一个正规式，表示所有以`b`开头，后面跟零个或多个`a`的字符串集合。 7. 正规式的基本操作：包括选择运算（|）、连接运算（）、和重复运算（*）。这些运算组合成更为复杂的正规式，并规定了运算的优先级和括号使用规则。 8. 举例与正规集：通过实例展示了如何构造正规式以及它们对应的正规集。比如，`ba*`表示所有以`b`开头，后面跟任意数量`a`的字符串集合。 这个PPT深入浅出地讲解了词法分析的基础理论和应用，对于理解和编写编程语言的解析器或理解计算机科学中的语言学原理具有重要意义。