Question? Leave a message!




Regular Expressions and Context-Free Grammars

Regular Expressions and Context-Free Grammars
Dr.MasonHanks Profile Pic
Dr.MasonHanks,Germany,Teacher
Published Date:23-07-2017
Website URL
Comment
MIT 6.035 Specifying Languages with Regular Exp pressions and Context-Free Grammars Martin Rinard Laboratory for Computer Science Massachusetts Institute of Technology Language Definition Problem • How to precisely define language • L Layeredd st truct ture of f l language d defifi nitii ti on • Start with a set of letters in language • • Lexical Lexical structure structure - identifies identifies “words words ” in in language language (each word is a sequence of letters) • • Syntactic Syntactic s structure tructure - identifies identifies “sentences sentences ” in in language (each sentence is a sequence of words) • Semantics - meaning g of p prog gram ( (sp pecifies what result should be for each input) • Today’s topic: lexical and syntactic structures Specifying Formal Languages • Huge Triumph of Computer Science • Beautiful Theoretical Results • Practical Techniques and Applications • Two Dual Notions • Generative approach (g ( rammar or regullar expressiion) ) • Recognition approach (automaton) • Lots Lots of of theorems theorems about about converting converting o one ne approach approach automatically to another Specifying Lexical Structure Using Regular Regular Expressions Expressions • Have some alphabet ∑ = set of letters • R Regull ar expressii ons are b b uilt ilt f f rom: • ε -empty string • • Any A nyl letter ett erf from roma alphabet l ph ab et ∑∑ •r r – regular expression r followed by r 1 2 1 2 (sequence) (sequence) •r r – either regular expression r or r 1 2 1 2 ( (choice) ) • r - iterated sequence and choice ε r rr … • Parentheses to indicate grouping/precedence Concept of Regular Expression Generating Generating a a String String Rewrite regular expression until have only a sequence sequence of of letters letters (string) (string) left left Examp ple Gener Genera al l R Rul ules es (0 1).(01) 1) r r→ r 1 2 1 () (0 1)((0 ) 1).((01)) 2) r r→ r 1(01).(01) 1 2 2 1.(01) 3) ) r →rr 1.(01)(01) 4) r →ε 1.(01) 1.0 Nondeterminism in Generation • Rewriting is similar to equational reasoning • But different rule applications may yield different final results Examp p le 1 Example Example 2 2 (01).(01) (01).(01) (01)(01).(01) (() 01)((01)).((01)) 1(01).(01) 0(01).(01) 1.(01) 0.(01) 1 1.(01)(01) (01)(01) 0.(01)(01) 1.(01) 0.(01) 110 .0 001 .1 Concept of Language Generated by Regular Regular Expressions Expressions • Set of all strings generated by a regular expression expression is is language language of of regular regular expression expression • In general, language may be (countably) infinite • • String String in in language language is is often often called called a a token tokenExamples of Languages and Regular Expressions Expressions • ∑ = 0, 1, . • (01) (01) .(01) (01) Bi Binary fl fl oati ti ng poii nt t numb bers - • (00) - even-length all-zero strings • • 1(0101) 1(0101) strings strings w with ith e even ven number number of of - zeros • ∑∑ = a a,bb ,cc , 00 , 11 , 2 2 • (abc)(abc012) - alphanumeric identifiers • (012) - trinary numbers Alternate Abstraction Finite Finite-State State A Automata utomata •Alphabet ∑ • S S et t of f st tat tes wiith th i iniiti ti al l and d accept t st tat tes • Transitions between states, labeled with letters (01).(01) Start state 1 1 . 0 0 Accept stateAutomaton Accepting String Conceptually, run string through automaton • Have current state and current letter in string • Start with start state and first letter in string • At each step, match current letter against a transition wh hose llab bell is same as lletter • Continue until reach end of string or match fails • If If end d iin accept t st tat te, aut tomat ton accept ts st triing • Language of automaton is set of strings it accepts Examp p le Current state Start state 1 1 . . 0 0 Accept state 11.0 Current Current let letter ter Examp ple Current state Start state 1 1 . . 0 0 Accept state 11.0 Current Current let letter ter Examp ple Current state Start state 1 1 . . 0 0 Accept state 11.0 Current Current let letter ter Examp ple Current state Start state 1 1 . . 0 0 Accept state 11.0 Current Current let letter ter Examp ple Current state Start state 1 1 . . 0 0 Accept state 11.0 Current Current let letter ter Examp ple Current state Start state 1 1 . . 0 0 Accept state 11.0 String is accepted Current Current let letter ter Generative Versus Recognition • Regular expressions give you a way to generate all strings in language • Automata give you a way to recognize if a specific string is in language •Phl hilosoph hicalllly very d diff fferent • Theoretically equivalent (for regular expressions expressions a and nd automata) automata) • Standard approach • • Use Use r regular egular expressions expressions w when hen d define efine llanguage anguage • Translated automatically into automata for implementation implementation From Regular Expressions to Automata Automata • Construction by structural induction • Gi Given an arbit bitrary regull ar expressiion r • Assume we can convert r to an automaton with • • One One start start state state • One accept state • • Show Show how how to convert all constructors to deliver o c c o an automaton with • One One start start state state • One accept state Basic Constructs Start state Accept Accept s state tate ε εε a a∈Σ Sequence Start state Accept Accept s state tate r r r r 1 1 2 2 1 1 2 2