编译原理2-词法分析 - 方塘的半亩塘

本文最后更新于：2021年4月9日下午

# 编译原理2-词法分析

2.0 状态转换图与正规表达式

状态转换图：有限的有向图。圆圈（结点）表示状态，其间用有向边连接，边上可标记字符，表示某一状态接受有向边上的字符/字符集输入后到达另一状态。必有一初态及若干终态，终态结点用双圈表示。终态上用 “ * ”标识表明识别符号时多读了一个其它字符要予以回退，即去掉到终态的有向边上的字符。

[图以后补]

将状态转换图的概念通过正规式加以形式化。

正规表达式（正规式）：形式化的表示法，可以表示单词符号的结构，从而精确地定义单词符号集。其表示的集合即正规集。

闭包

如果正规集相等则正规式等价。

(α+ β)*= (α* + β*)*= (α* β*)*

给出语言推正规表达式：最小连接递增倍数闭包

2.1 状态转换图的实现（词法分析器示例）

简单的词法分析器示例，书p13图2-5：

重要函数解释：

token：用来存单词符号的字符串。

concatenation()：将token中的字符串与扫描到的字符连接得到新的token。

getbe()：过滤空格读字符。

letter() 和 digit()：分别用于判断字符类型是否为字母和是否为数字。

retract()：扫描指针回退一个字符，并把字符变量置空。

reserve()：查是否为保留字，不是则为标识符，返回0。

buildlist()：将标识符登记到符号表中或将常数登记到常数表中。

error()：出现非法字符报错。

关键部分代码：

token=''; //初始化token数组
s=getchar(); //读字符
getbe(); //过滤空格
switch(s)
{
    //遇到字母时
	case'a':
    ...
    case'z':
        while(letter()||digit()) //当读到字母或数字时
        {
            concatenation(); //连接组成新token
            getchar(); //继续读下一个字符
        }
        //读到非字母或数字之后跳出循环
        retract(); //扫描指针回退一个字符。由于while时多读了一个字符，要退回去再判断
        c=reserve(); //读一个字符c，判断c是不是保留字
        if(c==0) //如果是标识符（不是保留字）
        {
            buildlist(); //将标识符登记到符号表里
            return(id,指向id的符号表入口指针);
        }
        else
        {
            retrn(保留字码,null);
        }
        break; //到达终态

    //遇到数字时
    case'0':
    ...
    case'9':
        while(digit())
        {
            concatenation();
            getchar();
        }
        retract();
        buildlist();
        return(num,num的常数表入口指针);
       break;
    case'...':
        return(...,...);
        break;
        
    default:
        error(); //剩下的都是非法字符，读到就报错
}