diff options
Diffstat (limited to 'Homework/cs5300/project-one/p1-scanner/scanner')
6 files changed, 634 insertions, 0 deletions
diff --git a/Homework/cs5300/project-one/p1-scanner/scanner/Main.java b/Homework/cs5300/project-one/p1-scanner/scanner/Main.java new file mode 100644 index 0000000..a1d5f9c --- /dev/null +++ b/Homework/cs5300/project-one/p1-scanner/scanner/Main.java @@ -0,0 +1,235 @@ +/* + * 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 { + runRegisterTests(); + runHexTests(); + + System.out.println(tests.getSuccesses() + "/" + tests.getN() + + " tests succeeded"); + int failures = tests.getFailures(); + + System.exit(failures); + } + } + + private static void runRegisterTests() + 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/register.table"; + TableReader tableReader = new TableReader(tableFile); + Scanner scanner = new Scanner(tableReader); + + tests.test(scanner.getCategory('r').equals("register")); + tests.test(scanner.getCategory('3').equals("digit")); + tests.test(scanner.getCategory('8').equals("digit")); + tests.test(scanner.getCategory(' ').equals("whitespace")); + tests.test(scanner.getCategory('x').equals("not in alphabet")); + + tests.test(scanner.getNewState("s0", "register").equals("s1")); + tests.test(scanner.getNewState("s1", "digit").equals("s2")); + tests.test(scanner.getNewState("s2", "digit").equals("s2")); + tests.test(scanner.getNewState("s0", "whitespace").equals("s3")); + tests.test(scanner.getNewState("s0", "digit").equals("error")); + tests.test(scanner.getNewState("s1", "register").equals("error")); + tests.test(scanner.getNewState("s2", "register").equals("error")); + + tests.test(scanner.getTokenType("s0").equals("error")); + tests.test(scanner.getTokenType("s1").equals("error")); + tests.test(scanner.getTokenType("s2").equals("register")); + tests.test(scanner.getTokenType("s3").equals("ignore")); + + //------------------------------------------------------------ + // The following tests should pass once you have + // Scanner.nextToken() implemented. + //------------------------------------------------------------ + { + ScanStream ss = getDataStream("data/test1-reg.txt"); + testToken(scanner, ss, "register", "r302"); + testToken(scanner, ss, "ignore"); + testToken(scanner, ss, "register", "r02"); + testToken(scanner, ss, "ignore"); + testToken(scanner, ss, "register", "r233987"); + } + { + ScanStream ss = getDataStream("data/err1-reg.txt"); + testToken(scanner, ss, null); + } + { + ScanStream ss = getDataStream("data/err2-reg.txt"); + testToken(scanner, ss, null); + } + { + ScanStream ss = getDataStream("data/err3-reg.txt"); + testToken(scanner, ss, "register", "r33"); + testToken(scanner, ss, null); + } + } + + private static void runHexTests() 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/hexadecimal.table"; + TableReader tableReader = new TableReader(tableFile); + Scanner scanner = new Scanner(tableReader); + + tests.test(scanner.getCategory('x').equals("x")); + tests.test(scanner.getCategory('0').equals("zero")); + tests.test(scanner.getCategory('8').equals("digit")); + tests.test(scanner.getCategory('B').equals("digit")); + tests.test(scanner.getCategory(' ').equals("whitespace")); + tests.test(scanner.getCategory('z').equals("not in alphabet")); + + tests.test(scanner.getNewState("s0", "zero").equals("s1")); + tests.test(scanner.getNewState("s1", "x").equals("s2")); + tests.test(scanner.getNewState("s2", "zero").equals("s3")); + tests.test(scanner.getNewState("s2", "digit").equals("s3")); + tests.test(scanner.getNewState("s3", "zero").equals("s3")); + tests.test(scanner.getNewState("s3", "digit").equals("s3")); + tests.test(scanner.getNewState("s0", "whitespace").equals("s4")); + tests.test(scanner.getNewState("s4", "whitespace").equals("s4")); + tests.test(scanner.getNewState("s0", "digit").equals("error")); + tests.test(scanner.getNewState("s1", "zero").equals("error")); + tests.test(scanner.getNewState("s2", "x").equals("error")); + + tests.test(scanner.getTokenType("s0").equals("error")); + tests.test(scanner.getTokenType("s1").equals("error")); + tests.test(scanner.getTokenType("s2").equals("error")); + tests.test(scanner.getTokenType("s3").equals("hexnumber")); + tests.test(scanner.getTokenType("s4").equals("ignore")); + + //------------------------------------------------------------ + // The following tests should pass once you have + // Scanner.nextToken() implemented. + //------------------------------------------------------------ + { + ScanStream ss = getDataStream("data/test1-hex.txt"); + testToken(scanner, ss, "hexnumber", "0x3F"); + testToken(scanner, ss, "ignore"); + testToken(scanner, ss, "hexnumber", "0x1234"); + testToken(scanner, ss, "ignore"); + testToken(scanner, ss, "hexnumber", "0x1234567890ABCDEF"); + } + { + ScanStream ss = getDataStream("data/err1-hex.txt"); + testToken(scanner, ss, null); + } + { + ScanStream ss = getDataStream("data/err2-hex.txt"); + testToken(scanner, ss, null); + } + { + ScanStream ss = getDataStream("data/err3-hex.txt"); + testToken(scanner, ss, "hexnumber", "0x3A"); + 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) { + System.out.println(e.toString()); + tests.addFailure(); + } + } + + 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-one/p1-scanner/scanner/ScanStream.java b/Homework/cs5300/project-one/p1-scanner/scanner/ScanStream.java new file mode 100644 index 0000000..04cff68 --- /dev/null +++ b/Homework/cs5300/project-one/p1-scanner/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-one/p1-scanner/scanner/Scanner.java b/Homework/cs5300/project-one/p1-scanner/scanner/Scanner.java new file mode 100644 index 0000000..2581dcb --- /dev/null +++ b/Homework/cs5300/project-one/p1-scanner/scanner/Scanner.java @@ -0,0 +1,121 @@ +package scanner; + +import java.util.HashMap; +import java.util.Stack; + +public class Scanner { + HashMap<Character, String> charCategories; + HashMap<String, HashMap<String, String>> transitions; + HashMap<String, String> tokenTypes; + String s0; + + /** + * Builds the tables needed for the scanner. + */ + public Scanner(TableReader tableReader) { + charCategories = new HashMap<>(); + transitions = new HashMap<>(); + tokenTypes = new HashMap<>(); + + // Build catMap, mapping a character to a category. + for (TableReader.CharCat cat : tableReader.getClassifier()) + charCategories.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()) { + if (s0 == null) + s0 = t.getFromStateName(); + if (!transitions.containsKey(t.getFromStateName())) + transitions.put(t.getFromStateName(), new HashMap<String, String>()); + + transitions.get(t.getFromStateName()) + .put(t.getCategory(), t.getToStateName()); + } + + // Build the token types table + for (TableReader.TokenType tt : tableReader.getTokens()) + tokenTypes.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 (charCategories.containsKey(c)) + return charCategories.get(c); + + return "not in alphabet"; + } + + /** + * 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 (transitionExists(state, category)) + return transitions.get(state).get(category); + + return "error"; + } + + private boolean transitionExists(String state, String category) { + if (transitions.containsKey(state)) { + HashMap<String, String> transitionTable = transitions.get(state); + return transitionTable.containsKey(category); + } + return false; + } + + /** + * 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 (tokenTypes.containsKey(state)) + return tokenTypes.get(state); + return "error"; + } + + /** + * Return the next token or null if there's a lexical error. + */ + public Token nextToken(ScanStream ss) { + String state = s0; + String lexeme = ""; + + Stack<String> stack = new Stack<>(); + stack.push("bad"); + + while (!state.equals("error") && !ss.eof()) { + char c = ss.next(); + lexeme += c; + + if (tokenTypes.containsKey(state)) + stack.clear(); + + stack.push(state); + + state = getNewState(state, getCategory(c)); + } + + while (!tokenTypes.containsKey(state) && !state.equals("bad")) { + state = stack.pop(); + if (lexeme.length() > 0) + lexeme = lexeme.substring(0, lexeme.length() - 1); + + ss.rollback(); + } + + if (tokenTypes.containsKey(state)) + return new Token(tokenTypes.get(state), lexeme); + + return null; + } +} diff --git a/Homework/cs5300/project-one/p1-scanner/scanner/TableReader.java b/Homework/cs5300/project-one/p1-scanner/scanner/TableReader.java new file mode 100644 index 0000000..a074547 --- /dev/null +++ b/Homework/cs5300/project-one/p1-scanner/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-one/p1-scanner/scanner/Tests.java b/Homework/cs5300/project-one/p1-scanner/scanner/Tests.java new file mode 100644 index 0000000..bb51147 --- /dev/null +++ b/Homework/cs5300/project-one/p1-scanner/scanner/Tests.java @@ -0,0 +1,49 @@ +/* + * 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() { + N++; + failures++; + } + + public int getN() { + return N; + } + + public int getSuccesses() { + return N - failures; + } + + public int getFailures() { + return failures; + } +} diff --git a/Homework/cs5300/project-one/p1-scanner/scanner/Token.java b/Homework/cs5300/project-one/p1-scanner/scanner/Token.java new file mode 100644 index 0000000..4c0151a --- /dev/null +++ b/Homework/cs5300/project-one/p1-scanner/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; + } + +} |