COMSM1201 NUCLEI
The programming language LISP, developed in 1958, is one of the oldest languages still in
common use. The langauage is famous for: being fully parenthesised (that is, every instruction
is inside its own brackets), having a prefix notation (e.g. functions are written (PLUS 1 2) and
Copyright By PowCoder代写 加微信 powcoder
not (1 PLUS 2)) and its efficent linked-list Car/Cdr structure for (de-)composing lists.
Here, we develop a very simple langauge inspired by these concepts called NUCLEI (Neill’s
UnCommon Lisp Expression Interpreter) and a means to parse or interpret the instructions.
The interpreter (but not parser) builds on Exercise 11.4 – you’ll need to have your own
version of the linked.c, lisp.h and specific.h files.
(SET A ’1’)
leads to the output :
or with the interpreter :
The CONS instruction is used to construct lists :
(PRINT (CONS ’1’ (CONS ’2’ NIL)))
and when interpreted :
The CAR instruction is used to deconstruct lists :
(SET A ’(5 (1 2 3))’)
(PRINT (CAR A))
and when interpreted :
Loops are possible too, here a loop counts down from 5 to 1, using the variable C as a counter
and a Boolean test :
12.7 NUCLEI 107
(SET C ’5’)
(WHILE (LESS ’0’ C)(
(SET A (PLUS ’-1’ C))
(SET C A))
and when interpreted :
The IF is similar; based on a Boolean, one of two possible sets of instructions are taken :
(IF (EQUAL ’1’ ’1’) ((PRINT “YES”))((GARBAGE)))
Here the parser fails because it doesn’t understand GARBAGE :
Was expecting a Function name ?
However, the interpreter never gets to the f alse instruction since the Boolean equates to true
The Formal Grammar
# (N)eill’s (U)n(C)ommon (L)isp (E)xpression (I)nterpreter
| “CDR”
| “CONS”
| “LENGTH”
| “GREATER”
| “EQUAL”
# (IF (CONDITION) ((IF-TRUE-INSRCTS)) ((IF_FALSE_INSTRCTS)))
108 Chapter 12. Parsing Data
::= |
# Variables are just A, B, Z etc.
::= [A-Z]
# For printing only:
# Since lists appear in bracket, to differentiate them
# from instructions, we use ’single’ quotes:
Exercise 12.7.1 • 30% Implement a recursive descent parser – this will report whether
or not a given NUCLEI program follows the formal grammar or not. The input file is
specified via argv[1] – and if the file is valid the output is :
Otherwise, a suitbale error message is given and a non-zero exit is made.
• 30% Extend the parser, so it becomes an interpreter. The instructions are now ‘ex-
ecuted’. Do not write a new program for this, simply extend your existing parser. To
help with this, I’ve provided a Makefile that does some conditional compilation – it
effectively does a :
#define INTERP
depending upon whether you’re compiling the parser or interpreter version of the code.
In the C file, you can do conditional compilation using the #ifdef :
#ifdef INTERP
return Listfunc(s);
Listfunc(s);
• 20% Show a testing strategy on the above in testing.txt – you should give details
of unit testing, white/black-box testing done on your code, or any test-harnesses used.
Convince me that every line of your C code has been tested, but not just by showing it
running on some NUCLEI files.
• 20% Show an extension to the project in a direction of your choice. It should demon-
strate your understanding of some additional aspect of programming or S/W engin-
eering. If you extend the formal grammar make sure that you show the new, full
Don’t try to write the entire program in one go. Try a cut down version of the grammar
first, maybe something similar to :
| “CDR”
| “CONS”
| “PRINT”
::=
::= [A-Z]
12.7 NUCLEI 109
•• Some issues, such as what happens if you use an undefined variable, or if you use
a variable before it is set, are not explained by the formal grammar. Use your own
common-sense, and explain what you have done.
• Once your parser works, extend it to become an interpreter. DO NOT aim to parse the
program first and then interpret it separately. Interpreting and parsing are inseparably
bound together.
• Start testing very early – this is a complex beast to test and trying to do it near the end
won’t work.
• In NUCLEI, all variables are global i.e. they are not local to loops etc.
Submission
Your testing strategy will be explained in testing.txt, and your extension as extension.txt.
For the parser, interpreter and extension sections, make sure there’s a Makefile, so that I
can easily build the code using make parse, make interp and make extension. Submit
a single nuceli.zip file, which has all the files required without sub-directories.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com