锘??xml version="1.0" encoding="utf-8" standalone="yes"?>免费欧美视频,99精品国产在热久久婷婷,欧美性色综合http://www.shnenglu.com/airtrack/<a ><font color="White">涓漢鐙珛鍗氬</font></a> <a ><font color="White">寰崥@airtrack</font></a>zh-cnWed, 24 Sep 2025 21:07:20 GMTWed, 24 Sep 2025 21:07:20 GMT60鎿嶄綔緋葷粺瀹炵幇錛堜笁錛夛細(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>鎻愬埌褰撹闂殑欏佃〃鍜岄〉涓嶅湪鍐呭瓨?shù)腑鏃朵細(xì)瑙﹀?Page Fault 寮傚父錛屾搷浣滅郴緇熼渶瑕佸湪寮傚父澶勭悊鍑芥暟涓垎閰嶅唴瀛橀〉騫惰緗ソ鐩稿簲鐨勫垎欏佃〃欏廣傚紓甯告槸涓縐嶄腑鏂被鍨嬶紝娉ㄥ唽寮傚父澶勭悊鍑芥暟灝辨槸娉ㄥ唽涓柇澶勭悊鍑芥暟錛屼腑鏂鐞嗗嚱鏁版敞鍐屽湪涓涓彨 IDT(Interrupt Descriptor Table) 鐨勫湴鏂廣?/div>

IDT

涓柇澶勭悊鍑芥暟鍦ㄥ疄妯″紡涓嬫敞鍐屽湪 IVT(Interrput Vector Table) 涓紝鍦ㄤ繚鎶ゆā寮忎笅娉ㄥ唽鍦?IDT(Interrupt Descriptor Table) 銆侷DT鏄寘鍚?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 錛宼ype_attr 鐨勭粨鏋勫涓嬶細(xì)
      7                           0
    +---+---+---+---+---+---+---+---+
    | P |  DPL  | S |    GateType   |
    +---+---+---+---+---+---+---+---+
P琛ㄧず鏄惁瀛樺湪錛孌PL 琛ㄧず鎻忚堪絎︾殑鏈浣庤皟鐢ㄦ潈闄愶紝GateType 瀹氫箟浜?jiǎn)涓柇绫诲瀷锛?2 浣嶇殑涓柇綾誨瀷鍒嗗埆鏄細(xì)
Interrupt Gate 鍜?Trap Gate 鐩鎬技錛屽尯鍒湪鍓嶈呮墽琛屼腑鏂鐞嗗嚱鏁板墠鍚庝細(xì)鑷姩鍏抽棴鍜屽紑鍚腑鏂?/div>
鍑嗗濂?IDT 錛岃緗ソ IDTR 瀵勫瓨鍣ㄥ氨鎶?IDT 閮借緗ソ浜?jiǎn)銆侷DTR 瀵勫瓨鍣ㄧ粨鏋勫涓嬶細(xì)
    struct idtr
    {
        uint16_t limit;
        struct idt_entry *base;
    };
limit 鏄暣涓〃鐨勫ぇ灝?-1 瀛楄妭錛宐ase 鎸囧悜 IDT 琛紝璁劇疆 IDTR 瀵勫瓨鍣ㄧ殑鎸囦護(hù)鏄?lidt銆?/div>

寮傚父鍜岀‖浠朵腑鏂?/h2>
浜?jiǎn)瑙?IDT 鐨勭粨鏋勪簡(jiǎn)涔嬪悗錛屾垜浠彲浠ヨ緗紓甯稿拰紜歡涓柇鐨?ISR(Interrupt Service Routine)銆傚浜庡紓甯革紝鎴戜滑鍙鐭ラ亾鏈夊摢浜涘紓甯鎬細(xì)瑙﹀彂錛岃Е鍙戠殑閫昏緫鏄粈涔堟牱錛屽疄鐜板悎閫傜殑寮傚父澶勭悊鍑芥暟鍗沖彲錛堣繖閲屾槸寮傚父鍒楄〃錛夈傚浜庣‖浠朵腑鏂紝闇瑕侀氳繃涓涓‖浠跺畬鎴?#8212;— PIC(Programmable Interrupt Controller)銆?/div>
PIC 鍒嗕負(fù) Master 鍜?Slave 錛屾瘡涓?PIC 閮芥湁涓涓懡浠ょ鍙ｅ拰涓涓暟鎹鍙ｏ紝閫氳繃榪欎袱涓鍙ｅ彲浠ヨ鍐?PIC 鐨勫瘎瀛樺櫒銆傛瘡涓?PIC 閮藉彲榪?8 涓緭鍏ヨ澶囷紝x86涓?Slave 闇瑕侀氳繃 line 2 榪炴帴鍒?Master 涓婃墠鑳藉搷搴旇緭鍏ヨ澶囷紝榪炴帴鐨勮緭鍏ヨ澶囨湁涓柇璇鋒眰鐨勬椂鍊欎細(xì)浜х敓 IRQ(Interrupt Request)錛孧aster 浜х敓 IRQ 0 ~ IRQ 7錛孲lave 浜х敓 IRQ 8 ~ IRQ 15銆備繚鎶ゆā寮忎笅鍙互璁懼畾 PIC 浜х敓鐨勪腑鏂搴旂殑 ISR 鎵鍦?IDT 涓殑 offset錛岄氬父璁劇疆涓轟粠 0x20 寮濮嬶紝鍒?0x2F 緇撴潫錛?x0 鍒?0x1F 琚紓甯稿崰鐢級(jí)銆?/div>
PIC 鐨勭鍙ｅ彿濡備笅琛細(xì)

PIC 浜х敓鐨勬爣鍑?IRQ 濡備笅琛細(xì)

PIC 鍒濆鍖栫殑鏃跺欙紝瑕佽緗?Master 鍜?Slave 閫氳繃 line 2 鐩歌繛錛屽悓鏃惰緗ソ IRQ 瀵瑰簲鐨?ISR 鍦?IDT 涓殑璧峰涓柇鍙楓侾IC 鎻愪緵涓涓?IMR(Interrupt Mask Register) 瀵勫瓨鍣ㄦ潵鏍囪瘑涓柇鏄惁灞忚斀錛岃緗?bit 浣嶄細(xì)灞忚斀瀵瑰簲鐨?IRQ銆傚綋 IMR 鏈緗紝騫朵笖 CPU 鐨勪腑鏂墦寮錛屽鏋滄湁璁懼涓柇璇鋒眰鍙戠敓錛岄偅涔?ISR 灝嗕細(xì)鎵ц銆侷SR 鎵ц瀹屾瘯涔嬪悗瑕侀氱煡 PIC 涓柇澶勭悊瀹屾垚錛岄渶瑕佸悜 PIC 鐨勫懡浠ょ鍙ｅ啓鍏ヤ竴涓?EOI(End Of Interrupt) 鍛戒護(hù)(0x20)錛屼腑鏂姹傚鏋滄潵鑷?Slave錛岄偅涔堥渶瑕佸厛寰(xiàn) Slave 鍛戒護(hù)绔彛鍐欏叆 EOI錛屽啀鍚?Master 鍛戒護(hù)绔彛鍐欏叆 EOI銆?/div>

Spurious IRQs

鐢變簬 CPU 涓?PIC 涔嬮棿鐨?a >绔炰簤鏉′歡鍙兘浼?xì)漶旂?IRQ 7錛圡aster 浜х敓錛?鍜?IRQ 15錛圫lave 浜х敓錛?鐨?Spurious IRQs銆備負(fù)浜?jiǎn)澶勭悊杩櫩U嶆儏鍐碉紝鎴戜滑瑕佺煡閬撲粈涔堟椂鍊欐槸鏃犳晥鐨?IRQ錛岄氳繃鍒ゆ柇 IRR(Interrupt Request Register) 瀵勫瓨鍣ㄧ殑鍊煎彲浠ヨ幏鐭ュ摢浜?IRQ 鍙戠敓浜?jiǎn)锛寴q欎釜瀵勫瓨鍣ㄧ殑姣忎釜 bit 琛ㄧず鐩稿簲鐨?IRQ 鏄惁鍙戠敓銆傚湪 IRQ 7 鍜?IRQ 15 鐨?ISR 涓厛璇誨彇 IRR錛岀劧鍚庡垽鏂搴旂殑 bit 浣嶆槸鍚﹁璁劇疆錛屽鏋滄病鏈夎緗紝閭ｄ箞琛ㄧず褰撳墠鏄竴涓?Spurious IRQ錛屼笉闇瑕佸鐞嗭紝涔熶笉闇瑕佸啓鍏?EOI錛岀洿鎺ヨ繑鍥炲嵆鍙紙濡傛灉鏄?Slave PIC 浜х敓鐨勶紝闇瑕佸線(xiàn) Master PIC 鍐欏叆 EOI錛岀敱浜?Master 涓嶇煡閬?Slave 浜х敓鐨?IRQ 鏄笉鏄?Spurious 鐨勶級(jí)銆?/div>

PIT

鐜頒唬鎿嶄綔緋葷粺閮芥湁鎶㈠崰寮忓浠誨姟鑳藉姏錛岄氬父鏄氳繃璁劇疆涓涓‖浠?Timer錛屼竴涓繘紼嬬殑鎵ц鏃墮棿鍒頒簡(jiǎn)涔嬪悗鍒囨崲鎴愬彟涓涓繘紼嬫墽琛岋紝榪欎釜紜歡 Timer 鏄?PIT(Programmable Interval Timer)銆侾IT 鏈夊涓?channel 鍜屽縐嶅伐浣?mode錛屽叾涓?channel 0 榪炴帴鍒?PIC 浼?xì)漶旂?IRQ 0錛宮ode 2 鍜?mode 3 鏄父鐢ㄧ殑宸ヤ綔妯″紡銆傛搷浣滅郴緇熷垵濮嬪寲鐨勬椂鍊欒緗ソ PIT錛屽悓鏃惰緗ソ PIT 浜х敓鐨?IRQ 0 鐨?ISR錛屽湪榪欎釜 ISR 涓搷浣滅郴緇熷氨鍙互鎵ц澶氫換鍔＄殑璋冨害銆?/div>

涓柇澶勭悊緇撴潫

IDT 涓緗殑 ISR 榪斿洖鏃朵笉鑳戒嬌鐢ㄦ櫘閫氱殑鍑芥暟榪斿洖鎸囦護(hù) ret錛岄渶瑕佷嬌鐢ㄤ竴鏉＄壒孌婄殑榪斿洖鎸囦護(hù) iret銆傚湪浜?jiǎn)瑙ｄ簡(jiǎn)杩欎簺涔嬪悗锛屾垜浠湁浜?jiǎn)鍝嶅簲澶栭儴璁懼鐨勮兘鍔涳紝鍙互鎺ュ叆澶栭儴杈撳叆璁懼浜?jiǎn)锛屼笅涓姝ユ帴鍏ラ敭鐩樸?/div>

airtrack 2015-05-05 10:03 鍙戣〃璇勮
]]>鎿嶄綔緋葷粺瀹炵幇錛堜簩錛夛細(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 寮濮嬪埌鍐呮牳杞藉叆浣跨敤鐨勯兘鏄鉤鍧﹀唴瀛橈紝鍗蟲(chóng)墍鏈夊湴鍧瀵瑰簲瀹為檯鐨勭墿鐞嗗湴鍧銆傜幇浠ｆ搷浣滅郴緇熼兘浣跨敤鍒嗛〉鏉ョ鐞嗗唴瀛橈紝鍒嗛〉鍙互璁╂瘡涓繘紼嬮兘鏈夊畬鏁寸殑铏氭嫙鍦板潃絀洪棿錛岃繘紼嬮棿鐨勮櫄鎷熷湴鍧絀洪棿鐩鎬簰闅旂浠ユ彁渚涢〉灞傜駭鐨勪繚鎶ゃ傚彟澶栧垎欏靛彲浠ヨ鐗╃悊鍐呭瓨灝戜簬铏氭嫙鍦板潃絀洪棿錛屽悓鏃跺彲浠ヤ嬌鐢ㄧ鐩樺瓨鍌ㄦ殏鏃舵湭浣跨敤鐨勫唴瀛橀〉錛屾彁渚涙洿澶氱殑銆屽唴瀛樸嶃?/div><div></div><h2>鍒嗛〉</h2><div></div><div>鍒嗛〉閫氳繃 CPU 鐨?MMU(Memory Management Unit) 瀹屾垚錛孧MU 閫氳繃褰撳墠鐨勫垎欏佃〃瀹屾垚铏氭嫙鍦板潃鍒扮墿鐞嗗湴鍧鐨勮漿鎹€傚湪 x86 涓?MMU 閫氳繃涓ょ駭鍒嗛〉琛紙涔熷彲浠ュ紑鍚笁綰э級(jí)瀹屾垚鍦板潃杞崲錛岃繖涓ょ駭鍒嗗埆鏄〉鐩綍(Page Directory)鍜岄〉琛?Page Table)銆傚湪 x86 涓嬶紝鐢?cr3 瀵勫瓨鍣ㄥ瓨鍌ㄩ〉鐩綍鐨勫湴鍧錛堢墿鐞嗗湴鍧錛夛紝欏電洰褰曞拰欏佃〃閮藉寘鍚?1024 欏癸紝姣忛」 4 瀛楄妭錛屽洜姝ら〉鐩綍鍜岄〉琛ㄥぇ灝忎負(fù) 4KB 錛屾寜鐓?4KB 涓欏電殑璇濓紝鍒氬ソ鍗犵敤涓欏點(diǎn)?/div><div></div><div>MMU 灝嗚櫄鎷熷湴鍧杞崲鎴愮墿鐞嗗湴鍧鐨勬柟寮忔槸錛屽彇铏氭嫙鍦板潃鐨?22~31bits 琛ㄧず欏電洰褰曠殑涓嬫爣錛岃幏寰楅〉鐩綍欏瑰畾浣嶅埌欏佃〃錛屽啀鍙?12~21bits 琛ㄧず欏佃〃鐨勪笅鏍囷紝鑾峰緱欏佃〃欏瑰畾浣嶅埌欏碉紝鏈鍚庡彇 0~11bits 琛ㄧず欏靛亸縐匯傞〉鐩綍欏瑰拰欏佃〃欏圭殑涓嬫爣鍒嗗埆鐢?10bits 琛ㄧず錛屽垰濂芥渶澶?1024 欏癸紝欏靛唴鍋忕Щ鐢?12bits 琛ㄧず錛屽垰濂?4KB銆?/div><div></div><div>欏電洰褰曢」緇撴瀯濡備笅錛?/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 榪樻槸 4MB錛孭 琛ㄧず欏佃〃鏄惁鍦ㄥ唴瀛樹(shù)腑錛屽鏋滃湪鍐呭瓨?shù)腑锛岄偅涔?12锝?1 bits 瀛樺偍浜?4KB 瀵歸綈鐨勯〉琛ㄥ湴鍧錛堝悓鏍鋒槸鐗╃悊鍦板潃錛夛紝鍏跺畠 bit 鐨勫惈涔夎鍙傝?a >榪欓噷</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 琛ㄧず姝ら〉鏄惁鍦ㄥ唴瀛樹(shù)腑錛屽鏋滃湪鍐呭瓨?shù)腑锛?2~31 bits 瀛樺偍浜?jiǎn)椤电殑鍦板潃銆?/div><div></div><div>鎴戜滑鐭ラ亾浜?jiǎn)椤电洰褰曞拰椤佃〃鐨劸l撴瀯錛屽噯澶囧ソ欏電洰褰曞拰欏佃〃錛屽氨鍙互寮鍚垎欏典簡(jiǎn)錛屽紑鍚垎欏靛彧闇鎶婇〉鐩綍鍦板潃鏀懼埌 cr3 瀵勫瓨鍣ㄤ腑錛屽茍鎶?cr0 鐨勬渶楂?bit 緗?1銆傞氳繃欏電洰褰曢」錛屾垜浠彲浠ュ彂鐜伴〉琛ㄤ笉闇瑕侀兘瀛樺湪鍐呭瓨褰撲腑錛屽綋璁塊棶涓涓櫄鎷熷湴鍧錛屽畠瀵瑰簲鐨勯〉琛ㄦ垨鑰呴〉涓嶅瓨鍦ㄥ唴瀛樹(shù)腑鏃朵細(xì)瑙﹀彂 <a >Page Fault</a> 寮傚父錛屾垜浠彲浠ュ湪寮傚父澶勭悊鍑芥暟涓畬鎴愰〉琛ㄦ垨鑰呴〉鐨勫垎閰嶏紝鐞嗚涓婂紑鍚垎欏靛彧闇瑕佸噯澶囧ソ欏電洰褰曘?/div><div></div><h2>鍒嗛〉鍓嶅悗</h2><div></div><div>鍑嗗濂介〉鐩綍欏佃〃錛岃緗?cr3 鍜?cr0錛屽紑鍚簡(jiǎn)鍒嗛〉涔嬪悗錛屽唴鏍哥殑鎵鏈夊湴鍧閮藉彉鎴愪簡(jiǎn)铏氭嫙鍦板潃錛屾墍鏈夌殑鍦板潃閮借閫氳繃 MMU 鏄犲皠鍒扮墿鐞嗗湴鍧鍐嶈闂唴瀛樸傝繖涓鍙樺寲鏄渶瑕佸皬蹇?jī)娉ㄦ剰鐨勫Q屽紑鍚垎欏靛墠錛岃闂殑鎵鏈夊湴鍧鏄墿鐞嗗湴鍧錛屽紑鍚垎欏典箣鍚庯紝鎵鏈夌殑鍦板潃閮藉彉鎴愪簡(jiǎn)铏氭嫙鍦板潃錛屽洜姝わ紝濡傛灉鍒嗛〉鐢卞唴鏍告潵瀹屾垚錛岄偅涔堝唴鏍稿氨闇瑕佽冭檻鍒板墠鍚庣殑鍙樺寲錛屽嵆鏈変竴閮ㄥ垎浠ｇ爜榪愯鍦ㄧ墿鐞嗗湴鍧涓嬶紝鍏跺畠浠ｇ爜閮借繍琛屽湪铏氭嫙鍦板潃涓嬶紱濡傛灉鍒嗛〉鐢?Bootloader 瀹屾垚錛岄偅涔?Bootloader 闇瑕佹敞鎰忚繖涓彉鍖栵紝騫舵紜煩杞埌鍐呮牳錛岃鍐呮牳瀹屾暣榪愯鍦ㄨ櫄鎷熷湴鍧涓嬨?/div><div></div><div><a >涓婁竴綃?/a>鎴戞妸鍐呮牳灞曞紑鍒頒粠 0x100000 寮濮嬬殑鐗╃悊鍐呭瓨?shù)腑锛尵~栬瘧閾炬帴鍐呮牳鐨勬椂鍊欎篃鎶婁唬鐮佹鐨勫湴鍧鎸囧畾鍒?0x100000 鐨勫湴鍧銆傚紑鍚垎欏典箣鍚庯紝鍐呮牳涓鑸繍琛屽湪楂樺湴鍧錛堟瘮濡?Linux 鍐呮牳鍦板潃浠?0x80000000 寮濮嬶紝W(xué)indows 浠?0xC0000000 寮濮嬶級(jí)錛岃屽唴鏍稿悓鏍鋒槸灞曞紑鍒頒粠 0x100000 寮濮嬬殑鐗╃悊鍐呭瓨?shù)腑銆傛垜閫夋嫨鎶婂唴鏍哥殑铏氭嫙鍦板潃閾炬帴鍒頒粠 0xC0100000 寮濮嬶紝騫舵妸榪欎釜铏氭嫙鍦板潃鏄犲皠鍒?0x100000 鐨勭墿鐞嗗湴鍧錛屽紑鍚垎欏典箣鍓嶈繍琛岀殑浠ｇ爜錛屽嚒鏄秹鍙?qiáng)鍒板湴鍧鐨勬搷浣滐紝鎴戦兘浼?xì)鎶婅櫄鎷熷湴鍧璋冩暣涓虹墿鐞嗗湴鍧鍐嶆搷浣滐紝寮鍚垎欏典箣鍚庯紝鎵鏈夎櫄鎷熷湴鍧灝卞彲浠ユ甯歌繍琛屼簡(jiǎn)銆?/div><div></div><h2>鐗╃悊鍐呭瓨綆＄悊</h2><div></div><div>鎿嶄綔緋葷粺閲囩敤鍒嗛〉鏂瑰紡綆＄悊鍐呭瓨錛屽洜姝ょ墿鐞嗗唴瀛樼殑綆＄悊涔熼渶鎸夌収欏電殑鏂瑰紡綆＄悊錛屽湪 Page Fault 寮傚父瑙﹀彂鏃訛紝鍦ㄥ紓甯稿鐞嗗嚱鏁頒腑鍒嗛厤鏂扮殑鐗╃悊欏靛茍鎶婂畠鏄犲皠鍒板垎欏佃〃涓傝繖閲岀壍娑夊埌絀洪棽鐗╃悊鍐呭瓨欏電殑鍒嗛厤鍜岄噴鏀撅紝鎴戜滑寰堝鏄撴兂鍒頒竴縐嶇洿瑙傜殑鏂規(guī)硶錛屾妸鎵鏈夌┖闂插唴瀛橀〉鐢ㄩ摼琛ㄤ覆鑱旇搗鏉ワ紝鍒嗛厤閲婃斁涓欏靛彧闇瀵歸摼琛ㄨ繘琛屾搷浣溿傝繖縐嶆柟寮忕鐞嗗榪涚▼鐨勭墿鐞嗛〉鍒嗛厤綆鍗曟湁鏁堬紝浣嗘槸瀵瑰唴鏍告湰韜嬌鐢ㄧ殑鍐呭瓨鍒嗛厤閲婃斁浼?xì)瀵艰嚧鍐呭瓨鍒╃敤鐜囦笉楂樺Q屽洜涓鴻繖縐嶆柟寮忕鐞嗙殑鏈澶ц繛緇唴瀛樻槸涓欏碉紝鑰屽唴鏍鎬腑緇忓父浼?xì)鍒嗛厤澶у璞″Q岃繛緇欏電殑鐗╃悊鍐呭瓨鏈夋洿濂界殑鍒╃敤鐜囥侺inux 閲囩敤 <a >Buddy memory allocation</a> 鏂瑰紡綆＄悊鐗╃悊鍐呭瓨錛屼嬌鐢?Slab/Slub 綆＄悊鍐呮牳瀵硅薄鐨勫垎閰嶉噴鏀俱?/div><div></div><div>鎴戠殑瀹炵幇涔熼噰鐢?Buddy 鏂瑰紡綆＄悊鐗╃悊鍐呭瓨錛屾妸絀洪棽鍐呭瓨欏電敤澶氬眰綰х殑 Buddy 鏂瑰紡綆＄悊錛屽垎鍒槸 order 0 ~ order 10錛岃〃紺?2^order 欏佃繛緇唴瀛橀〉鍧楋紝鍗?order 0 綆＄悊鍗曢〉鐨勭┖闂插唴瀛樺潡錛宱rder 10 綆＄悊榪炵畫(huà) 1024 欏電殑絀洪棽鍐呭瓨鍧椼傚垎閰嶅唴瀛樻椂錛岀畻鍑烘渶浣崇殑 order錛屽湪鐩稿簲鐨?order 灞傜駭閲屽垎閰嶄竴鍧楀唴瀛樺潡錛屽鏋滃綋鍓?order 涓病鏈夊彲鐢ㄧ殑絀洪棽鍐呭瓨鍧楋紝灝卞悜 order + 1 灞傜駭涓熶竴鍧楋紝騫舵妸鍊熸潵鐨勭┖闂插唴瀛樺潡騫沖垎鎴?2 鍧?order 灞傜駭鐨勭┖闂插唴瀛樺潡錛屽叾涓竴鍧楀綋浣滃垎閰嶇粨鏋滆繑鍥烇紝鍙︿竴鍧楁斁鍏ュ埌 order 灞傜駭涓緟浠ュ悗鍒嗛厤浣跨敤銆傚綋絎?order 鍧楃殑鍐呭瓨?shù)娇鐢ㄥ畬閲婃斁鏃跺Q屾妸榪欏潡閲婃斁鐨勫唴瀛樺潡鏀懼叆 order 灞傜駭鏃訛紝鍒ゆ柇涓庡畠鐩歌繛鐨勫悓鏍峰ぇ灝忕殑鍐呭瓨鍧楁槸鍚﹀湪 order 灞傜駭涓紝濡傛灉瀛樺湪錛屾妸瀹冨拰瀹冪殑 Buddy 鍚堝茍鎴愪竴涓?order + 1 鐨勫唴瀛樺潡鏀懼叆鍒?order + 1鐨勫眰綰т腑銆?/div><div></div><h2>鍐呭瓨綆＄悊鍣ㄥ垵濮嬪寲涔嬪墠</h2><div></div><div>鍦ㄥ唴瀛樼鐞嗗垵濮嬪寲涔嬪墠錛屽唴鏍告病鏈夊姩鎬佸唴瀛樺垎閰嶈兘鍔涳紝鍥犳寰堝鏃跺欐垜浠渶瑕佷嬌鐢ㄩ潤(rùn)鎬佸叏灞鍙橀噺銆傚唴瀛樼鐞嗗櫒鍒濆鍖栨椂錛屽彲鑳戒細(xì)浣跨敤鍒板姩鎬佸唴瀛樺垎閰嶏紝榪欏氨鍑虹幇楦′笌铔嬬殑闂錛屼負(fù)浜?jiǎn)瑙ｅ唽櫩欎釜闂锛岄氬父浼?xì)瀹炵庮C竴涓畝鍗曠殑 Boot Allocator 鐢ㄥ湪鍐呭瓨綆＄悊鍣ㄥ垵濮嬪寲涔嬪墠鍒嗛厤鍔ㄦ佸唴瀛樸傛垜鐨勫疄鐜版槸浠庡唴鏍稿睍寮鐨勬湯灝句綅緗紑濮嬪緩绔嬩竴涓彧鍒嗛厤涓嶉噴鏀劇殑 Boot Allocator錛岀瓑鍒板唴瀛樼鐞嗗櫒鍒濆鍖栧畬鎴愪箣鍚庯紝Boot Allocator 鐨勪嬌鍛戒究瀹屾垚浜?jiǎn)銆?/div><div></div><div>鍙﹀榪樻湁涓涓棶棰橈紝鎴戜滑綆＄悊鐗╃悊鍐呭瓨錛岄渶瑕佺煡閬撳畨瑁呬簡(jiǎn)澶氬皯鐗╃悊鍐呭瓨錛屽洜姝ゆ垜浠鎺㈡祴瀹夎浜?jiǎn)澶殲畱鐗╃悊鍐呭瓨锛?a >榪欓噷</a>浠嬬粛浜?jiǎn)鍑牽U嶆帰嫻嬫柟娉曪紝鎴戜嬌鐢ㄧ殑鏄?BIOS 鐨?INT 0x15, EAX = 0xE820 鍑芥暟錛屽畠鐢?Bootloader 璋冪敤瀹屾垚錛屾渶鍚庨氳繃鍙傛暟鎶婂畠浼犻掔粰鎿嶄綔緋葷粺鍐呮牳銆?/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>鐢≧ust鍐欎簡(jiǎn)涓涓猅unnelhttp://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.html2014騫寸殑鏈鍚庝竴涓槦鏈熺敤Rust鍐欎簡(jiǎn)涓涓猅unnel錛屼唬鐮佹斁鍦?a >GitHub涓娿備富瑕佸師鍥犳槸VPN鍦?2鏈堝紑濮嬫瀬涓嶇ǔ瀹氾紝鍏舵鏄疺PN鐢ㄨ搗鏉ヤ笉鐖斤紝姣忔涓嬩笢瑗塊兘瑕佸叧VPN錛岃岀敤ssh -D鏃跺伓灝?dāng)鍙堜細(xì)鏂紑錛屾渶鍚庡共鑴嗚嚜宸卞啓涓涓紙鍏跺疄騫村垵灝辨兂鍐欙紝鍥犱負(fù)涔頒簡(jiǎn)VPN灝變笉鎯蟲(chóng)姌鑵句簡(jiǎn)錛夈?/div>

緙栬瘧鍜屼嬌鐢?/h3>
鐜頒唬璇█涓鑸兘鑷甫緙栬瘧宸ュ叿錛屼笉鐢ㄦ姌鑵緈ake cmake絳変笢瑗匡紝Rust瀹樻柟鎻愪緵浜?a >Cargo錛屾墍浠ョ紪璇戝緢綆鍗曪紝瀹夎濂紺argo錛岀劧鍚庡埌婧愮爜鐩綍涓婥argo build灝卞畬鎴愪簡(jiǎn)銆?br />
緙栬瘧瀹屾垚寰楀埌涓や釜鍙墽琛屾枃浠訛紝鍒嗗埆鏄細(xì)client, server錛宻erver鍚姩鍦ㄦ湇鍔″櫒涓婏紝client鍚姩鍦ㄦ湰鏈哄茍緇戝畾鍒板湴鍧127.0.0.1:1080錛屾祻瑙堝櫒鐢變唬鐞嗘彃浠墮氳繃SOCKS v5鍗忚榪炴帴榪欎釜鍦板潃鍗沖彲銆?

Tunnel閫昏緫緇撴瀯

涓嬮潰鏄昏緫鍥撅細(xì)
Client鍜孲erver涔嬮棿閫氳繃涓鏉CP閾炬帴鐩歌繛錛屽鎴風(fēng)姣忔敹鍒頒竴涓猅CP璇鋒眰灝卞紑涓涓猵ort澶勭悊錛屽悓鏃跺湪Server涓婃湁涓涓猵ort涓庝箣瀵瑰簲錛岃繖鏍峰氨鍦–lient鍜孲erver涔嬮棿寤虹珛浜?jiǎn)涓涓細(xì)璇濆眰錛岃繖涓猅CP閾炬帴鐨勬暟鎹叏閮ㄩ兘鍦ㄥ搴旂殑port閲屼紶杈撱?br />
Tunnel鏈韓璺烻OCKS v5涓嶇浉鍏籌紝涓轟簡(jiǎn)璁╂祻瑙堝櫒浠ｇ悊鑳借繛涓婏紝Client鎻愪緵浜?jiǎn)SOCKS v5涓渶綆鍗曠殑NO AUTHENTICATION TCP鏂規(guī)硶錛屽嵆鏃犵敤鎴峰悕鍜屽瘑鐮佺殑TCP浠ｇ悊銆?br />
Client鍜孲erver涔嬮棿浼犺緭鐨勬暟鎹兘鍔犱簡(jiǎn)瀵嗭紝鍔犲瘑綆楁硶鏄疊lowfish錛屽伐浣滄ā寮忔槸Counter Mode錛宑lient鍜宻erver鍚姩鏃剁殑鍙傛暟Key鍗沖姞瀵嗙畻娉曠殑Key銆?/div>

Rust鐨勪嬌鐢ㄦ劅鍙?/h3>
浠ュ墠铏芥湁鍏蟲(chóng)敞Rust錛屽嵈浠庢病鐢≧ust鍐欒繃浠ｇ爜錛屼富瑕佹槸榪樻湭鍙戝竷1.0錛岃娉曚笉紼沖畾錛屾渶榪?.0蹇湁鐪夌洰浜?jiǎn)锛屽彲浠ョ敤鏉ュ啓鍐櫈畯涓滆タ浜?jiǎn)銆傚洜涓烘湁Haskell鐨勫熀紜錛屾墍浠ヤ笂鎵婻ust瀵規(guī)垜鏉ヨ娌′粈涔堥毦搴︺?br />
Rust鎻愪緵浜?jiǎn)ADT(Algebraic Data Type), Pattern Matching, Traits錛岃娉曡〃杈捐兘鍔涘緢寮猴紝鍚屾椂涔熸彁渚涗簡(jiǎn)macro錛屽彲鑷畾鎵╁睍璇硶錛岃繘涓姝ュ姞寮轟簡(jiǎn)璇硶琛ㄨ揪鑳藉姏銆傝嚜鍔ㄥ唴瀛樼鐞嗕篃璁╃▼搴忔洿瀹夊叏錛屼笉榪囩敱姝や篃甯︽潵涓浜涜娉曡〃杈捐兘鍔涚殑鍓婂急錛屾瘮濡傞渶瑕佸湪鍑芥暟榪斿洖鐨勬椂鍊欒嚜鍔ㄨ皟鐢╯ocket.close_read錛岄氬父鍙互瀹氫箟涓涓猻truct錛屽茍璁╄繖涓猻truct impl trait Drop錛屽湪緇撴瀯浣撻攢姣佺殑鏃跺欒皟鐢╯ocket.close_read錛屽張鍥犱負(fù)socket.close_read闇瑕乵ut鐨剆ocket寮曠敤錛岃宮ut鐨勫紩鐢ㄥ彧鑳絙orrow涓嬈★紝鎵浠ヨ繖涓猻truct涓鏃orrow浜?jiǎn)socket鐨刴ut寮曠敤錛屼箣鍚庡啀璋冪敤榪欎釜socket鐨刴ut鍑芥暟灝變細(xì)鎶ラ敊錛屼竴涓獁orkaround鐨勬柟娉曞氨鏄痵truct淇濆瓨socket鐨勪竴浠芥嫹璐濓紙socket鏈韓閫氳繃寮曠敤璁℃暟綆＄悊錛夛紝铏界劧鍙錛屼絾鏄繪劅瑙夋湁浜涢噸浜?jiǎn)锛屼粎浠呬负鍐欒典h潵鏂逛究鐨勪竴涓棶棰樺紩鍏ヤ簡(jiǎn)涓嬈″紩鐢ㄨ鏁板璞＄殑鎷瘋礉銆傚悓鏃朵篃浼?xì)漶旂敓涓涓鍛婏紝鐢變簬閭ｄ釜struct鐨勫璞℃病鏈夎浣跨敤榪囥?br />
Rust緙栬瘧鍣ㄦ姤閿欎俊鎭緢璇︾粏鍙嬪ソ錛岃繍琛屾椂渚濊禆灝忥紝Tunnel緙栬瘧鍑烘潵鐨勭殑client鍜宻erver閮藉彲浠ュ湪鍏跺畠鏈哄櫒涓婄洿鎺ヨ繍琛屻傚叾瀹冩柟闈富瑕佹槸API鏂囨。璺熶笉涓婏紝鏈鏂版枃妗ｄ笂鏈夌殑鍑芥暟錛岀紪璇戝櫒緙栬瘧鍙兘鎶ラ敊錛屽嚱鏁板凡緇忎笉瀛樺湪浜?jiǎn)锛堝垰鍒氬幦潨嬩簡(jiǎn)鐪嬫渶鏂扮殑鏂囨。錛宻td::io鍙樻垚浜?jiǎn)std::old_io錛夈傚簱鏂歸潰錛岃櫧鐒禖argo浠撳簱閲屾湁涓浜涚涓夋柟搴擄紝浣嗘槸鎬諱綋鏁伴噺榪樹(shù)笉澶氥?/div>

airtrack 2015-02-03 21:03 鍙戣〃璇勮
]]>鎿嶄綔緋葷粺瀹炵幇錛堜竴錛夛細(xì)浠嶣ootloader鍒癊LF鍐呮牳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

鎴戜滑鐭ラ亾璁＄畻鏈哄惎鍔ㄦ槸浠嶣IOS寮濮嬶紝鍐嶇敱BIOS鍐沖畾浠庡摢涓澶囧惎鍔ㄤ互鍙?qiáng)鍚姩椤哄簭锛屾瘮濡傚厛浠嶥VD鍚姩鍐嶄粠紜洏鍚姩絳夈傝綆楁満鍚姩鍚庯紝BIOS鏍規(guī)嵁閰嶇疆鎵懼埌鍚姩璁懼錛屽茍璇誨彇榪欎釜璁懼鐨勭0涓墖鍖猴紝鎶婅繖涓墖鍖虹殑鍐呭鍔犺澆鍒?x7c00,涔嬪悗璁〤PU浠?x7c00寮濮嬫墽琛岋紝榪欐椂BIOS宸茬粡浜ゅ嚭浜?jiǎn)璁〗帡鏈虹殑鎺у埗鏉冨Q岀敱琚姞杞界殑鎵囧尯紼嬪簭鎺ョ璁＄畻鏈恒?/div>
榪欑涓涓墖鍖虹殑紼嬪簭灝卞彨Boot錛屽畠涓鑸仛涓浜涘噯澶囧伐浣滐紝鎶婃搷浣滅郴緇熷唴鏍稿姞杞借繘鍐呭瓨錛屽茍鎶婃帶鍒舵潈浜ょ粰鍐呮牳銆傜敱浜嶣oot鍙兘鏈変竴涓墖鍖哄ぇ灝忥紝鍗?12瀛楄妭錛屽畠鎵鑳藉仛鐨勫伐浣滃緢鏈夐檺錛屽洜姝ゅ畠鏈夊彲鑳戒笉鐩存帴鍔犺澆鍐呮牳錛岃屾槸鍔犺澆涓涓彨Loader鐨勭▼搴忥紝鍐嶇敱Loader鍔犺澆鍐呮牳銆傚洜涓篖oader涓嶆槸BIOS鐩存帴鍔犺澆鐨勶紝鎵浠ュ畠鍙互紿佺牬512瀛楄妭鐨勭▼搴忓ぇ灝忛檺鍒訛紙鍦ㄥ疄妯″紡涓嬬悊璁轟笂鍙互杈懼埌1M錛夈傚鏋淏oot娌℃湁鍔犺澆Loader鑰岀洿鎺ュ姞杞藉唴鏍革紝鎴戜滑鍙互鎶婂畠鍙仛Bootloader銆?/div>
Bootloader鍔犺澆鍐呮牳灝辮璇誨彇鏂囦歡錛屽湪瀹炴ā寮忎笅鍙互鐢˙IOS鐨処NT 13h涓柇銆傚唴鏍告枃浠舵斁鍦ㄥ摢閲岋紝鎬庝箞鏌ユ壘璇誨彇錛岃繖閲岀壍娑夊埌鏂囦歡緋葷粺錛孊ootloader瑕佷粠紜洏錛堣蔣鐩橈級(jí)鐨勬枃浠剁郴緇熶腑鏌ユ壘鍐呮牳鏂囦歡錛屽洜姝ootloader闇瑕佽В鏋愭枃浠剁郴緇熺殑鑳藉姏銆侴RUB鏄竴涓笓涓氱殑Bootloader錛屽畠瀵硅繖浜涙彁渚涗簡(jiǎn)寰堝ソ鐨勬敮鎸併?/div>
瀵逛簬涓涓猅oy鎿嶄綔緋葷粺鏉ヨ錛屽彲浠ョ畝鍗曞鐞嗭紝鎶婂唴鏍告枃浠舵斁鍒癇ootloader涔嬪悗錛屽嵆浠庤蔣鐩樼殑絎?涓墖鍖哄紑濮嬶紝榪欐牱鎴戜滑鍙互涓嶉渶瑕佹敮鎸佹枃浠剁郴緇燂紝鐩存帴璇誨彇鎵囧尯鏁版嵁鍔犺澆鍒板唴瀛樺嵆鍙?/div>

瀹炴ā寮忓埌淇濇姢妯″紡

鎴戜滑鐭ラ亾Intel x86緋誨垪CPU鏈夊疄妯″紡鍜屼繚鎶ゆā寮忥紝瀹炴ā寮忎粠8086寮濮嬪氨鏈夛紝淇濇姢妯″紡浠?0386寮濮嬪紩鍏ャ備負(fù)浜?jiǎn)鍏煎锛孖ntel x86緋誨垪CPU閮芥敮鎸佸疄妯″紡銆傜幇浠ｆ搷浣滅郴緇熼兘鏄繍琛屽湪淇濇姢妯″紡涓嬶紙Intel x86緋誨垪CPU錛夈傝綆楁満鍚姩鏃訛紝榛樿鐨勫伐浣滄ā寮忔槸瀹炴ā寮忥紝涓轟簡(jiǎn)璁╁唴鏍歌兘榪愯鍦ㄤ繚鎶ゆā寮忎笅錛孊ootloader闇瑕佷粠瀹炴ā寮忓垏鎹㈠埌淇濇姢妯″紡錛屽垏鎹㈡楠ゅ涓嬶細(xì)
  1. 鍑嗗濂紾DT(Global Descriptor Table)
  2. 鍏充腑鏂?/li>
  3. 鍔犺澆GDT鍒癎DTR瀵勫瓨鍣?/li>
  4. 寮鍚疉20錛岃CPU瀵誨潃澶т簬1M
  5. 寮鍚疌PU鐨勪繚鎶ゆā寮忥紝鍗蟲(chóng)妸cr0瀵勫瓨鍣ㄧ涓涓猙it緗?
  6. 璺寵漿鍒頒繚鎶ゆā寮忎唬鐮?/li>
GDT鏄疘ntel CPU淇濇姢妯″紡榪愯鐨勬牳蹇?jī)鏁版嵁缁撴瀯锛屾墍鏈変繚鎶ゆā寮忔搷浣滅殑鏁版嵁閮戒粠GDT琛ㄥ紑濮嬫煡鎵撅紝榪欓噷鏈塆DT鐨勮緇嗕粙緇嶃?/div>
GDT涓殑姣忎竴涓〃欏圭敱8瀛楄妭琛ㄧず錛屽涓嬪浘錛?/div>


鍏朵腑Access Byte鍜孎lags濡備笅鍥撅細(xì)


榪欓噷鏄緇嗚鏄庛?/div>
GDTR鏄竴涓?瀛楄妭鐨勫瘎瀛樺櫒錛屾湁4瀛楄妭琛ㄧずGDT琛ㄧ殑鍩哄湴鍧錛?瀛楄妭琛ㄧずGDT琛ㄧ殑澶у皬錛屽嵆鏈澶?5536錛堝疄闄呭兼槸65535錛?6浣嶆渶澶у兼槸65535錛夛紝姣忎釜琛ㄩ」8瀛楄妭錛岄偅涔圙DT琛ㄦ渶澶氬彲浠ユ湁8192欏廣?/div>
瀹炴ā寮忕殑瀵誨潃鎬葷嚎鏄?0bits錛屼負(fù)浜?jiǎn)璁╁d潃瓚呰繃1M錛岄渶瑕佸紑鍚疉20錛屽彲浠ラ氳繃浠ヤ笅鎸囦護(hù)寮鍚細(xì)
    in al, 0x92
    or al, 2
    out 0x92, al
鎶婁笂榪版楠ゅ畬鎴愪箣鍚庯紝鎴戜滑灝辮繘鍏ヤ繚鎶ゆā寮忎簡(jiǎn)銆傚湪淇濇姢妯″紡涓嬫垜浠浣跨敤GDT閫氳繃GDT Selector瀹屾垚錛屽畠鏄疓DT琛ㄩ」鐩稿浜庤搗濮嬪湴鍧鐨勫亸縐伙紝鍥犳瀹冪殑鍊間竴鑸槸0x0 0x8 0x10 0x18絳夈?/div>

ELF鏂囦歡

Bootloader紼嬪簭鏄師濮嬪彲鎵ц鏂囦歡錛屽鏋滅▼搴忕敱姹囩紪鍐欐垚錛屾眹緙栫紪璇戝櫒緙栬瘧鐢熸垚鐨勬枃浠跺氨鏄師濮嬪彲鎵ц鏂囦歡錛屼篃鍙互浣跨敤C璇█緙栧啓錛岀紪璇戞垚鍙墽琛屾枃浠朵箣鍚庨氳繃objcopy杞崲鎴愬師濮嬪彲鎵ц鏂囦歡錛?a >榪欑瘒鏂囩珷浠嬬粛浜?jiǎn)鐢–璇█鍐橞ootloader銆?/div>
閭ｄ箞鍐呮牳鏂囦歡鏄粈涔堟牸寮忕殑鍛紵璺烞ootloader涓鏍風(fēng)殑褰撶劧鍙互銆傚唴鏍鎬竴鑸嬌鐢–璇█緙栧啓錛屾瘡嬈＄紪璇戦摼鎺ュ畬鎴愪箣鍚庤皟鐢╫bjcopy鏄彲浠ョ殑銆傛垜浠篃鍙互鏀寔閫氱敤鐨勫彲鎵ц鏂囦歡鏍煎紡錛孍LF(Executable and Linkable Format)鍗蟲(chóng)槸涓縐嶉氱敤鐨勬牸寮忥紝瀹冪殑緇村熀鐧劇銆?/div>
ELF鏂囦歡鏈変袱縐嶈鍥撅紙View錛夛紝閾炬帴瑙嗗浘鍜屾墽琛岃鍥撅紝濡備笅鍥撅細(xì)



閾炬帴瑙嗗浘閫氳繃Section Header Table鎻忚堪錛屾墽琛岃鍥鵑氳繃Program Header Table鎻忚堪銆係ection Header Table鎻忚堪浜?jiǎn)鎵鏈塖ection鐨勪俊鎭紝鍖呮嫭鎵鍦ㄧ殑鏂囦歡鍋忕Щ鍜屽ぇ灝忕瓑錛汸rogram Header Table鎻忚堪浜?jiǎn)鎵鏈塖egment鐨勪俊鎭紝鍗砊ext Segment, Data Segment鍜孊SS Segment錛屾瘡涓猄egment涓寘鍚簡(jiǎn)涓涓垨澶氫釜Section銆?/div>
瀵逛簬鍔犺澆鍙墽琛屾枃浠訛紝鎴戜滑鍙渶鍏蟲(chóng)敞鎵ц瑙嗗浘錛屽嵆瑙ｆ瀽ELF鏂囦歡錛岄亶鍘哖rogram Header Table涓殑姣忎竴欏癸紝鎶婃瘡涓狿rogram Header鎻忚堪鐨凷egment鍔犺澆鍒板搴旂殑铏氭嫙鍦板潃鍗沖彲錛岀劧鍚庝粠ELF header涓彇鍑篍ntry鐨勫湴鍧錛岃煩杞繃鍘誨氨寮濮嬫墽琛屼簡(jiǎn)銆傚浜嶦LF鏍煎紡鐨勫唴鏍告枃浠舵潵璇達(dá)紝榪欎釜宸ヤ綔灝遍渶瑕佺敱Bootloader瀹屾垚銆侭ootloader鏀寔ELF鍐呮牳鏂囦歡鍔犺澆涔嬪悗錛岀敤C璇█緙栧啓鐨勫唴鏍哥紪璇戝畬鎴愪箣鍚庡氨涓嶉渶瑕乷bjcopy浜?jiǎn)銆?/div>

涓轟粈涔堝啓鎿嶄綔緋葷粺

棣栧厛鏄叴瓚ｏ紝鍦ㄧ幇鍦ㄨ繖涓椂浠ｏ紝鍐欐搷浣滅郴緇熷嚑涔庢病鏈夊疄鐢ㄤ環(huán)鍊鹼紝鍙兘鏄竴涓猅oy錛屽湪鍐欎竴涓猅oy OS鏃訛紝鍙互瀛︿範(fàn)鎺屾彙寰堝鐭ヨ瘑錛屽茍鎶婅繖浜涚煡璇嗚瘡絀垮疄鐢ㄨ搗鏉ャ傛搷浣滅郴緇熸槸涓涓鏉傜殑緋葷粺錛岀壍娑夊埌鐨勪笢瑗垮緢澶氾紝鎴戠浉淇″啓鎿嶄綔緋葷粺鍙互甯姪鐞嗚В鐜頒唬鎿嶄綔緋葷粺鍙?qiáng)鍏跺畠搴曞眰鐭ヨ瘑銆傛垜鐩墠鎵嶅垰寮濮嬪啓錛屼唬鐮佹斁鍦?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
鍘誨勾鑺變簡(jiǎn)涓や笁涓槦鏈熺殑涓氫綑鏃墮棿瀹炵幇浜?jiǎn)鍩轰簬DFA鐨勬鍒欏紩鎿庯紙姝ｅ垯寮曟搸甯歌鐨勫疄鐜版柟娉?/strong>

姝ｅ垯鐨勫父瑙佸疄鐜版柟寮忔湁涓夌錛欴FA銆丅acktracking銆丯FA錛?/div>



  • NFA(Thompson NFA)鏈夌浉瀵笵FA鏉ヨ鐨勬瀯閫犵畝鍗曪紝騫跺吋鏈夋帴榪慏FA鐨勬晥鐜囷紝騫朵笖鍦ㄩ潰瀵笲acktracking鍑虹幇鎸囨暟澶嶆潅搴︽椂鐨勬鍒欒〃杈懼紡淇濇寔鑹ソ鐨勬ц兘銆?/li>

NFA-based鐨勫疄鐜?/strong>

榪欓噷鎻忚堪鐨凬FA鏄寚Thompson NFA銆俆hompson NFA瀹炵幇鐨勬牳蹇?jī)鏄浜庢鍒欒〃杈惧紡澶氫釜鍙兘鐨勫寶w厤騫跺彂鐨勫悜鍓嶅尮閰嶏紝姝よ繃紼嬫槸鍦ㄦā鎷烡FA榪愯銆傛瘮濡傚浜庢鍒欒〃杈懼紡"abab|abbb"鍖歸厤瀛楃涓?abbb"錛?/div>

  • Backtracking鐨勫尮閰嶈繃紼嬫槸鍙栨鍒欑殑絎竴涓瓙琛ㄨ揪寮?abab"鍖歸厤錛屽墠涓や釜瀛楃鍖歸厤鎴愬姛錛屽尮閰嶇涓変釜瀛楃鐨勬椂鍊欏け璐ワ紝榪欐椂寮曟搸鍥炴函閫夋嫨絎簩涓瓙琛ㄨ揪寮?abbb"鍖歸厤錛屾渶緇堝尮閰嶆垚鍔熴?/li>

  • Thompson NFA鏄悓鏃跺彇涓や釜瀛愯〃杈懼紡"abab"鍜?abbb"鍖歸厤錛屽墠涓や釜瀛楃鍖歸厤鏃訛紝涓や釜瀛愯〃杈懼紡閮借兘鍖歸厤鎴愬姛錛屽綋鍖歸厤絎笁涓瓧絎︽椂錛屽瓙琛ㄨ揪寮?abab"鍖歸厤澶辮觸錛屽洜姝や涪寮冿紝"abbb"鍖歸厤鎴愬姛鎺ョ潃鍖歸厤錛屾渶緇堝尮閰嶆垚鍔熴?/li>

涓婇潰鏄竴涓畝鍗曠殑渚嬪瓙錛屾病鏈夊嚭鐜?*" "+" "{m,n}"榪欑澶嶆潅鐨刴etacharacters錛屽湪澶勭悊榪欑repeat鐨刴etacharacter鏃禩hompson NFA浼樺娍鏇村姞鏄庢樉銆?/div>

鍦ㄥ疄闄呭鏉傜殑姝ｅ垯琛ㄨ揪寮忎腑錛孨FA鏋勯犳槸蹇呯劧浼?xì)漶旂敓涓鍫唀psilon杈癸紝榪欏湪絎簩綃囨枃绔?/a>涓湁鎻忚堪銆備笂闈㈡弿榪癟hompson NFA瀹為檯鏄湪妯℃嫙DFA榪愯錛屽湪姣忎釜瀛楃鍖歸厤瀹屾垚涔嬪悗闇瑕佽煩榪噀psilon杈瑰緱鍒板悗闈㈣鍖歸厤鐨勫茍鍙戠殑鐘舵侀泦鍚堬紝榪欐牱鎸佺畫(huà)鐨勫茍鍙戝尮閰嶄笅鍘伙紝褰撳瓧絎︿覆鍖歸厤瀹屾垚鏃跺彧瑕佹湁涓涓揪鍒頒簡(jiǎn)鎺ュ彈鐘舵侊紝灝辨槸鍖歸厤鎴愬姛錛岃嫢榪欎釜闆嗗悎涓虹┖錛岄偅琛ㄧず鍖歸厤澶辮觸銆?/div>

鍦ㄦ垜鐨勫疄鐜頒腑錛屾瀯閫犱簡(jiǎn)涓緇勭姸鎬佸拰鐢辮繖緇勭姸鎬佸姞epsilon杈歸泦鍚堟瀯閫犵殑鏈夊悜鍥撅紝姣忎釜鐘舵佹湁鑷繁鐨勭姸鎬佺被鍨嬶紝鍒嗕負(fù)涓ょ錛?/div>

  • 涓縐嶆槸鍖歸厤鐘舵佺被鍨嬶紝鍗崇敤鏉ュ尮閰嶅瓧絎︾殑鐘舵侊紝鑻ュ瓧絎﹀尮閰嶆垚鍔燂紝鍒欒繘鍏ヤ笅涓涓姸鎬侊紱

  • 涓縐嶆槸鎿嶄綔鐘舵佺被鍨嬶紝鍗充笉鍖歸厤瀛楃鐨勭姸鎬侊紝鍦ㄦ瘡涓瓧絎﹀尮閰嶇粨鏉熶箣鍚庤嫢鍒拌揪榪欎簺鐘舵侊紝鍒欎細(xì)榪涜鐩稿簲鐨勬搷浣滐紝姣斿repeat鐘舵侊紝璁板綍鍖歸厤璁℃暟錛屽茍鍒ゆ柇鍖歸厤璁℃暟鏄惁瀹屾垚鍐嶅喅瀹氭槸鍚﹁繘鍏ョ殑涓嬮潰鐨勭姸鎬併?/li>

repeat鏄竴縐嶄細(xì)鍒嗗寲鐨勭姸鎬侊紝杈懼埌鏈灝忓尮閰嶆鏁版椂錛屽彲浠ユ帴鐫寰(xiàn)涓嬭蛋錛屼篃鍙互緇х畫(huà)閲嶅鍖歸厤repeat鐨勫瓙姝ｅ垯琛ㄨ揪寮忥紝榪欐牱灝卞垎鍖栨垚涓ゆ潯綰夸簡(jiǎn)錛屽茍涓旀瘡鏉＄嚎閮藉甫鏈夎嚜宸辯殑鐘舵佹暟鎹紝鍥犳錛屾垜鐨勫疄鐜頒腑寮曞叆鐨則hread鏉ヨ〃紺轟竴鏉″尮閰嶇嚎錛岄噷闈㈡湁鐘舵佹暟鎹?/div>

Match鍜孲earch

鐘舵佹瀯閫犲畬鎴愪簡(jiǎn)涔嬪悗錛屽氨瑕佸紑濮嬪尮閰嶄簡(jiǎn)銆傚尮閰嶆湁涓ょ錛屼竴縐嶆槸match錛屽嵆涓涓鍒欒〃杈懼紡鑳藉惁瀹屾暣鍖歸厤涓涓瓧絎︿覆錛岃嫢瀹屾暣鍖歸厤鍒欏尮閰嶆垚鍔燂紱鍙︿竴縐嶆槸search錛岃鍦ㄤ竴涓瓧絎︿覆涓垨鑰呬竴鍧梑uffer涓煡鎵炬瘡涓弧瓚崇殑鍖歸厤銆傝繖閲屽氨鏈変釜闂錛屼粠絎竴涓瓧絎﹀紑濮嬪尮閰嶏紝鍖歸厤浜?jiǎn)鍑犱釜瀛椊W︿箣鍚庡彂鐜板尮閰嶅け璐ヤ簡(jiǎn)鎬庝箞鍔炲憿錛熷洖閫鍒扮浜屼釜瀛楃閲嶆柊鍖歸厤錛熸垜浠煡閬撳浜庢櫘閫氱殑瀛楃涓叉煡鎵撅紝鏈塊MP綆楁硶鍙互淇濊瘉涓嶅洖閫瀛楃錛堝叾瀹濳MP綆楁硶鐨勯澶勭悊灝辨槸鏋勯燚FA錛夛紝鎴栬呮湁Boyer-Moore綆楁硶灝介噺鍥為灝戠殑瀛楃涓暟銆傚浜庢鍒欒繖縐嶅鏉傜殑鍖歸厤璇ユ庝箞鍔炲憿錛熶粠涓婇潰鐨凾hompson NFA鐨勬弿榪板彲浠ョ煡閬撳尮閰嶈繃紼嬫槸澶氭潯綰垮茍鍙戝尮閰嶏紝鍥犳鍙互鏋勯犱竴涓緇堜駭鐢熶竴鏉℃柊綰跨殑鐘舵侊紝鑻ュ尮閰嶅湪鍓嶉潰鐨勭嚎澶辮觸琚涪寮冧箣鍚庯紝鍚庨潰鐨勬柊綰垮緇堝彲浠ヨˉ涓婏紝榪欐牱鏌ユ壘鐨勮繃紼嬪氨涓嶅啀闇瑕佸洖閫瀛楃浜?jiǎn)銆?/div>

鎴戠殑瀹炵幇涓紝鐘舵佹瀯閫犲畬鎴愬悗鏄繖鏍風(fēng)殑錛?/div>

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

鐢╮epeat-any鏉ヤ駭鐢熸柊鐨勫尮閰嶇嚎銆傝嫢鍦╩atch妯″紡涓嬶紝鍒欎粠絎笁涓姸鎬佸紑濮嬪尮閰嶏紝涓嶄細(xì)浜х敓鏂扮殑鍖歸厤綰匡紝涓鏃﹀尮閰嶈繃紼嬪け璐ヤ簡(jiǎn)灝卞け璐ヤ簡(jiǎn)銆?/div>

緇撹

姝ｅ垯琛ㄨ揪寮忚娉曚竴鐩村湪鎵╁睍錛屾柊鐨勮娉曟湁浜涘緢闅懼湪DFA鍜孨FA涓疄鐜幫紝鑰屽湪Backtracking涓殑瀹炵幇鍙堟槸浠ョ壓鐗叉ц兘涓轟唬浠楓傚洜姝ゆ湁浜涙鍒欒〃杈懼紡瀹炵幇浼?xì)缁撳悎澶毧U嶅疄鐜版柟寮忥紝鍒ゆ柇姝ｅ垯琛ㄨ揪寮忕殑綾誨瀷閫夋嫨涓嶅悓鐨勫紩鎿庯紝姣斿鏅氬瓧絎︿覆鍔犱笂涓浜涚畝鍗曠殑姝ｅ垯璇硶閲囩敤DFA寮曟搸鍖歸厤錛屾垨鑰呭彧鏈夋櫘閫氬瓧絎︿覆鐨勫尮閰嶅彲浠ョ敤Boyer-Moore綆楁硶錛屾瘯绔烞oyer-Moore綆楁硶鍦ㄦ櫘閫氭枃鏈煡鎵句腑瑕佷紭?shù)簬KMP綆楁硶錛氾級(jí)錛屽浜庡鏉傜殑姝ｅ垯琛ㄨ揪寮忛噰鐢˙acktracking錛岀敋鑷蟲(chóng)湁浜涙鍒欏紩鎿庝嬌鐢↗IT鏉ュ姞閫熴?/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鐨勫垎綾?/h2>
閫氬父鎯呭喌涓婫C鍒嗕負(fù)涓ょ錛屽垎鍒槸錛氭壂鎻廏C(Tracing GC)鍜屽紩鐢ㄨ鏁癎C(Reference counting GC)銆傚叾涓壂鎻廏C鏄瘮杈冨父鐢ㄧ殑GC瀹炵幇鏂規(guī)硶錛屽叾鍘熺悊鏄細(xì)鎶婃鍦ㄤ嬌鐢ㄧ殑瀵硅薄鎵懼嚭鏉ワ紝鐒跺悗鎶婃湭琚嬌鐢ㄧ殑瀵硅薄閲婃斁銆傝屽紩鐢ㄨ鏁癎C鍒欐槸瀵規(guī)瘡涓璞￠兘娣誨姞涓涓鏁板櫒錛屽紩鐢ㄥ鍔犱竴涓鏁板櫒灝卞姞涓錛屽紩鐢ㄥ噺灝戜竴涓鏁板櫒灝卞噺涓錛屽綋璁℃暟鍣ㄥ噺鑷抽浂鏃訛紝鎶婂璞″洖鏀墮噴鏀俱傚紩鐢ㄨ鏁癎C璺烠++涓殑shared_ptr綾諱技錛岃嚜鐒朵篃浼?xì)瀛樺湪弩@鐜紩鐢ㄩ棶棰樸?br />
鎵弿GC(Tracing GC)鏄箍娉涗嬌鐢ㄧ殑GC鏂規(guī)硶錛屾渶綆鍗曠殑瀹炵幇鏂瑰紡鏄痬ark-sweep錛屽嵆鎵弿鎵鏈夊瓨?gòu)z葷殑瀵硅薄騫秏ark錛岀劧鍚庨亶鍘嗘暣涓狦C瀵硅薄鍒楄〃錛屾妸鎵鏈夋爣璁拌繃鐨勫璞℃竻闄ゆ爣璁幫紝鎶婃湭鏍囪榪囩殑瀵硅薄閲婃斁銆傚鏋淕C浣跨敤鐨勬槸mark-sweep鏂規(guī)硶錛岀▼搴忚繍琛屼竴孌墊椂闂村悗瑙﹀彂浜?jiǎn)GC錛屾瘡嬈C鐨勬椂鍊欎細(xì)鎶婂綋鍓嶇▼搴忎腑鐨勬墍鏈夊璞￠兘鎵弿涓嬈★紝鐒跺悗閲婃斁鏈嬌鐢ㄧ殑瀵硅薄銆傝繖瀵逛簬鍒嗛厤GC瀵硅薄灝戠殑紼嬪簭鏉ヨ娌℃湁浠涔堥棶棰橈紝褰撶▼搴忎腑瀛樺湪澶ч噺鍒嗛厤GC瀵硅薄鏃訛紝姣忔鍚姩GC鎵弿鎵鏈夊璞＄殑浠ｄ環(huán)鏄緢楂樼殑錛屽張鍥犱負(fù)GC鐨勮繃紼嬮氬父鏄痵top-the-world錛屾墍浠ラ珮?shù)唬洵h(huán)鐨凣C浼?xì)瀵艰嚧鏁翠釜绋嬪簭鍗蹇涓孌墊椂闂淬傚浜庤繖涓棶棰橈紝瑙ｅ喅鏂規(guī)硶鏈夊閲廏C(Incremental GC)鍜屽垎浠C(Generational GC)銆?br />
澧為噺GC(Incremental GC)浼?xì)鎶婃暣涓狦C榪囩▼鍒嗘垚寰堝姝?phase)錛屾瘡姝ョ殑鎵ц鍙互瀛樺湪涓瀹氶棿闅旇繍琛岀▼搴忔湰韜紝榪欏氨灝介噺鎶妔top-the-world鐨勬椂闂村彉鐭紝浣垮緱紼嬪簭涓嶄細(xì)鍥犱負(fù)GC鑰屽鑷村歡榪熷お澶с侺ua榛樿閲囩敤鐨勬槸榪欑瀹炵幇鏂規(guī)硶錛孡ua 5.2涓篃寮曞叆浜?jiǎn)鍒嗕唬GC浣滀負(fù)澶囬塆C鏂規(guī)硶銆?br />
鍒嗕唬GC(Generational GC)鎶婂璞″垎鎴愬嚑浠?Generation)錛岄氬父鎶奊C鍒嗕負(fù)涓ょ錛歁inor GC鍜孧ajor GC銆傚垰鍒氬垎閰嶅嚭鏉ョ殑瀵硅薄灞炰簬鏈騫磋交鐨勪竴浠ｏ紝鍦ㄤ竴嬈C榪囧悗鎶婂勾杞諱唬涓瓨?gòu)z葷殑瀵硅薄涓婂崌鍒板勾鑰佺殑涓浠ｄ腑銆傛妸鍙壂鎻忓勾杞諱竴浠ｇ殑瀵硅薄浠ュ噺灝戞壂鎻忓璞℃暟閲忕殑GC榪囩▼縐頒負(fù)Minor GC錛屽彧鏈夊湪鐗瑰畾鎯呭喌涓嬫墠浼?xì)鍚姩瀹屾暣鐨凪ajor GC銆傚垎浠C鏄熀浜庡湪澶у鏁扮▼搴忎腑鏂板垱寤虹殑瀵硅薄鍚屾椂涔熸槸鏈蹇彉鎴愭棤鏁堢殑瀵硅薄鐨勭粡楠岃璁＄殑錛屽騫磋交浠ｅ璞C鏃訛紝鍙互閲婃斁澶у鏁版棤鏁堝璞★紝瀛樻椿涓嬫潵鐨勫璞′竴鑸瓨?gòu)z繪椂闂翠篃浼?xì)鏇撮暱锛屽洜姝ゆ妸瀹冧滑涓婂崌鍒颁笅涓浠ｄ腑浠ュ噺灝戞渶榪欎簺瀵硅薄鐨勬壂鎻忋?br />
瀵逛簬GC鍐呭瓨鐨勭鐞嗭紝鏈夌Щ鍔ㄥ拰闈炵Щ鍔ㄤ箣鍒嗐傜Щ鍔ㄧ殑灝辨槸鎶婁竴嬈C榪囧悗瀛樻椿鐨勫璞ompact鍒頒竴璧鳳紝浣縂C綆＄悊鐨勫唴瀛樹(shù)繚鎸佽繛緇紝榪欓噷澧炲姞浜?jiǎn)涓涓Щ鍔ㄥ璞＄殑寮閿錛屼笉榪囧畠涔熷悓鏍峰甫鏉ヤ笉灝戝ソ澶勶細(xì)鍒嗛厤閲婃斁瀵硅薄蹇拰鏇村揩鐨勫簭鍒楅亶鍘?鍦–PU cache涓強(qiáng)鍦ㄥ悓涓涓猇irtual memory page涓?銆傛鍥犱負(fù)瀹冧細(xì)鎶婂璞ompact鍒頒竴璧鳳紝瀵硅薄鐨勫湴鍧灝變細(xì)鍙戠敓鍙樺寲錛岃繖涔熷氨瀵艱嚧涓涓槑鏄劇殑緙虹偣錛屼笉鑳戒嬌鐢ㄦ寚閽堝紩鐢℅C瀵硅薄銆?br />
鍏跺畠楂樼駭GC鏂規(guī)硶錛屾瘮濡?NET鐨刡ackground GC錛屽嚑涔庝笉闇瑕乻top-the-world灝卞彲浠ュ湪GC綰跨▼涓畬鎴怗C錛岃繖縐嶉珮縐戞妧鐨凣C瀵逛簬鎴戣繖縐嶅垵綰т漢澹熀鏈睘浜庝笉鍙兂璞°?br />

鍒濈駭鍒嗕唬GC璁捐

浜?jiǎn)瑙ｄ簡(jiǎn)鍩烘湰鐨凣C鏂規(guī)硶涔嬪悗錛屾垜涓?a >luna絎簩鐗?/a>瀹炵幇浜?jiǎn)涓涓垵綰х殑鍒嗕唬GC錛屾妸瀵硅薄鍒嗘垚涓変唬錛欸CGen0,GCGen1,GCGen2:

   GCGen0鏄渶騫磋交鐨勪竴浠ｏ紝榛樿鎵鏈夊璞￠兘鏄垎閰嶅湪榪欎唬涓?/div>
   GCGen1鏄勾鑰佺殑涓浠ｏ紝鍦ㄤ竴嬈C榪囧悗GCGen0浠ｅ瓨?gòu)z葷殑瀵硅薄浼?xì)绉诲姩鍒皹q欎竴浠ｄ腑銆?/div>
   GCGen2鏄渶鑰佺殑涓浠ｏ紝涓鑸儏鍐典笅鐢ㄤ簬瀛樻斁緙栬瘧鏃跺垎閰嶇殑浼?xì)闀挎湡瀛樺湪鐨勫璞″Q屾瘮濡傚嚱鏁板強(qiáng)瀛楃涓插父閲忋?br />
鐢變簬鎴戝湪寰堝鍦版柟鐩存帴寮曠敤浜?jiǎn)GC瀵硅薄鐨勬寚閽堬紝涓轟簡(jiǎn)綆鍗曡搗瑙侊紝鎴戞病鏈夊湪GC涔嬪悗縐誨姩瀵硅薄錛岃屾槸瀵規(guī)瘡涓璞″崟鐙垎閰嶉噴鏀懼唴瀛樸傛瘡涓璞￠兘鏈塆eneration鏍囪鍜孏C鏍囪浠ュ強(qiáng)涓涓敤浜庢寚鍚戣窡鑷繁灞炰簬鍚屼唬鐨凣C瀵硅薄鐨勬寚閽堛?br />
Minor GC瀵笹CGen0浠ｅ璞ark-sweep錛屽茍鎶婂瓨?gòu)z葷殑瀵硅薄縐誨姩鍒癎CGen1浠ｄ腑銆傛棦鐒墮渶瑕乵ark錛岃嚜鐒墮渶瑕佸鎵鏈塆CGen0浠ｅ瓨?gòu)z葷殑瀵硅薄鏍囪錛岃繖閫氳繃瀵箁oot瀵硅薄鐨勯亶鍘嗗畬鎴愶紝root鏄寚鎵鏈夊璞＄殑寮曠敤鍏ュ彛錛屾瘮濡傜▼搴忕殑鏍堝拰鍏ㄥ眬琛ㄣ傚浜嶮inor GC鐨剅oot瀵硅薄閬嶅巻鏈綆鍗曠殑鏂規(guī)硶鏄窡Major GC鐨剅oot閬嶅巻瀹屽叏涓鑷達(dá)紝涓嶈繃榪欐牱鐨勯亶鍘嗗浜庢湰鏉ュ氨鏄負(fù)浜?jiǎn)鍑彏畱閬嶅巻瀵硅薄鐨凪inor GC鏉ヨ浼間箮涓嶅悎錛屾墍浠ラ氬父鍙鏌愪竴灝忓潡root閬嶅巻錛屾瘮濡傚彧瀵規(guī)爤涓婄殑瀵硅薄閬嶅巻錛岀劧鍚庡啀鎶婂瓨?gòu)z葷殑瀵硅薄淇濈暀涓嶅瓨?gòu)z葷殑瀵硅薄閲婃斁銆?br />
Minor GC鐨剅oot閬嶅巻瀛樺湪涓涓棶棰橈細(xì)鍋囪鍙妸鏍堜笂鐨勫璞′綔涓簉oot閬嶅巻錛屼細(xì)瀛樺湪涓浜涗粠GCGen0浠ｅ垎閰嶅嚭鏉ョ殑瀵硅薄娌℃湁琚爤涓婄殑瀵硅薄寮曠敤錛岃岃鍏ㄥ眬琛ㄤ腑鐨勬煇涓璞″紩鐢紝鎴栬呭叾瀹冩煇涓潪GCGen0瀵硅薄寮曠敤浜?jiǎn)锛寴q欐牱瀵笹CGen0浠weep鐨勬椂鍊欏彲鑳戒細(xì)鎶婅繖涓瓨?gòu)z葷殑瀵硅薄褰撳仛鏃犳晥瀵硅薄鑰岄噴鏀炬帀錛岃繖縐嶆搷浣滆嚜鐒朵篃灝變細(xì)瀵艱嚧鏁翠釜紼嬪簭crash銆備簬鏄負(fù)浜?jiǎn)鎺у埗root閬嶅巻鐨勮寖鍥達(dá)紝鍙堣瑙ｅ喅榪欎釜闂錛屽闈濭CGen0瀵硅薄寮曠敤GCGen0瀵硅薄鐨勬椂鍊欙紝闇瑕佹妸榪欎釜闈濭CGen0鐨勫璞′篃鍔犲叆鍒皉oot閬嶅巻鍒楄〃涓幓銆傝繖鏃跺紩鍏ヤ簡(jiǎn)barrier錛屽浜庨潪GCGen0瀵硅薄寮曠敤GCGen0瀵硅薄鏃訛紝鎶婅繖涓潪GCGen0鐨勫璞℃斁鍒癰arrier鍒楄〃涓?br />
Major GC鏄竴涓畬鏁寸殑GC錛屽畠閬嶅巻鎵鏈夌殑root騫秏ark錛屽茍鎶婃墍鏈夌殑鏃犳晥鐨勫璞￠兘sweep閲婃斁銆?br />

GC鍚姩鐨勬椂鏈?/h2>

GC浠涔堟椂鍊欏惎鍔ㄦ槸涓涓渶瑕佷粩緇嗚冭檻鐨勯棶棰橈紝鐢變簬鎴戝疄鐜扮殑GC騫舵病鏈夎嚜宸辯鐞嗗唴瀛?Lua涔熸病鏈夎嚜宸辯鐞嗗唴瀛橈紝鎵鏈夊唴瀛樺垎閰嶉兘閫氳繃realloc)錛屾墍浠ユ垜鎶奊CGen0浠ｅ拰GCGen1浠ｇ殑瀵硅薄鏁伴噺浣滀負(fù)鍚姩鏃舵満鐨勮　閲忔寚鏍囷紝褰揋CGen0鍜孏CGen1鐨勫璞℃暟閲忓ぇ浜庡畠浠殑闃堝兼椂錛屽垎鍒惎鍔∕inor GC鍜孧ajor GC銆傛垜瑙夊緱瀵硅薄鐨勬暟閲忔瘮璧峰唴瀛樺崰鐢ㄥぇ灝?鍚勭澶嶆潅鐨凣C瀵硅薄瀵艱嚧鍐呭瓨鍗犵敤寰堥毦綺劇‘鐨勭粺璁★紝Lua鐨勫唴瀛樼粺璁′篃涓嶅綺劇‘)鏇磋兘鍙嶆槧GC鏃墮棿鐨勯暱鐭紝濡傛灉涓よ呯粨鍚堜篃璁鎬細(xì)鏇村ソ銆?br />
閫氳繃鍒ゆ柇GC瀵硅薄涓暟瓚呰繃闃堝兼椂鍚姩GC錛屽悓鏃墮渶瑕佸湪GC涔嬪悗鑷姩璋冩暣闃堝煎ぇ灝忋傛瘮濡傛煇浜涚▼搴忓緢蹇殑杈懼埌GCGen0鐨勯槇鍊煎茍鍦∕inor GC涔嬪悗鏈夎秴榪囦竴鍗婄殑瀵硅薄榪樻槸瀛樻椿鐨勶紝榪欐椂闇瑕佹妸闃堝艱皟澶э紝浠ュ噺灝慓C鍚姩鐨勬鏁幫紝榪欎釜闃堝間篃涓嶈兘鏃犻檺鎵╁ぇ錛岃繖涓嶄粎浼?xì)瀵艰嚧涓孌墊椂闂村唴鍐呭瓨鍗犵敤涓鐩翠笂鍗囷紝涔熶細(xì)瀵艱嚧涓鏃﹁Е鍙慓C鎵闇鎵弿鐨勫璞℃暟閲忓お澶氾紝GC鑰楁椂澶暱錛岀▼搴忚繍琛岀殑寤舵椂澧炲姞銆?br />

緇撹

涓轟簡(jiǎn)鍑忓皯stop-the-world鐨勬椂闂達(dá)紝寮曞叆鐨勫悇縐嶆柟娉曢兘浼?xì)璁〨C瀹炵幇闅懼害鍔犲ぇ銆侴C鏄竴涓鏉傜殑涓滆タ錛岀綉涓婃墍鑳芥壘鍒扮殑璧勬枡鏂囩珷浼間箮涓嶅お澶氾紝鑰屾湁鍏矴C鐨勪功錛岀洰鍓嶅彧鍙戠幇銆奣he Garbage Collection Handbook銆?/a>(鎴戣繕娌℃湁鐪嬭繃)錛岃岃繖鏈功鏃㈡病鏈塸df涔熸病鏈塳indle鐗堬紝鍙兘鍦ㄧ編鍥紸mazon涓婁拱綰歌川涔︺傚彟澶栦竴涓弬鑰冭祫鏂欏氨鏄悇涓璦鐨勫疄鐜版簮鐮佷簡(jiǎn)銆?/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>宸茬粡鏈夎繎涓や釜鏈堢殑鏃墮棿浜?jiǎn)锛寴q欐鏃墮棿浜嬫儏鐑?chǔ)锛堝锛?jí)錛屽鑷存病蹇?jī)鎯呭啓锛岀幇鍦ㄤ簤鍙栬ˉ涓娿?/p>


鐢熸垚epsilon-NFA

epsilon-NFA鏄寘鍚玡psilon杈癸紙絀鴻竟錛夌殑NFA錛屾妸綆鍗曟鍒欒〃杈懼紡杞崲鎴恊psilon-NFA鐨勬柟娉曞涓嬶細(xì)

姝ｅ垯琛ㄨ揪寮忥細(xì)”ab” 瀵瑰簲鐨別psilon-NFA鏄細(xì)


姝ｅ垯琛ㄨ揪寮忥細(xì)”a|b”瀵瑰簲鐨別psilon-NFA鏄細(xì)


姝ｅ垯琛ㄨ揪寮忥細(xì)”a*” 瀵瑰簲鐨別psilon-NFA鏄細(xì)


榪欐槸鏈鍩烘湰鐨?縐嶆鍒欒〃杈懼紡鐨凬FA琛ㄧず錛屽叾涓璦*鍦ㄥ疄闄呯殑姝ｅ垯琛ㄨ揪寮忓疄鐜頒腑閫氬父鐢熸垚鐨別psilon-NFA涓嶆槸榪欐牱鐨勶紝鍥犱負(fù)鏈変笅闈㈣繖浜涙鍒欒〃杈懼紡瀛樺湪錛?/p>

a{m}       閲嶅a錛宮嬈?br />a{m,n}     閲嶅a錛宮鍒皀嬈?br />a{m,}      閲嶅a錛岃嚦灝憁嬈?br />a+         閲嶅a錛岃嚦灝?嬈?br />a?         閲嶅a錛?嬈℃垨1嬈?/div>

鎵浠ュ浜巃*琛ㄧず閲嶅鑷沖皯0嬈＄殑瀹炵幇鍙互璺熶笂闈㈣繖浜涙鍒欒〃杈懼紡閲囩敤鐩稿悓鏂規(guī)硶鐨勫疄鐜般?/p>

鎸夌収榪欎簺鐢熸垚瑙勫垯灝卞彲浠ユ妸姝ｅ垯琛ㄨ揪寮忚漿鎹㈡垚epsilon-NFA錛屾垜浠ｇ爜涓嵆鎶婅繖浜涚敓鎴愯鍒欏疄鐜版垚涓涓狝ST鐨剉isitor銆?/p>

 

epsilon-NFA subset construction to DFA

鍦ㄧ敓鎴愪簡(jiǎn)epsilon-NFA涔嬪悗錛岄氬父浼?xì)鏈夊緢澶歟psilon鐨勮竟瀛樺湪錛屼篃浼?xì)鏈夊緢澶氭棤鐢ㄧ殑state瀛樺湪錛屾墍浠ラ氬父闇瑕佹妸epsilon杈規(guī)秷闄ゅ茍鍚堝茍state錛岃繖涓繃紼嬮噰鐢ㄧ殑綆楁硶鏄痵ubset construction錛屽涓嬶細(xì)

subset construction:
start_subset <- epsilon_extend(start_state)    // 鎶妔tart_state閫氳繃epsilon鎵╁睍寰楀埌璧峰subset
subsets <- { start_subset }                    // 鍒濆鍖杝ubsets
work_list <- subsets                           // 鍒濆鍖杦ork_list
while (!work_list.empty())
{
    subset <- work_list.pop_front()
    for edge in epsilon-NFA                    // 鍙栧嚭NFA涓殑姣忔潯杈?/span>
    {
        next_subset <- delta(subset, edge)     // 瀵箂ubset涓殑姣忎釜state閫氳繃edge鎵鍒拌揪鐨剆tate鐨別psilon杈規(guī)墿灞曞緱鍒皀ext_subset
        if (!subsets.exist(next_subset))       // 濡傛灉next_subset涓嶅瓨鍦ㄤ簬subsets涓紝鍒欐妸榪欎釜next_subset鍔犲叆鍒皐ork_list涓?/span>
            work_list.push_back(next_subset)
        map[subset, edge] = next_subset        // 鏋勫緩subset鍒皀ext_subset鐨勮竟鏄犲皠
        subsets.merge({next_subset})           // 鎶妌ext_subset鍚堝茍鍒皊ubsets
    }
}

delta:
next_subset <- { }    // 鍒濆鍖杗ext_subset涓虹┖闆嗗悎
for state in subset
{
    // 鍙栧嚭next_state騫跺皢瀹冮氳繃epsilon杈規(guī)墿灞曞緱鍒扮殑subset鍚堝茍鍒皀ext_subset涓?/span>
    next_state <- map[state, edge]
    if (next_state)
        next_subset.merge(epsilon_extend(next_state))
}

 

榪欓噷闈嬌鐢ㄤ簡(jiǎn)epsilon_extend錛屽畠鏄妸涓涓猻tate鐨勬墍鏈塭psilon杈硅兘鍒拌揪鐨剆tate鏋勬垚涓涓泦鍚堬紝姣斿涓婇潰姝ｅ垯琛ㄨ揪寮廰*瀵瑰簲鐨別psilon-NFA涓殑鎵鏈塻tate鐨別psilon_extend鏄細(xì)

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

瀵逛簬涓涓猠psilon-NFA鏉ヨ錛屾瘡涓猻tate鐨別psilon_extend鏄浐瀹氱殑錛屽洜姝ゅ彲浠ュepsilon-NFA涓殑姣忎釜state閮芥眰鍑篹psilon_extend騫朵繚瀛樹(shù)笅鏉ワ紝綆楁硶濡備笅錛?/p>

epsilon_extend_construct:
work_list <- { }
// 涓烘瘡涓猻tate鍒濆鍖杄psilon_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)
    // 鎶妔tate閫氳繃epsilon鎵鑳藉埌杈劇殑state鐨別psilon_extend
    // 鍚堝茍鍒板綋鍓峴tate鐨別psilon_extend
    for next_state in map[state, epsilon]
        state_epsilon_extend.merge(epsilon_extend(next_state))
    // 濡傛灉褰撳墠state鐨別psilon_extend鍙樺寲浜?jiǎn)涔嬪?br />    // 鎶婃墍鏈夐氳繃杈筫psilon鍒拌揪state鐨刾re_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鏋勯犳垚瀹屼箣鍚庯紝騫舵妸鏋勯犵殑subsets涓殑subset杞崲鎴怐FA涓殑state錛屽啀鎶奛FA涓櫎epsilon杈逛箣澶栫殑鎵鏈夎竟閮借漿鎹㈡垚DFA鐨勮竟錛岃繖鏍峰氨鎶奃FA鏋勯犲畬鎴愩?/p>


DFA minimization

浠嶯FA鏋勯犲畬鎴怐FA涔嬪悗錛岃繖鏃剁殑鐘舵佹暟閲忎竴鑸笉鏄渶灝戠殑錛屼負(fù)浜?jiǎn)鍑彏畱鏈緇堢敓鎴愮殑鐘舵佹満鐨勭姸鎬佹暟閲忥紝閫氬父浼?xì)瀵笵FA鐨剆tate榪涜鏈灝忓寲鏋勯狅紝榪欎釜綆楁硶鍏蜂綋濡備笅錛?/p>

minimization:
// 鎶婃墍鏈塻tate鍒掑垎鎴恆ccept鐨剆tate闆嗗悎鍜岄潪accept鐨剆tate闆嗗悎
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鍙互鎶妔tate_set鎷嗗垎鎴愪袱涓猻ubset錛岄偅灝辨妸鏂版媶鍒嗗嚭鏉ョ殑
            // 涓や釜subset鍚堝茍鍒皊tate_sets閲岄潰錛屽茍break緇х畫(huà)work_list涓彇鍑轟笅涓涓?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())


榪欓噷闈㈢殑split鏄妸涓涓猻tate_set鎸塭dge鍒掑垎鎴愪袱涓猻ubset錛屽嵆瀵逛簬state_set涓殑姣忎竴涓猻tate閮介氳繃榪欐潯杈筫dge鍒拌揪鐨剆tate灞炰簬涓嶅悓鐨剆tate_set鏃跺氨鎶妔tate_set鎷嗗垎鎴愪袱涓猻ubset銆傞鍏堟妸絎竴涓猻tate鍒掑垎鍒皊ubset1涓紝浠庣浜屼釜state寮濮嬮氳繃杈筫dge鍒拌揪鐨剆tate鎵灞炵殑state_set鍜岀涓涓猻tate閫氳繃杈筫dge鍒拌揪鐨剆tate鎵灞炵殑state_set涓哄悓涓涓殑鏃跺欙紝鎶婅繖涓猻tate鍒掑垎鍒皊ubset1涓紝鍚﹀垯鍒掑垎鍒皊ubset2涓?/p>

榪欎釜綆楁硶灝辮繖鏍蜂緷嬈℃妸鏈鍒濈殑涓や釜state_set錛坅ccept鐨剆tate緇勬垚鐨剆et鍜岄潪accept鐨剆tate緇勬垚鐨剆et錛夊垝鍒嗗埌涓嶈兘鍐嶅垝鍒嗕負(fù)姝紝姝ゆ椂灝辨妸鑳藉悎騫剁殑state閮藉悎騫跺埌浜?jiǎn)鍚屼竴涓猻tate_set涓紝榪欐椂鍙渶瑕佹妸姣忎釜state_set杞崲鎴愭渶緇堢姸鎬佹満涓殑state錛屽嵆鍙畬鎴怐FA鐨勬渶灝忓寲鏋勯犲茍杞崲鎴愮姸鎬佹満銆傚緱鍒扮姸鎬佹満涔嬪悗錛屽氨鍙互浣跨敤鐘舵佹満榪涜瀛楃鍖歸厤浜?jiǎn)銆?/p>



airtrack 2013-09-01 23:25 鍙戣〃璇勮
]]>姝ｅ垯琛ㄨ揪寮忓疄鐜幫紙涓錛?/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="hvzpftn" id="bd423564-6412-419c-8b26-45edcb529002" style="border-width: 0px; margin: 4px 0px 0px;"><p>瀹炵幇姝ｅ垯琛ㄨ揪寮忕殑鎯蟲(chóng)硶寰堟棭灝辨湁錛屽悇縐嶅師鍥犲鑷存病鏈夊仛錛屾渶榪戣姳浜?jiǎn)鐐规棄櫁村?a target="_blank">瀹炵幇浜?jiǎn)鍑犱釜绠鍗曠殑姝ｅ垯璇硶</a>錛屽垎鍒槸concatenation銆乤lternation鍜宑losure錛屽叾浠栬娉曞強(qiáng)metacharacter絳夋湁鏃墮棿浜?jiǎn)鏈夋兿x(chóng)硶浜?jiǎn)涔嬪悗鍐嶆墿灞曘?/p> <p> </p> <p>榪欎笁縐嶅熀鏈殑璇硶鍒嗗埆鏄搴旇繖鏍風(fēng)殑錛?/p> <p>concatenation: abc    琛ㄧず鍖歸厤瀛楃涓瞐bc</p> <p>alternation: abc|def   琛ㄧず鍖歸厤瀛楃涓瞐bc鎴栬卍ef</p> <p>closure: a*               琛ㄧず鍖歸厤闆朵釜鍒板涓猘鏋勬垚鐨勫瓧絎︿覆</p> <p> </p> <p>鎴戜滑鐭ラ亾姝ｅ垯琛ㄨ揪寮忔渶緇堥渶瑕佽漿鎹㈡垚鑷姩鏈烘墠鑳界敤鏉ュ尮閰嶅瓧絎︿覆錛屾垜瀹炵幇鐨勬鍒欓氳繃濡備笅鍑犱釜姝ラ鎶婃鍒欒〃杈懼紡杞崲鎴愯嚜鍔ㄦ満錛?/p> <p>姝ｅ垯琛ㄨ揪寮?>Parse鎴怉ST->鐢熸垚杈癸紙瀛楃錛夐泦鍚?>鐢熸垚NFA->NFA subset construction->杞崲鎴怐FA->DFA minimization</p> <p>鏈鍚庣敤DFA minimization涔嬪悗鏋勯犵殑鑷姩鏈烘潵鍖歸厤瀛楃涓層?/p> <p> </p> <h3>姝ｅ垯璇硶鐨勫垎鏋?/h3> <p>涓涓鍒欒〃杈懼紡鍐欏嚭鏉ワ紝瑕佽榪欎釜姝ｅ垯琛ㄨ揪寮忓尮閰嶅瓧絎︿覆絳夋搷浣滀箣鍓嶏紝鎴戜滑鍏堥渶瑕佷粠姝ｅ垯琛ㄨ揪寮忎腑鎻愬彇闇瑕佺殑淇℃伅騫跺湪姝ｅ垯璇硶閿欒鐨勬椂鍊欐彁紺洪敊璇紝榪欎釜榪囩▼鑷劧灝戜笉浜?jiǎn)parser銆備竴涓猵arser閫氬父鏄粠涓涓猯exer閲岄潰鑾峰彇涓涓猼oken錛岃屾鍒欒〃杈懼紡鐨則oken閮芥槸瀛楃錛岄偅涔坙exer涓嶉渶瑕佸仛浠諱綍鐨勫垎璇嶆搷浣滐紝鍙渶瑕佺畝鍗曠殑鎶婂瓧絎﹁繑鍥炵粰parser鍗沖彲銆?/p> <p>閭ｄ笁縐嶅熀鏈殑姝ｅ垯璇硶瀵瑰簲鐨凚NF涓猴細(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>榪欎釜parser鍒嗘瀽浜?jiǎn)姝ｅ垯琛ㄨ緫旨忎箣鍚庝骇鐢烝ST錛孉ST鐨刵ode綾誨瀷涓猴細(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鐨勫熀綾伙紝騫舵彁渚涙帴鍙ｅ疄鐜癡isitor妯″紡璁塊棶ASTNode綾誨瀷銆?/p> <p> </p> <h3>瀛楃錛堣竟錛夐泦鐨勬瀯閫?/h3> <p>AST鏋勯犲ソ浜?jiǎn)涔嬪悗锛岄渶瑕佹妸AST杞崲鎴怤FA銆傝娉曚腑鏈塠a-zA-Z0-9]榪欑瀛楃鍖洪棿琛ㄧず娉曪紝鎴戜滑鍙互鐢ㄦ渶綆鍗曞師濮嬬殑鏂規(guī)硶杞崲錛屽氨鏄妸鍖洪棿涓殑姣忎釜瀛楃閮借漿鍖栨垚鐩稿簲鐨勪竴鏉¤竟錛圢FA涓殑杈癸級(jí)錛岃繖鏍蜂竴鏉ヤ細(xì)瀵艱嚧瀛楃鍖洪棿瓚婂ぇ錛屽搴旇竟鐨勬暟閲忎細(xì)瓚婂錛屼嬌寰楀搴旂殑NFA涔熻秺澶с傚洜姝わ紝鎴戜滑闇瑕佹瀯閫犲尯闂村瓧絎﹂泦鍚堟潵鍑忓皯杈圭殑鏁伴噺銆?/p> <p>姣斿姝ｅ垯琛ㄨ揪寮忔槸錛歛[x-z]|[a-z]*e</p> <p>閭ｄ箞鎴戜滑甯屾湜瀵瑰簲鐨勫瓧絎﹂泦鍚堟槸榪欐牱錛歔a-a] [b-d] [e-e] [f-w] [x-z]</p> <p>榪欓渶瑕佹瀯閫犱竴涓瓧絎﹂泦錛屾瘡嬈℃彃鍏ヤ竴涓尯闂寸殑鏃跺欙紝鎶婃柊鎻掑叆鐨勫尯闂翠笌宸插瓨鍦ㄧ殑鍖洪棿榪涜鍒嗗壊錛屽垵濮嬫椂宸插瓨鍦ㄧ殑鍖洪棿闆嗕負(fù)絀猴紝閭ｄ箞姝ｅ垯琛ㄨ揪寮廰[x-z]|[a-z]*e鐨勫垝鍒嗘楠ゅ涓嬶細(xì)</p> <p>宸插瓨鍦ㄥ尯闂撮泦鍚坽}錛屾彃鍏a-a]錛屽緱鍒皗[a-a]}</p> <p>宸插瓨鍦ㄥ尯闂撮泦鍚坽[a-a]}錛屾彃鍏x-z]錛屽緱鍒皗[a-a], [x-z]}</p> <p>宸插瓨鍦ㄥ尯闂撮泦鍚坽[a-a], [x-z]}錛屾彃鍏a-z]錛屽緱鍒皗[a-a], [b-w], [x-z]}</p> <p>宸插瓨鍦ㄥ尯闂撮泦鍚坽[a-a], [b-w], [x-z]}錛屾彃鍏e-e]錛屽緱鍒皗[a-a], [b-d], [e-e], [f-w], [x-z]}</p> <p>榪欎釜鍖洪棿鏋勯犲畬鎴愪簡(jiǎn)涔嬪悗錛岃繕闇瑕佸湪鍚庨潰杞崲鎴怤FA杈圭殑鏃跺欙紝鏍規(guī)嵁瀛楃鍖洪棿鏌ヨ鍑哄湪榪欎釜闆嗗悎涓紝鐢卞摢鍑犱釜鍖洪棿鏋勬垚錛屾瘮濡傦細(xì)</p> <p>鏌ヨ鍖洪棿[a-a]錛屽緱鍒癧a-a]</p> <p>鏌ヨ鍖洪棿[x-z]錛屽緱鍒癧x-z]</p> <p>鏌ヨ鍖洪棿[a-z]錛屽緱鍒板尯闂碵a-a] [b-d] [e-e] [f-w] [x-z]</p> <p>鍦ㄨ漿鎹㈡垚NFA鏃訛紝闆嗗悎涓殑姣忎釜鍖洪棿閮藉搴斾竴鏉¤竟錛岃繖鏍風(fēng)浉瀵逛簬姣忎釜瀛楃瀵瑰簲涓鏉¤竟錛岃竟鐨勬暟閲忎笉浼?xì)澶銆?/p> <p>鏈変簡(jiǎn)榪欎箞涓涓泦鍚堟瀯閫犵殑綾諱箣鍚庯紝鎶婃鍒欑殑AST涓殑瀛楃淇℃伅鎻愬彇鍑烘潵鏋勯犲嚭榪欎箞涓泦鍚堝嵆鍙紝榪欐牱鍙渶瑕佸啓涓獀isitor灝卞畬鎴愪簡(jiǎn)錛?/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>杈歸泦鍚堟瀯閫犲畬鎴愪箣鍚庯紝涓嬩竴姝ュ氨鏄敓鎴怤FA浜?jiǎn)銆?/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>瀛︿範(fàn)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鏈榪戝嚑涓湀鍒╃敤涓婁笅鐝殑鏃墮棿鍦ㄥ涔?fàn)Haskell錛孒askell鏈変笉灝戣浜哄紑闃旀濊礬鐨勪笢瑗匡紝涔熸湁涓嶅皯鐪嬭搗鏉ュ緢緹庡ソ錛岀敤璧鋒潵涓嶉敊錛屼絾鏄璧鋒潵璐瑰姴鐨勪笢瑗褲侶askell鐨勮娉曞鐨勫樊涓嶅浜?jiǎn)涔嬪悗锛岀敤Haskell鍐欎簡(jiǎn)涓涓畝鍗曠殑C++浠ｇ爜琛岀粺璁″伐鍏?/a>錛屽啓榪囧嚑涓増鏈紝鐣欎笅浜?jiǎn)涓や釜锛屼竴涓槸鐩存帴鐢ㄦā寮忓尮閰嶅啓鐨勶紝涓涓槸灞卞浜?jiǎn)涓涓瀬綆鐨刾arse combinator錛岀劧鍚庣敤榪欎釜灞卞鐨刾arse combinator鍐欎簡(jiǎn)涓涓増鏈紝浠ｇ爜浼拌鍐欑殑閮芥瘮杈冪儌錛屼互鍚庤繘闃跺涔?fàn)涔嬪悗鏈夋棄櫁村啀鏀广傝繖涓粺璁″伐鍏峰茍涓嶆槸瀹屾暣鐨勫鐞咰++鐨勮娉曪紝涔熸病瀵瑰湪瀛楃涓插拰瀹忓畾涔夐噷闈㈢殑"http://" "/*" "*/"鍋氬鐞嗭紝鍥犳瀵規(guī)煇浜汣++紼嬪簭緇熻浠ｇ爜琛岋紝鍙兘涓嶅畬鍏ㄦ紜紝浣嗘槸鍩烘湰鍙互鐢ㄣ?/p>


data, type, newtype


Haskell閲岄潰鐢╠ata鏉ュ畾涔夋暟鎹被鍨嬶紝瀹冨彲浠ユ槸榪欐牱錛?br /> 

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

 

絎竴琛屽畾涔変簡(jiǎn)涓涓狹ode錛屽寘鍚玆eadMode鍜學(xué)riteMode錛?/p>

絎簩琛屽畾涔変簡(jiǎn)涓涓櫘閫氭暟鎹被鍨婼ome錛屽寘鍚竴涓狪nt鏁版嵁鍜屼竴涓猄tring鏁版嵁錛?/p>

絎笁琛屽畾涔変簡(jiǎn)涓涓櫘閫氭暟鎹被鍨婽hing錛屽寘鍚被鍨嬩負(fù)Int鐨刟鍜岀被鍨嬩負(fù)String鐨刡錛?/p>

絎洓琛屽畾涔変簡(jiǎn)涓涓鍚堟暟鎹被鍨婩unc錛岄噷闈㈡湁涓嚱鏁扮被鍨嬩負(fù)(a -> b)鐨勬暟鎹甪unc銆?/p>


絎竴縐嶇浉褰撲簬C++涓殑enum class錛岀浜岀絎笁縐嶇浉褰撲簬鏅氱殑struct鏁版嵁錛岀浜岀鍜岀涓夌鐨勫尯鍒槸絎簩縐嶄笉鑳界洿鎺ュ彇鍒癐nt鍜孲tring鐨勬暟鎹紝絎笁縐嶅彲浠ラ氳繃a,b鍙栧埌鏁版嵁錛岀鍥涚鐩稿綋浜嶤++鐨則emplate class(struct)錛岀鍥涚鍐欐垚榪欐牱鏉ュ畾涔夊叿浣撶殑鏁版嵁綾誨瀷錛?br />

type IntStringFunc = data Func Int String

 

type鍦ㄨ繖閲屽畾涔変簡(jiǎn)涓涓埆鍚岻ntStringFunc綾誨瀷錛屽寘鍚簡(jiǎn)涓涓嚱鏁扮被鍨嬫槸Int -> String鐨刦unc鐨勬暟鎹紝榪欓噷鐨則ype鐩稿綋浜嶤++ 11鐨剈sing鍒悕錛屽洜涓哄畠榪樺彲浠ヨ繖鏍峰啓錛?/p>


type IntBFunc b = data Func Int b


鍦–++ 11涓紝using鍖呭惈浜?jiǎn)typedef鐨勫姛鑳斤紝涔熸敮鎸佷簡(jiǎn)template class鐨勭被鍨媡ypedef錛屽涓嬶細(xì)


template <typename T, typename P>
class SomeType;

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


newtype瀹氫箟鐨勬暟鎹被鍨嬭窡type綾誨瀷錛屼笉榪噒ype瀹氫箟鐨勭函綺規(guī)槸鍒悕錛屽埆鍚嶇被鍨嬭窡鍘熷綾誨瀷鏄竴鑷寸殑錛岃宯ewtype鍒欏畾涔夌殑鏄竴涓獁rapper錛屾槸涓縐嶆柊鐨勬暟鎹被鍨嬶紝鎵浠ユ槸newtype銆俷ewtype瀹氫箟鐨勭被鍨嬫槸緙栬瘧鏃舵湡鐨剋rapper錛孒askell淇濊瘉娌℃湁榪愯鏃舵湡鐨勫紑閿錛宯ewtype瀹氫箟鐨勮窡data綾諱技錛?br />

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


妯″紡鍖歸厤


涓婇潰璇撮亾data瀹氫箟鐨勭浜岀鏁版嵁綾誨瀷錛屽寘鍚獻(xiàn)nt鍜孲tring鐨勬暟鎹紝浣嗘槸涓嶈兘鐩存帴鍙栧埌榪欎袱涓暟鎹紝鎵浠ユ垜浠渶瑕佸畾涔変袱涓嚱鏁版潵鍙栧叾涓殑鏁版嵁錛?/p>


some = Some 0 "test"  -- 瀹氫箟涓涓暟鎹紝綾誨瀷涓篠ome

-- 瀹氫箟涓や釜鍑芥暟鐢ㄤ簬鑾峰彇Some鐨勬暟鎹?br />getSomeInt Some i _ = i
getSomeString Some _ s = s

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


榪欓噷鐨刧etSomeInt鍜実etSomeString鍑芥暟閮芥槸閲囩敤妯″紡鍖歸厤鏉ュ疄鐜幫紝妯″紡鍖歸厤灝辨槸鎶婃暟鎹殑緇撴瀯鐩存帴鍐欏湪浠ｇ爜涓潵鍖歸厤錛岀劧鍚庡彇鍑烘兂瑕佷嬌鐢ㄧ殑鏁版嵁鍗沖彲銆?/p>


Haskell閲屽父鐢ㄧ殑Maybe鏁版嵁綾誨瀷鏄繖鏍峰畾涔夌殑錛?/p>


data Maybe a = Nothing
                     | Just a


濡傛灉瑕佸彇鐢∕aybe閲岄潰鐨勫鹼紝鎴戜滑閫氬父浣跨敤妯″紡鍖歸厤鏉ヨ幏鍙栨暟鎹紝濡備笅錛?/p>


useMaybe maybe =
     case maybe of
          Nothing -> …  -- Maybe鐨勫兼槸絀?br />          Just a -> …  -- 鐩存帴浣跨敤a鍗沖彲

useMaybe (Just 1)


涓嬮潰璋冪敤useMaybe鐨勫嚱鏁頒綋鍐呭彇鍒扮殑a鐨勫煎氨鏄?銆?/p>


Haskell閲岀殑鍐呯疆鏁版嵁綾誨瀷list錛屾瘮濡俒1, 2, 3, 4]錛屼嬌鐢?鍙互鎶婃柊鐨勫厓绱犳坊鍔犲埌l(fā)ist澶撮儴錛屽嵆錛?/p>


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


榪欐牱鐨勭壒鎬у悓鏍峰彲浠ョ畝鍗曠殑濂楃敤鍦ㄦā寮忓尮閰嶄笂闈紝濡備笅錛?/p>


useList [] = 
useList (x:xs) = … -- x鏄痩ist閲岄潰鐨勭涓涓厓绱狅紝xs鏄痩ist鐨勫熬閮?/div>


妯″紡鍖歸厤鍙互寰堢洿瑙傜殑鍖歸厤鏁版嵁鐨勫師濮嬭〃紺烘柟寮忥紝騫跺彲浠ュ彇鍑哄叾涓湁鐢ㄧ殑鍊煎仛鍏朵粬鎿嶄綔錛屽畠鏄竴涓畝鍗曠洿瑙傛湁鏁堢殑鎿嶄綔鏁版嵁鐨勬柟寮忥紝鐢氳嚦鍙互鍦ㄥ祵濂楀緢娣辯殑tuple鏁版嵁閲岄潰鐩存帴鍙栧嚭鎯寵鐨勬暟鎹紝鑰屼笉鐢ㄥ儚C++閭ｆ牱璋冪敤tuple::get涔嬬被鐨勫嚱鏁版潵鍙栧嚭鍏朵腑鐨勫鹼紝姣斿錛?/p>


getTupleValue (_, _, _, (_, _, (x:xs))) = … -- 鍙栧緱x鍜寈s鏁版嵁


Visitor妯″紡鍜孋++ template


鐜嬪灎璇磋璁℃ā寮?/a>涓煎緱涓鎻愮殑妯″紡涓嶅錛屽叾涓箣涓鐨剉isitor妯″紡鏄湪妯℃嫙妯″紡鍖歸厤銆倂isitor妯″紡閫氬父鏄闂幏鍙栨煇涓戶(hù)鎵跨被灞傛鏋勬垚鐨勪竴涓爲(wèi)褰㈢粨鏋勪腑鐨勬煇涓妭鐐圭殑鍏蜂綋綾誨瀷錛屽茍瀵硅繖縐嶅叿浣撶被鍨嬪仛鏌愪簺鎿嶄綔錛岃屾ā寮忓尮閰嶆槸鍙互浠庡鏉傜殑鏁版嵁緇撴瀯涓洿鎺ュ彇鍑烘兂瑕佺殑鏁版嵁銆?/p>


C++鐨則emplate meta-programming涔熷彲浠ョ湅鎴愭槸涓縐嶆ā寮忓尮閰嶏紝C++閲岄潰钁楀悕鐨凢actorial姹傚兼槸榪欐牱鐨勶細(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;


鑰岃繖孌典唬鐮佸鏋滅敤Haskell鍐欐槸榪欐牱鐨勶細(xì)


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

v = factorial 10


C++涓殑妯℃澘鍙傛暟灝辨槸鐢ㄦ潵鍋氭ā寮忓尮閰嶇殑錛屾瘡鐗瑰寲涓縐嶇被鍨嬪氨鍙互鍖歸厤鏌愮綾誨瀷錛岀劧鍚庡閭ｇ鍖歸厤鐨勭被鍨嬪仛鐩稿簲鐨勬搷浣溿侰++鐨則emplate meta-programming鏄紪璇戞椂鏈燂紙緙栬瘧鍣ㄨ繍琛屾湡錛夌殑琛屼負(fù)錛屾墍浠ュ畠鍙兘鎿嶄綔綾誨瀷浠ュ強(qiáng)緙栬瘧鏃舵湡鑳藉紜畾鐨勫鹼紝鑰屾ā寮忓尮閰嶆槸紼嬪簭鏈韓鐨勮繍琛屾湡鐨勮涓恒?/p>


Currying


Haskell鐨凜urrying鏄竴涓緢鏈夌敤鐨勭壒鎬э紝浣嗘槸鎴戣寰楄繖涓壒鎬ф互鐢ㄧ殑璇濓紝涔熶細(xì)璁╃▼搴忎唬鐮佺殑鍙鎬ч檷浣庝笉灝戙傛墍璋揅urrying灝辨槸鍙互鍚戜竴涓鍙傛暟鐨勫嚱鏁頒紶閫掓瘮瀹冩墍闇鐨勫弬鏁頒釜鏁版洿灝戠殑鍙傛暟鍚庤繑鍥炵敓鎴愮殑涓涓柊鍑芥暟鎺ュ彈鍓╀綑鐨勫弬鏁扮殑鍑芥暟銆侶askell閲岀殑鍑芥暟榛樿閮芥槸curried鐨勶紝鎵浠askell閲岄潰鐨勫嚱鏁板彲浠ラ殢鎰廲urrying錛屾瘮濡傦細(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鐨勫疄鐜版槸浣跨敤鐨勫崟鍙傛暟鐨刲ambda鏋勬垚鐨勯棴鍖?closure)錛宎dd鍙互鐪嬫垚鏄帴鍙椾竴涓狪nt鍙傛暟榪斿洖涓涓嚱鏁幫紝榪欎釜鍑芥暟鐨勭被鍨嬫槸Int -> Int銆?/p>


Partial application


Currying鏄竴涓粠宸﹀埌鍙抽儴鍒嗕紶鍙傛暟鐨勪竴涓繃紼嬶紝涔熷氨鏄笉浼?xì)鍑虹幇鍙傛暟a榪樻病緇欙紝灝辯粰浜?jiǎn)鍏蜂綋鐨勫弬鏁癰鐨勬儏鍐點(diǎn)傚鏋滅‘瀹氳鍏堢粰鍙傛暟b錛岄偅涔堝畠鏄疨artial application錛屽涓嬶細(xì)


addTwo a = add a 2

addTwo 1 -- result: 3

(+ 2) 1 -- result: 3


(+ 2)榪欑綾諱技鐨勭敤娉曞彲鑳戒細(xì)浣滀負(fù)鍙傛暟浼犻掔粰鍙﹀涓涓嚱鏁般侾artial application鏄竴縐嶆洿瀹芥硾鐨勬蹇碉紝涓婇潰鐨凜urrying鏄竴縐峆artial application銆?/p>


姝ｅ鐜嬪灎鎵璇?/a>鐨勶紝濡傛灉涓涓嚱鏁版帴鍙椾簡(jiǎn)澶氫釜鍙傛暟錛屼絾鏄繖涓嚱鏁板湪瀹為檯璋冪敤涓Currying浜?jiǎn)寰堝娆″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鍑芥暟鐨勬椂鍊欙紝鎴戜滑鏄緢闅懼垽鏂璬o5鍒板簳鎺ュ彈鍑犱釜鍙傛暟錛屽挨鍏舵槸do5璺熷墠闈㈠嚑涓猟oN鍑芥暟涓嶅湪鍚屼竴涓湴鏂瑰畾涔夛紝寰堟湁鍙兘do5鍙槸浼犻掔粰鏌愪釜鍑芥暟鐨勫弬鏁幫紝褰撶劧濡傛灉緇欐瘡涓嚱鏁伴兘鍔犱笂鍑芥暟綾誨瀷澹版槑浼?xì)娓呮櫚璁稿銆傚綋Currying紕板埌浜?jiǎn)flip涔嬪悗錛岄偅浠ｇ爜鐨勫彲璇繪т細(xì)闄嶄綆鏇村錛屾墍浠ユ垜瑙夊緱Currying鏄竴涓緢鏈夌敤鐨勭壒鎬э紝浣嗘槸濡傛灉琚互鐢ㄧ殑璇濓紝閭ｄ唬鐮佺殑鍙鎬т細(xì)鏄竴涓棶棰樸?/p>


C++: function + bind


C++涓殑function + bind鍏跺疄鏄竴縐峆artial application瀹炵幇錛屾瘮濡傦細(xì)


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

std::function<int (int, int)> 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);


鎴戣寰桟++鐨刦unction + bind浼?xì)姣擟urrying鐨勫彲璇繪ц濂戒竴浜涳紝姣曠珶鎴戜滑鍙互瀹屾暣鐪嬪埌f1鍜宖2鐨勫嚱鏁扮被鍨嬶紝鐭ラ亾鍙傛暟綾誨瀷鍙?qiáng)涓暟鍜寴q斿洖鍊鹼紝鏄湁鍒╀簬浠ｇ爜鐨勫彲璇繪х殑錛屽綋鐒惰繖閲屽畬鍏ㄥ彲浠ヤ笉鍐欏嚭f1鍜宖2鐨勭被鍨嬶紝閲囩敤auto錛屾垜浠悓鏍峰彲浠ヤ粠璋冪敤鍑芥暟bind鐨刾laceholder鐨勪釜鏁板緱鐭ind涔嬪悗鐨刦unction鐨勫弬鏁頒釜鏁幫紝榪欐牱鎴戜滑鍙互涓嶇敤鐪嬪埌鍑芥暟Func鐨勫０鏄庯紝灝辯煡閬撻渶瑕佷紶鍑犱釜鍙傛暟銆俧unction + bind璺烠urrying涓鏍蜂細(xì)褰卞搷浠ｇ爜鐨勫彲璇繪э紝濡傛灉宓屽鐨勫眰嬈¤秺澶氾紝鍙鎬у氨瓚婂樊錛屾墍浠ヤ嬌鐢ㄨ繖浜涚壒鎬х殑鏃跺欎笉瑕佽繃搴︺?/p>


typeclass


Haskell鐢╰ypeclass鏉ヨ〃紺轟竴涓猚oncept錛屽畠鏄竴緇勬娊璞″嚱鏁扮殑闆嗗悎錛屼竴涓弧瓚蟲(chóng)煇涓猼ypeclass鐨勬暟鎹被鍨嬶紝瀹冨氨鍙互璺熷叾浠栦嬌鐢ㄨ繖涓猼ypeclass鐨勫嚱鏁版垨鑰呮暟鎹被鍨嬬粍鍚堜嬌鐢ㄣ倀ypeclass涓鑸繖涔堝畾涔夛細(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


瀹冨畾涔変簡(jiǎn)涓涓彨Monad鐨則ypeclass錛岃繖涓猼ypeclass鐨刢oncept閲屾湁鍥涗釜鍑芥暟錛屽垎鍒槸(>>=), (>>), return鍜宖ail錛宮鏄竴涓甫綾誨瀷鍙傛暟鐨勬暟鎹被鍨嬨傛垜浠笂闈㈢煡閬撲簡(jiǎn)Maybe鏄竴涓甫綾誨瀷鍙傛暟鐨刣ata綾誨瀷錛屽畠瀹氫箟濡備笅錛?/p>


data Maybe a = Nothing
                     | Just a


鏃㈢劧Maybe鏄竴涓甫綾誨瀷鍙傛暟鐨刣ata錛岄偅瀹冨氨婊¤凍Monad typeclass涓璵鐨勯渶姹傦紝鍥犳鍙互鎶奙aybe瀹氫箟鎴怣onad錛屽涓嬶細(xì)


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

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

     return = Just

     fail = error


榪欓噷(\_ -> maybeB)瀹氫箟浜?jiǎn)涓涓猯ambda錛屽弬鏁?_ 绱ф帴 \錛?> 鍚庨潰鍒欐槸鍑芥暟浣撱傚嚱鏁?>>)鍜宖ail鏄彲浠ヤ綔涓洪粯璁ゅ疄鐜版斁鍒癱lass Monad鐨勫畾涔夐噷闈紝鑰宨nstance Monad鐨勬椂鍊欏彧闇瑕佸疄鐜?>>=)鍜宺eturn鍗沖彲銆?/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


瀵逛簬鍐呯疆list綾誨瀷[a]錛屼篃鏄甫鏈変竴涓被鍨嬪弬鏁癮錛屽洜姝わ紝鎴戜滑鍚屾牱鍙互鎶奫] instance鎴愪負(fù)class Monad錛屽涓嬶細(xì)


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


鍑芥暟(>>)鍜宖ail鎴戜滑淇濈暀榛樿鐨勫疄鐜板嵆鍙?/p>


Monad


涓婇潰瀹炵幇鐨勫畾涔夌殑typeclass灝辨槸Haskell钁楀悕鐨凪onad錛屽畠鏄粍鍚堝叾浠栨搷浣滅殑涓涓熀紜typeclass錛屾槸涓巒o pure浜や簰鐨勪竴涓噸瑕佸獟浠嬨備竴鑸儏鍐典笅Monad鏈変袱縐嶏紝涓縐嶆槸鏁版嵁wrapper錛屼竴縐嶆槸action鐨剋rapper銆備笂闈㈠畾涔夌殑Maybe Monad鍜宭ist Monad閮芥槸鏁版嵁綾誨瀷鐨剋rapper錛屽畠浠疄鐜頒簡(jiǎn)Monad瀹氫箟鐨勬帴鍙ｅ嚱鏁幫紝鎴戜滑榪樺彲浠ュ皢鍏跺畠data instance鎴怣onad錛屽彧闇瑕侀伒寰簡(jiǎn)Monad鐨勬帴鍙ｅ嵆鍙?/p>


鎴戜滑鐭ラ亾Haskell鐨勫嚱鏁伴兘鏄痯ure鐨勶紝娌℃湁浠諱綍鐘舵佺殑鍑芥暟錛屼絾鏄笌鐜板疄涓栫晫浜や簰蹇呯劧闇瑕佸獎(jiǎng)鍝嶆垨淇敼鏌愮鐘舵侊紝騫朵笖浼?xì)闇瑕侀『搴忔墽琛屾煇浜涙搷浣滀互瀹屾垚浜や簰銆傛垜浠妸action鎿嶄綔灝佽鍦ㄤ竴涓猟ata閲岄潰錛屽茍璁╁畠instance Monad錛屼負(fù)浜?jiǎn)璁╁墠涓涓猘ction鐨勭粨鏋滃間綔涓烘煇縐嶇姸鎬佸線(xiàn)涓嬩紶閫掞紝Monad鐨?>>=)灝辨槸涓轟簡(jiǎn)榪欎釜鐩殑鑰屽瓨鍦ㄧ殑錛?>>=) 鍑芥暟鐨勭被鍨嬫槸 m a -> (a -> m b) -> m b錛屽畠鐨勬剰鎬濆氨鏄墽琛屽皝瑁呭湪m a榪欎釜鏁版嵁閲岄潰鐨刟ction錛岀劧鍚庢妸榪欎釜action鐨勭粨鏋滃煎仛涓哄弬鏁頒紶閫掔粰(>>=)鐨勭浜屼釜鍙傛暟(a -> m b)錛岀浜屼釜鍙傛暟鏄竴涓嚱鏁幫紝榪欏嚱鏁板彲浠ュ彇鐢ㄧ涓涓弬鏁扮殑緇撴灉錛屽啀榪斿洖涓涓猰 b鐨勬暟鎹紝m b鐨勬暟鎹篃鏄竴涓猘ction鐨勫皝瑁咃紝榪欐牱褰撲竴榪炰覆鐨?>>=)鏀懼埌涓璧風(fēng)殑鏃跺欙紝灝卞彲浠ユ妸涓涓姸鎬佸間綔涓篴ction鐨勫弬鏁板拰緇撴灉鍊煎線(xiàn)涓嬩紶閫掋?/p>


浠嶮onad鐨勫嚱鏁?>>)鐨勫疄鐜版垜浠彲浠ョ湅鍒幫紝瀹冩妸m a鐨刟ction鐨勭粨鏋滃間涪寮冪洿鎺ヨ繑鍥炰簡(jiǎn)m b錛屽綋涓榪炰覆鐨?>>)鏀懼埌涓璧風(fēng)殑鏃跺欙紝鍏跺疄灝辨槸璁╀竴緇刟ction欏哄簭鎵ц銆傞氳繃(>>=)鍜?>>)錛屽彲浠ユ妸涓緇凪onad action data緇勫悎璧鋒潵銆?/p>


IO Monad


IO Monad鏄竴涓妸IO action灝佽鐨刣ata錛屾垜浠彲浠ヤ嬌鐢↖O Monad涓庡鐣岃繘琛岃緭鍏ヨ緭鍑轟氦浜掞紝涓嬮潰鏄竴涓?hello world"錛?/p>


helloWorld = do
     putStr "hello "
     putStrLn "world"


榪欓噷do璇硶緋栧叾瀹炲氨鏄敤鐨凪onad鏉ュ疄鐜幫紝灞曞紑涔嬪悗鏄繖鏍鳳細(xì)


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


鐢?>>)鍑芥暟紜畾(putStr "hello ")鍜?putStrLn "world")闇瑕佹槸鍚屼竴涓狹onad綾誨瀷錛屾垜浠彲浠ユ煡璇㈠埌putStr鍜宲utStrLn鐨勭被鍨嬫槸String -> IO ()錛岄偅涔?putStr "hello ")鍜?putStrLn "world")鐨勭被鍨嬮兘鏄疘O ()錛宧elloWorld鍑芥暟鎶婁袱涓狪O ()鐨刟ction鏁版嵁欏哄簭緇勫悎璧鋒潵鐢熸垚涓涓柊鐨処O ()錛屽綋榪欎釜helloWorld IO action琚墽琛岀殑鏃跺欙紝瀹冧細(xì)渚濇鎵ц灝佽鍦ㄥ畠閲岄潰鐨処O action銆傛垜浠彲浠ユ妸helloWorld IO action鏀懼埌Main鍑芥暟閲岄潰鐒跺悗緙栬瘧鎵ц錛屼篃鍙互鐩存帴鍦╣hci閲岄潰鎵ц銆?/p>


鎴戜滑鍙互鑷繁瀹氫箟鏌愮data鍐峣nstance Monad錛岃繖鏍峰彲浠ユ瀯鎴愪竴緇刣ata combination錛屽彲浠ュ疄鐜頒換鎰忕殑action combine銆傛垜灞卞鐨勬瀬綆鐨刾arse combinator鐨勬暟鎹被鍨嬪畾涔夊涓嬶細(xì)


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


榪欓噷Parser甯︿竴涓被鍨嬪弬鏁癮錛宒eriving (Monad, MonadState (ByteString, Context))琛ㄧず緙栬瘧鍣ㄨ嚜鍔╥nstance Monad鍜宨nstance MonadState (ByteString, Context)銆傛湁浜?jiǎn)杩欎釜Parser涔嬪悗錛屽彲浠ュ啓鍑虹畝鍗曠殑鍑犱釜combinator錛岀劧鍚庝嬌鐢ㄨ繖鍑犱釜combinator緇勫悎鎴愭洿鍔犲鏉傜殑錛岀粍鍚堢殑榪囩▼灝辨槸鍒╃敤浜?jiǎn)Monad鐨勭粍鍚堣兘鍔涖傚綋鎵闇鐨刢ombinator閮藉疄鐜頒簡(jiǎn)濂戒簡(jiǎn)涔嬪悗錛屽彲浠ユ渶緇堝疄鐜頒竴涓狿arser a鏉ュ垎鏋愭暣涓狢++鏂囦歡錛?/p>


file = repeatP $ spaceLine <||> normalLine


file灝辨妸鍒嗘瀽鏁翠釜C++鏂囦歡鎵闇鐨勬搷浣滈兘combine鍒頒簡(jiǎn)涓璧鳳紝鏈変簡(jiǎn)榪欎釜鍒嗘瀽鏁翠釜鏂囦歡鐨凱arser a涔嬪悗錛岄渶瑕佹妸瀹冭窇璧鋒潵錛岄偅灝遍渶瑕佸畾涔変笅闈㈣繖涓嚱鏁幫細(xì)


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


榪欎釜鍑芥暟鎺ュ彈涓涓狿arser a鍜屼竴涓枃浠跺唴瀹笲yteString浣滀負(fù)鍙傛暟錛屾妸鏁翠釜Parser a灝佽鐨刟ction鐢ㄤ簬鍒嗘瀽鏂囦歡鍐呭錛屽啀浜х敓涓涓垎鏋愮粨鏋溿?/p>


榪欓噷鐨刦ile錛屽畠鏄竴涓竴涓皬鐨刢ombinator鏋勬垚鐨勶紝姣忎釜combinator鏄竴涓猘ction鍔犱笂瀹冩墍闇鏁版嵁鏋勬垚涓涓?#8220;闂寘”鍐嶅瓨鏀懼埌Parser a鐨刣ata閲岄潰錛屽叾瀹炲彲浠ヨ涓哄疄鐜頒簡(jiǎn)Monad鐨勬暟鎹被鍨嬫槸涓涓?#8220;闂寘”鐨勮澆浣撱傚湪鍏跺畠璇█閲岋紝鎴戜滑鍙互浣跨敤闂寘鏉ュ疄鐜癱ombinator錛屾垜璁板緱涓ゅ勾鍗婂墠錛屾垜浣跨敤lua鐨勯棴鍖呭疄鐜頒簡(jiǎn)涓緇勬父鎴忓壇鏈唴瀹圭帺娉曟搷浣滅殑combinator錛岃繖浜涢棴鍖呰嚜鐢辯粍鍚堝湪涓璧蜂箣鍚庡氨鑳藉畬鎴愪竴涓壇鏈腑鎵闇鐨勭帺娉曟搷浣溿?/p>


Monad transformer


涓縐峂onad綾誨瀷鍙兘灝佽鍜岀粍鍚堜竴縐峚ction鎿嶄綔錛岃屼笌澶栫晫浜や簰鐨勬椂鍊欙紝寰堝鏃跺欎竴縐峂onad綾誨瀷鏄笉澶熺殑錛屼負(fù)浜?jiǎn)璁╁绉峂onad綾誨瀷緇勫悎鍦ㄤ竴璧鳳紝灝遍渶瑕佸畾涔塎onad transformer錛屽畠璺烳onad涓鏍蜂篃鏄竴涓暟鎹被鍨嬶紝涓嶅悓鐨勬槸瀹冩帴鍙楄嚦灝戜袱縐嶇被鍨嬪弬鏁幫紝鍏朵腑涓縐嶅氨鏄疢onad鐨勭被鍨嬶紝榪欐牱灝卞彲浠ユ妸鏌愪釜Monad綾誨瀷宓屽鍦ㄥ畠閲岄潰銆?/p>


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


榪欓噷StateT灝辨槸涓涓狹onad transformer錛屽畠鍏佽宓屽涓涓狹onad m綾誨瀷錛屽畠鏄痶ypeclass MonadState鐨勪竴涓猧nstance錛孧onadState濡備笅錛?/p>


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


涓轟簡(jiǎn)璁㎝onad transformer鍙互宓屽榪汼tateT錛屽叾瀹冪被鍨嬬殑Monad transformer灝遍渶瑕乮nstance MonadState錛岃孲tateT Monad transformer涓轟簡(jiǎn)鍙互宓屽鍦ㄥ叾瀹僊onad transformer涓紝灝遍渶瑕佸鍏跺畠Monad transformer鎶借薄鍑烘潵鐨則ypeclass instance錛岀鍚堣繖縐嶈鍒欑殑Monad transformer灝卞彲浠ョ浉浜掍箣闂村祵濂椾簡(jiǎn)錛屽祵濂楃殑灞傛鍙互浠繪剰娣憋紝榪欐牱鏋勯犲嚭鏉ョ殑Monad閲岄潰鏈変釜Monad transformer stack錛岃岃繖涓柊鏋勯犲嚭鏉ョ殑Monad灝卞彲浠ヤ嬌鐢ㄥ縐峂onad鐨刟ction鎿嶄綔緇勫悎鍦ㄤ竴璧蜂簡(jiǎn)銆?/p>


Monad transformer浼?xì)甯︽潵涓涓棶棰橈紝濡傛灉鎯沖畾涔変竴涓柊鐨凪onad transformer錛岄渶瑕佸厛鎶借薄鍑?guó)櫩欎釜Monad transformer鐨則ypeclass錛屽氨鍍廙onadState typeclass涓鏍鳳紝鐒跺悗鎶婂叾瀹僊onad transformer閮絠nstance榪欎釜鏂版娊璞″嚭鏉ョ殑typeclass錛岃繖鏍鋒墠鑳借榪欎釜鏂扮殑Monad transformer宓屽鍦ㄥ叾瀹冪殑Monad transformer涔嬩腑錛屾帴鐫錛屼負(fù)浜?jiǎn)璁╁叾瀹僊onad transformer鑳藉宓屽鍦ㄦ柊鐨凪onad transformer涔嬩腑錛岄渶瑕佹妸鏂扮殑Monad transformer instance鍏跺畠Monad transformer鎶借薄鐨則ypeclass銆?/p>


鎴戣寰楀叾瀹濰askell涓轟粈涔堜細(xì)鏈塎onad鍜孧onad transformer鐨勫瓨鍦紝鏄洜涓篐askell鏄竴涓函鍑芥暟寮忚璦錛屽畠鏈韓娌℃湁欏哄簭鎵ц璇彞鐨勮兘鍔涳紝涓轟簡(jiǎn)鑳借Haskell鎷ユ湁淇敼澶栭儴鐘舵佸茍鑳藉欏哄簭鎵ц璇彞鐨勮兘鍔涳紝寮曞叆浜?jiǎn)Monad錛屽張涓轟簡(jiǎn)璁╁縐峚ction鐨凪onad鑳藉緇勫悎鍒頒竴璧鳳紝鐢變簬Monad鏄竴涓猟ata type錛屽畠涓嶈兘綆鍗曠殑緇勫悎鍒頒竴璧鳳紝鍥犱負(fù)綾誨瀷涓嶄竴鑷達(dá)紝涓轟簡(jiǎn)璁╁畠浠粍鍚堝埌涓璧鳳紝鍙堝紩鍏ヤ簡(jiǎn)鏇翠竴鑸寲鐨凪onad transformer錛岃榪欎簺Monad transformer宓屽鍦ㄤ竴璧鋒瀯鎴愪竴涓猻tack錛屾墠鑳藉皢榪欎簺涓嶅悓綾誨瀷鐨凪onad緇勫悎銆?/p>


Lazy evaluation


Haskell閲岄潰浣跨敤鐨勬槸鎯版ф眰鍊兼柟寮忥紝鐜嬪灎璇?a >Haskell鐨勬儼鎬ф眰鍊?/a>鏄竴涓緢涓ラ噸鐨勯棶棰樸傛垜鐩墠涔熻寰楁儼鎬ф眰鍊兼槸涓縐嶈礋鎷咃紝鍥犱負(fù)鎯版ф眰鍊鹼紝浼?xì)鋴慑緱绋嬪簭寰堝?guī)槗灝卞嚭鐜皊pace leak錛屾垜鍐欑殑閭ｄ袱涓増鏈殑緇熻C++浠ｇ爜琛屽伐鍏烽兘鏈夎繖涓棶棰橈紝鍥犱負(fù)瀹冩槸鎯版ф眰鍊鹼紝鎵浠ュ畠浼?xì)鎶婃暣涓洰褰曠殑鏁版嵁鍏ㄩ儴鍙栧嚭鏉ユ瀯閫犲瓨鏀懼埌鍐呭瓨?shù)腑锛屾渶鍚庡啀榪涜姹傚鹼紝榪欏氨鑷劧瀵艱嚧緇熻澶ч噺C++浠ｇ爜鏂囦歡鐨勭洰褰曟椂錛屽崰鐢ㄥ唴瀛樹(shù)細(xì)寰堥珮錛堝嚑鐧綧涓奊錛夛紝涔熻褰撴垜榪涗竴姝ュ涔?fàn)涔嬪悗锛屾垜鑳藉閬垮厤杩櫩U峴pace leak錛屼絾榪欏浜庝竴涓垵瀛askell鐨勪漢鏄竴涓笉灝忕殑璐熸媴錛屽洜涓洪殢渚垮啓涓涓皬紼嬪簭閮芥湁鍙兘鑰楃敤鍑犵櫨M鐨勫唴瀛橈紝鑰岀敤鍏朵粬璇█瀹炵幇鐨勮瘽錛屽唴瀛樺緢瀹規(guī)槗寰堣嚜鐒剁殑鎺у埗鍦ㄥ嚑M涔嬪唴銆傦紙鐪嬪畬浼樺寲绔犺妭錛屽彧瀵圭▼搴忎慨鏀逛簡(jiǎn)鍑犺浠ｇ爜灝辮鍐呭瓨?shù)娇鐢ㄩ檷鍒板彲浠ユ帴鍙楃殑绋嬪害锛岀湅鏉azy 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 鍙戣〃璇勮
]]> 青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

      <noscript id="pjuwb"></noscript>
            <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

              <dd id="pjuwb"></dd>
              <abbr id="pjuwb"></abbr>
              
欧美日韩视频专区在线播放|
欧美在线你懂的|
午夜精品福利一区二区蜜股av|
一区二区三区波多野结衣在线观看|
亚洲大片在线|
你懂的一区二区|
亚洲最新中文字幕|
一本色道久久88综合日韩精品|
欧美日韩亚洲网|
欧美一区高清|
狂野欧美激情性xxxx|
亚洲精品小视频|
亚洲在线观看免费|
狠狠色2019综合网|
亚洲激情啪啪|
国产欧美日韩亚洲精品|
免费久久精品视频|
欧美精品综合|
久久精品视频免费|
欧美福利视频在线观看|
午夜日韩电影|
老鸭窝91久久精品色噜噜导演|
亚洲一区二区在线免费观看|
欧美一区二区三区精品电影|
亚洲激情成人网|
亚洲一区精彩视频|
亚洲精品国产拍免费91在线|
亚洲欧美综合精品久久成人|
亚洲精品久久7777|
性欧美18～19sex高清播放|
亚洲精品乱码久久久久久久久
|
91久久久久久久久|
国产日韩欧美在线|
日韩午夜在线观看视频|
精品成人一区二区|
国产精品99久久久久久宅男|
亚洲高清视频在线观看|
午夜亚洲激情|
亚洲性线免费观看视频成熟|
久久综合久色欧美综合狠狠|
久久国产精品99久久久久久老狼|
欧美精品首页|
欧美夫妇交换俱乐部在线观看|
国产欧美日韩综合一区在线观看
|
亚洲精品免费电影|
亚洲二区视频在线|
欧美一区二区三区在线视频|
亚洲制服av|
欧美日本在线播放|
欧美激情一区二区三区高清视频
|
亚洲国产精品久久|
久久精品一区二区三区不卡牛牛
|
亚洲国产精品久久久久秋霞不卡|
午夜日韩在线|
欧美影院一区|
国产精品―色哟哟|
亚洲特色特黄|
亚洲女人天堂成人av在线|
激情综合色综合久久|
亚洲国产另类久久精品|
亚洲欧美日韩另类|
亚洲欧美一区二区原创|
欧美理论视频|
亚洲精品一区二区三区蜜桃久|
亚洲国产高潮在线观看|
久久亚洲精品一区|
欧美r片在线|
亚洲日本成人网|
欧美精品一级|
99这里只有精品|
亚洲欧美另类久久久精品2019|
欧美日韩一区三区四区|
在线午夜精品|
香蕉久久一区二区不卡无毒影院|
国产精品裸体一区二区三区|
亚洲系列中文字幕|
久久爱91午夜羞羞|
黄色日韩网站|
欧美成人国产va精品日本一级|
亚洲精品久久久久中文字幕欢迎你|
日韩视频在线一区|
国产精品私人影院|
欧美在线在线|
亚洲国产另类精品专区
|
国产日韩欧美在线播放|
久久久久久久性|
亚洲激情在线激情|
亚洲一级在线|
伊人久久大香线蕉av超碰演员|
欧美成人精品福利|
亚洲色在线视频|
久久午夜精品|
99精品国产热久久91蜜凸|
国产精品日产欧美久久久久|
久久国产欧美|
日韩视频在线观看国产|
久久av免费一区|
亚洲欧洲日产国产综合网|
久久久亚洲国产美女国产盗摄|
亚洲国产婷婷香蕉久久久久久|
欧美视频一区在线观看|
久久久精品五月天|
99精品国产高清一区二区|
久久免费国产精品|
亚洲香蕉网站|
亚洲东热激情|
国产精品一区二区久久久|
老司机精品视频网站|
亚洲一区二区精品视频|
欧美激情第一页xxx|
欧美有码视频|
亚洲伊人观看|
亚洲精品久久久久久久久|
国产日韩在线看片|
欧美三级视频|
欧美电影免费网站|
久久精品女人的天堂av|
亚洲一区二区影院|
亚洲伦理久久|
亚洲国产aⅴ天堂久久|
欧美中文字幕在线观看|
亚洲一区二区三区四区在线观看|
亚洲第一色在线|
含羞草久久爱69一区|
国产美女精品在线|
国产精品卡一卡二|
欧美日韩国产美女|
欧美黄色免费网站|
欧美成在线观看|
久久婷婷国产综合精品青草|
国产精品xxxav免费视频|
久久在线91|
欧美一区二区精品|
亚洲自拍偷拍麻豆|
亚洲五月六月|
亚洲午夜视频在线|
在线视频精品|
亚洲视频一起|
一区二区三区久久久|
亚洲最新在线视频|
一本大道久久a久久综合婷婷|
亚洲精品国产精品国自产观看浪潮|
欧美激情aⅴ一区二区三区|
免费精品99久久国产综合精品|
老司机精品视频一区二区三区|
久久久无码精品亚洲日韩按摩|
久久久久国内|
免费观看成人www动漫视频|
美女脱光内衣内裤视频久久网站|
久久久久久网址|
麻豆精品精华液|
欧美日韩国产区一|
欧美日韩在线精品|
国产精品爽爽爽|
国产一区二区三区黄|
黑人极品videos精品欧美裸|
在线免费一区三区|
99国产精品私拍|
亚洲中字在线|
久久久免费av|
亚洲第一综合天堂另类专|
亚洲精品免费一区二区三区|
一区二区三区视频在线看|
亚洲中字在线|
麻豆成人小视频|
欧美日本国产精品|
国产日韩欧美一区二区|
在线免费日韩片|
亚洲深夜福利在线|
久久久久久欧美|
亚洲精品国产无天堂网2021|
亚洲永久精品大片|
嫩草伊人久久精品少妇av杨幂|
欧美性天天影院|
一区精品在线|
正在播放亚洲一区|
久久人91精品久久久久久不卡|
欧美国产亚洲视频|
亚洲一区日韩|
欧美另类一区|
伊人久久久大香线蕉综合直播|
一个色综合av|
蜜桃伊人久久|
亚洲欧美日韩爽爽影院|
欧美大片在线观看一区|
国产日韩欧美综合精品|
一区二区久久久久|
免费观看成人www动漫视频|
亚洲性色视频|
欧美精品乱码久久久久久按摩|
国产综合av|
亚洲欧美视频在线|
亚洲国内精品在线|
亚洲一二三区在线|
欧美电影在线观看|
欧美日韩在线播放|
9l国产精品久久久久麻豆|
久久久噜噜噜久久中文字免
|
国产精品欧美日韩一区二区|
在线不卡欧美|