编译原理2E全套配套课件龙书 Chapter_three(2).ppt

《编译原理2E全套配套课件龙书 Chapter_three(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、COMPILERCONSTRUCTIONPrinciplesandPracticeKennethC.Louden3.Context-FreeGrammarsandParsingPARTTWOContentsPARTONE3.1TheParsingProcess3.2Context-FreeGrammars3.3ParseTreesandAbstract3.4AmbiguityPARTTWO3.5ExtendedNotations:EBNFandSyntaxDiagrams[More]3.6Formal

2、PropertiesofContext-FreeLanguages[More]3.7SyntaxoftheTINYLanguage[More]3.5ExtendedNotations:EBNFandSyntaxDiagrams3.5.1EBNFNotationSpecialNotationsforRepetitiveConstructsRepetitionAA

3、(leftrecursive),andAA

4、(rightrecursive)whereandarearbitrarystrin

5、gsofterminalsandnon-terminals,andInthefirstruledoesnotbeginwithAandIntheseconddoesnotendwithASpecialNotationsforRepetitiveConstructsNotationforrepetitionasregularexpressionsuse,theasterisk*.A*,andA*EBNFoptstousecurlybrackets{...}toexpressrepetit

6、ionA{},andA{}Theproblemwithanyrepetitionnotationisthatitobscureshowtheparsetreeistobeconstructed,but,aswehaveseen,weoftendonotcare.ExamplesExample:ThecaseofstatementsequencesThegrammarasfollows,inrightrecursiveform:stmt-Sequencestmt;stmt-Sequence

7、

8、stmtstmtsInEBNFthiswouldappearasstmt-sequence{stmt;}stmt(rightrecursiveform)stmt-sequencestmt{;stmt}(leftrecursiveform)ExamplesAmoresignificantproblemoccurswhentheassociativitymattersexpexpaddopterm

9、termexpterm{addopterm}(implyleftassociativity)ex

10、p{termaddop}term(implyrightassociativity)SpecialNotationsforOptionalConstructsOptionalconstructareindicatedbysurroundingthemwithsquarebrackets[...].Thegrammarrulesforif-statementswithoptionalelse-partswouldbewrittenasfollowsinEBNF:statementif-stmt

11、oth

12、erif-stmtif(exp)statement[elsestatement]exp0

13、1stmt-sequencestmt;stmt-sequence

14、stmtiswrittenasstmt-sequencestmt[;stmt-sequence]3.5.2SyntaxDiagramsSyntaxDiagramsSyntaxDiagrams:GraphicalrepresentationsforvisuallyrepresentingEBNFrules.Anexample:consider

15、thegrammarrulefactor(exp)

16、numberThesyntaxdiagram:factornumber()expSyntaxDiagramsBoxesrepresentingterminalsandnon-terminals.Arrowedlinesrepresentingsequencingandchoices.Non-terminallabelsforeachdiagramrepresentingthegrammarrulede