DOC PREVIEW
U of I CS 421 - Programming Languages and Compilers

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 421 - Programming Languages and Compilers

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Programming Languages and Compilers
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 Programming Languages and Compilers 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 Programming Languages and Compilers 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?