Chapter 4Syntax AnalysisAdvantages of Using BNF to Describe SyntaxReasons to Separate Lexical and Syntax AnalysisLexical AnalysisLexical Analysis (continued)Lexical Analysis with State-DiagramSlide 8State DiagramLexical AnalyzerThe Parsing ProblemThe Parsing Problem (continued)Slide 13Slide 14Slide 15PowerPoint PresentationRecursive-Descent ParsingRecursive-Descent Parsing (continued)Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Grammar for expression - LLSlide 26Slide 27Slide 28Slide 29Slide 30Slide 31Parsing example: nParsing example: ( n )LL Parsing example: n + nLL Parsing – a few issuesLL Parsing – pairwise disjointnessLL ParsingLL ParsingSlide 39Bottom-up ParsingBottom-up Parsing (continued)HandlePhrase, Simple Phrase, HandleSlide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Structure of An LR ParserSlide 52LR Parsing TableLR ParsingLR ParsingSlide 56Slide 57Slide 58Chapter 4Lexical and Syntax AnalysisIntroductionLexical AnalysisThe Parsing ProblemRecursive-Descent ParsingBottom-Up ParsingCopyright © 2012 Addison-Wesley. All rights reserved. 1-2Syntax Analysis•The syntax analysis portion of a language processor nearly always consists of two parts:–A low-level part called a lexical analyzer (mathematically, a finite automaton based on a regular grammar)–A high-level part called a syntax analyzer, or parser (mathematically, a push-down automaton based on a context-free grammar, or BNF)–BNF for syntax specificationCopyright © 2012 Addison-Wesley. All rights reserved. 1-3Advantages of Using BNF to Describe Syntax•BNF example<expr>  <term> {(+ | -) <term>}<term>  <factor> {(* | /) <factor>}<factor>  id | int_constant | ( <expr> )•Provides a clear and concise syntax description•The parser can be based directly on the BNF•Parsers based on BNF are easy to maintainCopyright © 2012 Addison-Wesley. All rights reserved. 1-4Reasons to Separate Lexical and Syntax Analysis•Simplicity - less complex approaches can be used for lexical analysis; separating them simplifies the parser•Efficiency - separation allows optimization of the lexical analyzer•Portability - parts of the lexical analyzer may not be portable, but the parser always is portableCopyright © 2012 Addison-Wesley. All rights reserved. 1-5Lexical Analysis•A lexical analyzer is a pattern matcher for character stringsis a “front-end” for the parser•Identifies substrings of the source program that belong together - lexemes–Lexemes match a character pattern, which is associated with a lexical category called a token–sum is a lexeme; its token may be IDENTCopyright © 2012 Addison-Wesley. All rights reserved. 1-6Lexical Analysis (continued)•The lexical analyzer is usually a functionwhich is called by the parser when it needs the next token•Two approaches to building a lexical analyzer:–Write a formal description of the tokens and use a software tool that constructs a table-driven lexical analyzer from such a description–Design a state diagram that describes the tokens and write a program that implements the state diagram (or hand-construct a table-driven implementation of the state diagram).Copyright © 2012 Addison-Wesley. All rights reserved. 1-7Lexical Analysis with State-Diagram•In many cases, transitions can be combined to simplify the state diagram–When recognizing an identifier, all uppercase and lowercase letters are equivalent•Use a character class that includes all letters–When recognizing an integer literal, all digits are equivalent - use a digit class•Reserved words and identifiers can be recognized together (rather than having a part of the diagram for each reserved word)–Use a table lookup to determine whether a possible identifier is in fact a reserved wordCopyright © 2012 Addison-Wesley. All rights reserved. 1-8Lexical Analysis (continued)•Convenient utility subprograms:–getChar - gets the next character of input, puts it in nextChar, determines its class and puts the class in charClass–addChar - puts the character from nextChar into the place the lexeme is being accumulated, lexeme–lookup - determines whether the string in lexeme is a reserved word (returns a code)Copyright © 2012 Addison-Wesley. All rights reserved. 1-9State DiagramCopyright © 2012 Addison-Wesley. All rights reserved. 1-10Lexical AnalyzerFollowing is the output of the lexical analyzer of front.c (pp.172-177) when used on (sum + 47) / totalNext token is: 25 Next lexeme is (Next token is: 11 Next lexeme is sumNext token is: 21 Next lexeme is +Next token is: 10 Next lexeme is 47Next token is: 26 Next lexeme is )Next token is: 24 Next lexeme is /Next token is: 11 Next lexeme is totalNext token is: -1 Next lexeme is EOFCopyright © 2012 Addison-Wesley. All rights reserved. 1-11The Parsing Problem•Goals of the parser, given an input program:–Find all syntax errors; for each, produce an appropriate diagnostic message and recover quickly–Produce the parse tree, or at least a trace of the parse tree, for the programCopyright © 2012 Addison-Wesley. All rights reserved. 1-12The Parsing Problem (continued)•Two categories of parsers–Top down - produce the parse tree, beginning at the root•Order is that of a leftmost derivation•Traces or builds the parse tree in preorder–Bottom up - produce the parse tree, beginning at the leaves•Order is that of the reverse of a rightmost derivation•Many parsers look only one token ahead in the input (lookahead)Copyright © 2012 Addison-Wesley. All rights reserved. 1-13The Parsing Problem (continued)•Top-down Parsers–Given a sentential form, xA , the parser must choose the correct A-rule to get the next sentential form in the leftmost derivation, using only the first token produced by A•The most common top-down parsing algorithms:–Recursive descent - a coded implementation–LL parsers - table driven implementationCopyright © 2012 Addison-Wesley. All rights reserved. 1-14The Parsing Problem (continued)•Bottom-up parsers–Given a right sentential form, , determine what substring of  is the right-hand side of the rule in the grammar that must be reduced to produce the previous sentential form in the right derivation–The most common bottom-up parsing algorithms are in the LR familyCopyright © 2012 Addison-Wesley. All rights reserved. 1-15The Parsing Problem (continued)•The Complexity of Parsing–Parsers that work for any unambiguous grammar are complex and inefficient: O(n3), where n is the