COMP712 Programming Languages
Assignment 2 (35%)
Part 1 LL(1) Grammar for mLang (20%)
1. Develop a syntax grammar for the mLang programming language as described in Assignment
1. The description of the language is provided after Part 2 of this assignment for convenience.
It must be shown to be an LL(1) Grammar. BNF notation should be used. Take care to include
all types of statements allowed and function declarations and calls. At least one production
rule should include ε.
Hint: Search for the grammar definitions of an imperative language like C on the Internet. Use
relevant parts of this grammar as a starting point. But note that the grammars are not be
exactly the same.
2. Derive the Parse Table for your grammar. Obtain the FIRST and FOLLOW sets and then derive
the PREDICT sets (Parse Table) from them.
Submission: Submit a document that includes both tasks for this part of the assignment. The grammar
must be typed with the grammar production rules formatted neatly. You will need to include a short
explanation why your grammar is considered LL(1). The second part could be typed or handwritten.
But handwriting should be legible. It must be submitted through Blackboard by the deadline.
Marking Scheme: 12 marks are allocated for the LL(1) grammar rules. One mark will be deducted for
each error in the grammar submitted, excluding LL(1) compliance. 2 marks are allocated to LL(1)
compliance and your short explanation why you consider this an LL(1) grammar. 2 marks are allocated
to the correct FIRST sets, 2 marks for the FOLLOW sets, and 2 marks for the Parse Table.
Part 2 Implementation of Table Driven LL(1) Parser (15%)
Task: Write a Racket program that performs Table-driven LL(1) parsing based on the skeleton
pseudo-code described in the lecture. The parser will be passed a list of tokens that are
generated as the output of the Lexer you have developed in Assignment 1. The output of the
parser should be a parse tree corresponding to the list of tokens. Error messages need not be
elaborate but should indicate to the user that a syntax error is encountered.
You have the freedom to decide how the grammar rules are to be encoded in Racket.
Submission: Your submission should consists of the following files:
(1) Racket source code of your parser AND lexer. Although the lexer is not marked, it is
required for completeness;
(2) a file of mLang source codes used for testing; and
(3) a file of the outputs of the test cases conducted.
These three files must be archived (i.e. zipped) into a single file with your name and student
number as the filename.
Parser runs correctly for all test cases provided 5%
Test cases provided covers all major elements of the language 2%
Parser runs correctly for the unseen test cases of the marker 5%
Parser generates error messages 1%
Adequate comments in the Racket source code 2%
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: firstname.lastname@example.org 微信号:vipnxx