Unformatted text preview:

Syntax Analysis (Section 2.2-2.3)Review: Compilation/InterpretationReview: Syntax AnalysisPhases of CompilationSyntax AnalysisContext Free GrammarsParsingParsing exampleTop-down derivation of A, B, C;Slide 10Bottom-up parsing of A, B, C;Slide 12Slide 13LR Parsing vs. LL ParsingAn appropriate LR GrammarLL(1) Grammar for the Calculator LanguageLR(1) Grammar for the Calculator LanguageHierarchy of Linear ParsersBigger PictureImplementation of an LL ParserRecursive Descent Parser ExampleSlide 22Slide 23Slide 24Slide 25Semantic Analysis11Syntax AnalysisSyntax Analysis(Section 2.2-2.3)(Section 2.2-2.3)CSCI 431 Programming LanguagesCSCI 431 Programming LanguagesFall 2003Fall 2003A modification of slides developed by Felix A modification of slides developed by Felix Hernandez-Campos at UNC Chapel HillHernandez-Campos at UNC Chapel Hill22Review: Compilation/InterpretationReview: Compilation/InterpretationCompiler or InterpreterCompiler or InterpreterTranslation Translation ExecutionExecutionSource CodeSource CodeTarget CodeTarget CodeInterpre-Interpre-tationtation33Review: Syntax AnalysisReview: Syntax AnalysisCompiler or InterpreterCompiler or InterpreterTranslation Translation Execution ExecutionSource CodeSource Code•Specifying the Specifying the formformof a programming of a programming languagelanguage–TokensTokens»Regular ExpressionsRegular Expressions(also F.A.s & Reg. Grammars)(also F.A.s & Reg. Grammars)–SyntaxSyntax»Context-FreeContext-FreeGrammarsGrammars(also P.D.A.s)(also P.D.A.s)Target CodeTarget Code44Phases of CompilationPhases of Compilation55Syntax AnalysisSyntax Analysis•Syntax:Syntax:–Webster’s definition: Webster’s definition: 1 a : the way in which linguistic 1 a : the way in which linguistic elements (as words) are put together to form constituents elements (as words) are put together to form constituents (as phrases or clauses)(as phrases or clauses)•The syntax of a programming languageThe syntax of a programming language–Describes its formDescribes its form»Organization of tokensOrganization of tokens »Context Free Grammars (CFGs)Context Free Grammars (CFGs)–Must be Must be recognizablerecognizable by compilers and interpreters by compilers and interpreters»ParsingParsing»LL and LR parsersLL and LR parsers66Context Free GrammarsContext Free Grammars•CFGsCFGs–Add recursion to regular expressionsAdd recursion to regular expressions»Nested constructionsNested constructions–NotationNotationexpressionexpression  identifieridentifier | | numbernumber | | -- expressionexpression | | (( expressionexpression )) | | expressionexpression operatoroperator expressionexpressionoperator operator  ++ | | -- | | ** | | //»Terminal symbolsTerminal symbols»Non-terminal symbolsNon-terminal symbols»Production rule (i.e. substitution rule)Production rule (i.e. substitution rule)terminal symbol terminal symbol  terminal and non-terminal symbols terminal and non-terminal symbols77ParsingParsing•Parsing an arbitrary Context Free GrammarParsing an arbitrary Context Free Grammar–O(nO(n33))–Too slow for large programsToo slow for large programs•Linear-time parsingLinear-time parsing–LL parsers (a ‘Left-to-right, Left-most’ derivation)LL parsers (a ‘Left-to-right, Left-most’ derivation)»Recognize LL grammarRecognize LL grammar»Use a top-down strategyUse a top-down strategy–LR parsers (a ‘Left-to-right, Right-most’ derivation)LR parsers (a ‘Left-to-right, Right-most’ derivation)»Recognize LR grammarRecognize LR grammar»Use a bottom-up strategyUse a bottom-up strategy88Parsing exampleParsing example•Example: comma-separated list of identifierExample: comma-separated list of identifier–CFGCFGid_list id_list  idid id_list_tailid_list_tailid_list_tail id_list_tail  ,, id_list_tailid_list_tailid_list_tail id_list_tail  ;;–ParsingParsingA, B, C;A, B, C;99Top-down derivation of Top-down derivation of A, B, C;A, B, C;CFGCFGLeft-to-right,Left-to-right,Left-most derivationLeft-most derivationLL(1) parsingLL(1) parsing1010Top-down derivation of Top-down derivation of A, B, C;A, B, C;CFGCFG1111Bottom-up parsing of Bottom-up parsing of A, B, C;A, B, C;CFGCFGLeft-to-right,Left-to-right,Right-most derivationRight-most derivationLR parsingLR parsing(a shift-reduce parser)(a shift-reduce parser)1212Bottom-up parsing of Bottom-up parsing of A, B, C;A, B, C;CFGCFG1313Bottom-up parsing of Bottom-up parsing of A, B, C;A, B, C;CFGCFG1414LR Parsing vs. LL ParsingLR Parsing vs. LL Parsing•LLLL–A ‘top-down’ or ‘predictive’ parserA ‘top-down’ or ‘predictive’ parser–Predict needed productions based on the current left-most Predict needed productions based on the current left-most non-terminal in the tree and the current input tokennon-terminal in the tree and the current input token–The top-of-stack contains the left-most non-terminalThe top-of-stack contains the left-most non-terminal–The stack contains a record of what the parser expects to The stack contains a record of what the parser expects to seesee•LRLR–A ‘bottom-up’ or shift-reduce parserA ‘bottom-up’ or shift-reduce parser–Shifts tokens onto the stack until it recognizes a right-hand Shifts tokens onto the stack until it recognizes a right-hand side then reduces those tokens to their left-hand sideside then reduces those tokens to their left-hand side–The stack contains a record of what the parser has already The stack contains a record of what the parser has already seenseen1515An appropriate LR GrammarAn appropriate LR Grammarid_listid_list  id_list_prefixid_list_prefix ;;id_list_prefixid_list_prefix  id_list_prefixid_list_prefix ,, idid  ididThis grammar can’t be parsed top-down!This grammar can’t be parsed top-down!Problems for LL grammars:Problems for LL grammars:- left recursion, example above- left recursion, example above- common prefixes, example:- common prefixes, example:stmtstmt  id := id := exprexpr | id ( | id (arg_listarg_list))1616LL(1) Grammar for the Calculator LL(1) Grammar for the Calculator LanguageLanguage1717LR(1) Grammar for the Calculator LR(1) Grammar for the Calculator LanguageLanguage1818Hierarchy of Linear ParsersHierarchy of Linear Parsers•Basic containment relationshipBasic containment relationship–All CFGs can be recognized by LR parserAll CFGs can be recognized by LR


View Full Document

UNCA CSCI 431 - Syntax Analysis

Download Syntax Analysis
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Syntax Analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Syntax Analysis 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?