【编译原理】第三章：词法分析

语言

正则表达：

正则表正拆唤达式可以由较小的正则表达式递归构建。每个正则表达御蠢式r定一个语言记作L(r)。

正则表达式举凯优先级为：克林闭包>连接>或。

简单来说就是重定义。

例如：

letter ->字母

number ->数

\d ->整数

系统根据 当前状态 与 当前的输入信息 决定 后继行为 。

每当处理完当前输入后，状态也发生改变。

如果给定输入串x，如果存在对于该串 从初始状态到某个终止状态 的转换序列，则该串被该FA 接收 。

例：对于FA

abbaabb 是被接收的，而 abbaaba 则不被接收。

重点： 转换表 ；

一个有穷自动机可以由转换表表示。

例：

以上两种自动机都可以用正则表达式 来表示。

事实上， 正则表达式与有穷自动机是等价的 。

从人的角度看，NFA比DFA更加直观；但对于程序来说，DFA比NFA容易实现。

直接从RE转换到DFA是比较困难的，所以一般通过NFA作为中介。

DFA中的每个状态都是NFA中状态集合的一个子集。

即，先写出NFA的转换表，再通过新的状态构建出DFA。

例：

记数字为 ，字母为 ，那么标识符的正则表达式为：

这个正则表达式转换为NFA，表示如下：

这个NFA同时也是一个DFA，所以不用再进行转换。

记：

数字

数字串

小数部分

指数部分

数

即一个数由一个数字串+可选的小数部分+可选的指数部分构成。

转换为NFA，表示如下：

通过子集构造法，将NFA转换为DFA：

可以表示10进制、8进制、16进制的DFA：

词法分析（英语：lexical analysis）是计算机科学中将字符序列转换贺启渣为单词（Token）序列的过程。

词法分析会记录每一个token的位置（行号，列号），所以可以指出其位置。

词法分析阶段可以产生的错误是“不能被识别的单词”错误。

如，未知的禅悄标识符、 *** 作符、错误格式之类。旁敏

分成词法分析，语法分析（LL算法，递归下降算法，LR算法），语义悉尘分析，运行时环境，中间代码，代码生成，代码优化这些部分。其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的，所以那本龙书的内容格式几乎成了现在编译原理凳孙教材的定式，包括国内的教材也是如此。一般来说，大学里面的本科教学是不可能把上面的所有部分都认真讲完的，而是比较偏重于前面几个部分。像代码优化那部分东西，就像个无底洞一样，如果要认真讲，就是单独开一个学期的课也不可能讲得清楚。所以，一般对于本科生，对词法分析和语法分析掌握要求就相对要高一点了。

词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道枣陆链理很明显，就是要让词法分析从程序上升到理论的地步。

语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法，LL自顶向下算法和LR自底向上算法。LL算法还好说，到了LR算法的时候，困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了，又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器，一般都是用工具Yacc来生成，实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法，因为其实践十分简单，那么就应该要求每个学生都能自己写。当然，现在也有不少好的LL算法的语法分析器，不过要是换在非C平台，比如Java,Delphi,你不能运用YACC工具了，那么你就只有自己来写语法分析器。

---