|
自上而下的语法分析：（推导） 由根节点到叶节点 ※最左推导和最右推导 （每一步替换最左边的非终结符/每一步替换最右边的非终结符），最右推导称为规范推导。最右推导对应于最左规约（规范规约） 例： 文法： S--->AB A--->a|t B---->+CD C--->a D---->a 最右推导： S--->AB---->A+CD--->A+Ca---->A+aa----->a+aa 最左推导： S---->AB----->aB--->a+CD--->a+aD----->a+aa 自上而下文法设计所要注意的: ※※左递归： 左递归会使分析进入到无限循环之中 直接左递归和间接左递归 直接左递归：如果A→A α，则称文法G是直接左递归的 消除左递归 消除简单的左递归: 对于含有左递归的产生式 A→A α| β 可用下面的非左递归的产生式 代替： A→ β A’ A’ → αA’| ε 消除左递归例：  一般情况消除左递归： 对于一般情况而言，若某一文法G的产生式具有如下形式：  则可用如下方法消除左递归:  间接左递归：  S→Qc→Rbc→Sabc，出现了左递归 消除以上文法的间接左递归： 1.将非终结符排序为R、Q、S 2.R不存在左递归，将R代入Q： Q → Sab|ab|b 3. Q不存在左递归，将Q代入S S→ Sabc|abc|bc|c 4.消除直接左递归后，得文法：  化简得：  ※※提取左因子： （如果最左边的是一样的，就不明确下一步应该走哪条路） 比如文法：P →（Q）|aP|a 遇到a，是P→aP，还是P→a？ 提取左因子的算法：  |
|
|
