??xml version="1.0" encoding="utf-8" standalone="yes"?>国产精品久久久久久久午夜片 ,久久久久久久波多野结衣高潮 ,欧美牲交A欧牲交aⅴ久久http://www.shnenglu.com/airtrack/<a ><font color="White">个h独立博客</font></a> <a ><font color="White">微博@airtrack</font></a>zh-cnTue, 06 May 2025 22:18:47 GMTTue, 06 May 2025 22:18:47 GMT60操作pȝ实现Q三Q:(x)中断http://www.shnenglu.com/airtrack/archive/2015/05/05/210543.htmlairtrackairtrackTue, 05 May 2015 02:03:00 GMThttp://www.shnenglu.com/airtrack/archive/2015/05/05/210543.htmlhttp://www.shnenglu.com/airtrack/comments/210543.htmlhttp://www.shnenglu.com/airtrack/archive/2015/05/05/210543.html#Feedback0http://www.shnenglu.com/airtrack/comments/commentRss/210543.htmlhttp://www.shnenglu.com/airtrack/services/trackbacks/210543.html上一?/a>提到当访问的表和页不在内存中时?x)触?Page Fault 异常Q操作系l需要在异常处理函数中分配内存页q设|好相应的分表V异常是一U中断类型,注册异常处理函数是注册中断处理函数Q中断处理函数注册在一个叫 IDT(Interrupt Descriptor Table) 的地斏V?/div>

IDT

中断处理函数在实模式下注册在 IVT(Interrput Vector Table) 中,在保护模式下注册?IDT(Interrupt Descriptor Table) 。IDT是包?256 的表,表项的结构如下:(x)
    struct idt_entry
    {
        uint16_t offset_0;
        uint16_t selector;
        uint8_t zero;
        uint8_t type_attr;
        uint16_t offset_1;
    };
其中 selector ?GDT 的代码段选择器,offerset_0 ?offset_1 分别表示中断处理函数 offset 地址?0~15bits ?16~31bits Qtype_attr 的结构如下:(x)
      7                           0
    +---+---+---+---+---+---+---+---+
    | P |  DPL  | S |    GateType   |
    +---+---+---+---+---+---+---+---+
P表示是否存在QDPL 表示描述W的最低调用权限,GateType 定义了中断类型,32 位的中断cd分别是:(x)
Interrupt Gate ?Trap Gate 怼Q区别在前者执行中断处理函数前后会(x)自动关闭和开启中断?/div>
准备?IDT Q设|好 IDTR 寄存器就?IDT 都设|好了。IDTR 寄存器结构如下:(x)
    struct idtr
    {
        uint16_t limit;
        struct idt_entry *base;
    };
limit 是整个表的大?-1 字节Qbase 指向 IDT 表,讄 IDTR 寄存器的指o(h)?lidt?/div>

异常和硬件中?/h2>
了解 IDT 的结构了之后Q我们可以设|异常和g中断?ISR(Interrupt Service Routine)。对于异常,我们只要知道有哪些异怼(x)触发Q触发的逻辑是什么样Q实现合适的异常处理函数卛_Q这里是异常列表Q。对于硬件中断,需要通过一个硬件完?#8212;— PIC(Programmable Interrupt Controller)?/div>
PIC 分ؓ(f) Master ?Slave Q每?PIC 都有一个命令端口和一个数据端口,通过q两个端口可以读?PIC 的寄存器。每?PIC 都可q?8 个输入设备,x86?Slave 需要通过 line 2 q接?Master 上才能响应输入设备,q接的输入设备有中断h的时候会(x)产生 IRQ(Interrupt Request)QMaster 产生 IRQ 0 ~ IRQ 7QSlave 产生 IRQ 8 ~ IRQ 15。保护模式下可以讑֮ PIC 产生的中断对应的 ISR 所?IDT 中的 offsetQ通常讄Z 0x20 开始,?0x2F l束Q?x0 ?0x1F 被异常占用)(j)?/div>
PIC 的端口号如下表:(x)

PIC 产生的标?IRQ 如下表:(x)

PIC 初始化的时候,要设|?Master ?Slave 通过 line 2 相连Q同时设|好 IRQ 对应?ISR ?IDT 中的起始中断受PIC 提供一?IMR(Interrupt Mask Register) 寄存器来标识中断是否屏蔽Q设|?bit 位会(x)屏蔽对应?IRQ。当 IMR 未设|,q且 CPU 的中断打开Q如果有讑֤中断h发生Q那?ISR 会(x)执行。ISR 执行完毕之后要通知 PIC 中断处理完成Q需要向 PIC 的命令端口写入一?EOI(End Of Interrupt) 命o(h)(0x20)Q中断请求如果来?SlaveQ那么需要先往 Slave 命o(h)端口写入 EOIQ再?Master 命o(h)端口写入 EOI?/div>

Spurious IRQs

׃ CPU ?PIC 之间?a >竞争条g可能?x)?IRQ 7QMaster 产生Q??IRQ 15QSlave 产生Q??Spurious IRQs。ؓ(f)了处理这U情况,我们要知道什么时候是无效?IRQQ通过判断 IRR(Interrupt Request Register) 寄存器的值可以获知哪?IRQ 发生了,q个寄存器的每个 bit 表示相应?IRQ 是否发生。在 IRQ 7 ?IRQ 15 ?ISR 中先d IRRQ然后判断对应的 bit 位是否被讄Q如果没有设|,那么表示当前是一?Spurious IRQQ不需要处理,也不需要写?EOIQ直接返回即可(如果?Slave PIC 产生的,需要往 Master PIC 写入 EOIQ由?Master 不知?Slave 产生?IRQ 是不?Spurious 的)(j)?/div>

PIT

C操作pȝ都有抢占式多d能力Q通常是通过讄一个硬?TimerQ一个进E的执行旉C之后切换成另一个进E执行,q个g Timer ?PIT(Programmable Interval Timer)。PIT 有多?channel 和多U工?modeQ其?channel 0 q接?PIC ?x)?IRQ 0Qmode 2 ?mode 3 是常用的工作模式。操作系l初始化的时候设|好 PITQ同时设|好 PIT 产生?IRQ 0 ?ISRQ在q个 ISR 中操作系l就可以执行多Q务的调度?/div>

中断处理l束

IDT 中设|的 ISR q回时不能用普通的函数q回指o(h) retQ需要用一条特D的q回指o(h) iret。在了解了这些之后,我们有了响应外部讑֤的能力,可以接入外部输入讑֤了,下一步接入键盘?/div>

airtrack 2015-05-05 10:03 发表评论
]]>操作pȝ实现Q二Q:(x)分页和物理内存管?/title><link>http://www.shnenglu.com/airtrack/archive/2015/04/27/210451.html</link><dc:creator>airtrack</dc:creator><author>airtrack</author><pubDate>Mon, 27 Apr 2015 04:53:00 GMT</pubDate><guid>http://www.shnenglu.com/airtrack/archive/2015/04/27/210451.html</guid><wfw:comment>http://www.shnenglu.com/airtrack/comments/210451.html</wfw:comment><comments>http://www.shnenglu.com/airtrack/archive/2015/04/27/210451.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/airtrack/comments/commentRss/210451.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/airtrack/services/trackbacks/210451.html</trackback:ping><description><![CDATA[<div><a >上一?/a>?Bootloader 开始到内核载入使用的都是^坦内存,x有地址对应实际的物理地址。现代操作系l都使用分页来管理内存,分页可以让每个进E都有完整的虚拟地址I间Q进E间的虚拟地址I间怺隔离以提供页层的保护。另外分可以让物理内存于虚拟地址I间Q同时可以用磁盘存储暂时未使用的内存页Q提供更多的「内存」?/div><div></div><h2>分页</h2><div></div><div>分页通过 CPU ?MMU(Memory Management Unit) 完成QMMU 通过当前的分表完成虚拟地址到物理地址的{换。在 x86 ?MMU 通过两分页表(也可以开启三U)(j)完成地址转换Q这两分别是页目录(Page Directory)和页?Page Table)。在 x86 下,?cr3 寄存器存储页目录的地址Q物理地址Q,늛录和表都包?1024 ,每项 4 字节Q因此页目录和页表大ؓ(f) 4KB Q按?4KB 一늚话,刚好占用一c(din)?/div><div></div><div>MMU 虚拟地址转换成物理地址的方式是Q取虚拟地址?22~31bits 表示늛录的下标Q获得页目录定位到表Q再?12~21bits 表示表的下标,获得表定位到,最后取 0~11bits 表示偏UR页目录和表的下标分别?10bits 表示Q刚好最?1024 ,内偏移?12bits 表示Q刚?4KB?/div><div></div><div>늛录项l构如下Q?/div><div></div><div><img src="http://wiki.osdev.org/images/9/94/Page_dir.png" width="432" height="255" alt="" /></div><div></div><div>其中 S 表示大是 4KB q是 4MBQP 表示表是否在内存中Q如果在内存中,那么 12?1 bits 存储?4KB 寚w的页表地址Q同h物理地址Q,其它 bit 的含义请参?a >q里</a>?/div><div></div><div>表结构如下:(x)</div><div></div><div><img src="http://wiki.osdev.org/images/9/9b/Page_table.png" alt="" /></div><div></div><div>同样的,P 表示此页是否在内存中Q如果在内存中,12~31 bits 存储了页的地址?/div><div></div><div>我们知道了页目录和页表的l构Q准备好늛录和表Q就可以开启分了Q开启分只需把页目录地址攑ֈ cr3 寄存器中Qƈ?cr0 的最?bit |?1。通过늛录项Q我们可以发现页表不需要都存在内存当中Q当讉K一个虚拟地址Q它对应的页表或者页不存在内存中时会(x)触发 <a >Page Fault</a> 异常Q我们可以在异常处理函数中完成页表或者页的分配,理论上开启分只需要准备好늛录?/div><div></div><h2>分页前后</h2><div></div><div>准备好页目录表Q设|?cr3 ?cr0Q开启了分页之后Q内核的所有地址都变成了虚拟地址Q所有的地址都要通过 MMU 映射到物理地址再访问内存。这一变化是需要小心注意的Q开启分前Q访问的所有地址是物理地址Q开启分之后,所有的地址都变成了虚拟地址Q因此,如果分页由内核来完成Q那么内核就需要考虑到前后的变化Q即有一部分代码q行在物理地址下,其它代码都运行在虚拟地址下;如果分页?Bootloader 完成Q那?Bootloader 需要注意这个变化,q正蟩转到内核Q让内核完整q行在虚拟地址下?/div><div></div><div><a >上一?/a>我把内核展开C 0x100000 开始的物理内存中,~译链接内核的时候也把代码段的地址指定?0x100000 的地址。开启分之后,内核一般运行在高地址Q比?Linux 内核地址?0x80000000 开始,W(xu)indows ?0xC0000000 开始)(j)Q而内核同h展开C 0x100000 开始的物理内存中。我选择把内核的虚拟地址链接C 0xC0100000 开始,q把q个虚拟地址映射?0x100000 的物理地址Q开启分之前运行的代码Q凡是涉?qing)到地址的操作,我都?x)把虚拟地址调整为物理地址再操作,开启分之后,所有虚拟地址可以正常运行了?/div><div></div><h2>物理内存理</h2><div></div><div>操作pȝ采用分页方式理内存Q因此物理内存的理也需按照늚方式理Q在 Page Fault 异常触发Ӟ在异常处理函C分配新的物理ƈ把它映射到分表中。这里牵涉到I闲物理内存늚分配和释放,我们很容易想CU直观的Ҏ(gu)Q把所有空闲内存页用链表串联v来,分配释放一只需寚w表进行操作。这U方式管理对q程的物理页分配单有效,但是对内核本w用的内存分配释放?x)导致内存利用率不高Q因U方式管理的最大连l内存是一,而内怸l常?x)分配大对象Q连l多늚物理内存有更好的利用率。Linux 采用 <a >Buddy memory allocation</a> 方式理物理内存Q?Slab/Slub 理内核对象的分配释放?/div><div></div><div>我的实现也采?Buddy 方式理物理内存Q把I闲内存는多层U的 Buddy 方式理Q分别是 order 0 ~ order 10Q表C?2^order 连l内存页块,?order 0 理单页的空闲内存块Qorder 10 理q箋 1024 늚I闲内存块。分配内存时Q算出最佳的 orderQ在相应?order 层里分配一块内存块Q如果当?order 中没有可用的I闲内存块,向 order + 1 层中借一块,q把借来的空闲内存块q_?2 ?order 层的空闲内存块Q其中一块当作分配结果返回,另一块放入到 order 层中待以后分配使用。当W?order 块的内存使用完释放时Q把q块释放的内存块攑օ order 层Ӟ判断与它相连的同样大的内存块是否在 order 层中,如果存在Q把它和它的 Buddy 合ƈ成一?order + 1 的内存块攑օ?order + 1的层U中?/div><div></div><h2>内存理器初始化之前</h2><div></div><div>在内存管理初始化之前Q内核没有动态内存分配能力,因此很多时候我们需要用静态全局变量。内存管理器初始化时Q可能会(x)使用到动态内存分配,q就出现鸡与蛋的问题Qؓ(f)了解册个问题,通常?x)实C个简单的 Boot Allocator 用在内存理器初始化之前分配动态内存。我的实现是从内核展开的末位|开始徏立一个只分配不释攄 Boot AllocatorQ等到内存管理器初始化完成之后,Boot Allocator 的命便完成了?/div><div></div><div>另外q有一个问题,我们理物理内存Q需要知道安装了多少物理内存Q因此我们要探测安装了多物理内存,<a >q里</a>介绍了几U探方法,我用的?BIOS ?INT 0x15, EAX = 0xE820 函数Q它?Bootloader 调用完成Q最后通过参数把它传递给操作pȝ内核?/div><div></div><img src ="http://www.shnenglu.com/airtrack/aggbug/210451.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/airtrack/" target="_blank">airtrack</a> 2015-04-27 12:53 <a href="http://www.shnenglu.com/airtrack/archive/2015/04/27/210451.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>用Rust写了一个Tunnelhttp://www.shnenglu.com/airtrack/archive/2015/02/03/209720.htmlairtrackairtrackTue, 03 Feb 2015 13:03:00 GMThttp://www.shnenglu.com/airtrack/archive/2015/02/03/209720.htmlhttp://www.shnenglu.com/airtrack/comments/209720.htmlhttp://www.shnenglu.com/airtrack/archive/2015/02/03/209720.html#Feedback0http://www.shnenglu.com/airtrack/comments/commentRss/209720.htmlhttp://www.shnenglu.com/airtrack/services/trackbacks/209720.html2014q的最后一个星期用Rust写了一个TunnelQ代码放?a >GitHub上。主要原因是VPN?2月开始极不稳定,其次是VPN用v来不爽,每次下东襉K要关VPNQ而用ssh -D时偶?dng)又会(x)断开Q最后干脆自己写一个(其实q初想写,因ؓ(f)CVPN׃x腾了Q?/div>

~译和?/h3>
C语言一般都自带~译工具Q不用折腾make cmake{东西,Rust官方提供?a >CargoQ所以编译很单,安装好CargoQ然后到源码目录下Cargo build完成了?br />
~译完成得到两个可执行文Ӟ分别是:(x)client, serverQserver启动在服务器上,client启动在本机ƈl定到地址127.0.0.1:1080Q浏览器׃理插仉过SOCKS v5协议q接q个地址卛_?

Tunnel逻辑l构

下面是逻辑图:(x)
Client和Server之间通过一条TCP链接相连Q客L(fng)每收C个TCPh开一个port处理Q同时在Server上有一个port与之对应Q这样就在Client和Server之间建立了一个会(x)话层Q这个TCP链接的数据全部都在对应的port里传输?br />
Tunnel本n跟SOCKS v5不相养IZ让浏览器代理能连上,Client提供了SOCKS v5中最单的NO AUTHENTICATION TCPҎ(gu)Q即无用户名和密码的TCP代理?br />
Client和Server之间传输的数据都加了密,加密法是BlowfishQ工作模式是Counter ModeQclient和server启动时的参数Key卛_密算法的Key?/div>

Rust的用感?/h3>
以前虽有xRustQ却从没用Rust写过代码Q主要是q未发布1.0Q语法不E_Q最q?.0快有眉目了,可以用来写写东西了。因为有Haskell的基Q所以上手RustҎ(gu)来说没什么难度?br />
Rust提供了ADT(Algebraic Data Type), Pattern Matching, TraitsQ语法表达能力很强,同时也提供了macroQ可自定扩展语法Q进一步加Z语法表达能力。自动内存管理也让程序更安全Q不q由此也带来一些语法表达能力的削弱Q比如需要在函数q回的时候自动调用socket.close_readQ通常可以定义一个structQƈ让这个struct impl trait DropQ在l构体销毁的时候调用socket.close_readQ又因ؓ(f)socket.close_read需要mut的socket引用Q而mut的引用只能borrow一ơ,所以这个struct一旦borrow了socket的mut引用Q之后再调用q个socket的mut函数׃(x)报错Q一个workaround的方法就是struct保存socket的一份拷贝(socket本n通过引用计数理Q,虽然可行Q但是L觉有些重了,仅仅为写h方便的一个问题引入了一ơ引用计数对象的拯。同时也?x)生一个警告,׃那个struct的对象没有被使用q?br />
Rust~译器报错信息很详细友好Q运行时依赖,Tunnel~译出来的的client和server都可以在其它机器上直接运行。其它方面主要是API文档跟不上,最新文档上有的函数Q编译器~译可能报错Q函数已l不存在了(刚刚ȝ了看最新的文Qstd::io变成了std::old_ioQ。库斚wQ虽然Cargo仓库里有一些第三方库,但是M数量q不多?/div>

airtrack 2015-02-03 21:03 发表评论
]]>操作pȝ实现Q一Q:(x)从Bootloader到ELF内核http://www.shnenglu.com/airtrack/archive/2014/10/30/208729.htmlairtrackairtrackThu, 30 Oct 2014 11:13:00 GMThttp://www.shnenglu.com/airtrack/archive/2014/10/30/208729.htmlhttp://www.shnenglu.com/airtrack/comments/208729.htmlhttp://www.shnenglu.com/airtrack/archive/2014/10/30/208729.html#Feedback1http://www.shnenglu.com/airtrack/comments/commentRss/208729.htmlhttp://www.shnenglu.com/airtrack/services/trackbacks/208729.html

Bootloader

我们知道计算机启动是从BIOS开始,再由BIOS军_从哪个设备启动以?qing)启动顺序,比如先从DVD启动再从盘启动{。计机启动后,BIOSҎ(gu)配置扑ֈ启动讑֤Qƈdq个讑֤的第0个扇区,把这个扇区的内容加蝲?x7c00,之后让CPU?x7c00开始执行,q时BIOS已经交出了计机的控制权Q由被加载的扇区E序接管计算机?/div>
q第一个扇区的E序叫BootQ它一般做一些准备工作,把操作系l内核加载进内存Qƈ把控制权交给内核。由于Boot只能有一个扇区大,?12字节Q它所能做的工作很有限Q因此它有可能不直接加蝲内核Q而是加蝲一个叫Loader的程序,再由Loader加蝲内核。因为Loader不是BIOS直接加蝲的,所以它可以H破512字节的程序大限Ӟ在实模式下理Z可以辑ֈ1MQ。如果Boot没有加蝲Loader而直接加载内核,我们可以把它叫做Bootloader?/div>
Bootloader加蝲内核pd文gQ在实模式下可以用BIOS的INT 13h中断。内核文件放在哪里,怎么查找dQ这里牵涉到文gpȝQBootloader要从盘QY盘)(j)的文件系l中查找内核文gQ因此Bootloader需要解析文件系l的能力。GRUB是一个专业的BootloaderQ它对这些提供了很好的支持?/div>
对于一个Toy操作pȝ来说Q可以简单处理,把内核文件放到Bootloader之后Q即从Y盘的W?个扇区开始,q样我们可以不需要支持文件系l,直接d扇区数据加蝲到内存即可?/div>

实模式到保护模式

我们知道Intel x86pdCPU有实模式和保护模式,实模式从8086开始就有,保护模式?0386开始引入。ؓ(f)了兼容,Intel x86pdCPU都支持实模式。现代操作系l都是运行在保护模式下(Intel x86pdCPUQ。计机启动Ӟ默认的工作模式是实模式,Z让内核能q行在保护模式下QBootloader需要从实模式切换到保护模式Q切换步骤如下:(x)
  1. 准备好GDT(Global Descriptor Table)
  2. 关中?/li>
  3. 加蝲GDT到GDTR寄存?/li>
  4. 开启A20Q让CPUd大于1M
  5. 开启CPU的保护模式,xcr0寄存器第一个bit|?
  6. 跌{C护模式代?/li>
GDT是Intel CPU保护模式q行的核心数据结构,所有保护模式操作的数据都从GDT表开始查找,q里有GDT的详l介l?/div>
GDT中的每一个表由8字节表示Q如下图Q?/div>


其中Access Byte和Flags如下图:(x)


q里
是详l说明?/div>
GDTR是一?字节的寄存器Q有4字节表示GDT表的基地址Q?字节表示GDT表的大小Q即最?5536Q实际值是65535Q?6位最大值是65535Q,每个表项8字节Q那么GDT表最多可以有8192V?/div>
实模式的dȝ?0bitsQؓ(f)了让d过1MQ需要开启A20Q可以通过以下指o(h)开启:(x)
    in al, 0x92
    or al, 2
    out 0x92, al
把上q步骤完成之后,我们p入保护模式了。在保护模式下我们要使用GDT通过GDT Selector完成Q它是GDT表项相对于v始地址的偏U,因此它的g般是0x0 0x8 0x10 0x18{?/div>

ELF文g

BootloaderE序是原始可执行文gQ如果程序由汇编写成Q汇~编译器~译生成的文件就是原始可执行文gQ也可以使用C语言~写Q编译成可执行文件之后通过objcopy转换成原始可执行文gQ?a >q篇文章介绍了用C语言写Bootloader?/div>
那么内核文g是什么格式的呢?跟Bootloader一L(fng)当然可以。内怸般用C语言~写Q每ơ编译链接完成之后调用objcopy是可以的。我们也可以支持通用的可执行文g格式QELF(Executable and Linkable Format)x一U通用的格式,它的l基癄?/div>
ELF文g有两U视图(ViewQ,链接视图和执行视图,如下图:(x)



链接视图通过Section Header Table描述Q执行视N过Program Header Table描述。Section Header Table描述了所有Section的信息,包括所在的文g偏移和大等QProgram Header Table描述了所有Segment的信息,即Text Segment, Data Segment和BSS SegmentQ每个Segment中包含了一个或多个Section?/div>
对于加蝲可执行文Ӟ我们只需x执行视图Q即解析ELF文gQ遍历Program Header Table中的每一,把每个Program Header描述的Segment加蝲到对应的虚拟地址卛_Q然后从ELF header中取出Entry的地址Q蟩转过d开始执行了。对于ELF格式的内核文件来_(d)q个工作需要由Bootloader完成。Bootloader支持ELF内核文g加蝲之后Q用C语言~写的内核编译完成之后就不需要objcopy了?/div>

Z么写操作pȝ

首先是兴,在现在这个时代,写操作系l几乎没有实用h(hun)|只能是一个ToyQ在写一个Toy OSӞ可以学习(fn)掌握很多知识Qƈ把这些知识诏I实用v来。操作系l是一个复杂的pȝQ牵涉到的东西很多,我相信写操作pȝ可以帮助理解C操作pȝ?qing)其它底层知识。我目前才刚开始写Q代码放?a >Github上?/div>


airtrack 2014-10-30 19:13 发表评论
]]>正则表达式实玎ͼ三)(j)http://www.shnenglu.com/airtrack/archive/2014/09/15/208319.htmlairtrackairtrackMon, 15 Sep 2014 11:04:00 GMThttp://www.shnenglu.com/airtrack/archive/2014/09/15/208319.htmlhttp://www.shnenglu.com/airtrack/comments/208319.htmlhttp://www.shnenglu.com/airtrack/archive/2014/09/15/208319.html#Feedback0http://www.shnenglu.com/airtrack/comments/commentRss/208319.htmlhttp://www.shnenglu.com/airtrack/services/trackbacks/208319.html
d׃两三个星期的业余旉实现了基于DFA的正则引擎(正则引擎常见的实现方?/strong>

正则的常见实现方式有三种QDFA、Backtracking、NFAQ?/div>



  • NFA(Thompson NFA)有相对DFA来说的构造简单,q兼有接qDFA的效率,q且在面对Backtracking出现指数复杂度时的正则表辑ּ保持良好的性能?/li>

NFA-based的实?/strong>

q里描述的NFA是指Thompson NFA。Thompson NFA实现的核心是对于正则表达式多个可能的匚wq发的向前匹配,此过E是在模拟DFAq行。比如对于正则表辑ּ"abab|abbb"匚w字符?abbb"Q?/div>

  • Backtracking的匹配过E是取正则的W一个子表达?abab"匚wQ前两个字符匚w成功Q匹配第三个字符的时候失败,q时引擎回溯选择W二个子表达?abbb"匚wQ最l匹配成功?/li>

  • Thompson NFA是同时取两个子表辑ּ"abab"?abbb"匚wQ前两个字符匚wӞ两个子表辑ּ都能匚w成功Q当匚wW三个字W时Q子表达?abab"匚wp|Q因此丢弃,"abbb"匚w成功接着匚wQ最l匹配成功?/li>

上面是一个简单的例子Q没有出?*" "+" "{m,n}"q种复杂的metacharactersQ在处理q种repeat的metacharacter时Thompson NFA优势更加明显?/div>

在实际复杂的正则表达式中QNFA构造是必然?x)生一堆epsilon边,q在W二文?/a>中有描述。上面描qThompson NFA实际是在模拟DFAq行Q在每个字符匚w完成之后需要蟩qepsilon边得到后面要匚w的ƈ发的状态集合,q样持箋的ƈ发匹配下去,当字W串匚w完成时只要有一个达C接受状态,是匚w成功Q若q个集合为空Q那表示匚wp|?/div>

在我的实CQ构造了一l状态和pl状态加epsilon辚w合构造的有向图,每个状态有自己的状态类型,分ؓ(f)两种Q?/div>

  • 一U是匚w状态类型,即用来匹配字W的状态,若字W匹配成功,则进入下一个状态;

  • 一U是操作状态类型,即不匚w字符的状态,在每个字W匹配结束之后若到达q些状态,则会(x)q行相应的操作,比如repeat状态,记录匚w计数Qƈ判断匚w计数是否完成再决定是否进入的下面的状态?/li>

repeat是一U会(x)分化的状态,辑ֈ最匹配次数时Q可以接着往下走Q也可以l箋重复匚wrepeat的子正则表达式,q样分化成两条U了Qƈ且每条线都带有自q状态数据,因此Q我的实C引入的thread来表CZ条匹配线Q里面有状态数据?/div>

Match和Search

状态构造完成了之后Q就要开始匹配了。匹配有两种Q一U是matchQ即一个正则表辑ּ能否完整匚w一个字W串Q若完整匚w则匹配成功;另一U是searchQ要在一个字W串中或者一块buffer中查找每个满的匚w。这里就有个问题Q从W一个字W开始匹配,匚w了几个字W之后发现匹配失败了怎么办呢Q回退到第二个字符重新匚wQ我们知道对于普通的字符串查找,有KMP法可以保证不回退字符Q其实KMP法的预处理是构造DFAQ,或者有Boyer-Moore法量回退的字符个数。对于正则这U复杂的匚w该怎么办呢Q从上面的Thompson NFA的描q可以知道匹配过E是多条Uƈ发匹配,因此可以构造一个始l生一条新U的状态,若匹配在前面的线p|被丢弃之后,后面的新U始l可以补上,q样查找的过E就不再需要回退字符了?/div>

我的实现中,状态构造完成后是这L(fng)Q?/div>

    // |-----|--------|---------------|-----|-------------|
    
// | any | repeat | capture begin |  | capture end |
    
// |-----|--------|---------------|-----|-------------|

用repeat-any来生新的匹配线。若在match模式下,则从W三个状态开始匹配,不会(x)产生新的匚wU,一旦匹配过E失败了失败了?/div>

l语

正则表达式语法一直在扩展Q新的语法有些很隑֜DFA和NFA中实玎ͼ而在Backtracking中的实现又是以牺牲性能Z仗因此有些正则表辑ּ实现?x)结合多U实现方式,判断正则表达式的cd选择不同的引擎,比如普通字W串加上一些简单的正则语法采用DFA引擎匚wQ或者只有普通字W串的匹配可以用Boyer-Moore法Q毕竟Boyer-Moore法在普通文本查找中要优于KMP法Q)(j)Q对于复杂的正则表达式采用BacktrackingQ甚x些正则引擎用JIT来加速?/div>



airtrack 2014-09-15 19:04 发表评论
]]>初分代GChttp://www.shnenglu.com/airtrack/archive/2013/11/17/204295.htmlairtrackairtrackSun, 17 Nov 2013 14:20:00 GMThttp://www.shnenglu.com/airtrack/archive/2013/11/17/204295.htmlhttp://www.shnenglu.com/airtrack/comments/204295.htmlhttp://www.shnenglu.com/airtrack/archive/2013/11/17/204295.html#Feedback1http://www.shnenglu.com/airtrack/comments/commentRss/204295.htmlhttp://www.shnenglu.com/airtrack/services/trackbacks/204295.html

GC的分c?/h2>
通常情况下GC分ؓ(f)两种Q分别是Q扫描GC(Tracing GC)和引用计数GC(Reference counting GC)。其中扫描GC是比较常用的GC实现Ҏ(gu)Q其原理是:(x)把正在用的对象扑և来,然后把未被用的对象释放。而引用计数GC则是Ҏ(gu)个对象都d一个计数器Q引用增加一个计数器加一Q引用减一个计数器减一Q当计数器减至零Ӟ把对象回攉放。引用计数GC跟C++中的shared_ptrcMQ自然也?x)存在@环引用问题?br />
扫描GC(Tracing GC)是广泛用的GCҎ(gu)Q最单的实现方式是mark-sweepQ即扫描所有存?gu)zȝ对象qmarkQ然后遍历整个GC对象列表Q把所有标记过的对象清除标讎ͼ把未标记q的对象释放。如果GC使用的是mark-sweepҎ(gu)Q程序运行一D|间后触发了GCQ每ơGC的时候会(x)把当前程序中的所有对象都扫描一ơ,然后释放未用的对象。这对于分配GC对象的E序来说没有什么问题,当程序中存在大量分配GC对象Ӟ每次启动GC扫描所有对象的代h(hun)是很高的Q又因ؓ(f)GC的过E通常是stop-the-worldQ所以高代h(hun)的GC?x)导致整个程序卡一D|间。对于这个问题,解决Ҏ(gu)有增量GC(Incremental GC)和分代GC(Generational GC)?br />
增量GC(Incremental GC)?x)把整个GCq程分成很多?phase)Q每步的执行可以存在一定间隔运行程序本w,q就量把stop-the-world的时间变短,使得E序不会(x)因ؓ(f)GC而导致gq太大。Lua默认采用的是q种实现Ҏ(gu)QLua 5.2中也引入了分代GC作ؓ(f)备选GCҎ(gu)?br />
分代GC(Generational GC)把对象分成几?Generation)Q通常把GC分ؓ(f)两种QMinor GC和Major GC。刚刚分配出来的对象属于最q轻的一代,在一ơGCq后把年M中存?gu)zȝ对象上升到年老的一代中。把只扫描年M代的对象以减扫描对象数量的GCq程UCؓ(f)Minor GCQ只有在特定情况下才?x)启动完整的Major GC。分代GC是基于在大多数程序中新创建的对象同时也是最快变成无效的对象的经验设计的Q对q轻代对象GCӞ可以释放大多数无效对象,存活下来的对象一般存?gu)zL间也?x)更长,因此把它们上升到下一代中以减最q些对象的扫描?br />
对于GC内存的管理,有移动和非移动之分。移动的是把一ơGCq后存活的对象compactCP使GC理的内存保持连l,q里增加了一个移动对象的开销Q不q它也同样带来不好处:(x)分配释放对象快和更快的序列遍?在CPU cache中及(qing)在同一个Virtual memory page?。正因ؓ(f)它会(x)把对象compactCP对象的地址׃(x)发生变化Q这也就D一个明昄~点Q不能用指针引用GC对象?br />
其它高GCҎ(gu)Q比?NET的background GCQ几乎不需要stop-the-world可以在GCU程中完成GCQ这U高U技的GC对于我这U初Uh士基本属于不可想象?br />

初分代GC设计

了解了基本的GCҎ(gu)之后Q我?a >lunaW二?/a>实现了一个初U的分代GCQ把对象分成三代QGCGen0,GCGen1,GCGen2:

   GCGen0是最q轻的一代,默认所有对象都是分配在q代中?/div>
   GCGen1是年老的一代,在一ơGCq后GCGen0代存?gu)zȝ对象?x)移动到q一代中?/div>
   GCGen2是最老的一代,一般情况下用于存放~译时分配的?x)长期存在的对象Q比如函数及(qing)字符串常量?br />
׃我在很多地方直接引用了GC对象的指针,Z单v见,我没有在GC之后Ud对象Q而是Ҏ(gu)个对象单独分配释攑ֆ存。每个对象都有Generation标记和GC标记以及(qing)一个用于指向跟自己属于同代的GC对象的指针?br />
Minor GC对GCGen0代对象mark-sweepQƈ把存?gu)zȝ对象Ud到GCGen1代中。既焉要markQ自焉要对所有GCGen0代存?gu)zȝ对象标记Q这通过对root对象的遍历完成,root是指所有对象的引用入口Q比如程序的栈和全局表。对于Minor GC的root对象遍历最单的Ҏ(gu)是跟Major GC的root遍历完全一_(d)不过q样的遍历对于本来就是ؓ(f)了减遍历对象的Minor GC来说g不合Q所以通常只对某一块root遍历Q比如只Ҏ(gu)上的对象遍历Q然后再把存?gu)zȝ对象保留不存?gu)zȝ对象释放?br />
Minor GC的root遍历存在一个问题:(x)假设只把栈上的对象作为root遍历Q会(x)存在一些从GCGen0代分配出来的对象没有被栈上的对象引用Q而被全局表中的某个对象引用,或者其它某个非GCGen0对象引用了,q样对GCGen0代sweep的时候可能会(x)把这个存?gu)zȝ对象当做无效对象而释放掉Q这U操作自然也׃(x)D整个E序crash。于是ؓ(f)了控制root遍历的范_(d)又要解决q个问题Q对非GCGen0对象引用GCGen0对象的时候,需要把q个非GCGen0的对象也加入到root遍历列表中去。这时引入了barrierQ对于非GCGen0对象引用GCGen0对象Ӟ把这个非GCGen0的对象放到barrier列表中?br />
Major GC是一个完整的GCQ它遍历所有的rootqmarkQƈ把所有的无效的对象都sweep释放?br />

GC启动的时?/h2>

GC什么时候启动是一个需要仔l考虑的问题,׃我实现的GCq没有自q理内?Lua也没有自q理内存,所有内存分配都通过realloc)Q所以我把GCGen0代和GCGen1代的对象数量作ؓ(f)启动时机的衡量指标,当GCGen0和GCGen1的对象数量大于它们的阈值时Q分别启动Minor GC和Major GC。我觉得对象的数量比起内存占用大?各种复杂的GC对象D内存占用很难_的统计,Lua的内存统计也不够_)更能反映GC旉的长短,如果两者结合也怼(x)更好?br />
通过判断GC对象个数过阈值时启动GCQ同旉要在GC之后自动调整阈值大。比如某些程序很快的辑ֈGCGen0的阈值ƈ在Minor GC之后有超q一半的对象q是存活的,q时需要把阈D大,以减GC启动的次敎ͼq个阈g不能无限扩大Q这不仅?x)导致一D|间内内存占用一直上升,也会(x)D一旦触发GC所需扫描的对象数量太多,GC耗时太长Q程序运行的延时增加?br />

l语

Z减少stop-the-world的时_(d)引入的各U方法都?x)让GC实现隑ֺ加大。GC是一个复杂的东西Q网上所能找到的资料文章g不太多,而有关GC的书Q目前只发现《The Garbage Collection Handbook?/a>(我还没有看过)Q而这本书既没有pdf也没有kindle版,只能在美国Amazon上买U质书。另外一个参考资料就是各个语a的实现源码了?/div>


airtrack 2013-11-17 22:20 发表评论
]]>正则表达式实玎ͼ二)(j)http://www.shnenglu.com/airtrack/archive/2013/09/01/202935.htmlairtrackairtrackSun, 01 Sep 2013 15:25:00 GMThttp://www.shnenglu.com/airtrack/archive/2013/09/01/202935.htmlhttp://www.shnenglu.com/airtrack/comments/202935.htmlhttp://www.shnenglu.com/airtrack/archive/2013/09/01/202935.html#Feedback0http://www.shnenglu.com/airtrack/comments/commentRss/202935.htmlhttp://www.shnenglu.com/airtrack/services/trackbacks/202935.html

?a title="上一? href="http://www.shnenglu.com/airtrack/archive/2013/07/05/201530.html">上一?/a>已经有近两个月的旉了,q段旉事情?ch)(多?j)Q导致没心情写,现在争取补上?/p>


生成epsilon-NFA

epsilon-NFA是包含epsilon边(IQ的NFAQ把单正则表辑ּ转换成epsilon-NFA的方法如下:(x)

正则表达式:(x)”ab” 对应的epsilon-NFA是:(x)


正则表达式:(x)”a|b”对应的epsilon-NFA是:(x)


正则表达式:(x)”a*” 对应的epsilon-NFA是:(x)


q是最基本?U正则表辑ּ的NFA表示Q其中a*在实际的正则表达式实C通常生成的epsilon-NFA不是q样的,因ؓ(f)有下面这些正则表辑ּ存在Q?/p>

a{m}       重复aQm?br />a{m,n}     重复aQm到n?br />a{m,}      重复aQ至m?br />a+         重复aQ至??br />a?         重复aQ?ơ或1?/div>

所以对于a*表示重复臛_0ơ的实现可以跟上面这些正则表辑ּ采用相同Ҏ(gu)的实现?/p>

按照q些生成规则可以把正则表达式{换成epsilon-NFAQ我代码中即把这些生成规则实现成一个AST的visitor?/p>

 

epsilon-NFA subset construction to DFA

在生成了epsilon-NFA之后Q通常?x)有很多epsilon的边存在Q也?x)有很多无用的state存在Q所以通常需要把epsilonҎ(gu)除ƈ合ƈstateQ这个过E采用的法是subset constructionQ如下:(x)

subset construction:
start_subset <- epsilon_extend(start_state)    // 把start_state通过epsilon扩展得到起始subset
subsets <- { start_subset }                    // 初始化subsets
work_list <- subsets                           // 初始化work_list
while (!work_list.empty())
{
    subset <- work_list.pop_front()
    for edge in epsilon-NFA                    // 取出NFA中的每条?/span>
    {
        next_subset <- delta(subset, edge)     // 对subset中的每个state通过edge所到达的state的epsilonҎ(gu)展得到next_subset
        if (!subsets.exist(next_subset))       // 如果next_subset不存在于subsets中,则把q个next_subset加入到work_list?/span>
            work_list.push_back(next_subset)
        map[subset, edge] = next_subset        // 构徏subset到next_subset的边映射
        subsets.merge({next_subset})           // 把next_subset合ƈ到subsets
    }
}

delta:
next_subset <- { }    // 初始化next_subset为空集合
for state in subset
{
    // 取出next_stateq将它通过epsilonҎ(gu)展得到的subset合ƈ到next_subset?/span>
    next_state <- map[state, edge]
    if (next_state)
        next_subset.merge(epsilon_extend(next_state))
}

 

q里面用了epsilon_extendQ它是把一个state的所有epsilon边能到达的state构成一个集合,比如上面正则表达式a*对应的epsilon-NFA中的所有state的epsilon_extend是:(x)

epsilon_extend(1) –> { 1 }
epsilon_extend(2) –> { 1, 2, 4 }
epsilon_extend(3) –> { 1, 3, 4 }
epsilon_extend(4) –> { 4 }

对于一个epsilon-NFA来说Q每个state的epsilon_extend是固定的Q因此可以对epsilon-NFA中的每个state都求出epsilon_extendq保存下来,法如下Q?/p>

epsilon_extend_construct:
work_list <- { }
// 为每个state初始化epsilon_extend集合
for state in epsilon-NFA
{
    epsilon_extend(state) <- { state }
    work_list.push_back(state)
}
while (!work_list.empty())
{
    state <- work_list.pop_front()
    state_epsilon_extend <- epsilon_extend(state)
    // 把state通过epsilon所能到辄state的epsilon_extend
    
// 合ƈ到当前state的epsilon_extend
    for next_state in map[state, epsilon]
        state_epsilon_extend.merge(epsilon_extend(next_state))
    // 如果当前state的epsilon_extend变化了之?br />    // 把所有通过边epsilon到达state的pre_state都加入到work_list?/span>
    if (state_epsilon_extend.has_changed())
    {
        for pre_state in epsilon_pre(state)
            work_list.push_back(state)
    }
}

 

epsilon-NFA通过subset construction构造成完之后,q把构造的subsets中的subset转换成DFA中的stateQ再把NFA中除epsilon边之外的所有边都{换成DFA的边Q这样就把DFA构造完成?/p>


DFA minimization

从NFA构造完成DFA之后Q这时的状态数量一般不是最的Qؓ(f)了减最l生成的状态机的状态数量,通常?x)对DFA的stateq行最化构造,q个法具体如下Q?/p>

minimization:
// 把所有state划分成accept的state集合和非accept的state集合
state_sets <- { {accept_state(DFA)}, {non_accept_state(DFA)} }
do
{
    work_list <- state_sets
    old_state_sets_size <- state_sets.size()
    state_sets <- { }
    for state_set in work_list
    {
        split_success <- false
        for edge in DFA
        {
            // 如果edge可以把state_set拆分成两个subsetQ那把新拆分出来的
            
// 两个subset合ƈ到state_sets里面Qƈbreakl箋work_list中取Z一?br />            // state_set拆分
            subset1, subset2, split_success <- split(state_set, edge)
            if (split_success)
            {
                state_sets.merge({subset1, subset2})
                break
            }
        }
        if (!split_success)
            state_sets.merge({state_set})
    }
while (old_state_sets_size != state_sets.size())


q里面的split是把一个state_set按edge划分成两个subsetQ即对于state_set中的每一个state都通过q条边edge到达的state属于不同的state_set时就把state_set拆分成两个subset。首先把W一个state划分到subset1中,从第二个state开始通过边edge到达的state所属的state_set和第一个state通过边edge到达的state所属的state_set为同一个的时候,把这个state划分到subset1中,否则划分到subset2中?/p>

q个法p样依ơ把最初的两个state_setQaccept的statel成的set和非accept的statel成的setQ划分到不能再划分ؓ(f)止,此时把能合q的state都合q到了同一个state_set中,q时只需要把每个state_set转换成最l状态机中的stateQ即可完成DFA的最化构造ƈ转换成状态机。得到状态机之后Q就可以使用状态机q行字符匚w了?/p>



airtrack 2013-09-01 23:25 发表评论
]]>
正则表达式实玎ͼ一Q?/title><link>http://www.shnenglu.com/airtrack/archive/2013/07/05/201530.html</link><dc:creator>airtrack</dc:creator><author>airtrack</author><pubDate>Fri, 05 Jul 2013 05:30:00 GMT</pubDate><guid>http://www.shnenglu.com/airtrack/archive/2013/07/05/201530.html</guid><wfw:comment>http://www.shnenglu.com/airtrack/comments/201530.html</wfw:comment><comments>http://www.shnenglu.com/airtrack/archive/2013/07/05/201530.html#Feedback</comments><slash:comments>3</slash:comments><wfw:commentRss>http://www.shnenglu.com/airtrack/comments/commentRss/201530.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/airtrack/services/trackbacks/201530.html</trackback:ping><description><![CDATA[<div> <div> <div class="jrrxhoh" id="bd423564-6412-419c-8b26-45edcb529002" style="border-width: 0px; margin: 4px 0px 0px;"><p>实现正则表达式的x很早有Q各U原因导致没有做Q最q花了点旉?a target="_blank">实现了几个简单的正则语法</a>Q分别是concatenation、alternation和closureQ其他语法及(qing)metacharacter{有旉了有x了之后再扩展?/p> <p> </p> <p>q三U基本的语法分别是对应这L(fng)Q?/p> <p>concatenation: abc    表示匚w字符串abc</p> <p>alternation: abc|def   表示匚w字符串abc或者def</p> <p>closure: a*               表示匚w零个到多个a构成的字W串</p> <p> </p> <p>我们知道正则表达式最l需要{换成自动机才能用来匹配字W串Q我实现的正则通过如下几个步骤把正则表辑ּ转换成自动机Q?/p> <p>正则表达?>Parse成AST->生成边(字符Q集?>生成NFA->NFA subset construction->转换成DFA->DFA minimization</p> <p>最后用DFA minimization之后构造的自动机来匚w字符丌Ӏ?/p> <p> </p> <h3>正则语法的分?/h3> <p>一个正则表辑ּ写出来,要让q个正则表达式匹配字W串{操作之前,我们先需要从正则表达式中提取需要的信息q在正则语法错误的时候提C错误,q个q程自然不了parser。一个parser通常是从一个lexer里面获取一个tokenQ而正则表辑ּ的token都是字符Q那么lexer不需要做M的分词操作,只需要简单的把字W返回给parser卛_?/p> <p>那三U基本的正则语法对应的BNF为:(x)</p> <div style="background-color:#eeeeee;font-size:13px;border:1px solid #CCCCCC;padding-right: 5px;padding-bottom: 4px;padding-left: 4px;padding-top: 4px;width: 98%;word-break:break-all"><!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->re ::= alter<br />re_base ::= <span style="color: #0000FF; ">char</span> | char_range | '(' re ')'<br />alter ::= alter_base alter_end<br />alter_base ::= concat<br />alter_end ::= '|' alter_base alter_end | epsilon<br />concat ::= concat_base concat_end<br />concat_base ::= re_base | closure<br />concat_end ::= concat_base concat_end | epsilon<br />closure ::= re_base '*'</div> <p>q个parser分析了正则表辑ּ之后产生ASTQAST的nodecd为:(x)</p><pre><div style="background-color:#eeeeee;font-size:13px;border:1px solid #CCCCCC;padding-right: 5px;padding-bottom: 4px;padding-left: 4px;padding-top: 4px;width: 98%;word-break:break-all"><span style="color: #0000FF; ">class</span> ASTNode<br />{<br /><span style="color: #0000FF; ">public</span>:<br />    ACCEPT_VISITOR() = 0;<br />    <span style="color: #0000FF; ">virtual</span> ~ASTNode() { }<br />};<br /> <br /><span style="color: #0000FF; ">class</span> CharNode : <span style="color: #0000FF; ">public</span> ASTNode<br />{<br /><span style="color: #0000FF; ">public</span>:<br />    <span style="color: #0000FF; ">explicit</span> CharNode(<span style="color: #0000FF; ">int</span> c) : c_(c) { }<br /> <br />    ACCEPT_VISITOR();<br /> <br />    <span style="color: #0000FF; ">int</span> c_;<br />};<br /> <br /><span style="color: #0000FF; ">class</span> CharRangeNode : <span style="color: #0000FF; ">public</span> ASTNode<br />{<br /><span style="color: #0000FF; ">public</span>:<br />    <span style="color: #0000FF; ">struct</span> Range<br />    {<br />        <span style="color: #0000FF; ">int</span> first_;<br />        <span style="color: #0000FF; ">int</span> last_;<br /><br />        <span style="color: #0000FF; ">explicit</span> Range(<span style="color: #0000FF; ">int</span> first = 0, <span style="color: #0000FF; ">int</span> last = 0)<br />            : first_(first), last_(last)<br />        {<br />        }<br />    };<br /><br />    CharRangeNode() { }<br /><br />    <span style="color: #0000FF; ">void</span> AddRange(<span style="color: #0000FF; ">int</span> first, <span style="color: #0000FF; ">int</span> last)<br />    {<br />        ranges_.push_back(Range(first, last));<br />    }<br /> <br />    <span style="color: #0000FF; ">void</span> AddChar(<span style="color: #0000FF; ">int</span> c)<br />    {<br />        chars_.push_back(c);<br />    }<br /> <br />    ACCEPT_VISITOR();<br /> <br />    std::vector<Range> ranges_;<br />    std::vector<<span style="color: #0000FF; ">int</span>> chars_;<br />};<br /> <br /><span style="color: #0000FF; ">class</span> ConcatenationNode : <span style="color: #0000FF; ">public</span> ASTNode<br />{<br /><span style="color: #0000FF; ">public</span>:<br />    <span style="color: #0000FF; ">void</span> AddNode(std::unique_ptr<ASTNode> node)<br />    {<br />        nodes_.push_back(std::move(node));<br />    }<br /> <br />    ACCEPT_VISITOR();<br /> <br />    std::vector<std::unique_ptr<ASTNode>> nodes_;<br />};<br /> <br /><span style="color: #0000FF; ">class</span> AlternationNode : <span style="color: #0000FF; ">public</span> ASTNode<br />{<br /><span style="color: #0000FF; ">public</span>:<br />    <span style="color: #0000FF; ">void</span> AddNode(std::unique_ptr<ASTNode> node)<br />    {<br />        nodes_.push_back(std::move(node));<br />    }<br /> <br />    ACCEPT_VISITOR();<br /> <br />    std::vector<std::unique_ptr<ASTNode>> nodes_;<br />};<br /> <br /><span style="color: #0000FF; ">class</span> ClosureNode : <span style="color: #0000FF; ">public</span> ASTNode<br />{<br /><span style="color: #0000FF; ">public</span>:<br />    <span style="color: #0000FF; ">explicit</span> ClosureNode(std::unique_ptr<ASTNode> node)<br />        : node_(std::move(node))<br /> {<br />    }<br /> <br />    ACCEPT_VISITOR();<br /> <br />    std::unique_ptr<ASTNode> node_;<br />};</div></pre> <p>其中ASTNode作ؓ(f)AST的基c,q提供接口实现Visitor模式讉KASTNodecd?/p> <p> </p> <h3>字符Q边Q集的构?/h3> <p>AST构造好了之后,需要把AST转换成NFA。语法中有[a-zA-Z0-9]q种字符区间表示法,我们可以用最单原始的Ҏ(gu)转换Q就是把区间中的每个字符都{化成相应的一条边QNFA中的边)(j)Q这样一来会(x)D字符区间大Q对应边的数量会(x)多Q得对应的NFA也越大。因此,我们需要构造区间字W集合来减少边的数量?/p> <p>比如正则表达式是Qa[x-z]|[a-z]*e</p> <p>那么我们希望对应的字W集合是q样Q[a-a] [b-d] [e-e] [f-w] [x-z]</p> <p>q需要构造一个字W集Q每ơ插入一个区间的时候,把新插入的区间与已存在的区间q行分割Q初始时已存在的区间集ؓ(f)I,那么正则表达式a[x-z]|[a-z]*e的划分步骤如下:(x)</p> <p>已存在区间集合{}Q插入[a-a]Q得到{[a-a]}</p> <p>已存在区间集合{[a-a]}Q插入[x-z]Q得到{[a-a], [x-z]}</p> <p>已存在区间集合{[a-a], [x-z]}Q插入[a-z]Q得到{[a-a], [b-w], [x-z]}</p> <p>已存在区间集合{[a-a], [b-w], [x-z]}Q插入[e-e]Q得到{[a-a], [b-d], [e-e], [f-w], [x-z]}</p> <p>q个区间构造完成了之后Q还需要在后面转换成NFA边的时候,Ҏ(gu)字符区间查询出在q个集合中,由哪几个区间构成Q比如:(x)</p> <p>查询区间[a-a]Q得到[a-a]</p> <p>查询区间[x-z]Q得到[x-z]</p> <p>查询区间[a-z]Q得到区间[a-a] [b-d] [e-e] [f-w] [x-z]</p> <p>在{换成NFAӞ集合中的每个区间都对应一条边Q这L(fng)对于每个字符对应一条边Q边的数量不?x)太多?/p> <p>有了q么一个集合构造的cM后,把正则的AST中的字符信息提取出来构造出q么个集合即可,q样只需要写个visitor完成了Q?/p><pre><div style="background-color:#eeeeee;font-size:13px;border:1px solid #CCCCCC;padding-right: 5px;padding-bottom: 4px;padding-left: 4px;padding-top: 4px;width: 98%;word-break:break-all"><span style="color: #0000FF; ">class</span> EdgeSetConstructorVisitor : <span style="color: #0000FF; ">public</span> Visitor<br />{<br /><span style="color: #0000FF; ">public</span>:<br />    <span style="color: #0000FF; ">explicit</span> EdgeSetConstructorVisitor(EdgeSet *edge_set)<br />        : edge_set_(edge_set)<br />    {<br />    }<br /> <br />    EdgeSetConstructorVisitor(<span style="color: #0000FF; ">const</span> EdgeSetConstructorVisitor &) = delete;<br />    <span style="color: #0000FF; ">void</span> <span style="color: #0000FF; ">operator</span> = (<span style="color: #0000FF; ">const</span> EdgeSetConstructorVisitor &) = delete;<br /> <br />    VISIT_NODE(CharNode);<br />    VISIT_NODE(CharRangeNode);<br />    VISIT_NODE(ConcatenationNode);<br />    VISIT_NODE(AlternationNode);<br />    VISIT_NODE(ClosureNode);<br /><br /><span style="color: #0000FF; ">private</span>:<br />    EdgeSet *edge_set_;<br />};</div></pre> <p>辚w合构造完成之后,下一步就是生成NFA了?/p></div></div></div><img src ="http://www.shnenglu.com/airtrack/aggbug/201530.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/airtrack/" target="_blank">airtrack</a> 2013-07-05 13:30 <a href="http://www.shnenglu.com/airtrack/archive/2013/07/05/201530.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>学习(fn)Haskellhttp://www.shnenglu.com/airtrack/archive/2013/04/30/199862.htmlairtrackairtrackTue, 30 Apr 2013 12:41:00 GMThttp://www.shnenglu.com/airtrack/archive/2013/04/30/199862.htmlhttp://www.shnenglu.com/airtrack/comments/199862.htmlhttp://www.shnenglu.com/airtrack/archive/2013/04/30/199862.html#Feedback0http://www.shnenglu.com/airtrack/comments/commentRss/199862.htmlhttp://www.shnenglu.com/airtrack/services/trackbacks/199862.html最q几个月利用上下班的旉在学?fn)HaskellQHaskell有不让人开阔思\的东西,也有不少看v来很好Q用h不错Q但是读h费劲的东ѝHaskell的语法学的差不多了之后,用Haskell写了一个简单的C++代码行统计工?/a>Q写q几个版本,留下了两个,一个是直接用模式匹配写的,一个是山寨了一个极的parse combinatorQ然后用q个山寨的parse combinator写了一个版本,代码估计写的都比较烂Q以后进阶学?fn)之后有旉再改。这个统计工具ƈ不是完整的处理C++的语法,也没对在字符串和宏定义里面的"http://" "/*" "*/"做处理,因此Ҏ(gu)些C++E序l计代码行,可能不完全正,但是基本可以用?/p>


data, type, newtype


Haskell里面用data来定义数据类型,它可以是q样Q?br /> 

data Mode = ReadMode | WriteMode
data Some = Some Int String
data Thing = { a :: Int, b :: String }
data Func a b = { func :: a -> b }

 

W一行定义了一个ModeQ包含ReadMode和W(xu)riteModeQ?/p>

W二行定义了一个普通数据类型SomeQ包含一个Int数据和一个String数据Q?/p>

W三行定义了一个普通数据类型ThingQ包含类型ؓ(f)Int的a和类型ؓ(f)String的bQ?/p>

W四行定义了一个符合数据类型FuncQ里面有个函数类型ؓ(f)(a -> b)的数据func?/p>


W一U相当于C++中的enum classQ第二种W三U相当于普通的struct数据Q第二种和第三种的区别是W二U不能直接取到Int和String的数据,W三U可以通过a,b取到数据Q第四种相当于C++的template class(struct)Q第四种写成q样来定义具体的数据cdQ?br />

type IntStringFunc = data Func Int String

 

type在这里定义了一个别名IntStringFunccdQ包含了一个函数类型是Int -> String的func的数据,q里的type相当于C++ 11的using别名Q因为它q可以这样写Q?/p>


type IntBFunc b = data Func Int b


在C++ 11中,using包含了typedef的功能,也支持了template class的类型typedefQ如下:(x)


template <typename T, typename P>
class SomeType;

template <typename T>
using SomeTypeInt = SomeType<T, int>;


newtype定义的数据类型跟typecdQ不qtype定义的纯_Ҏ(gu)别名Q别名类型跟原始cd是一致的Q而newtype则定义的是一个wrapperQ是一U新的数据类型,所以是newtype。newtype定义的类型是~译时期的wrapperQHaskell保证没有q行时期的开销Qnewtype定义的跟datacMQ?br />

newtype NewType a b = NewType { func :: a -> b }


模式匚w


上面说道data定义的第二种数据cdQ包含I(xin)nt和String的数据,但是不能直接取到q两个数据,所以我们需要定义两个函数来取其中的数据Q?/p>


some = Some 0 "test"  -- 定义一个数据,cd为Some

-- 定义两个函数用于获取Some的数?br />getSomeInt Some i _ = i
getSomeString Some _ s = s

getSomeInt some  -- 0
getSomeString some  -- "test"


q里的getSomeInt和getSomeString函数都是采用模式匚w来实玎ͼ模式匚w是把数据的l构直接写在代码中来匚wQ然后取出想要用的数据卛_?/p>


Haskell里常用的Maybe数据cd是这样定义的Q?/p>


data Maybe a = Nothing
                     | Just a


如果要取用Maybe里面的|我们通常使用模式匚w来获取数据,如下Q?/p>


useMaybe maybe =
     case maybe of
          Nothing -> …  -- Maybe的值是I?br />          Just a -> …  -- 直接使用a卛_

useMaybe (Just 1)


下面调用useMaybe的函C内取到的a的值就??/p>


Haskell里的内置数据cdlistQ比如[1, 2, 3, 4]Q?可以把新的元素添加到l(f)ist头部Q即Q?/p>


0 : [1, 2, 3, 4]  -- [0, 1, 2, 3, 4]


q样的特性同样可以简单的套用在模式匹配上面,如下Q?/p>


useList [] = 
useList (x:xs) = … -- x是list里面的第一个元素,xs是list的尾?/div>


模式匚w可以很直观的匚w数据的原始表C方式,q可以取出其中有用的值做其他操作Q它是一个简单直观有效的操作数据的方式,甚至可以在嵌套很qtuple数据里面直接取出惌的数据,而不用像C++那样调用tuple::get之类的函数来取出其中的|比如Q?/p>


getTupleValue (_, _, _, (_, _, (x:xs))) = … -- 取得x和xs数据


Visitor模式和C++ template


王垠说设计模?/a>中值得一提的模式不多Q其中之一的visitor模式是在模拟模式匚w。visitor模式通常是访问获取某个承类层次构成的一个树(wi)形结构中的某个节点的具体cdQƈ对这U具体类型做某些操作Q而模式匹配是可以从复杂的数据l构中直接取出想要的数据?/p>


C++的template meta-programming也可以看成是一U模式匹配,C++里面著名的Factorial求值是q样的:(x)


template <int N>
struct Factorial
{
     enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0>
{
     enum { value = 1 };
};

int v = Factorial<10>::value;


而这D代码如果用Haskell写是q样的:(x)


factorial 0 = 1
factorial n = n * factorial (n - 1)

v = factorial 10


C++中的模板参数是用来做模式匹配的Q每特化一U类型就可以匚w某种cdQ然后对那种匚w的类型做相应的操作。C++的template meta-programming是编译时期(~译器运行期Q的行ؓ(f)Q所以它只能操作cd以及(qing)~译时期能够定的|而模式匹配是E序本n的运行期的行为?/p>


Currying


Haskell的Currying是一个很有用的特性,但是我觉得这个特性滥用的话,也会(x)让程序代码的可读性降低不。所谓Currying是可以向一个多参数的函C递比它所需的参C数更的参数后返回生成的一个新函数接受剩余的参数的函数。Haskell里的函数默认都是curried的,所以Haskell里面的函数可以随意curryingQ比如:(x)


add :: Int -> (Int -> Int)  -- 一般写?nbsp;Int -> Int -> Int
add a b = a + b

addOne :: Int -> Int
addOne = add 1

addOne 2 -- result: 3


Currying的实现是使用的单参数的lambda构成的闭?closure)Qadd可以看成是接受一个Int参数q回一个函敎ͼq个函数的类型是Int -> Int?/p>


Partial application


Currying是一个从左到右部分传参数的一个过E,也就是不?x)出现参数aq没l,q了具体的参数b的情c(din)如果确定要先给参数bQ那么它是Partial applicationQ如下:(x)


addTwo a = add a 2

addTwo 1 -- result: 3

(+ 2) 1 -- result: 3


(+ 2)q种cM的用法可能会(x)作ؓ(f)参数传递给另外一个函数。Partial application是一U更宽泛的概念,上面的Currying是一UPartial application?/p>


正如王垠所?/a>的,如果一个函数接受了多个参数Q但是这个函数在实际调用中被Currying了很多次Q那最后生成的那个函数它到底接受几个参数是不能很直观的看明白的Q比如:(x)


func a b c d e f = …

do1 = func 1
do2 = do1 2
do3 = do2 3
do4 = do3 4
do5 = do4 5


那当我们看到do5函数的时候,我们是很隑ֈ断do5到底接受几个参数Q尤其是do5跟前面几个doN函数不在同一个地方定义,很有可能do5只是传递给某个函数的参敎ͼ当然如果l每个函数都加上函数cd声明?x)清晰许多。当Currying到了flip之后Q那代码的可L会(x)降低更多Q所以我觉得Currying是一个很有用的特性,但是如果被滥用的话,那代码的可读性会(x)是一个问题?/p>


C++: function + bind


C++中的function + bind其实是一UPartial application实现Q比如:(x)


int Func(int a, int b, int c);

std::function<int (intint)> f1 = std::bind(Func, 1, std::placeholders::_1, std::placeholders::_2);
std::function<int (int)> f2 = std::bind(f1, std::placeholders::_1, 3);
f2(2); // Func(1, 2, 3);


我觉得C++的function + bind?x)比Currying的可L要好一些,毕竟我们可以完整看到f1和f2的函数类型,知道参数cd?qing)个数和q回|是有利于代码的可L的Q当然这里完全可以不写出f1和f2的类型,采用autoQ我们同样可以从调用函数bind的placeholder的个数得知bind之后的function的参C敎ͼq样我们可以不用看到函数Func的声明,q道需要传几个参数。function + bind跟Currying一样会(x)影响代码的可L,如果嵌套的层ơ越多,可读性就差Q所以用这些特性的时候不要过度?/p>


typeclass


Haskell用typeclass来表CZ个conceptQ它是一l抽象函数的集合Q一个满x个typeclass的数据类型,它就可以跟其他用这个typeclass的函数或者数据类型组合用。typeclass一般这么定义:(x)


class Monad m where
     (>>=) :: m a -> (a -> m b) -> m b
     (>>) :: m a -> m b -> m b
     return :: a -> m a
     fail :: String -> m a


它定义了一个叫Monad的typeclassQ这个typeclass的concept里有四个函数Q分别是(>>=), (>>), return和failQm是一个带cd参数的数据类型。我们上面知道了Maybe是一个带cd参数的datacdQ它定义如下Q?/p>


data Maybe a = Nothing
                     | Just a


既然Maybe是一个带cd参数的dataQ那它就满Monad typeclass中m的需求,因此可以把Maybe定义成MonadQ如下:(x)


instance Monad Maybe where
     (>>=) maybeA f =
          case maybeA of
               Nothing -> Nothing
               Just a -> f a

     (>>) maybeA maybeB = maybeA >>= (\_ -> maybeB)

     return = Just

     fail = error


q里(\_ -> maybeB)定义了一个lambdaQ参?_ 紧接 \Q?> 后面则是函数体。函?>>)和fail是可以作为默认实现放到class Monad的定义里面,而instance Monad的时候只需要实?>>=)和return卛_?/p>


class Monad m where
     (>>=) :: m a -> (a -> m b) -> m b
     (>>) :: m a -> m b -> m b
     (>>) ma mb = ma >>= (\_ -> mb)
     return :: a -> m a
     fail :: String -> m a
     fail = error


对于内置listcd[a]Q也是带有一个类型参数aQ因此,我们同样可以把[] instance成ؓ(f)class MonadQ如下:(x)


instance Monad [] where
     (>>=) (x:xs) f = (f x) ++ (xs >>= f)
     (>>=) [] _ = []
     return a = [a]


函数(>>)和fail我们保留默认的实现即可?/p>


Monad


上面实现的定义的typeclass是Haskell著名的MonadQ它是组合其他操作的一个基typeclassQ是与no pure交互的一个重要媒介。一般情况下Monad有两U,一U是数据wrapperQ一U是action的wrapper。上面定义的Maybe Monad和list Monad都是数据cd的wrapperQ它们实CMonad定义的接口函敎ͼ我们q可以将其它data instance成MonadQ只需要遵循了Monad的接口即可?/p>


我们知道Haskell的函数都是pure的,没有M状态的函数Q但是与现实世界交互必然需要媄(jing)响或修改某种状态,q且?x)需要顺序执行某些操作以完成交互。我们把action操作装在一个data里面Qƈ让它instance MonadQؓ(f)了让前一个action的结果g为某U状态往下传递,Monad?>>=)是Zq个目的而存在的Q?>>=) 函数的类型是 m a -> (a -> m b) -> m bQ它的意思就是执行封装在m aq个数据里面的actionQ然后把q个action的结果值做为参C递给(>>=)的第二个参数(a -> m b)Q第二个参数是一个函敎ͼq函数可以取用第一个参数的l果Q再q回一个m b的数据,m b的数据也是一个action的封装,q样当一q串?>>=)攑ֈ一L(fng)时候,可以把一个状态g为action的参数和l果值往下传递?/p>


从Monad的函?>>)的实现我们可以看刎ͼ它把m a的action的结果g弃直接返回了m bQ当一q串?>>)攑ֈ一L(fng)时候,其实是让一laction序执行。通过(>>=)?>>)Q可以把一lMonad action datal合h?/p>


IO Monad


IO Monad是一个把IO action装的dataQ我们可以用IO Monad与外界进行输入输Z互,下面是一?hello world"Q?/p>


helloWorld = do
     putStr "hello "
     putStrLn "world"


q里do语法p其实就是用的Monad来实玎ͼ展开之后是这P(x)


helloWorld =
     (putStr "hello ") >>
     (putStrLn "world")


?>>)函数定(putStr "hello ")?putStrLn "world")需要是同一个MonadcdQ我们可以查询到putStr和putStrLn的类型是String -> IO ()Q那?putStr "hello ")?putStrLn "world")的类型都是IO ()QhelloWorld函数把两个IO ()的action数据序l合h生成一个新的IO ()Q当q个helloWorld IO action被执行的时候,它会(x)依次执行装在它里面的IO action。我们可以把helloWorld IO action攑ֈMain函数里面然后~译执行Q也可以直接在ghci里面执行?/p>


我们可以自己定义某种data再instance MonadQ这样可以构成一ldata combinationQ可以实CQ意的action combine。我山寨的极的parse combinator的数据类型定义如下:(x)


newtype Parser a = Parser {
     runP :: State (ByteString, Context) a
} deriving (Monad, MonadState (ByteString, Context))


q里Parser带一个类型参数aQderiving (Monad, MonadState (ByteString, Context))表示~译器自动instance Monad和instance MonadState (ByteString, Context)。有了这个Parser之后Q可以写出简单的几个combinatorQ然后用这几个combinatorl合成更加复杂的Q组合的q程是利用了Monad的组合能力。当所需的combinator都实C好了之后Q可以最l实C个Parser a来分析整个C++文gQ?/p>


file = repeatP $ spaceLine <||> normalLine


file把分析整个C++文g所需的操作都combineC一P有了q个分析整个文g的Parser a之后Q需要把它跑hQ那需要定义下面这个函敎ͼ(x)


runParse :: Parser a -> ByteString -> (a, (ByteString, Context))
runParse p b = runState (runP p) $ (b, emptyContext)


q个函数接受一个Parser a和一个文件内容ByteString作ؓ(f)参数Q把整个Parser a装的action用于分析文g内容Q再产生一个分析结果?/p>


q里的fileQ它是一个一个小的combinator构成的,每个combinator是一个action加上它所需数据构成一?#8220;闭包”再存攑ֈParser a的data里面Q其实可以认为实CMonad的数据类型是一?#8220;闭包”的蝲体。在其它语言里,我们可以使用闭包来实现combinatorQ我记得两年半前Q我使用lua的闭包实C一l游戏副本内容玩法操作的combinatorQ这些闭包自q合在一起之后就能完成一个副本中所需的玩法操作?/p>


Monad transformer


一UMonadcd只能装和组合一Uaction操作Q而与外界交互的时候,很多时候一UMonadcd是不够的Qؓ(f)了让多种Monadcdl合在一P需要定义Monad transformerQ它跟Monad一样也是一个数据类型,不同的是它接受至两U类型参敎ͼ其中一U就是Monad的类型,q样可以把某个Monadcd嵌套在它里面?/p>


newtype StateT s m a = StateT {
     runStateT :: s -> m (a, s)
}


q里StateT是一个Monad transformerQ它允许嵌套一个Monad mcdQ它是typeclass MonadState的一个instanceQMonadState如下Q?/p>


class Monad m => MonadState s m | m -> s where
     get :: m s
     put :: s -> m ()


Z让Monad transformer可以嵌套qStateTQ其它类型的Monad transformer需要instance MonadStateQ而StateT Monad transformerZ可以嵌套在其它Monad transformer中,需要对其它Monad transformer抽象出来的typeclass instanceQ符合这U规则的Monad transformer可以相互之间嵌套了Q嵌套的层次可以L深,q样构造出来的Monad里面有个Monad transformer stackQ而这个新构造出来的Monad可以用多UMonad的action操作l合在一起了?/p>


Monad transformer?x)带来一个问题,如果惛_义一个新的Monad transformerQ需要先抽象个Monad transformer的typeclassQ就像MonadState typeclass一P然后把其它Monad transformer都instanceq个新抽象出来的typeclassQ这h能让q个新的Monad transformer嵌套在其它的Monad transformer之中Q接着Qؓ(f)了让其它Monad transformer能够嵌套在新的Monad transformer之中Q需要把新的Monad transformer instance其它Monad transformer抽象的typeclass?/p>


我觉得其实HaskellZ么会(x)有Monad和Monad transformer的存在,是因为Haskell是一个纯函数式语aQ它本n没有序执行语句的能力,Z能让Haskell拥有修改外部状态ƈ能够序执行语句的能力,引入了MonadQ又Z让多Uaction的Monad能够l合CP׃Monad是一个data typeQ它不能单的l合CP因ؓ(f)cd不一_(d)Z让它们组合到一P又引入了更一般化的Monad transformerQ让q些Monad transformer嵌套在一h成一个stackQ才能将q些不同cd的Monadl合?/p>


Lazy evaluation


Haskell里面使用的是惰性求值方式,王垠?a >Haskell的惰性求?/a>是一个很严重的问题。我目前也觉得惰性求值是一U负担,因ؓ(f)惰性求|?x)得程序很?gu)出现space leakQ我写的那两个版本的l计C++代码行工具都有这个问题,因ؓ(f)它是惰性求|所以它?x)把整个目录的数据全部取出来构造存攑ֈ内存中,最后再q行求|q就自然Dl计大量C++代码文g的目录时Q占用内存会(x)很高Q几百M上GQ,也许当我q一步学?fn)之后,我能够避免这Uspace leakQ但q对于一个初学Haskell的h是一个不的负担Q因为随便写一个小E序都有可能耗用几百M的内存,而用其他语言实现的话Q内存很Ҏ(gu)很自然的控制在几M之内。(看完优化章节Q只对程序修改了几行代码p内存使用降到可以接受的程度,看来Lazy evaluation的问题没之前惛_的那么严重。)(j)



airtrack 2013-04-30 20:41 发表评论
]]>字符~码http://www.shnenglu.com/airtrack/archive/2012/12/23/196540.htmlairtrackairtrackSun, 23 Dec 2012 05:44:00 GMThttp://www.shnenglu.com/airtrack/archive/2012/12/23/196540.htmlhttp://www.shnenglu.com/airtrack/comments/196540.htmlhttp://www.shnenglu.com/airtrack/archive/2012/12/23/196540.html#Feedback0http://www.shnenglu.com/airtrack/comments/commentRss/196540.htmlhttp://www.shnenglu.com/airtrack/services/trackbacks/196540.html阅读全文

airtrack 2012-12-23 13:44 发表评论
]]>
˾þ| 鶹AV뾫Ʒþ| ھƷ˾þþþվ| 91þۺ| þۺ77777鶹| þоƷ| 99þþƷһ| ҹŷƷþþþþþ| ˾Ʒþö| þþƷŮAV| þŮcc98cm| aaaƷþþùƬ| þþþAV| ڸþþþþ| þþƷһպ| þӰ| Ʒþþþþþþ| þav뾫Ʒ˳| ޾Ʒþþþþ| ʵҶ԰׾ʾþ| ƷŮٸAVѾþ | þþWWW˳ɾƷ| 99Ʒ99þþþþ97| XxŷʸƷþþþþ| 97Ʒ˾þþô߽| 99þùۺϾƷԭ| ھƷžžþþƷ| þþƷAɫ| þۺ㽶AV| þþþ޾Ʒ˵| þþþþþAv| ޾Ʒ˾þþ| 999Ʒþþþþ| þþƷ˳| þþžžþƷֱ| ƷŮͬһþ| þþƷavպ| þþŷղAV| þùӰԺ| ŷ þ| þþƷ鶹|