1Programming Languages and Compilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/sp07/cs421/Based in part on slides by Mattox Beckman, as updated by Vikram Adve and Gul AghaElsa L. GunterMeta-discourse• Language Syntax and Semantics• Syntax- DFSAs and NDFSAs- Grammars • Semantics- Natural Semantics- Transition SemanticsElsa L. GunterLanguage Syntax• Syntax is the description of which strings of symbols are meaningful expressions in a language• It takes more than syntax to understand a language; need meaning (semantics) too• Syntax is the entry pointElsa L. GunterSyntax of English Language• Pattern 1• Pattern 2Elsa L. GunterElements of Syntax• Character set – previously always ASCII, now often 64 character sets• Keywords – usually reserved• Special constants – cannot be assigned to• Identifiers – can be assigned to• Operator symbols• Delimiters (parenthesis, braces, brackets)• Blanks (aka white space)Elsa L. GunterElements of Syntax• Expressionsif ... then begin ... ; ... end else begin ... ; ... end• Type expressionstypexpr1-> typexpr2• Declarations (in functional languages)let pattern1= expr1in expr• Statements (in imperative languages)a = b + c • Subprogramslet pattern1= let rec inner = … in expr2Elsa L. GunterElements of Syntax• Modules• Interfaces• Classes (for object-oriented languages)Elsa L. GunterFormal Language Descriptions• Regular expressions, regular grammars, finite state automata• Context-free grammars, BNF grammars, syntax diagrams• Whole family more of grammars and automata – covered in automata theoryElsa L. GunterGrammars• Grammars are formal descriptions of which strings over a given character set are in a particular language• Language designers write grammar• Language implementers use grammar to know what programs to accept• Language users use grammar to know how to write legitimate programsElsa L. GunterRegular Expressions• Start with a given character set –a, b, c…• Each character is a regular expression– It represents the set of one string containing just that characterElsa L. GunterRegular Expressions• If x and y are regular expressions, then xy is a regular expression– It represents the set of all strings made from first a string described by x then a string described by yExample: If x = a and y = b then xy = ab.• If x and y are regular expressions, then x∨∨∨∨yis a regular expression– It represents the set of strings described by either x or yExample: If x = a and y = b then x ∨∨∨∨ y = a | b.Elsa L. GunterRegular Expressions• If x is a regular expression, then so is (x)– It represents the same thing as x• If x is a regular expression, then so is x*– It represents strings made from concatenating zero or more strings from xExample: If x = a then x* = a*.• εεεε– It represents the empty set3Elsa L. GunterExample Regular Expressions• (0∨∨∨∨1)*1– The set of all strings of 0’s and 1’s ending in 1, {1, 01, 11,…}• a*b(a*)– The set of all strings of a’s and b’s with exactly one b• ((01) ∨∨∨∨(10))*– The set of even length strings that has zero or more occurrences of 01 or 10 • Regular expressions (equivalently, regular grammars) important for lexing, breaking strings into recognized wordsElsa L. GunterExample: Lexing• Regular expressions good for describing lexemes (words) in a programming language– Identifier = (a ∨ b ∨ … ∨ z ∨ A ∨ B ∨ … ∨Z) (a ∨ b ∨ … ∨ z ∨ A ∨ B ∨ … ∨ Z ∨ 0 ∨ 1 ∨ … ∨ 9)*– Digit = (0 ∨ 1 ∨ … ∨ 9)– Natural Number = (1 ∨ … ∨ 9)(0 ∨ … ∨ 9)*– Keywords: if = if, while = while,…Elsa L. GunterImplementing Regular Expressions• Regular expressions reasonable way to generate strings in language• Not so good for recognizing when a string is in language• Problem with Regular Expressions–which option to choose,– how many repetitions to make• Answer: finite state automataElsa L. GunterFinite State Automata• A finite state automata over an alphabet is:– a directed graph– a finite set of states defined by the nodes– edges are labeled with elements of alphabet, or empty string; they define state transition– some nodes (or states), marked as final– one node marked as start state• Syntax of FSAElsa L. GunterExample FSA0 110Start StateFinal StateFinal State1010Elsa L. GunterDeterministic FSA’s• If FSA has for every state exactly one edge for each letter in alphabet then FSA is deterministic– No edge labeled with ε• In general FSA in non-deterministic.– NFSA also allows edges labeled by ε• Deterministic FSA special kind of non-deterministic FSA4Elsa L. GunterDFSA Language Recognition• Think of a DFSA as a board game; DFSA is board• You have string as a deck of cards; one letter on each card• Start by placing a disc on the start stateElsa L. GunterDFSA Language Recognition• Move the disc from one state to next along the edge labeled the same as top card in deck; discard top card • When you run out of cards,– if you are in final state, you win; string is in language–if you are not in a final state, you lose; string is not in languageElsa L. GunterDFSA Language Recognition -Summary• Given a string over alphabet• Start at start state• Move over edge labeled with first letter to new state• Remove first letter from string• Repeat until string gone• If end in final state then string in language• Semantics of FSAElsa L. GunterExample DFSA• Regular expression: (0 ∨ 1)* 1• Deterministic FSA0110Elsa L. GunterExample DFSA• Regular expression: (0 ∨ 1)* 1• Accepts string 0 1 1 0 10110Elsa L. GunterExample DFSA• Regular expression: (0 ∨ 1)* 1• Accepts string 0 1 1 0 101105Elsa L. GunterExample DFSA• Regular expression: (0 ∨ 1)* 1• Accepts string 0 1 1 0 10110Elsa L. GunterExample DFSA• Regular expression: (0 ∨ 1)* 1• Accepts string 0 1 1 0 10110Elsa L. GunterExample DFSA• Regular expression: (0 ∨ 1)* 1• Accepts string 0 1 1 0 10110Elsa L. GunterExample DFSA• Regular expression: (0 ∨ 1)* 1• Accepts string 0 1 1 0 10110Elsa L. GunterExample DFSA• Regular expression: (0 ∨ 1)* 1• Accepts string 0 1 1 0 10110Elsa L. Gunter• NFSA generalize DFSA in two ways:• Include edges labeled by ε– Allows process to non-deterministically change stateNon-deterministic FSA’s01ε06Elsa L.
View Full Document