文档介绍：词法分析——正则表达式
授课:胡静
8/25/20182004年12月28日
1
编译原理
状态转换图实例
其中的假设条件是:
,不允许使用他们作为自己定义的标识符
。把它们预先安排在一张表格中。
,如果关键字、标识符和常数之间没有确定的运算符或界符做间隔,则必须至少用一个空白符做间隔。
8/25/2018
2
编译原理
状态转换图的实现
ch:字符变量,存放最新读进的源程序字符
strToken:字符数组,存放构成单词符号的字符串
GetChar:子程序过程,将下一个输入字符读到ch中,搜索指示器前移一个字符位置。
GetBC:子程序过程,检查ch中的字符是否为空白。如果是,则调用GetChar,直至ch中进入一个非空白字符。
Concat:子程序过程,将ch中的字符连接到strToken之后。
IsLetter和IsDigit: 布尔函数过程,它们分别判断ch中的字符是否为字母和数字。
Reserve:整型函数过程,对strToken中的字符串查找保留字表,若它是一个保留字则返回它的编码,否则返回0值。
Retract:子程序过程,将搜索指示器回调一个字符位置,将ch置为空白字符
8/25/2018
3
编译原理
状态转换图的实现(续1)
InsertId:整型函数过程,将strToken中的标识符插入符号表,返回符号表指针
InsertConst:整型函数过程,将strToken中的常数插入常数表,返回常数表指针。
关于出错处理的一些说明:
如果后面还有状态图,出现在这个地方的代码应为:将搜索指示器回退一个位置,并令下一个状态图开始工作。
如果后面没有其他的状态图,则出现在上述位置的代码应该进行真正的出错处理,报告源程序含有非法符号,并进行善后处理。
8/25/2018
4
编译原理
状态转换图的实现(续2)
对于不含回路的分叉结点来说,可让它对应一个switch语句,或一组if…then…else语句
GetChar()
if(IsLetter()){…状态j的对应程序段…}
else if (IsDigit()) {…状态k的对应程序段…}
else if (ch == ‘/’) {…状态l的对应程序段…}
else {…错误处理…}
8/25/2018
5
编译原理
状态转换图的实现(续3)
对于含回路的状态结点来说,可让它对应一个由While语句和if语句构成的程序段
GetChar();
while(IsLetter() or IsDigit())
GetChar();
…状态j的对应程序段…
8/25/2018
6
编译原理
tokens
Identifiers: x y11 elsen _i00
Integers: 2 1000 -500 5L
Floating point: .02 -10
Strings: “x”“He said, \“Are you?\””
Comments: /** don’t change this **/
Keywords: if else while break
Symbols: + * { } ++ < << [ ] >=
8/25/2018
7
编译原理
如何描述tokens
我们可以使用正则表达式来描述程序设计语言中的tokens
正则表达式(RE, Regular Expression)的定义如下:
a ordinary character stands for itself
ε the empty string
R|S either R or S (alternation), where R, S = RE
RS R followed by S (concatenation), where R, S = RE
R* concatenation of a RE R zero or more times
(R* = ε|R|RR|RRR|RRRR…)
在实际形式中,会有优先级的限制,因此可以加入一些括号。
8/25/2018
8
编译原理
正规式的例子
令={a,b},
正规式正规集
a {a}
ab {a,b}
ab {ab}
(ab)(ab) {aa,ab,ba,bb}
a {,a,a, ……任意个a的串}
(ab){,a,b,aa,ab ……所有由a 和b组成的串}
(ab)(aabb)(ab){上所有含有两个相继的a或两个相继的b组成的串}
8/25/2018
9
编译原理
简单的例子
正则表达式R描述的字符串的集合