Object-Oriented Programming Homework Assignment #4

Object-Oriented Programming
Homework Assignment #4

Instructions
1. If any question is unclear, please ask for a clarification.
2. You may try to reuse as much of the source code supplemented as possible.
3. Unless stated otherwise, all the line numbers for the program listings are for reference only.
4. You are required to do all the homework assignments on Linux and use g++ version 10.2.0 or later.
5. You are required to give your TA a demo of your program. Make sure that your program can compile and
run on the server machine, which will be used for the demo.
6. For the program that you write, you are required to include a Makefile. Otherwise, your homework will not
be graded—meaning that you will receive zero marks.
7. Unless stated otherwise, you are required to work on the homework assignment individually.
8. No late homework will be accepted.
Programming Project
This assignment requires that you implement a scanner using inheritance in C++ for the language defined in
Appendix A of the dragon book, second edition,1
the source and class hierarchy of which are given in Listing 1
to Listing 8.
Listing 1: Main.java
1 package main;
2
3 import java.io.*;
4 import lexer.*;
5
6 public class Main {
7 public static void main(String[] args) throws IOException
8 {
1Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, Second Edition,
Addison-Wesley, 2007. Fortunately, you don’t have to understand the material as far as the homework assignment is concerned. Instead, all
you have to do is figure out how the Java version works and follow the class hierarchy for the C++ implementation.
1
9 Lexer lexer = new Lexer();
10 try {
11 while (true) {
12 Token t = lexer.scan();
13 System.out.println(t.toString());
14 }
15 }
16 catch (IOException e) {
17 System.out.println(e.getMessage());
18 }
19 }
20 }
Listing 2: Lexer.java
1 package lexer;
2
3 import java.io.*;
4 import java.util.*;
5
6 public class Lexer {
7 public static int line = 1;
8 char peek = ’ ’;
9 Hashtable words = new Hashtable();
10 void reserve(Word w)
11 {
12 words.put(w.lexeme, w);
13 }
14 public Lexer()
15 {
16 reserve(new Word("if", Tag.IF) );
17 reserve(new Word("else", Tag.ELSE) );
18 reserve(new Word("while", Tag.WHILE) );
19 reserve(new Word("do", Tag.DO) );
20 reserve(new Word("break", Tag.BREAK) );
21 reserve(Word.True);
22 reserve(Word.False);
23 reserve(Type.Int);
24 reserve(Type.Char);
25 reserve(Type.Bool);
26 reserve(Type.Float);
27 }
28 void readch() throws IOException
29 {
30 int i = System.in.read();
31 if (i != -1)
32 peek = (char) i;
33 else
34 throw new IOException("End of file reached");
35 }
36 boolean readch(char c) throws IOException
37 {
38 readch();
39 if (peek != c)
40 return false;
41 peek = ’ ’;
42 return true;
43 }
44 public Token scan() throws IOException
45 {
46 for ( ; ; readch()) {
47 if (peek == ’ ’ || peek == ’\t’)
48 continue;
49 else if (peek == ’\n’)
2
50 line = line + 1;
51 else
52 break;
53 }
54 switch (peek) {
55 case ’&’:
56 if (readch(’&’))
57 return Word.and;
58 else
59 return new Token(’&’);
60 case ’|’:
61 if (readch(’|’))
62 return Word.or;
63 else
64 return new Token(’|’);
65 case ’=’:
66 if (readch(’=’))
67 return Word.eq;
68 else
69 return new Token(’=’);
70 case ’!’:
71 if (readch(’=’))
72 return Word.ne;
73 else
74 return new Token(’!’);
75 case ’<’:
76 if (readch(’=’))
77 return Word.le;
78 else
79 return new Token(’<’);
80 case ’>’:
81 if (readch(’=’))
82 return Word.ge;
83 else
84 return new Token(’>’);
85 }
86
87 if (Character.isDigit(peek)) {
88 int v = 0;
89 do {
90 v = 10 * v + Character.digit(peek, 10);
91 readch();
92 } while (Character.isDigit(peek));
93 if (peek != ’.’)
94 return new Num(v);
95 float x = v;
96 float d = 10;
97 for (;;) {
98 readch();
99 if (!Character.isDigit(peek))
100 break;
101 x = x + Character.digit(peek, 10) / d;
102 d = d * 10;
103 }
104 return new Real(x);
105 }
106
107 if (Character.isLetter(peek)){
108 StringBuffer b = new StringBuffer();
109 do {
110 b.append(peek);
111 readch();
112 } while (Character.isLetterOrDigit(peek));
113 String s = b.toString();
3
114 Word w = (Word) words.get(s);
115 if (w != null)
116 return w;
117 w = new Word(s, Tag.ID);
118 words.put(s, w);
119 return w;
120 }
121
122 Token tok = new Token(peek);
123 peek = ’ ’;
124 return tok;
125 }
126 }
Listing 3: Tag.java
1 package lexer;
2
3 public class Tag {
4 public final static int
5 AND = 256,
6 BASIC = 257,
7 BREAK = 258,
8 DO = 259,
9 ELSE = 260,
10 EQ = 261,
11 FALSE = 262,
12 GE = 263,
13 ID = 264,
14 IF = 265,
15 INDEX = 266,
16 LE = 267,
17 MINUS = 268,
18 NE = 269,
19 NUM = 270,
20 OR = 271,
21 REAL = 272,
22 TEMP = 273,
23 TRUE = 274,
24 WHILE = 275;
25 }
Listing 4: Token.java
1 package lexer;
2
3 public class Token {
4 public final int tag;
5 public Token(int t)
6 {
7 tag = t;
8 }
9 public String toString()
10 {
11 return "" + (char) tag;
12 }
13 }
Listing 5: Word.java
1 package lexer;
2
3 public class Word extends Token {
4
4 public String lexeme = "";
5 public Word(String s, int tag)
6 {
7 super(tag);
8 lexeme = s;
9 }
10 public String toString()
11 {
12 return lexeme;
13 }
14 public static final Word
15 and = new Word("&&", Tag.AND),
16 or = new Word("||", Tag.OR),
17 eq = new Word("==", Tag.EQ),
18 ne = new Word("!=", Tag.NE),
19 le = new Word("<=", Tag.LE),
20 ge = new Word(">=", Tag.GE),
21 minus = new Word("minus", Tag.MINUS),
22 True = new Word("true", Tag.TRUE),
23 False = new Word("false", Tag.FALSE),
24 temp = new Word("t", Tag.TEMP);
25 }
Listing 6: Type.java
1 package lexer;
2
3 public class Type extends Word {
4 public int width = 0;
5 public Type(String s, int tag, int w)
6 {
7 super(s, tag);
8 width = w;
9 }
10 public static final Type
11 Int = new Type("int", Tag.BASIC, 4),
12 Float = new Type("float", Tag.BASIC, 8),
13 Char = new Type("char", Tag.BASIC, 1),
14 Bool = new Type("bool", Tag.BASIC, 1);
15 public static boolean numeric(Type p)
16 {
17 if (p == Type.Char || p == Type.Int || p == Type.Float)
18 return true;
19 else
20 return false;
21 }
22 public static Type max(Type p1, Type p2)
23 {
24 if (!numeric(p1) || !numeric(p2))
25 return null;
26 else if (p1 == Type.Float || p2 == Type.Float)
27 return Type.Float;
28 else if (p1 == Type.Int || p2 == Type.Int)
29 return Type.Int;
30 else
31 return Type.Char;
32 }
33 }
Listing 7: Num.java
1 package lexer;
2
5
3 public class Num extends Token {
4 public final int value;
5 public Num(int v)
6 {
7 super(Tag.NUM);
8 value = v;
9 }
10 public String toString()
11 {
12 return "" + value;
13 }
14 }
Listing 8: Real.java
1 package lexer;
2
3 public class Real extends Token {
4 public final float value;
5 public Real(float v)
6 {
7 super(Tag.REAL);
8 value = v;
9 }
10 public String toString()
11 {
12 return "" + value;
13 }
14 }
To make it easier for you to test your implementation, also given are the test programs (Listings 9 and 11) and the
output of the scanner in C++ (Listings 10 and 12). Note that the output of the scanner in C++ is different from
that in Java.
Listing 9: Test program 1
1 {
2 int i;
3 int j;
4 float v;
5 float x;
6 float[100] a;
7 while (true) {
8 do i = i+1; while (a[i] < v);
9 do j = j-1; while (a[j] > v);
10 if (i >= j) break;
11 x = a[i];
12 a[i] = a[j];
13 a[j] = x;
14 }
15 }
Listing 10: Output of the test program 1
1 Token: { ({)
2 Token: int (BASIC)
3 Token: i (ID)
4 Token: ; (;)
5 Token: int (BASIC)
6 Token: j (ID)
7 Token: ; (;)
8 Token: float (BASIC)
6
9 Token: v (ID)
10 Token: ; (;)
11 Token: float (BASIC)
12 Token: x (ID)
13 Token: ; (;)
14 Token: float (BASIC)
15 Token: [ ([)
16 Token: 100 (NUM)
17 Token: ] (])
18 Token: a (ID)
19 Token: ; (;)
20 Token: while (WHILE)
21 Token: ( (()
22 Token: true (TRUE)
23 Token: ) ())
24 Token: { ({)
25 Token: do (DO)
26 Token: i (ID)
27 Token: = (=)
28 Token: i (ID)
29 Token: + (+)
30 Token: 1 (NUM)
31 Token: ; (;)
32 Token: while (WHILE)
33 Token: ( (()
34 Token: a (ID)
35 Token: [ ([)
36 Token: i (ID)
37 Token: ] (])
38 Token: < (<)
39 Token: v (ID)
40 Token: ) ())
41 Token: ; (;)
42 Token: do (DO)
43 Token: j (ID)
44 Token: = (=)
45 Token: j (ID)
46 Token: - (-)
47 Token: 1 (NUM)
48 Token: ; (;)
49 Token: while (WHILE)
50 Token: ( (()
51 Token: a (ID)
52 Token: [ ([)
53 Token: j (ID)
54 Token: ] (])
55 Token: > (>)
56 Token: v (ID)
57 Token: ) ())
58 Token: ; (;)
59 Token: if (IF)
60 Token: ( (()
61 Token: i (ID)
62 Token: >= (GE)
63 Token: j (ID)
64 Token: ) ())
65 Token: break (BREAK)
66 Token: ; (;)
67 Token: x (ID)
68 Token: = (=)
69 Token: a (ID)
70 Token: [ ([)
71 Token: i (ID)
72 Token: ] (])
7
73 Token: ; (;)
74 Token: a (ID)
75 Token: [ ([)
76 Token: i (ID)
77 Token: ] (])
78 Token: = (=)
79 Token: a (ID)
80 Token: [ ([)
81 Token: j (ID)
82 Token: ] (])
83 Token: ; (;)
84 Token: a (ID)
85 Token: [ ([)
86 Token: j (ID)
87 Token: ] (])
88 Token: = (=)
89 Token: x (ID)
90 Token: ; (;)
91 Token: } (})
92 Token: } (})
93 End of file reached
Listing 11: Test program 2
1 {
2 int i;
3 int j;
4 float[10][10] a;
5 i = 0;
6 while ( i < 10 ) {
7 j = 0;
8 while ( j < 10 ) {
9 a[i][j] = 0;
10 j = j+1;
11 }
12 i = i+1;
13 }
14 i = 0;
15 while ( i < 10 ) {
16 a[i][j] = 1;
17 i = i+1;
18 }
19 }
Listing 12: Output of the test program 2
1 Token: { ({)
2 Token: int (BASIC)
3 Token: i (ID)
4 Token: ; (;)
5 Token: int (BASIC)
6 Token: j (ID)
7 Token: ; (;)
8 Token: float (BASIC)
9 Token: [ ([)
10 Token: 10 (NUM)
11 Token: ] (])
12 Token: [ ([)
13 Token: 10 (NUM)
14 Token: ] (])
15 Token: a (ID)
16 Token: ; (;)
17 Token: i (ID)
8
18 Token: = (=)
19 Token: 0 (NUM)
20 Token: ; (;)
21 Token: while (WHILE)
22 Token: ( (()
23 Token: i (ID)
24 Token: < (<)
25 Token: 10 (NUM)
26 Token: ) ())
27 Token: { ({)
28 Token: j (ID)
29 Token: = (=)
30 Token: 0 (NUM)
31 Token: ; (;)
32 Token: while (WHILE)
33 Token: ( (()
34 Token: j (ID)
35 Token: < (<)
36 Token: 10 (NUM)
37 Token: ) ())
38 Token: { ({)
39 Token: a (ID)
40 Token: [ ([)
41 Token: i (ID)
42 Token: ] (])
43 Token: [ ([)
44 Token: j (ID)
45 Token: ] (])
46 Token: = (=)
47 Token: 0 (NUM)
48 Token: ; (;)
49 Token: j (ID)
50 Token: = (=)
51 Token: j (ID)
52 Token: + (+)
53 Token: 1 (NUM)
54 Token: ; (;)
55 Token: } (})
56 Token: i (ID)
57 Token: = (=)
58 Token: i (ID)
59 Token: + (+)
60 Token: 1 (NUM)
61 Token: ; (;)
62 Token: } (})
63 Token: i (ID)
64 Token: = (=)
65 Token: 0 (NUM)
66 Token: ; (;)
67 Token: while (WHILE)
68 Token: ( (()
69 Token: i (ID)
70 Token: < (<)
71 Token: 10 (NUM)
72 Token: ) ())
73 Token: { ({)
74 Token: a (ID)
75 Token: [ ([)
76 Token: i (ID)
77 Token: ] (])
78 Token: [ ([)
79 Token: j (ID)
80 Token: ] (])
81 Token: = (=)
9
82 Token: 1 (NUM)
83 Token: ; (;)
84 Token: i (ID)
85 Token: = (=)
86 Token: i (ID)
87 Token: + (+)
88 Token: 1 (NUM)
89 Token: ; (;)
90 Token: } (})
91 Token: } (})
92 End of file reached
Grading Policy
The grading policy for this assignment is as follows:
• Make sure that a Makefile, which contains at least three targets—all, dep, and clean—is provided. Otherwise, the grade for your program will be zero.
• 100 points if your program compiles without errors and warnings and runs correctly.
10