当前位置: 首页 > news >正文

编译原理1

 NFA&DFA

在正规式的等价证明可以借助正规集,也可以通过有限自动机DFA来证明等价,以下例题是针对DFA证明正规式的等价,主要步骤是①NFA;②状态转换表; ③状态转换矩阵; ④化简DFA;

文法和语言

文法通常表示成 四元组 G[S] = ( V T V N S ξ):
(1)   V T 为终结符号集 ,这是一个非空有限集,它的每个元素 称为 终结符号
(2)   V N 为非终结符号集 ,它也是一个非空有限集,每个元 素称为 非终结符号 且有 V T ∩V N  = Φ
(3)  S 为文法开始符 ,是一个特殊的非终结符号,即 S V N
(4)   ξ /ksi/ 是产生式的非空有限集 ,其中每个产生式 ( 或称规 ) 是一序偶 β) ,通常写作
α → β α ::= β
α β 是由终结符和非终结 符组成的符号串, α (V T V N ) + 且至少有一个非终结符, β (V T V N ) *

例:产生标识符的文法

例:奇数集合,不允许出现以0开头的奇数文法 

例:上下文无关文法描述正规表达式 

基本概念: 

① 句子仅含有终结符,是特殊的句型;

②文法开始符号一定是句型

③文法产生的句子的全体为文法产生的语言;(标识符、表达式i+i*i都是语言,都由非终结符组成) 

④文法确定,则语言一定确定;反之,不一定可以由语言唯一确定文法;

⑤文法产生语言的过程中必须经过‘+’次推导(至少进行一次推导);

形式语言分类:

(1) 0型文法与语言

对应图灵机; 

文法G[S]的每一个产生式 都有   α->β  

α 作为产生式左端,至少有一个非终结符

β 作为产生式右端,不做要求(甚至可以为空); 

(2) 1型文法与语言

线性界限自动机,自然语言;

在0型文法的基础上要求文法产生式左端的长度要 小于等于 右端的长度;

 (3) 2型文法与语言

对应下推自动机,程序设计语言;

文法G[S]的每一个产生式 都有   A->α  

A∈非终结符

α∈(终结符和非终结符的闭包) 

(4) 3型文法与语言

对应有限自动机;

文法G[S]的每一个产生式 都有   A->α  或者  A->αB[右线性]  或者  A->Bα[左线性] 

A∈非终结符

α∈(终结符的闭包) 

关系和区别

① 1-3型文法属于 0 型文法;

② 2型 和 3型 文法不一定属于 1型 文法;

③ 1型文法 不允许有形如“”A->ε”, 2、3型文法允许;

④ 0、1型文法左边产生式 可以含有终结符或者两个以上终结符; 2、3型文法左端产生式要求单个非终结符(单非);

http://www.lryc.cn/news/389704.html

相关文章:

  • 【信息系统项目管理师知识点速记】组织通用管理:流程管理
  • 前端 JS 经典:箭头函数的意义
  • Java List操作详解及常用方法
  • 《mysql篇》--查询(进阶)
  • 数据库-MySQL 实战项目——书店图书进销存管理系统数据库设计与实现(附源码)
  • eNSP中WLAN的配置和使用
  • <sa8650>QCX ID16_UsecaseRawLiteAuto 使用详解
  • 为什么3d重制变换模型会变形?---模大狮模型网
  • ElasticSearch中的BM25算法实现原理及应用分析
  • web权限到系统权限 内网学习第一天 权限提升 使用手工还是cs???msf可以不??
  • ros1仿真导航机器人 hector_mapping gmapping
  • 嵌入式实验---实验五 串口数据接收实验
  • ubuntu 22.04下编译安装glog共享库
  • Linux环境安装配置nginx服务流程
  • 设计模式-模板模式
  • 物理删除和逻辑删除区别
  • C# 警告 warning MSB3884: 无法找到规则集文件“MinimumRecommendedRules.ruleset”
  • Lua网站开发之文件表单上传
  • 千益畅行,旅游卡,如何赚钱?
  • Element-plus点击当前行之后获取数据显示跟随行数据
  • Docker与微服务实战2022 尚
  • Spring @Cacheable缓存注解用法说明
  • Redis如何实现主从复制
  • 正则表达式以及文本三剑客grep、sed、awk
  • HSRP热备份路由协议(VRRP虚拟路由冗余协议)配置以及实现负载均衡
  • 不同集成学习算法的比较:随机森林、AdaBoost、XGBoost、LightGBM
  • 【聊聊原子性,中断,以及nodejs中的具体示例】
  • 常见网络端口号
  • 【数值计算库-超长笔记】Python-Mpmath库:高精度数值计算
  • 昇思25天学习打卡营第6天|函数式自动微分