BUAA-CO-P0-课下

正则表达式匹配

匹配规则：

• […]是指要匹配中括号中的字符(注意是字符不是字符串),比如[xyz]就是要匹配x y z这三个字符中的任意一个。
• {…}是指要求匹配“{”前的那个字符几次，比如a{2}是指要匹配a两次，a{2,4}是指要匹配a 2至4次,a{,4}指要匹配a 0至4次，a{2,}指要匹配a 2至无穷次。所以[cd]{1,2}就是要求匹配(c或d)一次或两次,即cc、dd、cd、dc、c、d都是能匹配的。

本题要求使用Mealy状态机匹配b{1,2}[ac]{2}的子串并输出。为简化电路，我们用00表示a，01表示b，10表示c，11表示其他字符

信号名	方向	描述
In[1:0]	I	串行方式输入字符串。
CLR	I	清除置位信号（同步复位）
Z	O	输出是否检测到了与表达式匹配的子串

首先状态机类型不能搞错了，搞错了是万万不可能过的。本题要求Mealy机，即输入与输出有关。这就确定了转移块有2个输入口一个输出口，输出块也有2个输入口一个输出口

如果是Moore机，那么会有4个状态，其中最后一个状态是用来判断是否输出的，但Mealy机3个状态即可，输出时通过判断“是否处于最后状态”&&“输入是否合理”，决定输出内容。

另外，虽然Mealy机的输出序列与Moore机相同，但Mealy机在输出时间上比Moore机快了一个周期。如果发现评测机返回的结果让你疑惑“这个时候怎么会有输出”，那么可能是状态机类型搞错了导致输出错位了一个周期

到此，思路清晰，只剩打表了

状态转移

导航

向4个方向走一格，若撞墙，则保持原地，且将hit置高一周期，不撞墙则继续走；若到达B点，arrive置高一周期，并在下一周期返回A

信号名	方向	描述
dir[1:0]	I	表示行走的方向：00：向北走 01：向东走 10：向南走 11：向西走
clk	I	时钟信号
reset	I	异步复位信号
arrive	O	是否到达
hit	O	是否撞上墙壁

Moore机，几个格子就几个状态，状态转移也比较简单，仔细看好哪个点往那边走会撞墙就好了；B点需要注意，无论往哪走都要转移到A点。

这个输出就比较tricky了，arrive没什么好说的，次态在B就置1不在就置0，关键在这个hit。我本来直接把hit这个输出口放在转移模块里了，也即hit由初态决定了，但是发现他永远比“当前位置的更新”快一个周期（也很好理解，因为转移模块是组合逻辑，它的更新与输入的更新是同步的，但是“撞墙”这个动作，显然不会是你刚到这个块就撞墙，而是从这个块出发往哪个方向走才会撞墙）所以肯定要由次态决定，且不能通过组合逻辑输出

怎么解决呢？让hit由次态和dir决定，同时设置一个reg存储hit，这样就能保证hit与arrive同步啦…（最简单粗暴的一集）

这两道组合逻辑比较简单，有缘再更吧…