New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Vince Cummings IV

ComparativeLanguages CS480

Vince Cummings IV
GPA 3.55


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 20 page Class Notes was uploaded by Vince Cummings IV on Thursday October 29, 2015. The Class Notes belongs to CS480 at Wright State University taught by Thirunarayan in Fall. Since its upload, it has received 14 views. For similar materials see /class/231104/cs480-wright-state-university in ComputerScienence at Wright State University.

Popular in ComputerScienence


Reviews for ComparativeLanguages


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: 10/29/15
Computer Language Engineering How to give instructions to a computer 7 Programming Languages How to make the computer carryout the instructions efficiently 7 Compilers maximum LZSyntax 1 What is a Lexical Analyzer Source program text gtTokens Examples of Token 39 Operators ltgt 39 Keywords if While for int double 39 Numeric literals 43 6035 36e10 0x13F3A 39 Character literals a N 39 String literals 3 142 Fall empty Examples of nontoken 39 White space space tab t endofline n 39 Comments this is notatoken cy rasa LZSyntax y Program character 7 Token Stream V Optimized Intermediate Repr emny code Svntax and quot of a language 0 Syntax 7 What is the structure of the program minus p 7 Textual representation le ipm eninp Formally de ned using contextfree mmm 3 grammars BackusNam Formalism Semantics 7 What is the meaning ofa program Harder to give amathematical de nition cthEKPnsa LZSyntax S mple arithmetic exl us with and 39 350 7 Wills n 1 39quotI minus What is the grammar for all 1n m mama wm ContextFree Grammars CFGs Terminals 7 Symbols for strings or tokens num7 7 Nonterminals 7 Syntactic variables ltexprgt Start symb ol 7 A special nonterminal ltexprgt Productions 7 The manner in which terminals and nonterrninals are combined to form strings 7 A nonterminal in LHS and a string oftenninals and non terminals in RHS exp ltexpr cthEKPrasa LZSyntax 9 English Language Letters abc Alphabet ab ZU AB Z Tokens Terminals English words Nonterminals ltSentencegt ltSubjectgt Clausegt Contextfree aspect Replacing ltNoungt by ltProper NOungt or ltCommon NOungt Contextsensitive aspects Agreement among words W rt number gender tense etc cysEEKPrasm 125me m Parse Tree Graphical Representation of the parsed structure Shows the sequence of derivations performed 7 Internal nodes are nonterminals 7 Leaves are terminals 7 Each parent node is LHS and the children are RHS of a production 39 Abstracts the details of sequencing of the rule applications but preserves decomposition of a non termjnal cthEKPnsa LZSyntax 13 Ambiguous Grammar Applying different derivation orders produces different parse trees D Leads to ambiguous results D Most probably Will produce unexpected results A CFG is ambiguous if the same string can be associated With two distinct parse trees 7 Eg The expression grammar canbe shown to be ambiguous using expressions containing binary in x operators and non ully parenthesized expressions cy XUQ nsaQ LZSymax m Removing Ambiguig Sometimes rewriting a grammar to re ect operator precedence with additional nonterminals will eliminate the ambiguity D more binding than D ampamp has precedence over H cysXEKPnsad LZSyntax Eliminating Ambiguity ltexprgt gt lttermgt ltexprgt ltexprgt gt lttermgt lttermgt gt ltunitgt lttermgt lttermgt gt ltunitgt ltun1tgt gt num ltexprgt e ltexprgt lt0pgt ltexprgt ltunitgt gt ltexprgt ltexprgt gt ltexprgt lt6Xprgt gt num lt0pgt gt lt0pgt a CMXEKPXASAQ LZSyntax 12 Extended BNF lteXprgt gt lttermgt lttermgt lttermgt gt ltunitgt ltunitgt ltunitgt gt num lteXprgt ltexprgt gt ltexprgt ltexprgt num ltopgt gr I Up lteXprgt gt lteXprgt ltopgt lteXprgt cysXEKPnsad LZSyntax Expression Parser Fragment Node expr PRE Expects lookahead token POST consume an Expression and update Lookahead token whlle 1nTokttype 3939 1nToknextToken7 Node templ term temp new OpNodetemp 3939temp1 return temp CMXEKPXASAQ LZSyntax 2n A hmetic Expressions ambiguous ltexprgt gt ltexprgt ltexprgt ltexprgt ltexprgt ltexprgt ltva1iab1egt ltconstantgt ltva1iab1egt gt X y z ltconstantgt gt 0 1 2 maximum LZSyntax 21 ResolVin Ambi it in EX ressions Different operators precedence relation Same operator 39 associativily relation 52 3 5 23 ZAIZ 2A8 0 6 Le Associative 523 Right Associative 234 CMXEKPXASAQ LZSymax 22 C operator precedence and Associatlvnl Lmi mmr r 1 9mm scape mm 12L Andaman aperatms 17 chsssc 20mm m momma quot5 39gtv m mbquot5 quot39m my gt gt relauamlaperamrs my mnymdex 9L my 0 fmcumcall my 0 2c mam 8quot 15R szeaf azembyt s 7 15R H mmmm Seaman 6 ISR bit 52 T 5 15R lag AL 15R r unuzy plus 3L 15R amp nderence addressuf 2R 15R 0 typecm x cm 15R new am free smumamgzmznt m rgt memberpmnurszlect L mmnpum 12 multiplicative apera ms maximum LZSyntax 23 Concurrent Programing c39lass Thread interface Runnable c39lass Object Multiprocessing 7 Using Multiple Processors Muftgarogramming Batc h 7 Switch and execute different jobs simultaneously to improve CPU utilization Muftitas ing Interactive 7 Perform more than one task at a time for each user to improve response time Muftit reaz ng 7 Threads in a user task process can share code data and system resources and access them concurrently 7 Each thread has a separate program counter registers and a runtime stack man Mm tumng man mm mum 2 Multitasking Browser A Mnhithrended A quot Concurrent Activities ls Q Is 7 Scrolhng a page more atxt Q xclock amp gcc ac 39 aout logout emacs nW ajava Q netscape amp Q emacs ajava amp Qjavac ajava java a Q man Pusan LllThreads 7 Downloading an appleUimage over the internet 7 Playing animation and sound simultaneously 7 Printing a page in the background 7 Updating Stock Quotes automatically 7 FTPing a remote le Browser is a mini OS man Pusan LHTmeads Threads in Java A single sequential ow of control of execution of expressions and statements is called a thread Athread indel endentlv executes Java code but ma share address space with other threads cf Process Java primitives for concurrent programming are based on Hoare s monitors man Pusan Ll lThreads 5 Motivation Application independent interleaving ofthreads Support Concurrent Activities 39 Multimedia Applications 39 Advertisements Sportsstocks ticker Improve user ICSpOl lSC 39 User input in interactive programs 39 10 in networked programs in the background Improve CPU utilization 39 Demanddriven threadscheduling man Pusan Lll39l nreads Overall Gameplan How to create and execute multiple threads 39 Interleaved computations 39 Indiscriminate interleaving interferes with application semantics Introduce Mutual Exclusion constucts 39 Example Printing documents on a shared printer Introduce Synchronization constructs 39 Example Buffering on a shared printer man Pusan Ll lThreads 7 Java Primitives Mutual exclusion synch r om zed methods in a class cannot be run concurrently on behalf of di erem threads Synchronized statement locks an object Object is aninstance ofa class incl class mass Synchronization Cooperation 39 Methods WaWtO HOU O notifyMM etc in Class Object enable threads to communicate and regulate each other s progress man Pusan Lll39l nreads Creating and Running Threads Define subclass of C1 ass Thread Override runO method Creatlng Threads pub39li void runO Create an instance of the subclass and invoke start on it Now who method executes in an independent thread man hum LllThreads 9 man mm LllThreads in Example using c39lass Th read gt Javac Echoava Wmdb lasjnkhoiextends Thread gt Java Echo IABC IABC 951 IABC l 139 IABC pub1139 void run while true 2AM Systemoutpr1nt1n1d ABC mm yieido mac 3 IABC IABC IABC IABC pub1139 stat139 void main smngU args IABC new Eh01 startO IABC new Eh0 2 start quot O IABC BC IABC man hum LllThreads 11 man mm LllThreads 12 Alternative Creating and Running Threads Threads can also be created from an instance of a class implementing the interface Runnable 39 equired When the class is de ned by extension man Pusan Ll lThreads 13 Example using interface Runnable ciass Ecno implements Runnable int id Ecnotint i t id i public VOld runo wnile true Systemoutpr lntlnld ABC quotJ yieldO public static veid main stringu args new Thread new Echo j startO new Thread new EChOQJJ startO man Pusan Llleeads 14 Same Example in C using Systemlhreadlng class Ecno int i Ecnoint i ld i publlc Vold runo wni e true systemtonsolewritetineid ABC J l l public static Vold Main new inread new inreadstart new Ecno1run start new inread new inreadstart new Ecno2run starto man Pusan Ll lThreads IS Alternate Rendition in Java Class Ecno inpienents Runnable p biic VOld runo wnile true Thread s1 eep1000 System out pr lntlnquotAElCquot catcn InterruptedException e return public static veid main String args n b w Edict u na e r ne new aneadtr startt man Pusan Llleeads m Threads and Applets A Simple Bouncing Ball Animation man Pusan Ll lThreads c39lass Ba39l39l stat39ic f39i naT 39int TOP 10 BOTTOM 150 39int 39incr 2 39int ypos TOP vo39id pa39intjavaawtGraph39ics g 1f ypos lt TOP ypos gt BOTTOM 39incr 39incr ypos 39incr gsetCo39lorjavaawtCo39orcyan gf39i39390va3910ypos 1010 man Puma Lll39l nreads 12 ltapplet codeEounceTass ne1gnt200 wTdtn50gtltappTetgt pub1139 Tass Boune extends javaapp1etAppTet Ball b pub1139 void init b new 5311 setBakgr0undjavaawtCOTOrred pub1139 void paintjavaawt6raphis g bpaintg repaint 15 Threaded Applet man Pusan Ll lThreads w pub1139 Tass ThreadedBOune extends javaapp1etAppTet impTements Runnable Ban 3 Thread t pub39l39ic vo39id 39in39itO b new Ba39I39IO setBakgrOundjaVaaWtCOTOr red t new Threadth39i s tstar39 man Puma Lll39l nreads 2n Another version of Threaded Applet pub1139 1355 ThreadedCo1orBoune pub11 Voni pa1ntavaawt6raph1s g ends javaapmetApmet moved the code from here mphments Runname 5311 b Thread t quotquotmquot wquot m0 pub1139 void init try b new Ba11 Wh e true setBak r0und39ava awt C010r red Thread s1 eepus Q J 39 39 39 Pamto puh1139c void startO 39 quotquot11 t h t t dE t i 1 ca c In errup e xcep 10quot e 1 t new Threadnms tstart0 man puma LHThreads 21 man mm LHThruds 22 Color Changlng Ball Pub V31 two 1355 C010rBa11 extends Thread 39 stat139 na1 int TOP 10 BOTTOM 150 javaawtCo1or c javaawtCo1orcyan pub11 v01d pa1ntavaawt6raph1s g int 1 bpainug int ypos 7 TOP 1 pub1139 C010rBa11 puh1139c void runO startO tr whi1e true Void paintjavaawt6raphis g Threads1eep15 39f ypos lt TOP H YPOS gt BOTTOM Pmquotto I ma 71nd yp s 1nr gsetCo1orc catch InterruptedExceptwn e 1 g HOW loyyposy 1010 man puma LHThreads 22 man mm LHThruds 24 pub11c void run try wh11e true s1eep600 c new javaawtCo1or f1oat Mathrandom f1oat Mathrandom f1oat Mathrandom catch InterruptedException e man Pusan Ll lThreads man Pusan Mutual Exclusion Sharing Data LHThreads Threads Sharlng Data Class Shared prwvate Wnt Cnt 0 synchronwzed Vowd prwnt Str1ng Id stemoutpr1ntld Cnt J Systemoutpr1nt1n 7 cntx Class Shared D outpr1nt1d Systemoutpr1nt1n 7 quot Cnt J mm man Pusan Ll lThreads 1355 SharingThread extends Thread private statit Shared s String Id SharingThread String Name Name start pubh39t void run wh e true spr139ntId yie1d0 pubh39t statit void main smng args new SharingThreadC A new SharingThread B I 7 new SharedO man Pusan LHThreads 3 22232 c quotmrrem Access Mutual Exclusion with 11 e39l dg 2 i122 it 39 quot quot n m la k thls quotSaleMMtEUd ansal eWr1eLwE lass SharingThread pnweee Stan Shared s new snaredo ng I Sharingl hread String Mane m e Mane pubh we run 0 wnue ruE SPrvvId pubh Stan vmd Maw sunny 1 e gs new Thread new Threadsrert new Sharingl hread nun Starto new n e r e s e n w Sharwgl hread a LN Starto ceszn Pusan LllThreads 29 man new LllThreads 3n Subclassmg Access Control Class Thread Tn rfea d gt I pubhc Void mno newsmnneem LEWVVOs39 c39lass SubThread extends Thread public Void runO Interaction of Language Features pee eeeeeeeeeeeeemeeeeeeeeeeeeeeeenee run 0 method case study vmd mo eeeeeeeeeeeeeeeeeeemeeeeeeeeeeeeeeeeeeee Otherwise r39un can be invoked on a SubThread instance via its reference in a Thread variable mamas when a csAXu meld 0 dynamic am in other PaCkage 2 Subclassing Exception Class Thread public Void who i class SubThread extends Thread public void run aamaaaaamaaaaamaaaaaaaaaaaaaaaaaaaa public vow who throws InterruptedExtepUnn sleep1000 eeeeeeeeeeeeeeeeeeemeeeeeeeeeeeeeeeeeeee run invoked on a Suleuead instance via a Thread variable by dynamic binding can violate the contract that run or class Thread does nottnrow any excepti canteen Subclassing I synchronized A synchronized method can override or be overridden by a nonsynch roni zed method However this does not alter synchronized status of the overridden method accessible using su pe r The locks are released when syn ch ron i zed statements and synchronized method invocations complete abruptly by th rowing an exception 39Z39Incorporating threads in the language enables dealing with problematic interactions with other language features man 1 an LllThrends synchronized methods A method that is not synchronized can run concurrently with a synchronized method on behalf of different threads 39 The locking analogy breaks down here 39 For concreteness consider an example involving two threads i T1 running synchronized method m1 and ii T2 running ordinary method m2 on the same object 0 A synchronized method can call another synchronized method in the same thread 39 Recursion meaningful sedan Pusan Li lThreads synchronized methods A synchronized instance resp static method locks instance resp static elds 39 A synch roni zed instance method doer not protect static elds and they can corrupt it thro an update 39 For concreteness consider an example involving two threa 5 T1 and T2 ru ning synchronized instance methods m1 and m2 on objects 01 and OZ ofthe same class C Both m1 and m2 are permitted to concurrently access the static elds of C and there is potential for corruption In such situations static elds must be accessed in the body ofinstance methods using calls to synchronized static methods man 1 an LllThrends Thread Scheduling man Pusan Ll lThreads 37 Blocked Thread 39 A thread is blocked that is it is not runnable if it is 7 sleeping 7 suspended 7 waiting 7 executing a blocked method 7 blocked for IO 39 Java neither detects nor prevents deadlocks man Pusan Lll39l nreads 32 Thread Scheduling Java runs a non blocked runnable highestpriority thread A thread can be preempted by a higher A rioritJ thread that becomes runnable 7 The scheduler may however choose to run lower priority thread to avoid starvation The same highest priority threads are run in round robin fashion man Pusan Ll lThreads 39 Scheduling Ambiguity JVM on W i ndows uses timeslicing to schedule same priority threads Fair policy JVM on 01 ar i S chooses one ofthe same priority threads to run until the thread voluntarily relinquishes the CPU by s 39I eeping yielding or exiting or until a higher priority thread preempls it man Pusan Lll39l nreads AU Cooperative Concurrent Threads Producer Consum er Problem Btmnded Buj rProblem Clients and Servers Resource Sharing man Pusan Ll lThreads 41 Simpl39 39c 1Ce11 Buffer 1355 Buffer Obje t x synthronized pubiit void put Objett 7x String id x x i synthronized pubiit Objett get String id retu rn x man Pusan LHTmeads tiass Producer extends Inread Butter b Strung ud pdbiut Producerradtter J3 Strung ud b e b ud ud pdbiut Vdud run 0 unt deiay Integer ir try I whi39le true bputir39 id tattn ExtEptiDn eSystemgutpruntin txteptugns 2 man Pusan Ll lThreads tiass Consmer extends Inread Butter b rung ud pdbiut Consumerradtter b Strung ud b e b ud e ud pdbiut Void run r unt deiay Integer ur e ndii tr whi39le true ur e Integer bgetid tattn ateptugn e Systemgutpruntin txteptuans 2 man Pusan LHTmeads ProducerConsumer Bounded Buffer pub1i 1355 PCB pub1i statit void mainString args fe b new BufferO new Consumerb C1 start new Produterb P1 start new Consumerb C2 startO Unfettered Run pr ature Ready gtgt Cl g3 twmn39 m rmhilinn Ready lt p2 puts 493 Done 2 p 5 Ready ltlt P2 puts 815 Ready ltlt P1 puts 1591 Done ltlt P2 puts 815 1w t Ready gtgt c2 gets D gtgt C2 et Done gtgt c2 gets488 Ready gtgt 1 e 5 Done gtgt c1 gets 1223 get u u Done gtgt C1gets488 new Produterb P2 startO Ready gtgt czg 5 Done F 03 Done gtgt c2 get5488 Read gtgt c2 gets Ready ltlt P1 puts 745 Done gtgt c2 gers 403 Done ltltP1puts745 emu new LllThreads 45 emu prism Lil39i meads 46 Concurrency control C1 a S S B u ffe r C ass Eu er 0 jeCt gtlt boo39lea ty true pubhc synchronized Void put t j Strmg 1d throws Exception public synchronized Object get String 1d throws Exception 1 Two producers consumers cannot putget two same bu pub1i synth ronized void put Objett 7x String id throws Exteption wh39i39le lempty wa39it empty 1 empty m m wint39hn rme v mie w 1 gr not39i fyA39l39l items in from the ffer slot simultaneously 39 Two producers consumers cannot putget two items 1 from me same bug 5101 Wlmom 3 39 Note that 39i f the n cannot replace wh39i quotI e because intervening consumer producer notj 1 AH d t ak tW 39 A consumer producer isnot permitted to get y e 0 a comumer canw 611p 0 put an item from into buffer if empty ill wa39l ting pmducerr and only one producer Will find the buffer empty 39 9 emu Pusan LiiThreads 47 emu Pusan Llleuds public synchronized Object get String id throws Exception wh39i39le empty wa39it empty 39 not39i fyA39l39l 0 return x 39 Note that notify cannot always be used in place of not39i fyA39I39I because a consumer may be woken up wh39i quotI e required because not39i fyA39I39I due to a producer does not guarantee that wa39i t ing consumers will nd an item in the buffer esAzn Pusan Ll lThreads 49 u 39 39 andMumalpwienn Ready gtgt c2 gets Ready ltlt p1 puts 622 Done ltlt p1 puts 622 Ready gt Done gtgt c1 gets 1263 Done ltlt p2 puts 95 es42n Pusan LllThreads 5n Methods in class Object public final void waitO throws InterruptedException 39 Current thread is suspended after aromically releasing the lock on thw 5 until some other thread invokes notwfyt or notifyM l 0 or interrupts pub39l 39i c fi nal vo id notifyO 39 Noti es exactly one thread waiting on this object for a condition to chan e The awakened thread cannot proceed until this thread relinquishes the lock pub39l 39i c fi nal vo id notifyA39l 39I 7 These methods must be invoked inside synch rom zed code or else IllEga39lMDmantatEEXCEpUDn will be thrown esAzn Pusan Ll lThreads Sl Single Cell Buffer in C s mg System using SystEthrEading Class Butter ObJEtt x haul empty ME puphe de put ObJEtt J String 1d WeethwsN wm e lEmpty MDmtDrWa1th15 y CDnSDlEWr1EL1nE DDnE ltlt M puts j 3 l 3 gtlt 7 J Mom or mseA U115 puphe ObJEtt gEt stung 1d lntkth15 m e empty MDmtDrWa1tth15 empty e l empty CDnSDlEMMtELwEC DDnE gtgt M gets gtlt MDmtDrFulSEAllth15 return x l es42n Pusan LllThreads 52 ass Fruduter prwatE SystEmRandnm r new SystEmRandnm Buffy b smng m pumnc rrcducerwutter b Strvvg cm b 4a m g n pumnc vmd run 0 1m dEWay try wh e truE dEWay e rNEgtlt2000 50 anead51eepde1ay c1ass Cansumer VatE SystEmRandnm r new SystmRandnm EuFFEr b Strvvg m pubh tcnsmerwutter b Strvvg cm b e c m 1 pubh vmd run 0 IN a Way i e dEWay e rNEgtlt2000 50 anead51eepde1ay tcnsmewnteunec neady ltlt m puts dEWay tunsmewntemeoReady gtgt m gets j uputmeway M NH 1nt b92t0d catcn EXCEpUDn etansmewnteuneocxceptmns 2 catcn EXCEpUDn e C nSDWEMMtELwnEC BltCEpUDn 2 csAEU new LHThreads 53 man pram LHThreads 54 pubh c1ass FCE pumnc Stan vmd Mawltstrmg 1 args Butter b new EuFfErO new tnneaa new rnneaaStartltnew tansunnerltb 1 mn Stanto new tnneaa new rnneaaStartltnew we erltb m gtmngtgt Stanto tn Thread5 ee1 at n Ex EpUan eansa ew1eLwe Ex entmns em new tnneaa new rnneaaStartltnew tansunnerltb tz gtmngtgt Stanto new tnneaa new rnneaaStartltnew we erltb vz gtmngtgt Stanto 55 man new Ll lThreads


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.