自上而下语法

第5章自顶向下语法分析方法内容语法分析的任务与分类自上而下分析面临的问题LL（1）分析法递归下降分析程序构造预测分析程序5.1语法分析的任务与分类1.任务

对于一个给定w∈VT*,判断w∈L(G)工作本质：根据产生式识别输入串是否为一个句子。2.语法分析器：是一个程序，它按照P，做识别w的工作。语法分析只管w在形式上是否正确，不管其具体含义，比如：“虎打武松”。5.1语法分析的任务与分类3.语法分析器在编译程序中的地位词法分析器语法分析器编译器的后继部分符号表源程序单词符号取下一个单词符号语法分析树5.1语法分析的任务与分类自上而下分析法从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导将文法开始符号做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上分析法从输入符号串开始，逐步进行归约，直至归约到文法的开始符号从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树4.语法分析的分类 S

A

A

cabd

ca

bd

ca

b

d

规约过程构造的推导：cAd

cabdScAd S S S

c A d

c A d

a

b推导过程：S

cAd

cAd

cabd例：文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否为该文法的句子自上而下分析自下而上分析5.2.1自上而下分析的主旨自上而下分析的主旨为输入串寻找一个最左推导对任何输入串，试图用一切可能的办法，从文法开始符号（根结点）出发，自上而下地为输入串建立一棵语法树例5.1假定有文法

(1)S→xAy(2)A→**|*

分析输入串x*y(记为)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*证明是一个句子实现途径让每个非终结符对应一个递归子程序如果发现某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值否则，保持原来的语法树和IP值不变，并返回“假”值自上而下的带回溯试探法自上而下分析过程中存在回溯回溯的缺点，在分析的过程中不断的试探（穷举法），导致语法分析效率很低。文法的左递归5.2自上而下分析面临的问题例：文法G:S->Sa|bw=baaaa#推导时，无法确定什么时候用S->b替换。文法的左递归问题一个文法是含有左递归的，若存在非终结符P将使自上而下分析陷入无限循环。回溯问题分析过程中，当一个非终结符用某一个候选式匹配成功时，这种匹配可能是暂时的。这时，不得不“回溯”，导致语法分析效率低下。5.2左递归与回溯区分三种左递归形式直接左递归

形如：P

→

P

/N

→N

间接左递归形如：N

→A

A

→

BβB

→

Nγ潜在左递归形如：N

→Nε5.2左递归与回溯+5.3LL(1)分析法左递归的消除提取左公共因子LL(1)文法分析5.3.1左递归的消除1.采用下列变换公式消除直接左递归，把直接左递归改写为右递归

如：文法G：S→Sa|b

可改写为：

S→bSS→aS|

改写后的文法所描述的L(G)={ban|n>=0}5.3.1左递归的消除一般而言，假定关于P的全部产生式是

P→P1|P2|…|Pm|1|2|…|n

其中，每个都不等于，而每个都不以P开头那么，消除P的直接左递归性就是改写这些规则：

P→1P|2P|…|nPP→1P|2P|…|mP|5.蒸3.甘1左递逝归的陪消除例5.嫌2文法E→述E＋T孟|涝TT→管T*楼F丈|娇FF→首(E垫)梳|腥i经消裳去直永接左赏递归协后变鹿成：E→腊TEE→+登TE|T→据FTT→*拼FT|F→煮(E朴)振|岛i注意把：这善个例亮子后夕面将佩再度她用到5.丹3.郊1左递乔归的避消除2.消除降间接有左递婶归（都代入旬法）间接员左递膝归的押消除助需先宏将间插接左疯递归等变为录直接完左递匪归，债然后柜再按淘第1种方赢法消计除直固接左菠递归如：衡文法G：S→想Q|b可改逆写为辛：Q译→P穴β|b5.莲3.挠1左递落归的凑消除代入组法将一句个产瓣生式窜规则量右部般的中的VNN替换喷为N的候甚选式盏。如懒果N有n个候概选式馆，右摸边重复n次，百而且怖每一汉次重荷复都卖有N的不壤同候双选式浪来代历替N。例如胃：N→a信|Bc码|在S→p注Nq中的生代入留结果S→p嗽aq焰|赛pBc厕q技|和pq5.涉3.笑1左递筒归的胖消除写一断个程畅序实新现间砖接左去递归桌，如乐何做啦？一条昌一条译查看漆，第息一条碧存在作左递败归消卸除之太；第截二条蜘代入1进行蹄分析些；第驳三条末代入1,表2分析助；以退此类逃推，仿一直抬代到怎底。5.蔑3.夏1左递锹归的捕消除3.消除糖文法燥中一捆切左民递归圣的算验法若VN的排唉序为A1，A2，…,利An代入滩法，宿发现东直接律左递毯归即炭消除星（见P89阴-9蜘0）去掉深无用庆产生面式5.所3.宜1左递值归的转消除消除照左递秤归的数算法把文服法G的所犁有非封终结姐符按粪任一枕种顺闪序排律列成P1，P2，…，Pn；按月此顺获序执广行；FO登R哑i跳:=萄1蔽T苏O怒n洽DOBE旷GI倚NFO绩R垮j饶:=怖1售T涝O晌i勤-1吉DO把形坊如Pi→Pj的规育则改决写成Pi→1|2|…赛|k;(其中Pj→1|2|…崇|k是关奶于Pj的所修有规也则)消除折关于Pi规则拆的直辉接左违递归摇性EN纤D化简富由第誓二步智所得御的文敬法即去只除那梦些从千开始付符号躁出发鹊永远故无法雄到达桐的非甚终结委符的炊产生粒规则5.数3.寄1左递滩归的核消除例5.耕3考虑址文法G(坛S)S→茅Qc序|cQ→拒Rb景|bR→毕Sa价|a令它壁的非墨终结煌符的排序油为R、Q、S对于R，不枝存在睬直接受左递惧归把R代入圾到Q的有曲关候斑选后忽，把Q的规机则变箭为Q→释Sa寨b买|骄ab听|仓b现在盯的Q不含阻直接叮左递贯归把Q代入贵到S的有阶关候喉选后槐，S变成S→女Sa桨bc劣|纹a殿bc香|家b英c纷|纠c5.裙3.做1左递罚归的辨消除S→此Sa隶bc楼|脸a克bc湖|堆b茶c禽|揪c存在寄直接膨左递经归消除S的直伴接左绣递归清后S→陡ab伤cS|慢bc盏S|童cSS→a交bc置S|Q→乱Sa绵b仪|a醋b息|侄bR→贵Sa荷|a关于Q和R的规卖则已陪是多保余的宋，化摩简为S→渔ab你cS|泼bc顿S|虎cSS→a蜡bc摧S|由于萌对非临终结跟符排瓦序的茎不同饺，最已后所凉得的渣文法胁在形颂式上蒙可能萌不一邪样。佛但它轰们都偿是等爆价的5.古3.颈1左递干归的授消除例5.餐3考虑堡文法G(珠S)S→暮Qc坡|cQ→薯Rb穷|bR→弯Sa痒|a非终念结符排序隙选为S、Q、R，那动么，R躁→Q美ca矮|c俊a|软aR跃→R师bc康a|福bc票a|沸ca粉|a最后论所得慈的无县左递攻归文殖法是酸：S→酸Qc扮|喷cQ→吼Rb贞|葡bR→健bc突aR|码ca摄R|a废RR→哲bc装a央R|不同俗排序昼所得脆的文裁法的每等价龟性是雀显然筑的5.徒3.卧1左递民归的鼻消除习题1A→旅aB表|B翅bB→扒Ac伐|d消去虎该文机法的复左递愁归。习题2消去朗文法G[途S]：S列→S士a|与Ab雀|aA→州Sc的左际递归吧。5.踪蝶3.跑2回溯喘的消胁除回溯若当蔬前符决号为：a，对A展开核，而A→1|2|烤…海|n，那么左，要数知道玩哪一采个i是获嫩得以a开头西的串宏的唯一替换敌式。怎样艰选择i？以a为头班的i如有调多个i以a为头牙的，勉这是博文法测的问叮题。Sa….IPA......5.性3.鸟2回溯攀的消胸除回溯岗产生辱的根舅源：头字坑符集颠合的江问题购。例如尝：语句→i除f条件th个en语句el烦se语句|迎wh莫il挣e条件do语句|边be秆gi功n语句en放d5.杰3.敏2回溯抖的消堂除为了消除彻回溯就必莫须保摔证对文覆法的庸任何荡非终徐结符陶，当栗要它谱去匹弟配输献入串考时，木能够婶根据矩它所庭面临掀的输北入符浴号准确夕地指表派它厦的一树个候微选去觉执行勺任务毒，并瞧且此惹候选办的工与作结泼果应谎是确农信无址疑的A→1|2|叶…抹|nSa….IPA......令G是一皇个不彻含左犁递归结的文赵法对G的所堡有非谱终结王符的栋每个杯候选定义神它的终结浊首符滨集FI按RS暴T()为

特别是，若，则规定FIRST()如果内非终伟结符A的所荷有候图选首予符集麻两两捕不相觉交即A的任迷何两足个不部同候顶选i和jFI芬RS骆T(i)∩伏FI价RS脖T(j)＝当要列求A匹配粗输入绸串时A就能梦根据替它所面临蜡的第乡丰一个迹输入妖符号a，准确兔地指孩派某裕一个越候选前去墙执行轰任务这个收候选冻就是靠那个终结积首符熟集含a的5.鉴3.雁2提公声共左萝因子提取婶公共括左因嚼子假定巾关于A的规宁则是A→1|2|偿…|n|1|2|兼…m(其中乡丰，每巷个不以开头)那么坐，可盯以把杜这些藏规则钩改写俊成A→A|1|2|叠…坑|mA→1|2|洗…奔|n经过反复愚提取志左因笨子，就锤能够良把每割个非浇终结陆符（堤包括钉新引散进者途）的所有愈候选反首符被集变紧成为逝两两伴不相悄交5.漆3.警2消除俱回溯炊、提晶左因楼子例5.辣4：考驴察文油法G：S爹→菌iC论tS元|职i宰Ct锁Se贡S及|启aC今→邻b解：盗由于S的前李两个演候选增项中垒含有饮左因疏子iC雄tS，提除取左株因子边之后句，等筝价文顷法G’如下猎：S松→碌iC程tS止S'洋|阶aS'显→境eS杨|嚼εC仿→伶b习换题1：文清法G为：S→愿a|拿(T农)T→怨T,厅S|工ε消去钓该文旁法的州左递晌归。2:若文法G1的产欲生式口为：S似→a忌Sb帜|a恰S|ε消去滤左公揉共因期子。5.贯3.锄3涝L隙L(规1)分析古条件LL槽(1寄)的含夏义第一螺个L从左蜂至右榨扫描接输入室串第二矛个L最左肢推导1分析养时每滩一步揪只需呆向前出查看走一个蹲符号对于凑一个LL敌(1尾)文法可以络对其落输入耀串进便行有胳效的瞒无回眼溯的千自上杂而下环分析5.凡3.篇3屈LL蒙(1失)分析那条件构造魂不带颈回溯番的自董上而饺下分粪析的晕文法躁条件文法锋不含革左递蝴归，对于庆文法谅中每沸一个偷非终集结符A的各睛个产爆生式鬼的候植选首盾符集览两两此不相述交若A→1|2|…|n，则FI醒RS厕T(i)∩缸FI照RS疤T(j)＝(ij)对文趁法中发的每宽个非刺终结俭符A，若糖它存姥在某惑个候顾选首导符集唤包含，则FI糖RS姿T(i)∩绿FO叼LL绍OW胡(A援)=i=缓1,军2,紫..津.,煌n若一溜个文执法G满足桂以上皂条件辩，则也称G为LL愤(1灰)文法特别是，若，则规定

＃FOLLOW(A)假定S是文孤法G的开步始符窝号，聋对于G的任半何非塘终结膝符A，我捞们定茫义5.梢3.专3寻LL陪(1兽)分析腐条件构造锻不带趴回溯深的自球上而露下分焦析的然文法箩条件文法克不含左左递秀归，对于究文法莲中每铲一个魔非终谋结符A的各耕个产弹生式华的候仔选首凭符集舌两两帜不相搁交若A→1|2|…|n，则FI排RS坟T(i)∩看FI纸RS茄T(j)＝(ij)对文扣法中粮的每眼个非砖终结蝇符A，若结它存戴在某粪个候控选首议符集宵包含，则FI怀RS扶T(i)∩株FO吊LL切OW麦(A借)=i=伙1,渴2,键..肠.,荒n若一叹个文脾法G满足雷以上供条件毫，则短称G为LL射(1怕)文法结论蓬：对LL杰(1茶)文法恶，可只构造毯不带柔回溯砍的自植上而役下的大分析找算法难。5.资3.挤3欣LL拆(1砍)分析劳条件LL割(1醉)分析层过程假设辆要用捎非终贸结符A进行钻匹配滩，面孕临的昆输入荐符号铲为a，A的所匀有产绒生式嚼为A→1|2|笑…嫁|n若aFI扩RS镇T(i)，则指派i执行痒匹配挥任务若a不属框于任垫何一暗个候乐选首搂符集急，则1）若属于滔某个FI妻RS境T(i)且aFO讯LL贷OW总(A淡)，则意让i与自动啦匹配2）否奇则，a的出夺现是慢一种卖语法衬错误5.浮3.毯3厉LL替(1犯)分析列条件构造FI狐RS抱T集计算单个喊文法峡符号的FI袄RS睛T集计算一组醒文法扛符号捉串的FI狂RS渗T集构造FO采LL皂OW集5.碑3.廊3.到1单个雁文法氧符号的FI叫RS丽T集FI谣RS恭T定义咏：FI棋RS羞T()惊={杏a|柱aβ,恶a∈VT,β∈Σ*}若冻乔,则规阁定∈厌FI才RS怀T()。对每劝一个框文法攻符号X∈Σ，计兵算FI急RS阔T(竿X)如果X∈VT，则FI供RS柳T(属X)是{X}如果X∈VN，且X→是一雾个产煌生式路，则拆将ε加到FI尼RS敏T(灿X)中如果X∈VN，且X→励Y1Y2…Yk（k≥栗1）是居一个衬产生式，愚则若ε∈侦FI渐RS愈T(处Yj)（j=梁1,优2,…,k），济则将ε加入FI鸡RS织T(饿X)当某木终结患符a∈唯FI脆RS寺T(萌Yi)或(1冬<i朱≤k复)且Y1Y2…Yi-壳1ε时，就眠把a加入阔到FI躲RS看T(凑X)中去即：ε∈廉FI流RS霜T(利Y1)，ε∈弄FI厨RS贩T(枕Y2)，…，ε∈剪FI演RS夫T(朝Yi-旁1)反复榜使用痒上述信规则售，直让到每我个符设号的FI择RS赤T集合门不再汗增大史为止疮。5.往3.滑3.宝1单个女文法共符号的FI昂RS食T集例1：对冰下面衰的文第法求适其非葡终结招符的FI危RS职TE→谦TEE→+耗TE|T→堪FTT→*轿FT|F→朗(E灶)涛|关i5.迹3.菌3.贱1单个觉文法情符号的FI刺RS摆T集例2：对偶下面廉的文逐法G[回S]求其李非终谣结符夸的FI宽RS宗T集S于→呀AB因|待b峰cA→点b悔|B→|植aDC→择A剪D夫|采bD→帆aS变|毙c5.控3.啊3.补2文法示符号臭串的FI唐RS干T集若符刊号串∈Σ*，=X1X2…Xn将集吐合FI丝式RS火T(兼X1)中的悔除ε的终世结符尊号加让入FI僚RS暑T()如果ε∈串FI另RS幻玉T(雁X1)，那宿么将乐集合FI同RS绕T(歉X2)中除ε的终胃结符汪号也敲加入FI奖RS肉T()依次纪类推如果X1,X2,…另,Xn中每奇一个言文法夺符号登的FI客RS段T集中偿都有ε,那么遇把ε也加坡入到FI沙RS馋T()中5.亲3.洪3.村2文法封符号跪串的FI啄RS剂T集例3在前健面两肌个例谜子的遣基础辨上求与下面沾符号奇串的FI址RS叙T集FI拳RS谊T(挡TE无’)FI领RS冶T(甩+T虫E’宰)FI际RS截T(招AB渐)FI基RS畅T(浙bc偿)FI邮RS雄T(燃ε)FI县RS粗T(缩慧aD休)FI渡RS校T(夺AD狗)FI糖RS景T(素E)幼={只(晒,i切}FI瞎RS倡T(诵E’邀)=讨{汽+,}FI箭RS背T(窗T)撕={振(写,I科}FI椒RS朝T(仁T’攻)=园{虑*,}FI骗RS橡T(掉F)双={殿(果,蒸i意}FI袍RS释T(裕S)条={迟b参,舟a,}FI店RS只T(独A)配={毙b握,}FI摇RS售T(枯B)浪={,布a扇}FI租RS疑T(撑C)荡={裙b抱,a,筝c}FI菌RS波T(粉D)晋={御a尽,阶c尊}练习昨题1.文法G:初S匪→讨a槽|模^远|伸(候T)T茅→施T,受S茫|农S要求洒：1）消缠除左案递归2）列深出FI俱RS狐T集合2.对P10期0习题2的文穗法求默每个VN的FI邮RS伯T集5.残3.食3.跳3构造FO嚼LL谦OW集计算雾文法室中每讲个非虫终结限符A的FO柜LL流OW产(A礼)如果S是文删法的狡开始窄符号清，那咽么把#添加输进FO句LL桐OW榜(S篮)（#是输静入串碰的结英束符税）如果滚有一旁个产尊生式A→αB芽β，那播么将今集合FI锅RS驻T(跌β)中除ε外的永所有藏元素事加入托到FO盯LL吧OW遭(B幅)中如果瓜有一验个产兆生式A→αB，或蔑有一宣个产为生式A→αB墨β且ε∈债FI沈RS姿T(第β)振,那么责将集延合FO挂LL龙OW盐(A凑)中的斥所有散元素连加入讯到集氧合FO拢LL蛛OW紫(B释)中反复斯使用2,薄3两个隶步骤尿，直没到每搏个VN的FO迹LL备OW集不过再增啊大为封止。FO广LL括OW腥(A模)=宴{魔a|雀S扔…纤Aa啦…,购a∈演VT}S乱…杰A,则规刘定#∈攻FO厚LL爷OW席(A权)5.杰3.扛3.饥3构造的FO蜜LL工OW集例1：对腥下面绩的文烧法求FO址LL裳OW集E→曾TEE→+妄TE|T→渐FTT→*瓶FT|F→李(E漠)织|劳iFI碗RS姨T(局E)若={浅(售,i投}FI浙RS悲T(期E’陷)=伏{量+,}FI羡RS驾T(滨T)胖={娃(猫,I统}FI狡RS文T(显T’侍)=圈{阴*,}FI眯RS饼T(榜F)编={水(闯,习i钓}5.柱3.野3.朋3构造的FO百LL贩OW集例2：对安下面树的文怪法G[学S]求其FO欢LL王OW集S碑→A税B|熊b竖cA→胆b谈|B→|茶aDC→魔A澡D屯|则bD→突aS岭|那cFI铜RS兄T(满S)寇={役b彻,栽a,}FI参RS献T(仙A)雁={处b魄,}FI血RS效T(个B)劝={,盏a呀}FI骆RS竭T(仔C)唱={背b卡,a,晕c}FI突RS妄T(乔D)射={谊a急,绸c废}习冰题设已岂给文宋法：S→馋S五aB颂|喝bBA→塞S跟|aB→Ac求出具各个VNFI忍RS复T集和FO题LL匹OW集。判断千该文暴法是芹否为LL柔(1吐)文法抹，如怨果不岂是将其颠改写吵为LL恋(1执)文法径。5.削4递归躲下降烂程序小的构金造当文盗法满清足LL刮(1上)条件慕时，灵构造鞭不带岂回溯忘的自倦上而喝下分脂析程券序该分恋析程掩序由踩一组浸递归虾过程久组成溉，每耐个过非程对光应文标法的老一个娘非终煤结符是不脖是所拒有的ij的fi横rs蕉t集的杰交集牢都为词空？思考不是省，仅间针对炊一个VN的候飘选式货有如势此的汤约定毅。5.睛4递归快下降编程序蛮的构敲造例E→雨E躁+T|暮TT→刷T愉*F谜|FF→(E但)|胡iE→封T转E’E’寨→疮+T阶E’|T→瓦F膨T’T’哀→迅*F室T’物|F→(E圆)|教i图1图25.迷4递归帖下降竞程序维的构港造E→钳T州E’E’舌→遇+T忌E’|T→宴F司T’T’床→采*F蹲T’长|F→(E缓)|床ivo晨id僻E谷()集{T(茫);E’尺()穴;}vo歌id典E扯’(业){If富(S骗YM捉==脏‘+交’)声{AD是VA桐NC铸E;T(捞);E’写()刊;}}vo喘id告F应()稍{If兆(S巨YM芒==缸‘i跃’)AD香VA千NC颗E;el技se绩i袋f(桐SY部M=骨=‘完(’耕){AD届VA谦NC踏E;E(魄);If旅(S脊YM恨==厦‘)狠’)AD控VA枪NC验E;el牛se向e架rr穿or休;}el营se磨e押rr矿or桑;}SY疾M：IP当前标所指角的输案入符瞒号；AD诉VA下NC元E：把因输入兆串指宗示器IP调至抵指向呼下一傻个输自入符探号。5.塔5烤LL（1）预恰测分氏析法一、修特征:根据婚当前穿输入铃符号窑，为经当前箱要处屡理蚁的非复终结户符选锅择产县生式二、师表驱炎动的傻预测组分析魂器包条含：一个护输入捧缓冲渣区一个相栈一张否分析者表一个克输出西流要求——文法递是LL暴(1鸟)的三、得预测驶分析阅器模暮型：…牙a熔+主b立#预测欣分析爆程序XYZ#分析旷表M输出#是输美入串雕的结束标娘记，芒也是龙栈底符笔号四、咸预测哈分析竿表M预测岩分析浓表是下一个M[册A，a]形式慨的矩歌阵其中细：A为非脚终结过符，a为终枝结符普或#M[爆A，a]中存班放着盟一条样关于A的产忙生式萍，指著出当A面临a时所匹应采麻取的桑候选傅；M[即A，a]中也盯可能洋存放呆一条南“出遇错标扁志”寨，指肯出Ａ菌不应雪该面抛临a例：描对于既文法G1稼E→足TE’2绣E’→膊+T所E’|ε3T→F稠T’4罩T’→*泉FT’|ε5谢F→俘(E硬)|id其预确测分乓析表哲为：非终扶结符输入看符号EE’TT’Fid*()#+E→充TE危’E→爱TE丈’E’暴→+盆TE热’E’英→εE’像→εT→傅FT倦’T→睁FT猴’T’纪→εT’单→εT’针→εT’吨→刷*F米T’F→尤(E并)F→博id预测确分析钳表预测守分析独表的苍构造fo肿r迈i:吉A→αdofo组r许a匀=ε∈FI恋RS屡T（α）be证gi宴nM[茅A,后a]筑=A→刃α;en固dif造ε∈FI趣RS您T（α）fo纳r殊b∈叠FO扫LL扫OW（A）M[匙A,洪b]插=A→剃α;将M的空宜白处剧均置岁为er毁ro勤r即A→ε例：仪对于撒文法G1鲜E→累TE’2熟E’→晒+T剪E’|ε3T→F旋T’4蝴T’→*荐FT’|ε5众F→森(E弱)|id解：FI雅RS仍T(懒E)竞={环(蚂,id}FI牙RS带T(械E’帐)=浪{+居,ε}FI想RS快T(绣T’款)=千{起*,ε}FI遗RS夸T(趁T)饰={肃(坊,id}FI勤RS见T(贿F)摇={临(使,id}FO灵LL泉OW模(E品)兄={气#,尸)请}FO分LL碍OW距(E息’)棚={岛),衡#呢}FO所LL苍OW句(T休’)断={活+,笔)漫,绍#扮}FO皂LL稠OW孝(T祖)园={绑+,齐)街,倒#东}FO躺LL惰OW楚(F帽)通={垦id蠢,棵),因*抽,惭#销}根据搞预测葡分析找表的异构造冷方法短构造剥该例谦题的誉预测索分析滔表。预测怕分析贵程序鞋的算能法：输入梯：串w和文元法G的分月析表M输出逐：如踏果w属于L（G），水则输棋出w的最诱左推盒