CS/CE 4337 Homework 01 Spring 2021 Chapter 3: Describing Syntax and Semantics 1. (2pts) Briefly describe what a lexeme and a token is. 2. (2pts) When can a parse tree be called “fully attributed”? 3....

This class is organization of Programming Languages. It is an undergraduate course. So keep the solutions appropriate to undergraduate level. The topic is: Describing Syntax and Semantics.

I only nee question 6-11. KEEP IN MIND THE 11TH QUESTION IS NOT TO BE DONE IMMEADIATLEY. AS PER GUIDELINES 11TH QUESTION STILL NEED TO BE UPDATED AND IS NOT FINSHED. So please don't work on 11 till told. Finish the remaining questions, till then. Strictly adhere to the deadline

CS/CE 4337 Homework 01 Spring 2021 Chapter 3: Describing Syntax and Semantics 1. (2pts) Briefly describe what a lexeme and a token is. 2. (2pts) When can a parse tree be called “fully attributed”? 3. (2pts) Briefly describe the two levels of uses of operational semantics. 4. (2pts) In denotational semantics, what are the syntactic and semantic domains? 5. (2pts) What is the weakest precondition? 6. (10pts) Consider the following grammar: → → | ENDLINE → ID “->” → | “,” → ID | “&” | “%” | “*” Assume is the start symbol. Assume that all caps represents a token, quoted sequence of symbols lexemes, and angle brackets nonterminals. Also assume that the ENDLINE token is the groups of lexemes representing an end of line. The ID token represents ids in the “C” sense (start with letter or underscore, a seqence of alphanumeric and underscore characters). (a) Give a sentence in this language that is generated from at least 3 . (b) Show the left-most derivation for your sentence. (c) Show the right-most derivation for your sentence. (d) Show the parse tree for your sentence. 7. (10pts) Consider the following grammar:

→ | → “a” | “a” → “b” | “b” → “a” “b” | “a” “b” (a) Show that this grammar is ambiguous. (b) Rewrite the grammar to a one that is unambiguous. The new grammar must generate the exact same language. HINT: Only a single rule needs to be changed. Organization of Programming Languages Page 2 CS/CE 4337 Homework 01 Spring 2021 8. (10pts) Recall the following grammar from question 6: → (1) → (2) | ENDLINE (3) → ID “->” (4) → (5) | “,” (6) → ID (7) | “&” (8) | “%” (9) | “*” (10) Consider the following semantic functions/predicates: (1) Predicate: “main” ∈ .ids (2) .ids = { .id} (3) [0].ids = { .id} ∪ [1].ids (4) .id = ID .id .id = ID .id (5) .id = .id (6) .id = [0].id [1].id = [0].id (7) Predicate: .id! = ID.id This attributed grammar specifies two static semantic “rules” (restrictions on the programs in this language). What are they? Give a brief description on how they are enforced. For each rule, are the attributes involved synthesized, inherited, or a mixture of both? Organization of Programming Languages Page 3 CS/CE 4337 Homework 01 Spring 2021 9. (10pts) Recall the attributed grammar from question 8. Consider the following op- erational semantics: // int x = 0 label ret label = !start goto main Expand !start: display x // Expand // Expand ENDLINE // Expand Expand ID “->” // ID: Expand // Expand “,” // Expand Expand // Expand ID // label oldret = ret label label cur = unique label() label ret label = cur goto ID cur: label ret label = oldret “&” // int x = x + 1 “%” // int x = x*2 “*” // display x NOTE: The format is similar to our example form class. The semantics in this ques- Organization of Programming Languages Page 4 CS/CE 4337 Homework 01 Spring 2021 tions is different from the one presented in other questions. For the following progams, what will be printed when it is ran? Brielfly explain why. (a) main -> step,show step -> &,& show -> %,&,* (b) main -> one,two,three,four one -> two,&,* two -> &,& three -> four,*,& four -> *,*,&,% 10. (10pts) Recall the attributed grammar from question 8. Consider the following de- notational semantics: densem( ENDLINE ) = densem( ) ∪ densem( ) densem( ID “->” ) = {( ID , bodysem( ))} bodysem( “,” ) = bodysem( ) + bodysem( ) bodysem( ID ) = if ID = main then 10 else 1 bodysem( “&” ) = 2 bodysem( “%” ) = 100 bodysem( “*” ) = −10 NOTE: The format is similar to our example form class. The semantics in this ques- tions is different from the one presented in other questions. For the following progams, what is the mathematical meaning? Brielfly explain why. (a) main -> step,show step -> &,& show -> %,&,* (b) main -> one,two,three,four one -> two,&,* two -> &,& three -> four,*,& four -> *,*,&,% Organization of Programming Languages Page 5 CS/CE 4337 Homework 01 Spring 2021 11. (10pts) Recall the attributed grammar from question 8. Consider the following ax- iomatic semantics: This problem is incomplete. I will update it later. NOTE: The semantics in this questions is different from the one presented in other questions. For the following progams, assuming the precondition is {}, what is the vlaue of δ(main(δ)) in the postcondition? Show the proof. (a) main -> step,show step -> &,& show -> %,&,* (b) main -> one,two,three,four one -> two,&,* two -> &,& three -> four,*,& four -> *,*,&,% Organization of Programming Languages Page 6