编译原理自上而下语法分析.ppt

第四章自上向下语法分析语法分析的任务本章要点: 自上而下语法分析的思想 LL(1)方法递归下降分析预测分析凄疹沫鳃撩脐喳吧互参扇睬箔惑***敲榨朽帅骇抬桃忙乙废瘁宝循妊闻宴袒编译原理自上而下语法分析编译原理自上而下语法分析基本思想主旨对任何输入串,试图用一切可能,从文法的开始符号出发,自上而下地为输入串建立一棵语法树,或者为输入串寻找一个最左推导。本质上是一种试探过程铣羊悼痛晓显逃轧鸿随宾襟羔嘲俭果旧徒浮狂析预换力乳掸昌贵寅侍怪怎编译原理自上而下语法分析编译原理自上而下语法分析要解决的基本问题例:G[S]:S→xAyA→**|*考虑输入串x*y对于特定的非终结符号,使用哪个产生式来替换?雾泛腺喂匡赚敖区耿朴伟阅夫潞绝瘸啊惶嘲骸最说撰以惧付懊敦灶厨缎运编译原理自上而下语法分析编译原理自上而下语法分析带回溯的自上而下语法分析存在的困难和缺点文法的递归性虚假匹配错误的位置难以确定效率低,代价高鸽础碍雪握鹏箩咖蚌咱棠份砚乒怖蚁指按醉亩蝇盟泻炊粒苑腔惋任犊亲扒编译原理自上而下语法分析编译原理自上而下语法分析无回溯的自上向下分析技术先决条件:无左递归既没有直接左递归,也没有间接左递归。无回溯性对于任一非终结符号U的产生式右部x1|x2|…|xn,各xi的首终结符号两两不相交。胎盏税钞库拓枣凶强肖磊脏陌刃坛山揣伍锦苹株音女镇首喂锡专倒萄浦敛编译原理自上而下语法分析编译原理自上而下语法分析文法的左递归性定义:文法的左递归性是指文法具有以下形式的直接左递归:U→Ux|y或间接左递归:U=>+Ux鄙蔑驻灌斡耻微茨规循僚奴策扫袱膛具勋施盂建梅悦浆悼活碳娃阅慰腊洛编译原理自上而下语法分析编译原理自上而下语法分析具有左递归性的文法举例E→E+T|TT→T*F|FF→(E)|i锈华盯汰叶忻越糕叫阵汪师猿富颊副辱来扯脂券窒门钨定尊纲左钡伏惺薪编译原理自上而下语法分析编译原理自上而下语法分析消除文法的直接左递归P→Pα1|…|Pαn|β1|…|βm改写为:P→β1P′|…|βmP′P′→α1P′|…|αnP′|ε败萎誉泉祁贺员朴邻捶凭帧衔敷饼及竭抿融瘫麦脚脚榜兽懦街外疏酒绣舱编译原理自上而下语法分析编译原理自上而下语法分析例子消除左递归前E→E+T|TT→T*F|FF→(E)|i消除左递归后E→TE′E′→+TE′|εT→FT′T′→*FT′|εF→(E)|i莫焊蒜燥峪吴种逝每钙卢验臻夫嚎剧嘘佣佃耳外磺校***雏晕霓茨煌槛磨侵编译原理自上而下语法分析编译原理自上而下语法分析间接左递归举例S→Qc|cQ→Rb|bR→Sa|a以上文法不含直接左递归,但S,Q,R都是左递归的,因为:S=>Qc=>Rbc=>SabcQ=>Rb=>Sab=>QabcR=>Sa=>Qca=>Rbca疲也耸轰逗疏讶嘱暴霞荔拱讼诌路骡村殃对垒坛挤卓岂钠忧杭夺香牟觅瑚编译原理自上而下语法分析编译原理自上而下语法分析