(4.3)--Samuel's Ch3_2编译原理与实践英文版.ppt

《(4.3)--Samuel's Ch3_2编译原理与实践英文版.ppt》由会员分享，可在线阅读，更多相关《(4.3)--Samuel's Ch3_2编译原理与实践英文版.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、compilerS1Chapter 3Context-Free Grammars and ParsingcompilerS2乔姆斯基分类法则乔姆斯基分类法则单词单词程序语言程序语言受限受限 自然语言自然语言自然语言自然语言识别对象识别对象有穷有穷 自动机自动机下推下推 自动机自动机线性线性 自动机自动机图灵机图灵机对应机器对应机器正则文法正则文法上下文上下文 无关文法无关文法上下文上下文 有关文法有关文法非限制性非限制性文法文法文法名称文法名称3型文法型文法2型文法型文法1型文法型文法0型文法型文法compilerS3oExample2.16 Grammar GS:P:S:=a|b|a S|b

2、S The derivation of it is S a S a b S a b b This means“abb”is a legal sentence in this language.L=w|w consists of arbitrary number of as and bsoNote:Grammar 3 can be recognized by finite pilerS4Left and Right RecursionoLeft recursive grammar:oA A a|aoA A|nEquivalent to *n、oRight recursive grammar:oA

3、 a A|aoA A|nEquivalent to *n、a+a+a a*a*acompilerS5-Productionoempty generates a language consisting of an empty string.oSuch a grammar rule is called an production.oA grammar that generates a language containing an empty string must have at least one production.oA A a|or A a A|are equivalent to the

4、regular expression a*.compilerS6Example 3.6statement if-stmt|otherif-stmt if(exp)statement else-partelse-part else statement|exp 0|1statement if-stmt|otherif-stmt if(exp)statement|if(exp)statement else statementexp 0|1compilerS7A Parse TreeoA parse tree corresponding to a derivation is a labeled tre

5、e nThe interior nodes are labeled by nonterminals.nThe leave nodes are labeled by terminals.nThe children of each node represent the replacement of the nonterminal in one step of derivation.exp(1)exp=exp op exp1234exp exp op exp|(exp)|numberop +|-|*(1)exp=exp op exp(2)=number op exp(3)=number+exp(4)

6、=number+number+number(2)=op exp(3)=number exp(4)=number+expopexpnumbernumber+numberexp exp op expexp (exp)exp numberop +op -op *compilerS8Same Tree,Different Numbering exp exp op exp number +number1324(1)exp=exp op exp(2)=exp+exp(3)=number+exp(4)=number+number exp exp op exp number +number1432(1)exp

7、=exp op exp(2)=exp op number(3)=exp+numbero =number+numbercompilerS9Leftmost and Rightmost DerivationsoA parse tree corresponds to many derivations.oIt is possible to distinguish particular derivations that are uniquely associated with the parse tree.oA leftmost derivation:nThe leftmost nonterminal

8、is replaced at each step.oA rightmost derivation:nThe rightmost nonterminal is replaced at each pilerS10Examples(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+numbero =numb

9、er+numberLeftmost derivationRightmost derivationPreorder numberingThe reverse of a Postorder numberingcompilerS11Example of Derivation(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)*numberexp

10、 exp op exp|(exp)|numberop +|-|*compilerS12(34 3)*43 exp exp op exp (exp)*number exp op expnumber -numberRightmost derivation14587632The reverse of a Postorder numberingcompilerS13Abstract Syntax TreesoA parse tree contains much more information that is necessary to produce executable code.exp exp o

11、p exp number +number (3)(4)+3 4compilerS14Example 3.8statement if-stmt|otherif-stmt if(exp)statement|if(exp)statement else statementexp 0|1 statement if-stmt if (exp)statement else statement 0 other otherif(0)other else other if0 other otherParse treeSyntax treecompilerS15Homework3.3 Given the grammarWrite down leftmost derivations,parse tree,andabstract syntax trees for the following expressions:a.3+4*5 6 b.3*(4 5+6)c.3 (4+5*6)exp exp addop term|termaddop +|term term mulop factor|factormulop *factor (exp)|number