呃,正则的内容就是他为什么这个有这个正则?他是背后的一个原理是啥啊?学术上的一个原理叫做那个自动机。 呃,自动机呢?他听起来很高大上,他实际上就是,呃,我们的一些流转图啊,你可以叫简单理解状态流转图,嗯,比如说这里有一个自动机,我给你放大一点哈, 放大 ctrl 加加来看这个自动机吧。 呃,这里有一个自动机,这啊就是状态流转 图。这个转转头转出是啥含义呢?呃,这个箭头就是入节点,就是你要这个图,你要从哪里开始便利啊?这里每个上面写了一个一二,就是你的一个 步骤吧,也不叫步骤,你不一定是非要只能走一到二。呃,你能走的步骤呢,取决于他后面的这些箭头,你可以跟着这些箭头走,然后假设这里 呃进来的是初始位置,就是在一上哈,然后呢,这里这个每个箭头就是你输入一个 a, 然后他就会导致跳到 二。嗯,再输了一个 a 就会导致跳到一,再输了一个 a, 导致跳到二,再输了一个 a, 导致跳到一。啊,这个就是一个这样这么样的一个状态流转图。好,他的歧视状态就是 是这个箭头,但他也有中指状态,中指状态就是这个圆上有两层的,叫做中指状态,因此呢,这个机器呢?他可以接受的自助串是什么呢?啊?假设你只输了一个 a, 他就跳到了二,对不对?然后他遇到这种双元的,他就,他就,你想停止,你就可以停了他,于是他可以接受 a, 只接受 a。 好,假设你输了一个 aa 会发生啥? a 跑到了二,再输了一个 a, 又跑到了一,你就不输入了, 此时他的结束位置并不是在双元上,他就拒绝接受啊。就是正则上匹配,就是匹配错误,返回 fast 就是这种状态。这个呢,就叫做,呃,那个自动 机,整个这个自动机就是这样玩的,其实就是状态流转。图 d f a 和 n f a 有奖吗?啊,这个就叫做那个确定性自动机吧,这个是 d f a 吧,然后下面就是非确定性自动机了,就是那个 n f a, 我们现在就叫做确定性自动机。 好,这个可能你看着很简单,那感觉没啥。那我们玩点复杂的,他下面有例子哈。 下面有例子,他是看他这个是搞一个啥例子。来看一下这台机器,这台机器哪些 zoo 串能接受,哪些不能接受?嗯 嗯,他这里也举了个例子,我们看一下这个 a b 是否能结束吧。呃,首先你在这个初始状态就是一了吗?此时他有两条路径啊,如果你输入 a 的话呢,他就不能二,如果你输入 b 的话呢,他还是在一上 啊。所以说输入第一个输入 a 拨到了二,然后又输了,又输了 b, 我们我们要测试 a b 哈, 然后此时在二上输入 b, 那就蹦到三,此时不再输入,他就停止,然后正好在双元上,那就是可接受的,也就是 ab 是可接受的。你再看这个 baba, 默认你就在一上,然后输入 b, 那还是在一上,再输入 b 还是在一上啊?当然他说的是 b a 哈。呃, b 在一上,再输入 a, 跑到二上,再输 b, 到三上,再输 a 啊,回来还是跑到三上啊?所以说这个 bab 也是可接受的啊,再看一下这个 a, 好磨轮,在一上,此时输入一个 a, 好停止输入, 然后他中指状态不在双元上,他就不可接受啊。再看这个 bba 啊, baa, 先输了个 b 在一上啊,又输了个 a 啊,在二上右输入 a, 然后呢又回到二上,此时中指输入,然后这个 b a a, 这个他就不可接受啊,当然巴拉巴拉还有一堆哈。呃,这个呢,就是一个自动机的一个玩法,这个是确定性自动机。呃,不知道 这样大家能不能理解这个,你看这个过程。呃,如果你能掌握这个编程思路,或者说你有这个思路呢?呃,你可以用程序来模拟一个这玩意啊,或者说模拟这么一个状态流展图,然后呢 设计一个状态流转图,然后呢你能去匹配上某些特定的一些支付串啊,这个呢,其实不就是跟正德的一个原理是一样的吗? 他这里所说的确定性是什么含义呢?嗯,确定性就是,嗯,你每到一个节点,他都有下一个节点的一个, 无论你输入什么,他都可以走向下下一个节点,这就叫确定性。当然这样解释你可能不太理解,我们看了不确定性 你就知道啥是确定性了,这里他有代码实现,我们就不讲了,我们就我们再去看那个非确定性。 好,他这里提了一个问题,假设我们想要一台有线的自动机,他能接受 a 和 b 组成的 第三个字符是 b 的任意字母串。这啥意思? a 和 b 能组成的第三个字符,也就说你这个字符串只要是和 a 和 b 组成就行,但是你必须是第三个字符串是 b, 比如说,嗯,那个 aab, aabb, bbb, 或者说是 逼逼逼逼逼逼逼啊,只要是第三个字符是逼就行。那你怎么去设计这台机器啊?他这里给设计了一台,呃,我们可以试一下哈,我们就拿这个 a、 b、 b 来试一下,在我们默认在一上,然后我们输入这个 a, 然后蹦到了二上,我们再输入 b, 蹦到了三上,我们再输入 b、 a、 b、 b 嘛, 然后蹦到了这里,蹦到了这个正好这是中指的位置,然后此时当然你可以还继续输入,你只能输入 a 和 b 吗? 你无论输入什么,他都是在这个五上,他就出不去了,这样他就设置了一个呃确定性的自动机,但是呢,他 他他又他又在问,刚才是接受倒数第三个字符哈,那我们倒数第五个字符怎么办?倒数第 n 个字符怎么办?呃,就是你, 呃,就是你无法确定这个,呃,在结束之前他这个支付串到底有多长,此时怎么办?他那个就提出了一些挑战。呃,你当然你可以设计只说,只不过说这个增动机呢。呃, 你不是你不说三吗?那我就反正我就走三步,然后就让他转呗,你输啥我都让他在这转。你不说倒数第五个吗?那我前面我就拼拼五个,那我就拼完以后在这转呗。那其实也可以,赢上也可以,但只是说 说他画的画这种状态图就比较麻烦,因此呢他就呃设计了另外一种这个自动机,只是说他这个这个规则稍微变了一下,然后呢?让他能实现上面的工作,而且画起来简单一点。 我们来看一下这个是,呃,咋实现的?看一下啊? 呃,对对,每一个输入序列不再只有一条执行路径处于状态一,并且读入 b 的时候,他可以按照一条规则仍然保持状态一,也就说,呃, 这个路径上是你处于一的时候呢?以前是,呃左边是 a, 右边是 b, 逼就明确的他就是一分为二啊。现在呢,他是可能应该是,就是你说的有两个逼,就是这个可以在同一条路径上,就是同一个逼可以出现在两条路径上。那因此呢,你可以有选择的走走一,也可以有选择的走二。 我们来看一下这个,嗯, b a a 是否接受?呃,假设呃开始状态就是一嘛。嗯,然后你输入 b, 那你可以是走这个 走一,回来也可以走到二,然后我们我们假设哈,这两种状态我们属于量子状态,我们都走了,然后我们再输入 a, 然后呢,你第一条分叉是我们回到了一,然后你如果是在二上呢?我们是去了三, 好,我我,我们现在是亮的状态哈,同时在一和三上,我们再输入 a, 呃,我们,我们在这个上面,我们也可以在一上呢,我们又回到了一,呃,我们在三上呢,到了四。那此时呢,有一个分支是到达了一个终点,那我们就认为这个是可接受的。 呃,如果是你在这种量子状态上呢,是没有到达一个终点,那我们就认为你是不可接受的 啊,应该是只有这一个区别,应该是只有这一个区别。我理解是我之前,我之前看我也,我忘了,差不多了。嗯? 为什么我,我不太在乎这个哈,因为下面他说了,呃,非确定性的这个有线自动机呢?他是可以转化成确定 性的有线自动机,无论是什么样的自动机,他都可以这么转化。转化的原理是什么呢?原理就是你可以对 这种非确认性的有线自动机呢,这种量子状态呢?我们可以做一个路径便利啊,我们把路径便利完以后呢,他自然他就转化成一个确定性的一个自动机了。 怎么把 af 转成啊?转的方式,刚才我们其实已经模拟了我们去执行它的过程,其实就是把它转成这个 dfa 的过程。 嗯,最简单方式,你就是做一个路径便利。嗯,当你不确定,嗯他是否接受的时候。比如说刚才我们输了这个 a, 我们输了这个 a, 我们不确定。嗯,这个 个下一步啊,我们出 b 的时候,我,我刚才说了 b, 我们不确定下一步是留在 a 上还是走,在走,在这个留在一上还是走。呃,走到二上去。 那我们保持两个节点,我们同时在,就两条分支,我们同时在。然后呢,我们继续去接收下来下面的支付串啊,直到有一个分支触达了这个终止节点, 此时你实际上已经是便利了两条分支,而且两条分支都便利完了。呃,你把刚才便利的路径展开,不就是上面的这个确定性的这个自动机吗? 不是模糊搜索,是精确搜索,你优化以后可以做模糊搜索。 那现在呢?这个确定性和非确定性的这个自动机呢?我们概念其实已经知道了,然后接下来呢,他给了一些代码实现,然后,呃,当然这本书呢,他讲这些东西的目的呢,也并非是 讲这个自动机本身,他这本书呢是讲机器, 他刚才给了两种不同的机器实现,然后呢在这种机器实现呢?呃,他认为基于这种机器呢,我们可以实现正的表达式,当然你不基于这种机器依然可以实现正的表达式。 好,这本书呢,他马上呢就去问了另外一个问题,就是说刚才的这种自动机呢,他能不能处理 这种括号的问题?能不能处理这种括号的问题?呃, 我,我告诉你答案哈。呃,啊,对,这本书就是编程的本质,我,我在那个我推了好几次了,他能不能处理这括号的问题啊?他实际上是不能处理括号的问题。我们在做趴测的问题的时候呢, 他本身就有一个括号的问题。呃,如果他没有欠套,还好我们说过他真的表达是里面的括号是可以欠套的,如果有括号怎么办? 嗯这本书给出来的答案呢当然是我们加一个站就够了,就是我们口号下压一下加个站,这个我们背过算法的应该都知道,所以说你要在实现这个程序的解析器 的这个括号的这个地方呢,你也要记得。呃,如果实在是抓耳挠腮搞不出来,你就想一下啊,是不是可以加一个外置存储器啊?加一,比如说加一个站,甚至你加一个数组也可以实现。好,嗯,我们再回到这本书, 嗯,当然这本书的这个目的呢,他也不也不仅一次,他认为。嗯,这个有没有能比这个 呃下推自动机,下推自动就是带站的那种自动机更加强大的机器呢? 因为刚才上面两种都是机器,然后他就提出了一个叫终极机器。啊,就是,呃,图灵机啊,当然他讲完这个图灵机以后呢,他还讲了另外一 些机器,比如说 number, 演算,然后还讲了不可能的程序。 嗯,那个反正越到后面越好玩。嗯,所以大建议大家来看一下这本书啊,当然这本书的内容已经脱离了我们今天的主题,嗯,我们今天的主题是那个正则表达式的一个实现原理。 好,应该我们这节课就完事了。 好,大家可以简单的问问几个问题,我们就可以睡觉了。 录了没有啊?录了,谢谢谢谢赞。 这个是另外一本书, really 用的这个主播用的这个 o b s。 这个这个 o b s。 一个应该是一个开源软件, 大家有啥问题,然后要没啥问题就就就早点睡觉。 哦,感谢关注感谢关注啊,那个没有关注的,大家可以可以关注一下。桌面。是啊,桌面,你说的桌面,这个很古老了,这个桌面 你看一下。这是能,这是看桌面的地方吗?这也不是这个桌面,是那个吴邦图的那个桌面。吴邦图十六,你听过没有? 那个桌面我也不知道叫啥桌面。嗯,反正是很老了, 但是他这个系统呢是 wobble 二十二十二,只是说现在因为有很多软件 他在这个最新的桌面上,他不支持,然后我就装回了这个桌面,而且他那个你看这是在闪,这是 bug。 嗯,这种 bug 呢,我用了好多年了,我能,我可控,我知道他有哪些 bug, 也知道怎么解决。呃, 但是新的桌面呢?它有很多 bug, 它不可控,我也不知道怎么解决,因此我也不喜欢那个新的桌面。啊。对,这个可能是是这种桌面吧,看这种 bug 一直在闪。这提示你这个保护眼睛。 呃, arch, 我以前是装的 arch, 然后后来滚挂了,然后时间长了就不想再装了。就就是每次你急用的时候就会挂这个不太稳定。 这个吴邦图还是我就不更新,反正就很稳定。呃,有有一有一台机器已经装了,从吴邦头出来到现在有十年了吧。快了快十年了,一直在那个电脑上运行,他都就不升级 cy。 反正到现在一直很稳定,都不出问题。 好,大家。呃,没啥问题啊,无帮图更点,更新必崩溃。那就不更新,少更新,尽量不更新啊。欢迎这个网言沉迷已经已经来晚了,已经讲完了,可以关注我一下,然后我把这个视频 剪出来,剪出来稍微剪一下,然后发到 b 站上。 好,大家没啥问题,我们就就睡觉了,睡觉了。这个正则暂时讲完了, 其实就相当于讲了一个小型的一个边缘里,这个边缘里相对简单一点,如果你 输入法是搜狗输入法啊,如果你是那个那个 啊,如果你自己没有实操过,你建议实操一下,你实操一下呢,基本上相当于会写一个基础的一个 编,编译要绘写一个编基础的编程语言了,只不过这个编程语言呢,很多算字,我们姑写叫他算字。这些小的节点具体怎么实现呢?他是不一样的,比如说你要实现一个函数,实现变量,还实现其他的东西。 请你复用现在的这一套框也不叫框架吧,这种格式结构构造方式,你复用这些东西呢,依然也可以实现一个编程语言。嗯, 也是这一套。然后趴色的话呢,这个就是非常简单的趴色啊,如果是复杂一点的趴色,肯定不是这样,写就要写成留的方式,嗯,就要复,类似于复用他复用这几个接口吧, 那个辣死 nice 的晕染回顾,然后服用这几个接口,在一个流上上下操作,而且是在地规的过程中去操作, 嗯,才能去好的做一个好的一个 pass。 当然这个编程语言写的最麻烦的地方就是 pass 这一部分, 嗯,而一旦 pass 完以后,拿到这个 ait, 在 ait 上实现每每个节点的一个具体的一个内容的时候呢,他反而会变得简单起来。嗯,所以说那个市面上有很多那个书, 就科班学那些书,什么龙书虎书,他们很多都会把这个最难的部分当成最精华的部分,就是 past 的那部分,然后去学。很多人也是这样,上课上过来的, 其实是没有学到精华的。精华在后面,精华在这些每个的具体实线上, 每个功能的具体实现上,比如说函数怎么实现?作用欲怎么实现?嗯,变量怎么实现?放循环怎么实现?地规怎么实现? b a 器后端简单还是前端简单?应该是后端吧,前端。前端你你也得看, 反正 passer 不简单,反正越过了 passer 的,其他的还行。 嗯,边气你。有的时候你,你做的时候,因为你要把你要既要兼容你上面一层,又要兼容你下面一层,上面一层就是一些语法不能变,还你下面一层,就是可能硬件也换了目边边与目边也换了 你,你只只能在中间去做这个优化,然后而且你上上不能变,下不能变,就像那接口似的,你是中间一个调用别人调用你,你再调用别人 都不能变,你只能中间做油画,他像一个魔术,就是比如说这个扎握的这个变音器,扎握变音器最开始的时候 说呢,是非很慢的,嗯,非常慢,现在已经接近于这个 c 和 c 加的一个速度了,运行速度他里面就是有很多魔法,所以说他做成了就是一个魔法,跟魔术一样东西很神奇。嗯,但是呢,他 他这坏处就是你,你就只能在中间,你没,其实只能在中间做,然后有很多发挥空间,你可能就没有办法去像写一个新的东西,放飞自我那种发挥限,而且越到后面限制越多,越到后面限制越多。 好,这个我们这个正则表达式,这这节课就讲完了。呃, l l v m。 不会不会, 我我,我在搞那个 circle 的那个编译,还在自己看一些那个普通的一个编程语言,没有去搞那个 l l v m, 其实 l l v m 它它基本上等价于那个 java 的那个字解码, 只不过还扎过资金码,哎,不,我不知道,我忘记哪个出现更早了。他们的那个思路都是一样的,就是通过一种中间的一种资金码,然后,嗯,我保证这个资金码的 变变化小一点,然后大家都兼容这个中间的这个四减码,然后这样那个上层的语法就可以变一下啊。嗯,然后 就是你可挪腾的空间变大了,语法可变的话呢,你那个编器开发的难度就会 会降低,你像那个 c 加加有很多那个兼容历史,那个后来就变得越来越恶心。而像扎我他一开始就用这个扎包,扎包里面的就是这个四节码,四节码的那格式就是相对就基本不变的。他这些年来, 嗯,那些上古时期的那个代码,他都可以通过扎包的方式保存下来。你像很多 c 啊, c 加加那些代码到现在都可能丢了,只有一些二星制,然后那那那个东西就遗失了。 嗯,即使没有仪式,你拿过来以后,他那些语法也和你现在编辑不兼容,那你也很难去把它跑起来,或者是跑好。所以说这个思想还是挺重要的,就是这个 l l v m 或者是 炸包的这种思想。还有那个,呃,新搞出来的叫什么外保苏木林的那那一套也差不多的,就是就是一个一个思路吧。 好,现在不能再说了,现在得睡觉了。嗯,下下播了,关关关,关灯,关电脑。