FPGA内存保护策略描述、合成与示例分析
1. 策略描述与合成
1.1 NFA与DFA构建
首先，编译器会使用Thompson算法从正则表达式构建非确定有限自动机（NFA）。之后，通过子集构造法将NFA转换为确定有限自动机（DFA），并应用Hopcroft分区算法对DFA进行最小化。
以下是这一过程的操作步骤：
1.NFA构建：使用Thompson算法，依据正则表达式生成NFA。例如，对于特定策略的正则表达式，生成对应的NFA（如图所示）。
2.DFA转换：采用子集构造法，将NFA转换为DFA。
3.DFA最小化：应用Hopcroft分区算法，对DFA进行最小化处理。
1.2 范围处理
编译器需要对范围进行处理，将其转换为能让电路高效计算包含给定地址范围的格式，可并行搜索整个范围集。具体操作如下：
1.使用无关位：对于大小为2的幂的范围，可使用无关位进行描述。例如，10XX对应于1000、1001、1010和1011，即[8, 11]。通过对输入地址的前两位与10XX进行按位异或操作，可判断地址是否在该范围内。
2.范围转换：对于大小不是2的幂的范围，编译器需将其转换为一组大小为2的幂的范围。例如，范围[7, 12]可转换为{[7, 7], [8, 11], [12, 12]}（或{0111|10XX|1100}）。
