Languages and Computation
Languages and Computation CS 3240
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 3240 at Georgia Institute of Technology - Main Campus taught by Santosh Pande in Fall. Since its upload, it has received 19 views. For similar materials see /class/234001/cs-3240-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Languages and Computation
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
CS 3240 Presentation 4 Finite Automata State Machine enum L1 L2 PB NONE input enum STOPUP MOTORUP STOPDOWN MOTORDOWN state while1 Get input here switchstate case STOPUP ifinput PB state MOTORUP break case MOTORUP ifinput PB input L2 state STOPDOWN break case STOPDOWN ifinput PB state MOTORDOWN break case MOTORDOWN ifinput PB input L1 state STOPUP break setMotorstate Previews of Coming Attractions azAZ azAZO9 letter 0 letter digit Deterministic Finite Automata Regular Expressions Coding a scanner Deterministic Finite Automata Recall that theoreticians have developed a number of theoretical models to describe quotcomputingquot Example Turing Machine Simplest model is known as a DFA Deterministic Machine will be in a state Upon receipt of a certain symbol will go to a known state Finite The machines only have a certain number of states The fascination here is that a machine with a finite number of states can quotrecognizequot an infinite number of strings Automata pl of automaton Cute little computing things DFA39S DFA39s recognize strings lfthe input ends and the DFA is in an accept state then the string is quotrecognizedquot A quotlanguagequot can be described as a set of strings A language is called a regular language if some finite automaton recognizes it There is a precise mathematical definition of exactly what is meant by a finite automaton Parts of a DFA start state I DFA Examples Accep r all s rr39ings Tha r end in 1 DFA Examples Accep r strings of 390395 and 39b39s Tha r begin and end wi rh same symbol DFA Examples Keep running coun r of 1 To ral of Symbols read in mod 3 Accep r on O DFA Examples S rr39ings wi rh an odd number of ones DFA Examples S rr39ings con raining The Subs rr39ing 001 Can DFA39s be designed to accept any string 1Yes 2No Examples Design a DFA to recognize strings that start out with k zeros followed by k ones Design a DFA to recognize strings with an equal number of ones and zeros Design a DFA to recognize strings with an equal number of strings quot01quot and quot10quot Impossible 1yes 2No Actually the third one is regular DFA to recognize strings with an 1 0 equal number of strings quot01quot and H 10quot DFAs Regex DFA39s are a mathematical concept representing a machine that can recognize strings in a language Languages recognizable by a DFA are regular DFAs Regex Regular expressions also may be used to provide a description of a language The value of the arithmetic expression 534 is 32 The value of a regular expression is a language Regular expressions and DFA are equivalent Regular expressions are common in many CS apps Lexical Analysis State Machines A lexical analyzer is a state machine A state machine is a virtual or real device which responds to inputs with certain outputs that depend on what internal state the machine is in This state is also changed as a result of the inputs State machines are very similar to finite automata GD Start Symbology Start State State 42 End State letter 3 letter digit Typical State Transitions Problem Create a state machine that will recognize identifiers Error states omitted for simplicity Recognize dentifiers CD Start Begin is quotStart Statequot Read a character Change state depending on character read Underscore omitted for simplicity Recognize Identifiers Letter Start Recognize Identifiers Letter Letter Digit Recognize Identifiers Letter Letter Digit Identi er Letter Digit Notice the difference between this and pure finite automata More Complex In a case like this i i 7 ltidentgt ltopergt ltidentgt ltopergt ltliteralgt ltspecialgt the white space characters terminate each identification but what about a case like this ii7 The character which terminates the identification process is part of the next token What to do We need to save the last character ie the one that put us in the end state How Push back on input Save a character in a variable VVhHespace Very little whitespace is actually required by c main return EXITSUCCESS would compile There are some places where c does require whitespace int i Lookahead In some languages the language specification is such that the determination of what token type is being scanned cannot be determined until well after the beginning of the token Example FORTRAN Variables don39t have to be explicitly declared Implicit typing based on first character Real numbers begin with AH or 02 Integers begin with lN Mimicked typical mathematical convention Lookaheadcon nued Fortran continued Typical loop construct DO 10 I 110000 10 CONTINUE meaning do all statements from the Do statement up to and including statement 10 starting I with a value of 1 and ending with a value of 10000 incrementing by 1 as default Lookaheadcon nued Fortran continued Spaces have no meaning so DO 10 I 1 100000 would be equivalent to D010I1100000 which would be differentiated from D010I1100000 when the compiler encountered the or State Machine to Recognize Number Digit Start State Machine to Recognize Number Digit Digit Start 39 Digit State Machine to Recognize Number Digit Digit Modify to Recognize Sign Modify to Recognize Decimals Int Digit Digit Problem with State Machines Drawings quickly get too big Need way to convert into code What is needed State variable While Loop Input a character Switch Recognize Identifiers Letter Letter Digit Identi er Letter Digit Example enum STATE1 STATE2 STATE3 state int inchar state STATEl whileinchargetcharEOF switchstate case STATEl ifinchar 39a39 ll inchar 39b39 inchar 39C39 II inchar 39d39 inchar 39e39 inchar 39f39 inchar 39g39 inchar 39h39 inchar 39i39 ll inchar 39j39 inchar 39k39 inchar 39139 How do you like it so far Example enum STATE1 STATE2 STATE3 state int inchar state STATEl whileinchargetcharEOF switchstate case STATEl ifinchar gt 39a39 ampamp inchar lt 39239 inchar gt 39A39 ampamp inchar lt 39Z39 Better Example enum STATE1 STATE2 STATE3 state int inchar state STATEl whileinchargetcharEOF switchstate case STATEl iftoupperinchar gt 39A39 ampamp toupperinchar lt 39Z39 Now we39re cookin39 Example enum STATE1 STATE2 STATE3 state int inchar state STATEl whileinchargetcharEOF switchstate case STATEl ifisalphainchar state STATE2 else ERROR endif break Example case STATE2 ifisalphainchar isdigitinchar Here we go again Example case STATE2 ifisalnuminchar state STATE2 else state STATE3 break Example case STATE2 ifisalnuminchar state STATE2 else state STATE3 break case STATE3 ungetcstdin inchar Check return break Okay 1 Yes 2 No Example case STATE2 ifisalnuminchar state STATE2 else state STATE3 break TATE3 inchar Why not Example case STATE2 ifisalnuminchar state STATE2 else state STATE3 break c TATE3 Example case STATE2 ifisalnuminchar state STATE2 else state STATE34 ungetc here break 0 TATE3 ungetc lt inchar Example case STATE2 ifisalnuminchar state STATE2 else state STATE3 ungetcstdin inchar break Depending on situation should be able to break out of loop upon reaching STATE3 Anything Missing Example case STATE2 ifisalnuminchar state STATE2 else state STATE3 ungetcstdin inchar break default Handle Error Longest Match Algorithm While inputcharread newlinellwhite spacelltab Loop skipping white space Decide which tokentokens start with inputcharread Set flags to note which tokens are potentially being recognized Whileinputcharread char that matches no token being recognized Adjust flags to reflect which tokens are still being recognized Push the character that matches no token back onto input stream Return token to caller based on flag TOKEN int alphanum TOKEN if other alphanum other other alphanum alphanum alphanum TOKEN identifier Lexical Analysis Tokens are assigned a number Each quotclassquot of literal is assigned a number int float string etc A single code is assigned to all identifiers Token Types Operators 0 1 2 3 4 Special 10 11 12 13 14 Keywords if else for while 20 21 22 23 Literals 42 3141592 quotHellonquot 30 31 32 Identifiers 4A Za zA Za z0 9 40 Questions Questions
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'