首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

编译原理:2. 词法分析

---- 2.4.1 将正则表达式转换为 NFA ---- 非确定的自动机是一个很有用的概念,因为它很容易将一个(静态的、说明性的)正则表达式转换成一个(可模拟的、准可执行的)NFA。...转换算法可以将任何一个正则表达式转换为有一个尾巴和一个脑袋的 NFA,它的尾巴即开始边,简称为尾;脑袋即末端状态,简称为头。...由此得到的结果(在合并了某些等价的 NFA 状态之后)如下图所示: ---- 2.4.2 将 NFA 转换为 DFA ---- 用计算机程序实现确定的有限自动机(DFA)较容易。...下面给出一个由四个正则表达式转换成的 NFA: 我们用一个字符串 "in" 来模拟,计算所有的 状态 1 开始,替代猜测应采用哪个 \epsilon 转换,此时 NFA 可能选择 {1, 4, 9,...继续计算,从状态 5 有一个 \epsilon 转换至状态 8,从状态 8 有一个 \epsilon 转换至状态 6。因此这个 NFA 一定属于状态集合 {2, 5, 6, 8, 15}。

65921
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    自己动手写编译器:从NFA到DFA

    在上一节我们描述的epsilon闭包操作可以看到,实际上所有由epsilon边连接在一起的节点其实都能看作是一个状态节点,由此我们就能通过epsilon操作将多个节点转化为一个DFA节点,同时epsilon...//dfa节点对应的nfa节点集合 state int //dfa 节点号码 acceptString string } 这里我们先定义基本的数据结构,在转换的DFA...在上面代码中我们定义了DFA节点,由于一个DFA节点由一组NFA节点转换而来,因此在它的定义中有一个NFA节点的指针数组。...接下来我们设计用于将NFA转换成DFA的类,其代码为: go type NfaDfaConverter struct { nstates int //当前dfa 节点计数...节点本质上对应一组NFA节点,因此当我们使用move 和epsilon闭包操作得到一组NFA节点后,我们需要看看是不是已经有DFA节点对应到了生成的NFA节点集合,如果有了,说明对应的DFA节点已经生成

    66020

    如何将Array转换为List?

    本教程展示了在Java中将数组转换为列表的几种方法。让我们开始吧! Arrays.asList 可以使用 Arrays.asList() 方法, 该方法接受一个数组作为输入,并返回一个列表作为输出。...(Arrays.asList(names)); Java 8 使用Java 8,您可以使用arres .stream()和collections . tolist()实用工具方法将数组转换为列表...namesLst = Arrays.stream(names).collect(Collectors.toList()); return namesLst; } Arrays.stream() 将数组转换为流...然后将该流转换为列表 Collectors.toList(). 返回列表的默认类型是 ArrayList....要确定需要生成的列表类型,可以使用以下内容: Collectors.toCollection(LinkedList::new) 传统的方法 您还可以通过遍历数组元素并填充一个元素来手动执行转换 ArrayList

    1.4K20

    如何将pdf转换为word 2.0

    之前我们发布了如何将pdf转为word,期间陆续收到了小伙伴的推荐。 如何将pdf转化为word 今天我们整理一下,是为2.0版本。...该网站是收费的,每月5欧 优点有: 没有限制 桌面版应用 移除广告 让PDF文件协助您更高效地工作 PDF转Word + 20种工具 批量处理 ? 由于收费,我没有体验......我们发现转换效果也很棒 ? 3.pdf编辑器 Adobe Acrobat Pro 像所有的Adobe软件一样,强大的它拥有短暂免费试用时间。...打开文件后,依次选择“另存为其他—Word—Word文档”,等待转换。 ? 效果还可以,就是中间空格比较多。 ?...该试用版有30天是试用期,100页的试用页数 直接点击转换为word,并选择文件 ? 保留了大部分原始格式 默认识别中文和英语 保留图片 保留页眉、页脚和页码 ? ?

    2.6K40

    形式语言笔记 - wuuconixs blog

    这也非常好理解,因为NFA和DFA一样,都是FA。 只不过它的状态转移函数和DFA不同。...NFA和DFA等价 对于一个输入字符,NFA可以进入若干个状态,而DFA智能进入一个唯一的状态 虽然从DFA看待的角度来说,NFA在某个时刻同时进入了若干个状态,但是,这若干个状态合起来的总效果相当于它处于这些状态对应的一个综合状态...因此我们考虑让DFA用一个状态来对应NFA的一组状态。 NFA转化为DFA的例子 上面讲了NFA与DFA的对应关系。这里给出一个实际转化的实例。...以下为最终DFA状态转换图。...ϵ−NFA\epsilon-NFAϵ−NFA 和 NFA转化的例子 小总结 在实现一个具体FA的时候,我们可以先写出最简单,最智能,最容易写的ϵ−NFA\epsilon-NFAϵ−NFA,然后通过等价转化

    65420

    自己动手写编译器:汤普森构造法

    我们再看看识别数字的转换图: 我们继续看识别空格,换行,制表等这些不被认为有效字符的识别: 这里我们看到的转换图有学名叫确定下状态机(DFA deterministic finite automa...),在每个状态,它都能根据当前输入确定下一个状态,但很多情况下,我们很难直接从正则表达式去构造DFA,因此我们需要将其扩展一下变成NFA(no-deterministic finite automa)。...相比于前者,NFA多了一种边叫ε,从一个状态节点可以发出多条这样的边,这种边表示不用输入任何字符就可以抵达给定状态,例如正则表达式any|d NFA比DFA更加灵活,但是也正是因为如此,它比较难以在计算机中进行应用...,在后面内容中,我们将看到如何将正则表达式先用NFA表达,然后再将其转换为DFA。...下面我们看看如何将正则表达式转换为NFA,这种算法也叫汤普森构造法。

    85920
    领券