Chinaunix首页 | 论坛 | 博客
  • 博客访问: 222719
  • 博文数量: 5
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 56
  • 用 户 组: 普通用户
  • 注册时间: 2019-06-26 09:19
文章分类
文章存档

2019年(5)

我的朋友

分类: C/C++

2019-06-27 08:50:18

在词法分析中最重要的运算方式就是并,连接和闭包。

运算 定义
L∪M
串s属于L或者属于M
L·M 串st中s属于L且t属于M
L* L的kleene闭包L*=∪0<=i<=∞Li
L+ L的正闭包L+=∪1<=i<=∞Li

例如:
L∪M中L∈{a-z或A-Z},M∈{0-9}则L包含26*2+10=62个字符的集合。
L·M中则表示26*10+26*10=520个长度为2的字符串的集合。
L*表示所有字母构成的集合包括空串?
L+表示有一个或多个字母构成的串。

下面看一个实例:
C语言中的标识符有以下规则,首字母必须为字母或者下划线,其他字母为字母数字下划线,所以可以构成以下正则表达式: (L|E)·(L|D|E)* {L∈{a-z|A-Z}, E∈{ _ }, D∈{0-9}。
正则表达式在程序中具有缩写的表示形式 [a-zA-Z0-9]表示L|D,则L|E应该写成[a-zA-Z_], L|D|E则写成[a-zA-Z0-9_]所以上述表达式可以写成:
[a-zA-Z_][a-zA-Z0-9_]*
所以在lex程序中就可以用上述扩展的正则表达式来表示。也可以将其封装:
letter     [a-zA-Z_]
digit      [0-9]

{letter}({letter}|{digit})*
在lex中定义了一个符号后,再使用它就需要在符号两边加花括号。   
正则表达式的扩展形式还可以用符号?来表示零个或者1个实例。
digit?表示空集或者一个在≤9的数字。

lex的正则表达式的扩展表示方法:
c             一个字符
\c            字符的转义
"S"          字符串S 
.              除了换行以外的任意字符
^             一行的开始,例如^#代表#符号必须位于本行的开始位置
$             行的结尾,例如abc$,表示c必须位于本行的末尾
[s]           s中的任意字符,例如: [abc]表示a|b|c
[^s]         不在s中的任意字符,例如: [^abc]表示除了abc的任意字符
s*            与串s匹配的0或多个串,例如:a*代表0或n个a
s+            与串s匹配的1或多个串,例如:a+代表1或n个a
s?            与串s匹配的0或1个串,例如: a?代表0或1个a
s{m, n}     最少m个,做多n个s的重复,例如:a{1, 5}代表a或者aaaaa
s1s2         s1后接s2,例如: ab
s1|s2        s1或s2,例如: (a|b)
s1/s2        s1后面必须接有s2,例如: abc/123代表匹配后面接123的abc

编译原理(第二版)            Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffery D.Ullman

阅读(225) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册