第二章部分習題答S→SS+|SS*|aaa解：SSS*SSS*→aSS*→aaS*→aaaaL={支持加法、乘法的表達式的后綴表示形式2.2S→0S 0L={0n1n|證明：1)L考慮最小語法 ，推導出的符號串01顯然假定結(jié)點數(shù)<n考慮結(jié)點數(shù)=n的語法樹S，其結(jié)構(gòu)必為S1結(jié)點數(shù)<nt1∈L，St=0t11t∈L2)LL01L中長度<2n的符號串都可由文法推導出，考慮長度=2nt＝0n1n0t11，t1∈L且長度<2n，因此它可被文法推導出，對應語法 構(gòu)造語法樹，顯然，它的輸出為t，即t可被文法推導出i)、ii)，2)得證S→+S -S 證明：1)La假定結(jié)點數(shù)<n考慮結(jié)點數(shù)=n的語法樹S，其結(jié)構(gòu)必為S1、S2結(jié)點數(shù)<nE1、E2∈L（前綴表達式，SE=+/-E1E2，E也是前綴表達式。2)LLaL中長度<n的符號串都可由文法推導出，考慮長度=nE，它的形式必為E1E2，E1、E2∈L且長度<n，因此可被文法推導出，對應語法樹、構(gòu)造語法樹，顯然，它的輸出為E，即E可被文法推導出i)、ii)，2)得證S→S(S) 證明：1)L考慮最小語法樹，推導出的符號串假定結(jié)點數(shù)<n考慮結(jié)點數(shù)=n的語法樹S，其結(jié)構(gòu)必為，S1、S2、S3結(jié)點數(shù)<nt1、t2、t3∈L，St=t1(t2)t3t∈L。2)LL中最短符號串L中長度<nt’的形式必為或（否則不是最短前綴t’t2，無論哪種t2∈L，t1、t2長度<n，可被文法推導出，對應語法樹、 ，顯然，它的輸出為t，即t可被文法推導出綜合i)、ii)，2)得證另外，文法有二義性，符號串S→aSb bSa L={a、b組成的所有符號串，包括}證明：1)L中考慮最小語法樹，推導出的符號串假定結(jié)點數(shù)<n考慮結(jié)點數(shù)=n的語法樹S，其結(jié)構(gòu)有兩種可能S1、S2結(jié)點數(shù)<nt1、t2∈L，St=at1bt2bt1at2t∈L。2)LL中最短符號串L中長度<n考慮長度=ntat=a…（b開頭的情況類似，尋找它的∈Lt’，t’a…b（否則不是最短前綴，t’=at1bt1∈L（可能為t=t’t2，t2∈Lt=at1bt2。i)t1、t2tt可被文法推導出i)、ii)，2)得證ababS→a S+S SS S* (S)b)aaa解：E→+EE|EE|*EE|/EE|解：list→list,id|id解：list→id,list|idexpr→expr+term|expr–term|termterm→term*factor|term/factor|factorfactor→id|num|(expr)expr→expr+term|expr–term|termterm→term*unary|term/unary|unaryunary→+factor|-factorfactor→id|num|(exprnum→11|1001|num0|num36、9、12、153整除2）假定結(jié)點數(shù)<n3整除，考慮結(jié)點數(shù)=n的語法樹，num1結(jié)點數(shù)<n，生成的二進制串y可被3整除，而num生x=y*23，numx=y*2n+z3整除，12310101213RomanNumeralThousandHundredsTensOnesOnesLowOnes|IV|VLowOnes|IXLowOnes|I|II|TensLowTens|XL|LLowTens|LowTens|X|XX|HundredsLowHundreds|CD|DLowHundreds|LowHundreds|C|CC|ThousandsMThousands|9-5+29-expr→{print(‘+’);}expr+|{print(‘-’);}expr–|term→{print(‘*’);}term*|{print(‘/’);}term/|factor→{print(num.value);}|(expr9-5+2的語法樹 ，輸出+-959-5*2的語法樹為，輸出-9*5E→{print(‘(’);}{print(‘+’);E{print(‘)’};+|{print(‘(’);}{print(‘-’);E{print(‘)’};-|{print(‘(’);}{print(‘*’);E{print(‘)’};*|{print(‘(’);}{print(‘/’);E{print(‘)’};/|id{print(id.lexeme);| {print(num.value);95-2*的語法樹，輸出為((9-952*-的語法樹，輸出為(9-Num表示完整的整數(shù)，每個NT設定一個屬性roman，為字符串類型，代表羅馬數(shù)字的表示形式。假定存在chrrep(charc,intn)函數(shù)，它將字符c重復n次，形成一個字符串，作為返回n＝0，則返回一個空串。NumThousandsHundredsTens Num.roman=Thousands.roman||Hundreds.roman||Tens.roman||Ones.roman;Thousands {Thousands.roman=chrrep(‘M’,digits.val);digitsdigits {digits.val=digits.val*10+digit.val;| {digits.val=0;digit {digit.val=small.val;| {digit.val=big.val;| {digit.val=4;| {digit.val=9;small {small.val=0;| {small.val=1;| {small.val=2;| {small.val=3;big {small.val=5;| {small.val=6;| {small.val=7;| {small.val=8;Hundreds {Hundreds.roman=chrrep(‘C’,small.val);| {Hundreds.roman=“D”||chrrep(‘C’,small.val);| {Hundreds.roman=“CD”;| {Hundreds.roman=“CM”; {Tens.roman=chrrep(‘X’,small.val);| {Tens.roman=“L”||chrrep(‘X’,small.val);| {Tens.roman=“XL”;| {Tens.roman=“XC”;Ones {Ones.roman=chrrep(‘I’,small.val);| {Ones.roman=“V”||chrrep(‘I’,small.val);| {Ones.roman=“IV”;| {Ones.roman=“IX”;NTval，表示對應整數(shù)值RomanNumeralThousandsHundredsTensOnes{RomanNumeral.val=Thousands.val++Tens.val+Ones.val;printf(“%d\n”,RomanNumeral.val;)}Ones {Ones.val=LowOnes.val;| {Ones.val=4;|VLowOnes{Ones.val=LowOnes.val+5;| {Ones.val=9;LowOnes{LowOnes.val=0;| {LowOnes.val=1;|II{LowOnes.val=2;|III{LowOnes.val=3;Tens {Tens.val=LowTens.val;| {Tens.val=40;|L {Tens.val=LowTens.val+50;| {Tens.val=90;LowTens {LowTens.val=0;| {LowTens.val=10;| {LowTens.val=20;| {LowTens.val=30;Hundreds {Hundreds.val=LowHundreds.val;| {Hundreds.val=400;|D {Hundreds.val=LowHundreds.val+500;| {Hundreds.val=900;LowHundreds {LowHundreds.val=0;| {LowHundreds.val=100;| {LowHundreds.val=200;| {LowHundreds.val=300;ThousandsM {Thousands.val=Thousands1.val+100