Syntax Specification (Sections 2.1-2.2.1)Phases of CompilationSyntax AnalysisReview: Formal definition of tokensReview: Regular ExpressionsReview: Token Definition ExampleExerciseSlide 8Slide 9Slide 10Context Free GrammarsBackus-Naur FormExtended Backus-Naur FormSlide 14DerivationsDerivation ExampleParse TreesAmbiguous GrammarsDesigning unambiguous grammarsExampleJava Language Specification11Syntax SpecificationSyntax Specification(Sections 2.1-2.2.1)(Sections 2.1-2.2.1)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 Hill22Phases of CompilationPhases of Compilation33Syntax 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»i.e.i.e. Organization of tokens Organization of tokens–Formal notationFormal notation»Context Free Grammars (CFGs)Context Free Grammars (CFGs)44Review: Formal definition of tokensReview: Formal definition of tokens•A set of tokens is a set of strings over an alphabetA set of tokens is a set of strings over an alphabet–{read, write, +, -, *, /, :=, 1, 2, …, 10, …, 3.45e-3, …}{read, write, +, -, *, /, :=, 1, 2, …, 10, …, 3.45e-3, …}•A set of tokens is a A set of tokens is a regular setregular set that can be defined by that can be defined by comprehension using a comprehension using a regular expressionregular expression•For every regular set, there is a For every regular set, there is a deterministic finite deterministic finite automatonautomaton (DFA) that can recognize it (DFA) that can recognize it–i.e.i.e. determine whether a string belongs to the set or not determine whether a string belongs to the set or not–Scanners extract tokens from source code in the same way Scanners extract tokens from source code in the same way DFAs determine membershipDFAs determine membership55Review: Regular ExpressionsReview: Regular Expressions•A regular expression (RE) is:A regular expression (RE) is:–A single characterA single character–The empty string, The empty string, –The The concatenationconcatenation of two regular expressions of two regular expressions»Notation:Notation: RE RE11 RE RE22 ( (i.e. i.e. RERE11 followed by RE followed by RE22))–The The unionunion of two regular expressionsof two regular expressions»Notation: Notation: RERE11 | RE | RE22–The The closureclosure of a regular expression of a regular expression»Notation: Notation: RE*RE*»* is known as the * is known as the Kleene starKleene star»* * represents the concatenation of 0 or more stringsrepresents the concatenation of 0 or more strings66Review: Token Definition ExampleReview: Token Definition Example•Numeric literals in PascalNumeric literals in Pascal–Definition of the token Definition of the token unsigned_numberunsigned_numberdigit digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9unsigned_integer unsigned_integer  digitdigit digitdigit**unsigned_number unsigned_number  unsigned_integer unsigned_integer ( ( . ( ( . unsigned_integer unsigned_integer ) | ) |  ) )( ( e ( + | – | ( ( e ( + | – | ) ) unsigned_integer unsigned_integer )) | |  ) )•Recursion is not allowed!Recursion is not allowed!77ExerciseExercisedigit digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9unsigned_integer unsigned_integer  digitdigit digitdigit**unsigned_number unsigned_number  unsigned_integer unsigned_integer ( ( ( ( .. unsigned_integer unsigned_integer ) | ) |  ) )( ( e ( + | – | ( ( e ( + | – | ) ) unsigned_integer unsigned_integer )) | |  ) )•Regular expression forRegular expression for–Decimal numbersDecimal numbersnumber number  … …88ExerciseExercisedigit digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9unsigned_integer unsigned_integer  digitdigit digitdigit**unsigned_number unsigned_number  unsigned_integer unsigned_integer ( ( ( ( .. unsigned_integer unsigned_integer ) | ) |  ) )( ( e ( + | – | ( ( e ( + | – | ) ) unsigned_integer unsigned_integer )) | |  ) )•Regular expression forRegular expression for–Decimal numbersDecimal numbersnumber number  ( + | – | ( + | – | ) ) unsigned_integer unsigned_integer ( ( ( (  unsigned_integer unsigned_integer ) | ) |  ) )99ExerciseExercisedigit digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9unsigned_integer unsigned_integer  digitdigit digitdigit**unsigned_number unsigned_number  unsigned_integer unsigned_integer ( ( ( ( .. unsigned_integer unsigned_integer ) | ) |  ) )( ( e ( + | – | ( ( e ( + | – | ) ) unsigned_integer unsigned_integer )) | |  ) )•Regular expression forRegular expression for–IdentifiersIdentifiersidentifier identifier  ……1010ExerciseExercisedigit digit  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9unsigned_integer unsigned_integer  digitdigit digitdigit**unsigned_number unsigned_number  unsigned_integer unsigned_integer ( ( ( ( .. unsigned_integer unsigned_integer ) | ) |  ) )( ( e ( + | – | ( ( e ( + | – | ) ) unsigned_integer unsigned_integer )) | |  ) )•Regular expression forRegular expression for–IdentifiersIdentifiersidentifier identifier  letter letter ( ( letterletter | digit | | digit |  )* )*letter letter  a | b | c | … | z a | b | c | … | z1111Context 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 