InitHEADmain

7 files changed, 794 insertions, 0 deletions

diff --git a/Homework/cs5300/project-two/scanner/Main.java b/Homework/cs5300/project-two/scanner/Main.java
new file mode 100644
index 0000000..6025afa
--- /dev/null
+++ b/Homework/cs5300/project-two/scanner/Main.java
@@ -0,0 +1,189 @@
+/*
+ * CS 4481 Compilers
+ * Project 1 - scanner part 1
+ *
+ * This file contains the method runTests(). You will uncomment tests
+ * as you develop your scanner code
+ */
+package scanner;
+
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileNotFoundException;
+import java.io.IOException;
+import java.io.PrintWriter;
+
+/**
+ * A different Main file will be used for grading, so you may make modifications
+ * as needed, but before submitting you should download a fresh copy of this
+ * file, uncomment the tests and make sure you pass them all.
+ */
+public class Main {
+
+  public static void main(String[] args)
+      throws FileNotFoundException, IOException {
+    if (args.length > 0) {
+      scanInputFile(args[0], args[1]);
+    } else {
+      runPascaTests();
+
+      System.out.println(tests.getSuccesses() + "/" + tests.getN() +
+                         " tests succeeded");
+      int failures = tests.getFailures();
+
+      System.exit(failures);
+    }
+  }
+
+  private static void runPascaTests()
+      throws FileNotFoundException, IOException {
+    // TODO: uncomment tests as you develop code
+
+    //------------------------------------------------------------
+    // Test register.table reading, table building and token
+    // parsing. These tests should pass once you have the Scanner
+    // constructor implemented.
+    //------------------------------------------------------------
+
+    String tableFile = "data/pasca.table";
+    TableReader tableReader = new TableReader(tableFile);
+    Scanner scanner = new Scanner(tableReader);
+
+    {
+      ScanStream ss = getDataStream("data/test1-pasca.txt");
+
+      testToken(scanner, ss, "identifier", "begin");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "identifier", "program");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "identifier", "a1");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "delimiter", "{");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "identifier", "var0");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "identifier", "is");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "integer", "8");
+      testToken(scanner, ss, "delimiter", ";");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "identifier", "var1");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "identifier", "var2");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "identifier", "variable");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "identifier", "var1able");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "delimiter", "}");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "integer", "123");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "integer", "1203");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "string", "' a crazy string abc(){}*''4013'");
+      testToken(scanner, ss, "ignore");
+      testToken(scanner, ss, "identifier", "end");
+      testToken(scanner, ss, "delimiter", ".");
+    }
+    {
+      ScanStream ss = getDataStream("data/test2-pasca.txt");
+      testToken(scanner, ss, "string", "'alks dfl;alsk k''jk{}'");
+    }
+    {
+      ScanStream ss = getDataStream("data/err1-pasca.txt");
+      testToken(scanner, ss, "ignore", "(* a comment *)");
+      testToken(scanner, ss, "ignore", " ");
+      testToken(scanner, ss, null);
+    }
+    {
+      ScanStream ss = getDataStream("data/err2-pasca.txt");
+      testToken(scanner, ss, null);
+    }
+    {
+      ScanStream ss = getDataStream("data/err3-pasca.txt");
+      testToken(scanner, ss, null);
+    }
+  }
+
+  //--------------------------------------------------------------------------------
+  // Utility stuff
+  // You can ignore code from here to the end of the file.
+  //--------------------------------------------------------------------------------
+
+  static Tests tests = new Tests();
+
+  private static void testToken(Scanner scanner, ScanStream ss, String type,
+                                String lexeme) {
+    try {
+      Token t = scanner.nextToken(ss);
+      if (type == null) {
+        tests.test(t == null, "expected lexical error");
+      } else {
+        tests.test(t.getType().equals(type),
+                   t.getType() + " not equal to " + type);
+      }
+
+      if (lexeme != null) {
+        tests.test(t.getLexeme().equals(lexeme),
+                   t.getLexeme() + " not equal to " + lexeme);
+      }
+    } catch (Exception e) {
+      tests.addFailure(e);
+    }
+  }
+
+  private static void testToken(Scanner scanner, ScanStream ss, String type) {
+    testToken(scanner, ss, type, null);
+  }
+
+  private static ScanStream getDataStream(String testFile) throws IOException {
+    File file = new File(testFile);
+    FileInputStream fis = new FileInputStream(file);
+    byte[] data = new byte[(int)file.length()];
+    fis.read(data);
+    fis.close();
+    ScanStream ss = new ScanStream(data);
+    return ss;
+  }
+
+  public static void scanInputFile(String tableFile, String testFile)
+      throws FileNotFoundException, IOException {
+    TableReader tableReader = new TableReader(tableFile);
+
+    File file = new File(testFile);
+    FileInputStream fis = new FileInputStream(file);
+    byte[] data = new byte[(int)file.length()];
+    fis.read(data);
+    fis.close();
+
+    PrintWriter writer = new PrintWriter(testFile + ".out", "UTF-8");
+
+    Scanner scanner = new Scanner(tableReader);
+    ScanStream ss = new ScanStream(data);
+    Token t;
+    do {
+      t = scanner.nextToken(ss);
+      if (t == null) {
+        System.out.println("Lexical error: " + ss.next());
+        ss.rollback();
+        writer.println("Lexical error: " + ss.next());
+      } else if (!t.getType().equals("ignore")) {
+        System.out.println(t.toString());
+        writer.println(t.toString());
+      }
+    } while (t != null && !ss.eof());
+
+    writer.close();
+  }
+}
diff --git a/Homework/cs5300/project-two/scanner/ScanStream.java b/Homework/cs5300/project-two/scanner/ScanStream.java
new file mode 100644
index 0000000..04cff68
--- /dev/null
+++ b/Homework/cs5300/project-two/scanner/ScanStream.java
@@ -0,0 +1,36 @@
+/*
+ * DO NOT MODIFY THIS FILE
+ */
+package scanner;
+
+/**
+ * Abstracts a stream reader that reads one byte at a time with possible
+ * rollback.
+ *
+ * Do not modify this file.
+ */
+public final class ScanStream {
+
+  final private byte[] data;
+  private int i;
+
+  public ScanStream(byte[] data) {
+    this.data = data;
+    i = 0;
+  }
+
+  public boolean eof() {
+    return i >= data.length;
+  }
+
+  public char next() {
+    if (eof()) {
+      throw new RuntimeException("EOF reached");
+    }
+    return (char) data[i++];
+  }
+
+  void rollback() {
+    --i;
+  }
+}
diff --git a/Homework/cs5300/project-two/scanner/Scanner.java b/Homework/cs5300/project-two/scanner/Scanner.java
new file mode 100644
index 0000000..5681932
--- /dev/null
+++ b/Homework/cs5300/project-two/scanner/Scanner.java
@@ -0,0 +1,166 @@
+package scanner;
+
+import java.util.HashMap;
+import java.util.Stack;
+
+/**
+ * This is the file you will modify.
+ */
+public class Scanner {
+
+  //------------------------------------------------------------
+  // TODO: declare the HashMaps that you will use to store
+  // your tables. Also declare the start state.
+  //------------------------------------------------------------
+
+  // Category table
+  final HashMap<Character, String> char2category = new HashMap<>();
+  // Transition table
+  final HashMap<String, HashMap<String, String>> state2category2state = new HashMap<>();
+  // Token type table
+  final HashMap<String, String> state2tokenType = new HashMap<>();
+  // Utility
+  final HashMap<String, String> name2state = new HashMap<>();
+  // Start state
+  private String s0;
+
+  //------------------------------------------------------------
+  // TODO: build your tables in the constructor and implement
+  // the get methods.
+  //------------------------------------------------------------
+
+  /**
+   * Builds the tables needed for the scanner.
+   */
+  public Scanner(TableReader tableReader) {
+    // TODO: starting with the skeleton code below, build the
+    // classifer, transition and token type tables. You will need
+    // to also implement the test functions below once you have your
+    // tables built.
+
+    // Build catMap, mapping a character to a category.
+    for (TableReader.CharCat cat : tableReader.getClassifier()) {
+//      System.out.println("Character " + cat.getC() + " is of category "
+//              + cat.getCategory());
+      char2category.put(cat.getC(), cat.getCategory());
+    }
+
+    // Build the transition table. Given a state and a character category,
+    // give a new state.
+    for (TableReader.Transition t : tableReader.getTransitions()) {
+      String from = t.getFromStateName();
+      String to = t.getToStateName();
+//      System.out.println(from + " -- " + t.getCategory()
+//              + " --> " + to);
+
+      if (s0 == null)
+        s0 = from;
+
+      HashMap<String, String> cat2state;
+      if (state2category2state.containsKey(from)) {
+        cat2state = state2category2state.get(from);
+      } else {
+        cat2state = new HashMap<>();
+        state2category2state.put(from, cat2state);
+      }
+      cat2state.put(t.getCategory(), to);
+    }
+
+    // Build the token types
+    for (TableReader.TokenType tt : tableReader.getTokens()) {
+//      System.out.println("State " + tt.getState()
+//              + " accepts with the lexeme being of type " + tt.getType());
+
+      state2tokenType.put(tt.getState(), tt.getType());
+    }
+
+  }
+
+  /**
+   * Returns the category for c or "not in alphabet" if c has no category. Do not hardcode
+   * this. That is, this function should have nothing more than a table lookup
+   * or two. You should not have any character literals in here such as 'r' or '3'.
+   */
+  public String getCategory(Character c) {
+    if (!char2category.containsKey(c)) return "not in alphabet";
+    return char2category.get(c);
+  }
+
+  /**
+   * Returns the new state given a current state and category. This models
+   * the transition table. Returns "error" if there is no transition.
+   * Do not hardcode any state names or categories. You should have only
+   * table lookups here.
+   */
+  public String getNewState(String state, String category) {
+    if (!state2category2state.containsKey(state)) return "error";
+    if (!state2category2state.get(state).containsKey(category)) return "error";
+    return state2category2state.get(state).get(category);
+  }
+
+  /**
+   * Returns the type of token corresponding to a given state. If the state
+   * is not accepting then return "error".
+   * Do not hardcode any state names or token types.
+   */
+  public String getTokenType(String state) {
+    if (!state2tokenType.containsKey(state)) return "error";
+    return state2tokenType.get(state);
+  }
+
+  //------------------------------------------------------------
+  // TODO: implement nextToken
+  //------------------------------------------------------------
+
+  /**
+   * Return the next token or null if there's a lexical error.
+   */
+  public Token nextToken(ScanStream ss) {
+    // TODO: get a single token. This is an implementation of the nextToken
+    // algorithm given in class. You may *not* use TableReader in this
+    // function. Return null if there is a lexical error.
+
+    String state = s0;
+    String lexeme = "";
+    Stack<String> stack = new Stack<>();
+    String bad = "bad";
+    String error = "error";
+    stack.push(bad);
+    while (state != error) {
+      char c;
+      try {
+        c = ss.next();
+        System.out.println("current state is " + state + " and next is " + c);
+      } catch(Exception e) {
+        state = error;
+        continue;
+      }
+      lexeme += c;
+      if (state2tokenType.containsKey(state))
+        stack.clear();
+      stack.push(state);
+      String category = char2category.get(c);
+      if (state2category2state.containsKey(state)) {
+        state = state2category2state.get(state).get(category);
+      } else {
+        state = null;
+      }
+      if (state == null) {
+        state = error;
+      }
+      System.out.println("Moving to state " + state);
+    }
+    while (state != bad && !state2tokenType.containsKey(state)) {
+      state = stack.pop();
+      if (!lexeme.isEmpty()) {
+        lexeme = lexeme.substring(0, lexeme.length() - 1);
+        ss.rollback();
+      }
+    }
+    if (state2tokenType.containsKey(state)) {
+      return new Token(state2tokenType.get(state), lexeme);
+    }
+    return null;
+  }
+
+}
diff --git a/Homework/cs5300/project-two/scanner/TableParser.java b/Homework/cs5300/project-two/scanner/TableParser.java
new file mode 100644
index 0000000..760e312
--- /dev/null
+++ b/Homework/cs5300/project-two/scanner/TableParser.java
@@ -0,0 +1,160 @@
+/*
+ * DO NOT MODIFY THIS FILE
+ */
+package scanner;
+
+import java.io.BufferedReader;
+import java.io.FileNotFoundException;
+import java.io.FileReader;
+import java.io.IOException;
+import java.util.ArrayList;
+
+/**
+ * TableParser provides all functionality for parsing the table definition file.
+ *
+ * Do not modify this file.
+ */
+public final class TableParser {
+
+  // CharCat class
+  // Used in the classifier table
+  public class CharCat {
+
+    final private char c;
+    final private String category;
+
+    public CharCat(char c, String category) {
+      this.c = c;
+      this.category = category;
+    }
+
+    public char getC() {
+      return c;
+    }
+
+    public String getCategory() {
+      return category;
+    }
+
+  }
+
+  // Transition class
+  // Used in the transition table
+  public class Transition {
+
+    final private String fromState;
+    final private String category;
+    final private String toState;
+
+    public Transition(String fromState, String category, String toState) {
+      this.fromState = fromState;
+      this.category = category;
+      this.toState = toState;
+    }
+
+    public String getFromStateName() {
+      return fromState;
+    }
+
+    public String getCategory() {
+      return category;
+    }
+
+    public String getToStateName() {
+      return toState;
+    }
+  }
+
+  // TokenType class
+  // Used in the token type table
+  public class TokenType {
+
+    final private String state;
+    final private String type;
+
+    public TokenType(String state, String type) {
+      this.state = state;
+      this.type = type;
+    }
+
+    public String getState() {
+      return state;
+    }
+
+    public String getType() {
+      return type;
+    }
+  }
+
+  private enum WhichTable {
+
+    CLASS, TRANS, TOKEN
+  };
+
+  private ArrayList<CharCat> classifier;
+  private ArrayList<Transition> transitions;
+  private ArrayList<TokenType> tokens;
+
+  public TableParser(String filename) throws IOException {
+    parse(filename);
+  }
+
+  public Iterable<CharCat> getClassifier() {
+    return classifier;
+  }
+
+  public Iterable<Transition> getTransitions() {
+    return transitions;
+  }
+
+  public Iterable<TokenType> getTokens() {
+    return tokens;
+  }
+
+  public void parse(String fn) throws FileNotFoundException, IOException {
+    this.classifier = new ArrayList<>();
+    this.transitions = new ArrayList<>();
+    this.tokens = new ArrayList<>();
+
+    WhichTable table = WhichTable.CLASS;
+    try (BufferedReader br = new BufferedReader(new FileReader(fn))) {
+      String line;
+      while ((line = br.readLine()) != null) {
+        final int idx = line.indexOf("//");
+        if (idx > -1) {
+          line = line.substring(0, idx);
+        }
+        line = line.trim();
+        if (!line.isEmpty()) {
+          if (line.equals("ClassifierTable")) {
+            table = WhichTable.CLASS;
+          } else if (line.equals("TransitionTable")) {
+            table = WhichTable.TRANS;
+          } else if (line.equals("TokenTypeTable")) {
+            table = WhichTable.TOKEN;
+          } else {
+            String[] lineTokens = line.split(" ");
+            if (table == WhichTable.CLASS) {
+              char c = lineTokens[0].charAt(0);
+              if (lineTokens[0].equals("\\space")) {
+                c = ' ';
+              } else if (lineTokens[0].equals("\\t")) {
+                c = '\t';
+              } else if (lineTokens[0].equals("\\n")) {
+                c = '\n';
+              }
+              CharCat cc = new CharCat(c, lineTokens[1]);
+              classifier.add(cc);
+            } else if (table == WhichTable.TRANS) {
+              Transition t = new Transition(lineTokens[0], lineTokens[1], lineTokens[2]);
+              transitions.add(t);
+            } else if (table == WhichTable.TOKEN) {
+              TokenType tt = new TokenType(lineTokens[0], lineTokens[1]);
+              tokens.add(tt);
+            }
+          }
+        }
+      }
+    }
+  }
+}
diff --git a/Homework/cs5300/project-two/scanner/TableReader.java b/Homework/cs5300/project-two/scanner/TableReader.java
new file mode 100644
index 0000000..a074547
--- /dev/null
+++ b/Homework/cs5300/project-two/scanner/TableReader.java
@@ -0,0 +1,160 @@
+/*
+ * Do not modify this file.
+ */
+package scanner;
+
+import java.io.BufferedReader;
+import java.io.FileNotFoundException;
+import java.io.FileReader;
+import java.io.IOException;
+import java.util.ArrayList;
+
+/**
+ * TableParser provides all functionality for parsing the table definition file.
+ *
+ * Do not modify this file.
+ */
+public final class TableReader {
+
+  // CharCat class
+  // Used in the classifier table
+  public class CharCat {
+
+    final private char c;
+    final private String category;
+
+    public CharCat(char c, String category) {
+      this.c = c;
+      this.category = category;
+    }
+
+    public char getC() {
+      return c;
+    }
+
+    public String getCategory() {
+      return category;
+    }
+
+  }
+
+  // Transition class
+  // Used in the transition table
+  public class Transition {
+
+    final private String fromState;
+    final private String category;
+    final private String toState;
+
+    public Transition(String fromState, String category, String toState) {
+      this.fromState = fromState;
+      this.category = category;
+      this.toState = toState;
+    }
+
+    public String getFromStateName() {
+      return fromState;
+    }
+
+    public String getCategory() {
+      return category;
+    }
+
+    public String getToStateName() {
+      return toState;
+    }
+  }
+
+  // TokenType class
+  // Used in the token type table
+  public class TokenType {
+
+    final private String state;
+    final private String type;
+
+    public TokenType(String state, String type) {
+      this.state = state;
+      this.type = type;
+    }
+
+    public String getState() {
+      return state;
+    }
+
+    public String getType() {
+      return type;
+    }
+  }
+
+  private enum WhichTable {
+
+    CLASS, TRANS, TOKEN
+  };
+
+  private ArrayList<CharCat> classifier;
+  private ArrayList<Transition> transitions;
+  private ArrayList<TokenType> tokens;
+
+  public TableReader(String filename) throws IOException {
+    parse(filename);
+  }
+
+  public Iterable<CharCat> getClassifier() {
+    return classifier;
+  }
+
+  public Iterable<Transition> getTransitions() {
+    return transitions;
+  }
+
+  public Iterable<TokenType> getTokens() {
+    return tokens;
+  }
+
+  public void parse(String fn) throws FileNotFoundException, IOException {
+    this.classifier = new ArrayList<>();
+    this.transitions = new ArrayList<>();
+    this.tokens = new ArrayList<>();
+
+    WhichTable table = WhichTable.CLASS;
+    try (BufferedReader br = new BufferedReader(new FileReader(fn))) {
+      String line;
+      while ((line = br.readLine()) != null) {
+        final int idx = line.indexOf("//");
+        if (idx > -1) {
+          line = line.substring(0, idx);
+        }
+        line = line.trim();
+        if (!line.isEmpty()) {
+          if (line.equals("ClassifierTable")) {
+            table = WhichTable.CLASS;
+          } else if (line.equals("TransitionTable")) {
+            table = WhichTable.TRANS;
+          } else if (line.equals("TokenTypeTable")) {
+            table = WhichTable.TOKEN;
+          } else {
+            String[] lineTokens = line.split(" ");
+            if (table == WhichTable.CLASS) {
+              char c = lineTokens[0].charAt(0);
+              if (lineTokens[0].equals("\\space")) {
+                c = ' ';
+              } else if (lineTokens[0].equals("\\t")) {
+                c = '\t';
+              } else if (lineTokens[0].equals("\\n")) {
+                c = '\n';
+              }
+              CharCat cc = new CharCat(c, lineTokens[1]);
+              classifier.add(cc);
+            } else if (table == WhichTable.TRANS) {
+              Transition t = new Transition(lineTokens[0], lineTokens[1], lineTokens[2]);
+              transitions.add(t);
+            } else if (table == WhichTable.TOKEN) {
+              TokenType tt = new TokenType(lineTokens[0], lineTokens[1]);
+              tokens.add(tt);
+            }
+          }
+        }
+      }
+    }
+  }
+}
diff --git a/Homework/cs5300/project-two/scanner/Tests.java b/Homework/cs5300/project-two/scanner/Tests.java
new file mode 100644
index 0000000..19413fa
--- /dev/null
+++ b/Homework/cs5300/project-two/scanner/Tests.java
@@ -0,0 +1,50 @@
+/*
+ * To change this license header, choose License Headers in Project Properties.
+ * To change this template file, choose Tools | Templates
+ * and open the template in the editor.
+ */
+package scanner;
+
+/**
+ * A test utility class.
+ *
+ * Do not modify this file.
+ */
+public class Tests {
+
+  private int N = 0;
+  private int failures = 0;
+
+  public void test(boolean b) {
+    N++;
+    if (!b) {
+      System.err.println("Failed test " + N);
+      failures++;
+    }
+  }
+
+  public void test(boolean b, String message) {
+    test(b);
+    if (!b) {
+      System.err.println(message);
+    }
+  }
+
+  public void addFailure(Exception e) {
+    N++;
+    failures++;
+    System.err.println("Failed test " + N + ": " + e);
+  }
+
+  public int getN() {
+    return N;
+  }
+
+  public int getSuccesses() {
+    return N - failures;
+  }
+
+  public int getFailures() {
+    return failures;
+  }
+}
diff --git a/Homework/cs5300/project-two/scanner/Token.java b/Homework/cs5300/project-two/scanner/Token.java
new file mode 100644
index 0000000..4c0151a
--- /dev/null
+++ b/Homework/cs5300/project-two/scanner/Token.java
@@ -0,0 +1,33 @@
+/*
+ * DO NOT MODIFY THIS FILE
+ */
+package scanner;
+
+/**
+ * A class that stores a token.
+ *
+ * Do not modify this file.
+ */
+public class Token {
+
+  private final String type;
+  private final String lexeme;
+
+  public Token(String type, String lexeme) {
+    this.type = type;
+    this.lexeme = lexeme;
+  }
+
+  public String toString() {
+    return type + ": " + lexeme;
+  }
+
+  public String getType() {
+    return type;
+  }
+
+  public String getLexeme() {
+    return lexeme;
+  }
+
+}