Spring 2026 Programming Languages Homework 1 cid 136 Due Monday February 16 2026 11 59 PM Eastern Standard Time cid 136 The homework must be submitted entirely through NYU Brightspace do not send by email Make I do not sure you complete the entire submission process in Brightspace before leaving the page recommend waiting until the last minute to submit in case you encounter di culties cid 136 Late submissions will not be accepted No exceptions I highly recommend that you submit well in advance of the deadline to ensure that your submission is successfully transmitted cid 136 This assignment consists of programming tasks in Flex Bison and also pencil and paper questions Submit programs according to the instructions in question 4 Submit all other written responses in a single PDF document It is okay if you scan in a handwritten document for some questions as long as everything is together in a single PDF document cid 136 The Flex and Bison part of this assignment requires some minor coding in either C or C in order to capture tokens and also specify the semantic actions whenever a rewrite rule is invoked It is highly recommended that you get started right away on writing the scanner and grammar This will require some time to complete properly cid 136 Your Flex and Bison assignments must be tested to execute properly on the CIMS computers using Flex 2 6 and Bison 3 7 These versions should already be installed on the CIMS computers You can use any system you want to perform the development work but in the end it must run on the CIMS machines All students registered in this course who do not already have accounts on CIMS should have received an email with instructions on how to request an account cid 136 While you are working on this assignment you may consult the lecture material class notes text book discussion forums and or recitation materials for general information concerning Flex Bison grammars or any topics related to the assignment You may under no circumstance collaborate with other students or use materials from an outside source i e people books Internet etc in answering speci c homework questions However you may collaborate and utilize reference material for understanding the general topics covered by the homework For example discussing the topic of regular expressions or the C C programming languages with a classmate is permitted as long as the discussion does not involve homework questions or solutions 1 1 15 points Language Standards A programming language s standard serves as an authoritative source of information concerning that language Someone who claims expertise in a particular programming language should be thoroughly familiar with the language standard governing that language In the exercises below you will look into the language standards of several well known languages includ ing C C Java and C to nd the answers to some basic questions You should use the standards documents on the course web page which contain recent publicly available documents In your answers to every question below you must cite the speci c sections and passages in the relevant standard s serving as the basis for your answer No prior knowledge of either language is assumed nor expected but you cannot simply provide the answer with no evidential support from the standard or you will lose credit Do not cite to web pages books textbooks Stack Over ow or any other source other than the language standard 1 In C where would we go in the standard to learn more about writing functions with variable arguments and the associated macros available for doing so 2 In C a class can be inherited from a base class using the protected access speci er What is the meaning of this 3 In C the user can create their own literals using four underlying C types What are the types What are the semantics of a user de ned literal what happens when it is used 4 In Java can data members of a class be initialized with default values if no other value is speci ed If so where can the default values be found 5 In Java what do instances of class String internally represent Are instances of String mutable can they be modi ed or are they constant 6 In Java most people know or can at least guess what an assignment is But what about a de nite assignment In your own words what does it mean to be de nitely assigned and what does de nite assignment ensure 7 What are the three kinds of linkages de ned in the context of identi ers in the C programming language Explain how each kind of linkage a ects the visibility and scope of identi ers within a program 8 In C elds declared as readonly generally cannot be assigned However there are exceptions Where can they be assigned meaning of a nullable type compiler required to enforce this 9 In C state in your own words what a lifted operator is You will likely also need to research the 10 In Java it is well known that the lesystem tends to mirror the package structure However is the 11 In Java the output of the compilation process is typically a set of so called class les les in a binary format containing intermediate code such as Bytecode However must the output of compilation be class les or does the standard allow other formats too Page 2 2 15 points Grammars and Parse Trees 1 For each of the following grammars describe in English the language described by the grammar Describe the language not the grammar Example answer The language whose strings all contain one or more a s followed by zero or more b s followed optionally by c Assume S is the start symbol The non terminals and terminals alphabet are implied by the rewrite rules EBNF a S aSb bSa b S 1T0 T 0S0 0S1 1S0 1S1 0 c S 1T T 0T 1T U U 1 T aba A 0B 1S B 1A 0S f S S S SS g S cSc cTc d S TS e S 0S 1A 1B 0 T A B A aA a B bB b 2 Consider the language of all strings over the alphabet a b c consisting of all the following a a possibly empty block of a s on the left b followed by at least one b c followed by a possibly empty block of a s on the right d Requirement the number of a s on the left is greater than or equal to the number of a s on the right Write a non ambiguous grammar satisfying the above requirements that contains no left recursion 3 a Give a context free grammar that accepts all the strings generated by the regular expression ab c d and rejects all other strings All the symbols have the same semantic meaning as discussed in the lecture b Draw a parse tree for the string acabc using the grammar described in a Does this string