In this semester you will implement a stack-based virtual machine. It is
patterned after the Java Virtual Machine, but the instruction set is
considerably downsized to make it suitable for student projects. The objective
of Project 1 is to implement a lexical analyzer for our VM language, which has
7 token categories ⟨unsigned int⟩ through ⟨comma⟩ defined by the following EBNF:
⟨digit⟩ → 0 | 1 | ... | 9
⟨unsigned int⟩ → {⟨digit⟩}+
⟨signed int⟩ → (+|−) {⟨digit⟩}+
⟨float⟩ → [+|−] ( {⟨digit⟩}+ "." {⟨digit⟩} | "." {⟨digit⟩}+ )
⟨floatE⟩ → ⟨float⟩ (e|E) [+|−] {⟨digit⟩}+
⟨instruction name⟩ → "iconst" |
"iload" | "istore" | "fconst" | "fload"
| "fstore" |
"iadd" | "isub" | "imul" | "idiv" |
"fadd" | "fsub" | "fmul" | "fdiv" |
"intToFloat" |
"icmpeq" | "icmpne" | "icmplt" |
"icmple" | "icmpgt" | "icmpge" |
"fcmpeq" | "fcmpne" | "fcmplt" |
"fcmple" | "fcmpgt" | "fcmpge" |
"goto" | "invoke" | "return" | "ireturn"
| "freturn" | "print"
⟨colon⟩ → ":"
⟨comma⟩ → ","
According to the above definitions, the integers and floating-point numbers may
be signed with "+" or "−". Moreover, the integer or fractional
part, but not both, of a string in ⟨float⟩ may be empty. The
instruction names are case-sensitive.
The
following is a DFA to accept the token categories, except for ⟨instruction name⟩.
The DFA has an auxiliary final state id defining ⟨id⟩ → {⟨letter⟩}+ to implement the extraction of the
instruction names in the following way:
1. Create 33 additional
special DFA states for the instruction names.
2. The DFA initially accepts
the instruction names as identifiers.
3. Each time the DFA accepts
an identifier, check if it is one of the instruction names. If so, move the DFA
to the corresponding instruction-name state; otherwise, issue a lexical error
message.
The
implementation should be based on the above DFA. Your lexical analyzer program
should clearly separate the driver and the state-transition function so that
the driver will remain invariant and only state-transition functions will
change from DFA to DFA. The enumerated or integer type is suggested for
representation of states.
The lexical analyzer program is to read an input text file, extract the tokens
in it, and write them out one by one on separate lines. Each token should be
flagged with its category. The output should be sent to an output text file.
Whenever invalid tokens are found, error messages should be printed, and the
reading process should continue.
You may modify one of these sample Java programs into your solution;
if you do so, modify the comments suitably as well.
Here's a sample set of test input/output files:
in1 | out1
in2 | out2
in3 | out3
in4 | out4
in5 | out5
in6 | out6
in7 | out7
Note that
when the unexpected char is the newline char, the error message is displayed on
the next line because my program, which is based on the sample lex analyzer,
appends the newline char to the string read so far and displays it. You should
make your own additional input files to test the program.
Since the purpose of this project is to reinforce, firsthand, the understanding
of the internal mechanism of lexical analyzers built from finite automata as
opposed to viewing them as black boxes, you are not allowed to
use any library functions/tools for lexical analysis (like the Java
StringTokenizer).
To make grading efficient and uniform, observe the following:
Our
project plan for the semester is to implement a top-down parser and instruction
store for this VM language in Project 2 and an interpreter of the instructions
in Project 3 and 4.
Submission
Project
1, your full name
Include concise instructions for how to compile and run your program. You may
email the entire materials in a .zip or .rar compressed file.
The due date is 10/04/19, Friday, 11 PM. No late projects will be accepted. If
you haven't been able to complete the project, you may send an incomplete
program for partial credit. In this case, include a description of what is and
is not working in your program along with what you believe to be the sources of
the problems.
Sun | Mon | Tue | Wed | Thu | Fri | Sat |
---|---|---|---|---|---|---|
23 | 24 | 25 | 26 | 27 | 28 | 1 |
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 | 1 | 2 | 3 | 4 | 5 |
Get Free Quote!
257 Experts Online