编译原理编译原理编译原理 (30).ppt

《编译原理编译原理编译原理 (30).ppt》由会员分享，可在线阅读，更多相关《编译原理编译原理编译原理 (30).ppt（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、CompilerS1Chapter 4Top-Down ParsingRecursive-DescentcompilerS2Why&what is top-down(bottom-up)parsing?(34 3)*421.exp=exp op exp2.=exp op number3.=exp*number4.=(exp)*number5.=(exp op exp)*number6.=(exp op number)*number7.=(exp number)*number8.=(number number)*number9.=(34 3)*42exp exp op exp|(exp)|num

2、berop +|-|*CompilerS3Examples(1)exp=exp op exp(2)=number op exp(3)=number+exp(4)=number+number exp exp op exp number +number1234 exp exp op exp number +number1432(1)exp=exp op exp(2)=exp op number(3)=exp+number =number+numberLeftmost derivationRightmost derivationPreorder numberingThe reverse of a P

3、ostorder numberingCompilerS4Top-down ParsingoA top-down parsing algorithm parses an input string of tokens by tracing out the steps in a leftmost derivation.oThe traversal of the parse tree occurs from the root to the leaves.oTwo forms of top-down parsing:1.Predictive parsers.oAttempts to predict th

4、e next construction in the input string using one or more lookahead tokens.2.Backtracking parsers.oTries different possibilities for a parse of the input,backing up an arbitrary amount in the input.May require exponential timeCompilerS5Two Kinds of Top-Down Parsing1.Recursive-descent parsingVersatileSuitable for handwritten parser 2.LL(1)parsingNo longer often usedSimple scheme with explicit stackPrelude for more powerful and complex bottom-up algorithmsFirst“L”the input is processed from left to rightSecond“L”leftmost derivation1 one lookahead symbol