1.设有文法G[S]：S—ABA—bB|AaB—Sb|a试消除该文法的左递归。解：本题考查消除左递归的方法。应用消除文法左递归的算法对文法G[S]消除左递归的过程如下：(1)将非终结符排序为：U1=S，U2=A，U3=B(2)进入算法排序：i=1时，对文法无影响i=2,j=1时：A—Aa有直接左递归，消去该直接左递归，得A—bBAA—aA£|i=3，j=1时：改写文法，有B—ABb|aj=2时：改写文法，有B—bBABb|e无左递归。(3)所以文法G[S]消除左递归后变为：G[S：]S—ABA...
