This project will explore the topics learned in class, and give you some simple handson experience. After completing all three parts, you should have a working interpreted language that is unique to you. You are encouraged to have fun and go above and beyond if you have the time. In Part 2 , you will then need to make another small, but substantial change, and create the parser for the modified language. Part 2 assumes you have your lexer form part 1. The changes you make may affect your lexer. So, you may need to go back and update the lexer. If for whatever reason, you do not want to use your lexer from part 1, a lexer will be provided. It will be attached to assignment, and contain instructions for using it. You will be making other changes to your language as the semester goes forward. So, take that into consideration when writing your code. All code should be written in either C,C++,Java, or Python. 1 What to do • Once again modify your language. Use the knowledge in class to decided what change to make. Think about when things should be bound, and the design issues the book presents for the language feature you are considering. For instance, In chapter 6, the book gives the method for implementing arrays. You can use this information to decide the exact kind of arrays you want (assuming that is the change you wish to make). • If the changes to your language causes the grammar to no longer be an LL grammar, then modify it. • Implement the recursive decent parser in your chosen language. At minimum the parser should tell if a program is in the language or not. Preferably, you should print out nice error messages. This will help you with debugging too. 2 What to turn in Upload your submission as a zip archive containing the following: • Source code (c, c++, python, or java files) – Source code should not require a particular IDE to compile and run. – Should work on the cs1 and cs2 machines • Readme (Plain text document) – List the files included in the archive and their purpose – Explain how to compile and run your project – Include any other notes that the TA may need Organization of Programming Languages Page 1 CS/CE 4337 Project Fall 2021 • Write-up (Microsoft Word or pdf format) – An description of your changes. This can be formal (modifying the grammar and semantics) or informal (A text description) – In addition, if you did not complete some feature of the project, why not? ∗ What unsolvable problems did you encounter? ∗ How did you try to solve the problems? ∗ Where do you think the solution might lay? · What would you do to try and solve the problem if you had more time? 3 Grading The grade for this project will be out of 100, and broken down as follows: The change to the language 25 The parser code 65 Correct Output 10 If you were not able to complete some part of the program discussing the problem and potential solutions in the write-up will reduce the points deducted for it. For example, suppose there is a bug in your code that sometimes allows two customers to approach the same worker, and could not figure out the problem before the due date. You can write 2-3 paragraphs in the write-up to discuss this issue. Identify the error and discuss what you have done to try to fix it/find the problem point, and discuss how you would proceed if you had more time. Overall, inform me and the TA that you know the problem exists and you seriously spend time trying to fix the problem. Normally you may lose 5 points (since it is a rare error) but with the write-up you only lose 2. These points can make a large difference if the problem is affecting a larger portion of the program. 4 The Base Language I provide a copy of the language from part 1 for convenience. 4.1 Syntax (1) Ñ (2) Ñ (3) | “;” (4) Ñ (5) | (6) | (7) | (8) | Organization of Programming Languages Page 2 CS/CE 4337 Project Fall 2021 (9) Ñ “print”
(10)
Ñ STRING (11) | (12) Ñ “get” ID (13) Ñ ID “=” (14) Ñ “if” “then” “else” “end” Ñ “while” “do” “end”(15) (16) Ñ (17) Ñ (18) | “and” (19) | “or” (20) Ñ (21) Ñ (22) | “+” (23) | “-” (24) Ñ (25) Ñ (26) | “*” (27) | “/” (28) | “%” (29) Ñ (30) Ñ (31) | “>” (32) | “>=” (33) | “ (34) | “ (35) | “==” (36) | “!=” Ñ “(” “)”(37) (38) | “not” (39) | “-” (40) | ID (41) | INT 4.1.1 Tokens This subsection describes the token used in the above grammar. Provided for each token is a regex and a description. The regex is for those that know regular expressions and prefer it as a description. The description says the same thing in English. Preprocessing describes how the lexeme is transformed before passing it to the parser. Organization of Programming Languages Page 3 CS/CE 4337 Project Fall 2021 STRING As a regex: "([ˆ"]|\")*" Description: A quotation mark followed by zero or more characters, where quotation marks must be preceded by a backslash, followed by another quotation mark. Preprocessing: The first and last quotation marks are removed. Scanning from left to right, “\\” is replaced with “\”, “\t” is replaced with a tab, “\n” is replaced with a newline, “\"” is replaced with “"”, and any “\” that is followed by anything else is removed. ID As regex: [_a-zA-Z][_a-zA-Z0-9]* Description: A letter or underscore followed by a combination of zero or more letters, underscores or digits. INT As Regex: (+|-)?[0-9]+ Description: an optional “+” or “-” followed by one or more digits. 4.2 Static Semantics 1 .ids “ tu 3 r1s.ids “ t .idu Y r0s.ids .ids “ r0s.ids 4 .ids “ .ids 5 .id “ .id 6 .id “ .id .ids “ .ids 7 .ids “ .ids 8 .ids “ .ids 9
.ids “ .ids 11 .ids “
.ids 12 .id “ ID .id 13 .id “ ID .id 16 .ids “ .ids “ Organization of Programming Languages Page 4 CS/CE 4337 Project Fall 2021 18 .ids “ 19 .ids “ 20 .ids “ .ids “ 22 .ids “ .ids 23 .ids “ .ids 24 .ids “ .ids .ids “ .ids 26 .ids “ .ids 27 .ids “ .ids 28 .ids “ .ids 29 .ids “ .ids .ids “ .ids 31 .ids “ .ids 32 .ids “ .ids 33 .ids “ .ids 34 .ids “ .ids 35 .ids “ .ids 36 .ids “ .ids 37 .ids “ .ids 38 r1s.ids “ r0s.ids 39 r1s.ids “ r0s.ids 40 Predicate: ID .id P .ids 4.3 Dynamic Semantics This section gives the dynamic semantics of the language using denotational semantics. Consider the demsem function the denotational semantics for this language. We will use a mapping from variable name to value to represent the symbol table of the program during execution, and in code can be represented as a HashMap or similar datatype in your language of choice. We will use a sequence of characters to represent the output of a program, with representing the empty sequence. I will also assume that all strings will be represented as sequences of characters. Assume there is a function append that, when given two sequences, appends the second sequence to the first. Also assume, there is a function Organization of Programming Languages Page 5 CS/CE 4337 Project Fall 2021 seq that takes an integer and gives a sequence of characters representing that integer as text. Assume there are the functions head, which maps a sequence to its first element, tail, which maps a sequence to a new one created by removing the first element, clean, which maps a sequence of input characters to a new sequence by removing any non-digits from the front of the sequence, and int that maps a sequence of digits to the corresponding integer. If the sequence is empty, int will give zero. A state, as well as the meaning of a program, will be a 3-tuple consisting of a variable name mapping function, a sequence of input characters and an output sequence. The initial state for any program is ptu, i, q, where i is some sequence of characters the user will input. If a token (represented by all caps and bold font) appears as a value on the right hand side of a function definition, then replace it with its lexeme. So if a ID was generated by the lexer from an x, then replace ID with x. densemp,pθ, i, pqq “ pθ, i, pq densemp “;” ,pθ, i, pqq “ densemp , densemp ,pθ, i, pqqq densemp “print” STRING ,pθ, i, pqq “ pθ, i, appendpp, STRING qq densemp “print” ,pθ, i, pq “ pθ, i, appendpp, seqpoutqqq where out “ exprsemp q densemp “get” ID ,pθ, i, pqq “ pθ 1 , i1 , pq where px, i1 q “ getIntpcleanpiqq θ 1 pnq “ if n “ ID then x else θpnq densemp ID “=” ,pθ, i, pqq “ pθ 1 , i, pq where θ 1 pnq “ if n “ ID then exprsemp , θq else θpnq densemp ,pθ, i, pqq “ if exprsemp . , θq ‰ 0 then densemp . r0s,pθ, i, pqq else densemp . r1s,pθ, i, pqq densemp ,pθ, i, pqq “ if exprsemp . , θq “ 0 then pθ, i, pq else densemp , densemp . ,pθ, i, pqqq exprsemp , θq “ if . “ then exprsemp . , θq else bexprsemp . , exprsemp . q, θq exprsemp , θq “ if . “ then exprsemp . , θq else texprsemp . , exprsemp . q, θq Organization of Programming Languages Page 6 CS/CE 4337 Project Fall 2021 exprsemp , θq “ if . “ then exprsemp . , θq else fexprsemp . , exprsemp . q, θq exprsemp , θq “ if . “ then exprsemp . , θq else vexprsemp . , exprsemp . q, θq exprsemp “(” “)” , θq “ exprsemp , θq exprsemp “not” , θq “ if exprsemp , θq “ 0 then 1 else 0 exprsemp “-” , θq “ ´exprsemp , θq exprsemp ID , θq “ θp ID q exprsemp INT , θq “ INT bexprsemp “and” , v, θq “ if v ‰ 0 and exprsemp , θq ‰ 0 then 1 else 0 bexprsemp “or” , v, θq “ if v ‰ 0 or exprsemp , θq ‰ 0 then 1 else 0 texprsemp “+” , v, θq “ v ` exprsemp , θq texprsemp “-” , v, θq “ v ´ exprsemp , θq fexprsemp “*” , v, θq “ v ˆ exprsemp , θq fexprsemp “/” , v, θq “ v exprsemp , θq fexprsemp “%” , v, θq “ v mod exprsemp , θq vexprsemp “>” , v, θq “ if v ą exprsemp , θq then 1 else 0 vexprsemp “>=” , v, θq “ if v ě exprsemp , θq then 1 else 0 vexprsemp “ , v, θq “ if v ă exprsemp , θq then 1 else 0 vexprsemp “ , v, θq “ if v ď exprsemp , θq then 1 else 0 vexprsemp “==” , v, θq “ if v “ exprsemp , θq then 1 else 0 vexprsemp “!=” , v, θq “ if v ‰ exprsemp , θq then 1 else 0 getIntpiq “ pintpxq, i1 q where px, i1 q “ getIntSeqp, iq getIntSeqpi1, i2q “ if digitpheadpi2qq then getIntSeqpappendpi1, headpi2qq, tailpi2qq else pi1, i2q 4.4 Some Example Programs This section contains a few example programs with output. You can use these to check your understanding of the syntax and semantics. In the output, italics are used to indicate the input given by the user. The “ê” symbol is used to show where a newline was printed Organization of Programming Languages Page 7 CS/CE 4337 Project Fall 2021 Code Output print "Hello World!"; Hello World Code Output get x; get y; get z; if (x > y and y) - z then print "\t It is true!\n"; else print "\t It is false!!\n"; end; 3 2 1 It is false!!ê Code Output print "Welcome to my program.\n"; print "Enter a number: "; get x; if x > 0 then x=x*2; else x=-x; end; print x; Welcome to my program.ê Enter a number: 3 6 Organization of Programming Languages Page 8 CS/CE 4337 Project Fall 2021 Code Output print "How many numbers will you input? "; get num; i=0; sum=0; while i