Oxida.s Blog

BLOG.OXIDA.CN
热爱与温柔
  1. 首页
  2. 软件设计
  3. 正文

文法中正规式、正规集定义

2022年5月25日 23点热度 0人点赞 0条评论
  • 语言中具有独立含义的最小语法单位是符号(单词),如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。
  • 词法规则可用3型文法(正规文法)或正规表达式描述,她产生的集合是语言规定的基本字符集∑(字母表)上的一个子集,称为正规集。

正规式和正规集:

对于字母表∑,其上的正规式及其表示的正规集可以递归定义如下:
1. ε(epsilon)是一个正规式,它表示集合 L(ε)={ε}。
2. 若a是Σ上的字符,则a是一个正规式。它所表示的正规集为{a}。
3. 若正规式 r 和 s 分别表示正规集L(r)和L(s),则:
a. r|s 是正规式,表示集合 L(r)∪L(s)。
b. r ·s 是正规式,表示集合L(r)L(s)。
c. r* 是正规式,表示集合(L(r))* 。
d. (r) 是正规式,表示集合 L(r)。

  • 仅通过有限次地使用上述3个步骤定义的表达式才是Σ上的正规式,其中运算符“|”、“·”、“ * ”、分别表示为 或、连接、闭包。 在正规式的书写中,连接运算符 "·"可省略,运算的优先级从高到低顺序排序为“ * ”、“·”、“|”。

设∑={a,b},下表列出了∑上的一些正规式和相应的正规集。

正规式 正规集
ab 字符串 ab 构成的集合
a|b 字符串 a、b 构成的集合
a* 由 0 或多个 a 构成的字符串集合
(a|b)* 所有字符 a 和 b 构成的串的集合
a(a|b)* 以 a 为首字符的 a、b 字符串的集合
(a|b)*abb 以 abb 结尾的 a、b 字符串的集合
本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可
标签: 软件设计师
最后更新:2022年5月25日

氧化先生

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >

文章评论

取消回复
分类
  • JAVA 编程
  • 产品经理
  • 奇淫技巧
  • 文档规范
  • 生活妙招
  • 虚拟货币
  • 软件设计
标签聚合
软件设计师 软件设计 freenom 奇淫技巧 Cloudflare Kubernetes 域名 狗狗币
广告

COPYRIGHT © 2022 闪闪的部落格. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

黔ICP备16010320号

粤公网安备 44030602005860号