DFA.java code:

/** * DFA format: alphabet states start state final state(s) transition_1 transition_2 ... transition_n Example DFA for RE (a|b)(a|b|0|1)* The diagram is a,b a,b,0,1 A-->B---->  finalStates; public static TreeMap transitions=new TreeMap(); /** Construct a DFA from a text file */ public DFA(String filename) throws Exception{ BufferedReader br = new BufferedReader(new FileReader(filename)); alphabet=br.readLine().trim().split(" "); String[] states=br.readLine().split(" "); startState=br.readLine().trim(); String[] finals=br.readLine().trim().split(" "); finalStates= new HashSet(Arrays.asList(finals)); String line=""; while ((line=br.readLine())!=null) { String[] transition=line.trim().split(" "); transitions.put(transition[0]+"_"+transition[1], transition[2]); } } public static void main(String[] args) throws Exception{ DFA dfa = new DFA(args[0]); String input = new BufferedReader(new FileReader(args[1])).readLine().strip(); boolean result=Simulator.run(dfa,input); BufferedWriter bw=new BufferedWriter(new FileWriter(args[2])); bw.write(result+""); bw.close(); System.out.println(input+"\t"+result); } } 

Sample of A2.input:

/** keywords (such as read and if) and identifiers should not be counted in * comments. * Comments can be longer than one line. **/ MAIN f() BEGIN you are not required to check the syntax of the program; so all these words are identifiers; except "quoted" strings and keywords; to check how many lines and words I have; type "wc A2.input" in "luna.cs"; your number of characters and lines may vary from sample output, depends on how you save this file; to count the identifers and keywords; you have to count me one by one; note that A1_A2 is not ONE identifier; as defined in the language lexicon specification; A1 and A2 should returned as two identifiers; special characters such as !@#$% and tab may also appear to test your program; both 123 and 123.45 are numbers; while 12,34 are two numbers; /** you can put more than one comment line with characters like * and ) **/ here is some more tricky part: " /** this is a quoted string **/ " but /** "this is a comment " **/ END

Sample of A2.output:

identifiers: 116 keywords: 3 numbers: 4 comments: 3 quotedString: 4

2 A 21: DFA (3 marks) 2.1 Purpose Automaton is a machine that can run by itself. Understand how it runs by implementing it. 2.2 What you will write In this assignment you need to write the DFA Simulator that can run a DFA against an input string. Given a DFA and an input string, the simulator will return yes if the DFA accepts the string, return false if the string is rejected. The Simulator algorithm in pseudo code is listed in Algorithm 1 You need to rewrite it into Java code, and make it work together with the DFA.java code. You can click the high-lighted link to download DFA.java. It is also listed at the end of this document. The code you should have the same class name and method name as is listed below: public class Simulator { public static boolean run (DFA dfa, String input) { \\you need to fill in the missing part here. } } Your code should work for any DFAs and input strings. You should test your code using sample DFAs and input strings. One example is the DFA that corresponds the regular expression (alb)(alb|0|1)*, whose transition diagram is as below. a,b,0,1 A Its corresponding dfa.txt is: a b 0 1 AB A B AaB BaB BOB B 1 B The format of the dfa.txt is like below: alphabet states start state final state(s) transition_1 transition_2 transition_n The first line is a set of characters, the second line is the set of states. The third line is the start state, the fourth line is the set of final states in this case it happens that there is only one final state). Input: An input string r, a DFA with start state so, move(s, c) function that moves states to a new state on input c, accepting states F. Output: "yes" if D accepts r, "no" otherwise. 8 = 30; while (c=nert Char())!=eof do | s=move(s.c); end if se F then | return "yes"; end return "no"; Algorithm 1: Simulate DFA (dragon book p. 151) 3 A22: Scanner generation using JLex (5 marks) 3.1 Purpose Understand the lexical definition of a language. Generate a scanner using JLex. 3.2 Assignment Specification The task is to write a JLex specification for Tiny language. Please note that in this assignment we don't need to use all the grammar definitions there. Only the lexical part is needed. You will write a JLex specification named "A2.lex. We will run the following commands to generate the scanner, compile it, and run it. JLex installation instruction is documented here > java JLex. Main A2.lex > javac A2.lex.java > java A2 You should take extra care on the file names. Make sure all the three commands can run without problem, and the A2.output file is generated. If any of the three commands fails, you will receive very low marks, even 0, no matter how good the remaining part of your program is. The A2.class program will read a text file named "A2.input", and produce a file named "A2.output" which contains following five lines: identifiers: NumberOfIdentifiers keywords : Number of Keyourds numbers: NumberOfIntergers Or RealNumbers comments: Number of Comments quotedString: NumberOfQuotedStrings Here are the sample A2.input and the corresponding output file A2.output. Note that this time you only need to count the occurrences of the identifiers, keywords, etc. You do not need to remove the duplicates as in last assignment. Note that you don't need to write any Java programs. The scanner is generated from your lex specification. 3.3 Marking scheme This assignment will give you bonus up to 0.5 point depending on the length of your program. If your program counts everything correct, you shall receive 5. On top of that, there is a bonus calculated using your program length. your Mark=0; if (A2.lex file is not sent properly or file name is incorrect) return; if (java program named A2.lex.java is generated from your lex file) your Mark +=0.5; if ( generated program is compiled correctly && A2. class is generated) { your Mark+=0.5; if (your java program reads A2.input && generates result file A2.output) { for each of the 5 counts in A2.output) { if (count is correct) { yourMark +=0.8; } 2 How to get started 3 A22: SCANNER GENERATION USING JLEX (5 MARKS) } } } yourMark += (lengthOf Your Program >140) 20:96/length Of Your Program; // length is counted by PHP in terms of words; Note that different programs count the words in different ways. for each day of your late submission) yourMark=yourMark*0.7; A21(3 marks) A22 (5 marks) Student ID: (e.g., 123456789) Email Usrid: (e.... joe2 if your email is joe2@uwindsor) Submit 21 public class Simulator public static boolean run(DFA dfa, String input) { l'You need to fill in the missing part here. You do not need to include the DFA class. } } Student ID: Email Usrid: // import the classes needed %% %{ // internal code such as variable declararions to be used in RE section public static void main(String argv[l) throws java.io.IOException { A2 yy = new A2(new FileInputStream(new File("A2.input")); lladd code for scanning I create the a file writer //the following write the counters to the file. fw.write("keywords: "+new Integer(k).toString()+" "); // write other things fw.close(); } %} lladd some directives here %% // write your regular expressions and the actions (counting) 1. The transisions are encoded inside DFA using Map data structure. The key of the map is the state_char. The valueof the map is the state it moves to. 2 A 21: DFA (3 marks) 2.1 Purpose Automaton is a machine that can run by itself. Understand how it runs by implementing it. 2.2 What you will write In this assignment you need to write the DFA Simulator that can run a DFA against an input string. Given a DFA and an input string, the simulator will return yes if the DFA accepts the string, return false if the string is rejected. The Simulator algorithm in pseudo code is listed in Algorithm 1 You need to rewrite it into Java code, and make it work together with the DFA.java code. You can click the high-lighted link to download DFA.java. It is also listed at the end of this document. The code you should have the same class name and method name as is listed below: public class Simulator { public static boolean run (DFA dfa, String input) { \\you need to fill in the missing part here. } } Your code should work for any DFAs and input strings. You should test your code using sample DFAs and input strings. One example is the DFA that corresponds the regular expression (alb)(alb|0|1)*, whose transition diagram is as below. a,b,0,1 A Its corresponding dfa.txt is: a b 0 1 AB A B AaB BaB BOB B 1 B The format of the dfa.txt is like below: alphabet states start state final state(s) transition_1 transition_2 transition_n The first line is a set of characters, the second line is the set of states. The third line is the start state, the fourth line is the set of final states in this case it happens that there is only one final state). Input: An input string r, a DFA with start state so, move(s, c) function that moves states to a new state on input c, accepting states F. Output: "yes" if D accepts r, "no" otherwise. 8 = 30; while (c=nert Char())!=eof do | s=move(s.c); end if se F then | return "yes"; end return "no"; Algorithm 1: Simulate DFA (dragon book p. 151) 3 A22: Scanner generation using JLex (5 marks) 3.1 Purpose Understand the lexical definition of a language. Generate a scanner using JLex. 3.2 Assignment Specification The task is to write a JLex specification for Tiny language. Please note that in this assignment we don't need to use all the grammar definitions there. Only the lexical part is needed. You will write a JLex specification named "A2.lex. We will run the following commands to generate the scanner, compile it, and run it. JLex installation instruction is documented here > java JLex. Main A2.lex > javac A2.lex.java > java A2 You should take extra care on the file names. Make sure all the three commands can run without problem, and the A2.output file is generated. If any of the three commands fails, you will receive very low marks, even 0, no matter how good the remaining part of your program is. The A2.class program will read a text file named "A2.input", and produce a file named "A2.output" which contains following five lines: identifiers: NumberOfIdentifiers keywords : Number of Keyourds numbers: NumberOfIntergers Or RealNumbers comments: Number of Comments quotedString: NumberOfQuotedStrings Here are the sample A2.input and the corresponding output file A2.output. Note that this time you only need to count the occurrences of the identifiers, keywords, etc. You do not need to remove the duplicates as in last assignment. Note that you don't need to write any Java programs. The scanner is generated from your lex specification. 3.3 Marking scheme This assignment will give you bonus up to 0.5 point depending on the length of your program. If your program counts everything correct, you shall receive 5. On top of that, there is a bonus calculated using your program length. your Mark=0; if (A2.lex file is not sent properly or file name is incorrect) return; if (java program named A2.lex.java is generated from your lex file) your Mark +=0.5; if ( generated program is compiled correctly && A2. class is generated) { your Mark+=0.5; if (your java program reads A2.input && generates result file A2.output) { for each of the 5 counts in A2.output) { if (count is correct) { yourMark +=0.8; } 2 How to get started 3 A22: SCANNER GENERATION USING JLEX (5 MARKS) } } } yourMark += (lengthOf Your Program >140) 20:96/length Of Your Program; // length is counted by PHP in terms of words; Note that different programs count the words in different ways. for each day of your late submission) yourMark=yourMark*0.7; A21(3 marks) A22 (5 marks) Student ID: (e.g., 123456789) Email Usrid: (e.... joe2 if your email is joe2@uwindsor) Submit 21 public class Simulator public static boolean run(DFA dfa, String input) { l'You need to fill in the missing part here. You do not need to include the DFA class. } } Student ID: Email Usrid: // import the classes needed %% %{ // internal code such as variable declararions to be used in RE section public static void main(String argv[l) throws java.io.IOException { A2 yy = new A2(new FileInputStream(new File("A2.input")); lladd code for scanning I create the a file writer //the following write the counters to the file. fw.write("keywords: "+new Integer(k).toString()+" "); // write other things fw.close(); } %} lladd some directives here %% // write your regular expressions and the actions (counting) 1. The transisions are encoded inside DFA using Map data structure. The key of the map is the state_char. The valueof the map is the state it moves to