第5章LL(1)文法及其分析程序自上而下分析算法带回溯的自上而下分析预测分析程序Predictiveparser无回溯的自顶向下分析程序PL/0语言的EBNF递归下降子程序voidMatchToken(intexpected){if(lookahead!=expected){printf("syntaxerror\n");exit(0);}else//ifmatch,consumetokenandmoveonlookahead=yylex();}例：递归子程序实现表达式的语法分析表驱动予测分析程序模型带a0a1a2a3a4a5a6a7a8…an-1an上下文无关语言句型分析（识别）程序的数学模型例：PdaP=({A,B,C),{a,b,c),f,{h,i},iA,{})分析算法分析输入串#a+a#FIRST集和FOLLOW集的定义设G=(VT,VN,P，S)是上下文无关文法FIRST（）={a|=>*a,a∈VT,,∈V*}若=>*ε则规定ε∈FRIST（）FOLLOW（A）={aS=>*A且a∈FRIST（），∈V*，∈V+}若S=>*uA,且=>*ε，则#∈FOLLOW(A)计算FIRST集计算FOLLOW集G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>(4)T–>FT’(5)T’–>*FT’(6)T’–>(7)F–>(E)(8)F–>aG[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>(4)T–>FT’(5)T’–>*FT’(6)T’–>(7)F–>(E)(8)F–>a予测分析表构造算法LL(1)分析中的一种错误处理办法review---parsingInthetop-downparsing,webeginwiththestartsymbolandateachstep,expandoneoftheremainingnonterminalsbyreplacingitwiththerightsideofoneitsproductions.Werepeatuntilonlyterminalsremain.Thetop-downparseprintsaleftmostderivationofthesentence.lookaheadsymbol.Thelookaheadsymbolisthenextsymbolcomingupintheinput.backtracking.Basedontheinformationtheparsercurrentlyhasabouttheinput,adecisionismadetogowithoneparticularproduction.Ifthischoiceleadstoadeadend,theparserwouldhavetobacktracktothatdecisionpoint,movingbackwardsthroughtheinput,andstartagainmakingadifferentchoiceandsoonuntiliteitherfoundtheproductionthatwastheappropriateoneorranoutofchoices.predictiveparserandLL(1)grammarrecursive-descentTable-drivenLL(1)parsingHowatable-drivenpredictiveparserworksThefollowsetofanonterminalAisthesetofterminalsymbolsthatcanappearimmediatelytotherightofAinavalidsentence.Abitmoreformally,foreveryvalidsentenceS=>*uAv,wherevbeginswithsometerminal,thatterminalisinFollow(A).ComputingfirstCalculatingfollowsets.Foreachnonterminalinthegrammar,dothefollowing:ConstructingtheparsetableLL(1)grammarError-reportingandrecoveryPanic-modeerrorrecovery练习3.对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。(1)A→aABe|aB→Bb|d(3)S→Aa|bA→SBB→ab