COMP 2049 Languages and Computation Coursework: Floating-Point Numbers and Simple Arithmetic Expressions
1 Floating-Point Numbers
Design a right-linear grammar G1 that generates the language of binary floating-point literals according to the following rules:
• Each number may be signed or unsigned.
– unsigned as in 1.01, signed as in +1.01 or -1.10
• The numerical part (also called the value field) must be non-empty and may optionally include a decimal point ’.’, in which case it must be followed by some other digits. For instance:
– In the number +110.11, the value filed is 110.11.
– 1 and .01, -.001, 001 are all acceptable, but 1., +, - and λ are not.
• There may be an optional exponent field, in which case, it must contain the letter ’e’, followed by a signed or unsigned integer.
– For instance, 101e+1 or -1.1e10 are acceptable, but 1.01e, 1.01e-1.1 and e11 are not. Furthermore, there must be at least one digit between the decimal point ’.’ and the letter ’e’. Hence,
strings such as 11.e01 are not acceptable.
Task 1. Implement the grammar G1 in JFLAP, and test it on some input strings of your choice.
A screenshot of the result of parsing of some sample input strings for grammar G1 in JFLAP is provided in Figure 1.
Figure 1: Some sample input and the corresponding results
Remark 1.1 In all of the tasks of this coursework, the default parsing method should be the “brute force parsing”. Hence, to test your grammars in JFLAP on several input strings, choose the tab “Input” and then the item “Multiple Brute Force Parse”.
1
2 Arithmetic Expressions
For the second task, you are required to design a context-free grammar (CFG) G2 that generates the language of arithmetic expressions over natural numbers in binary format. Each arithmetic expression is constructed from the following:
• Binary unsigned integer literals, with leading zeros accepted;
• Arithmetic operators +, -, *, and /;
• Properly nested parentheses.
For instance, an expression such as (11+0101)/001 must be accepted, whereas ((11-01) must be rejected because the parentheses do not match.
Task 2. Implement the grammar G2 in JFLAP and test it on some input expressions of your choice.
Check all the production rules of the grammar G2 to see if there are any λ-productions or unit- productions. If there are any such productions, you may notice that for more complicated input strings, it takes a long time for JFLAP to parse the string. In fact, at times it may enter into a non-terminating loop.
Task 3. Use JFLAP to remove the λ-productions and unit-productions of the grammar G2 to obtain the gram- mar G3. Then, try to parse the same strings as before and notice that it takes a shorter time to parse them, and the parser does not enter into non-terminating loops.
In JFLAP, to remove λ-productions and unit-productions, you may first choose the tab “Convert”, and then the item “Transform Grammar”. A screenshot of the result of parsing of some sample input strings for grammar G3 in JFLAP is provided in Figure 2. To compare the efficiency of G2 and G3, you may use the sample input “1+1-(1/1*1)”.
Figure 2: Some sample input and the corresponding results
3 Submission
You must submit one zip file which contains three JFLAP files, named according to the following templates: 1. A JFLAP file for grammar G1 of Task 1 named:
ID_Surname_FirstName_01.jff 2. A JFLAP file for grammar G2 of Task 2 named:
ID_Surname_FirstName_02.jff 3. A JFLAP file for grammar G3 of Task 3 named:
4. The zip file named:
ID_Surname_FirstName_03.jff ID_Surname_FirstName.zip
2
Remark 3.1 In case the grammar G2 of Task 2 that you have designed already has no λ-productions and no unit-productions, then you may submit the same grammar as G3. Nonetheless, even in this case, you must submit three files with the naming conventions as specified above.
• Release date: Tuesday, April 2nd, 2024
• Deadline: Friday, April 19th, 2024, 17:00 • Weight: 15% of the module mark
• How to submit: Via Moodle
4 Marking Scheme
Correctness: (80%) Correct answers for the three tasks contribute to 80% of the total mark, as follows: • Task 1: 40%
• Task 2: 20%
• Task 3: 20%
Format: (20%)
1. While the grammar G3 of Task 3 is generated by JFLAP, the grammars for Tasks 1 and 2 must be written by you. For grammars G1 and G2, all productions with the same left-hand-side variable must appear in one block one after another. (15%)
2. The zip file and three JFLAP files must be named according to the templates given above. (5%).
Late Submissions: The standard University penalty for late submission is applied, i.e., 5% absolute
standard University scale per day, until the mark reaches zero.
Use of Other Technologies: If you use technologies other than those specified in the assignment brief, e.g., chatGPT, 50% absolute deduction.
请加QQ：99515681 邮箱：99515681@qq.com WX：codinghelp