Challenge:
Build an ad-hoc scanner for a calculator language.
Specifications:
The tokens for the language are as follows:
assign → :=
plus → +
minus → -
times → *
div → /
lparen → (
rparen → )
id → letter (letter|digit)* number → digit digit * | digit * (.digit | digit.) digit *
-------excluding read and write
comment → /* (non-* | * non-/)* / | // (non-newline newline
For simplicity, halt in case of a lexical error.
Sample Input:
number := a + b
total := (a - b) * c
final := total + num
LexTest := )) a - b
My Solution:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class LexScan {
final static String[] ILLEGAL_IDS = {"read", "write"};
static enum Token {
ASSIGN(':', ":="),
PLUS('+'),
MINUS('-'),
TIMES('*'),
DIVIDES('/'),
LEFT_PARENTHESES('('),
RIGHT_PARENTHESES(')');
private final String lexeme;
private final char matcher;
Token(char matcher) {
this.matcher = matcher;
lexeme = String.valueOf(matcher);
}
Token(char matcher, String lexeme) {
this.matcher = matcher;
this.lexeme = lexeme;
}
public char matcher() {
return matcher;
}
public String lexeme() {
return lexeme;
}
@Override
public String toString() {
return name().replaceAll("_", " ");
}
public String toLexEntry() {
return toString() + ": " + lexeme;
}
}
public static void main(String[] args) {
if (args.length > 0) {
iterativePrintln(lexify(toTestString(args)));
System.exit(0);
}
Scanner input = new Scanner(System.in);
System.out.print("Enter test case: ");
iterativePrintln(lexify(input.nextLine()));
}
public static List<String> lexify(String testCase) {
String sanitized = testCase.replaceAll("\\s+", "");
List<String> lexEntryList = new ArrayList<>();
StringBuilder identifierBuilder = new StringBuilder();
StringBuilder numberBuilder = new StringBuilder();
int balancedParantheses = 0;
boolean buildingIdentifier = false;
boolean buildingNumber = false;
boolean singleLineCommenting = false;
boolean multiLineCommenting = false;
outer:
for (int i = 0; i < sanitized.length(); i++) {
char current = sanitized.charAt(i);
char next = ' ';
if (i != sanitized.length() - 1) {
next = sanitized.charAt(i + 1);
}
if (singleLineCommenting) {
if (current == '\n') {
singleLineCommenting = false;
}
continue;
} else if (multiLineCommenting) {
if (current == '*' && next == '/') {
i++;
multiLineCommenting = false;
}
continue;
}
if (Character.isLetter(current)) {
buildingIdentifier = true;
identifierBuilder.append(current);
continue;
}
if (isNumber(current)) {
if (buildingIdentifier) {
identifierBuilder.append(current);
continue;
} else {
buildingNumber = true;
numberBuilder.append(current);
continue;
}
}
for (Token token : Token.values()) {
if (current == token.matcher()) {
if (token == Token.ASSIGN) {
if (next == '=') {
i++;
} else {
haltPrint("Unmatched Assignment: ':' without '=' ");
}
} else if (token == Token.LEFT_PARENTHESES) {
balancedParantheses++;
} else if (token == Token.RIGHT_PARENTHESES) {
balancedParantheses--;
} else if (token == Token.DIVIDES) {
if (next == '/') {
i++;
singleLineCommenting = true;
continue outer;
} else if (next == '*') {
i++;
multiLineCommenting = true;
continue outer;
}
}
if (buildingNumber) {
lexEntryList.add("NUMBER: " + numberBuilder.toString());
numberBuilder.setLength(0);
buildingNumber = false;
}
if (buildingIdentifier) {
String id = identifierBuilder.toString();
if (!isLegalId(id)) {
haltPrint("Illegal ID: " + id);
}
lexEntryList.add("IDENTIFIER: " + id);
identifierBuilder.setLength(0);
buildingIdentifier = false;
}
lexEntryList.add(token.toLexEntry());
}
}
if (current == '=') {
haltPrint("Unmatched Assignment: '=' without ':'");
}
}
if (buildingNumber) {
lexEntryList.add("NUMBER: " + numberBuilder.toString());
} else if (buildingIdentifier) {
String id = identifierBuilder.toString();
if (!isLegalId(id)) {
haltPrint("Illegal ID: " + id);
}
lexEntryList.add("IDENTIFIER: " + id);
}
if (balancedParantheses != 0) {
haltPrint("Unbalanced Parantheses");
}
if (multiLineCommenting) {
haltPrint("Unclosed Comment");
}
return lexEntryList;
}
public static void iterativePrintln(List<String> list) {
for (String str : list) {
System.out.println(str);
}
}
public static void haltPrint(String str) {
System.out.println(str);
System.exit(0);
}
public static String toTestString(String[] args) {
return String.join("", args);
}
public static boolean isLegalId(String id) {
for (String illegalId : ILLEGAL_IDS) {
if (illegalId.equals(id)) {
return false;
}
}
return true;
}
public static boolean isNumber(char c) {
try {
Double.parseDouble(String.valueOf(c));
} catch (NumberFormatException nfe) {
return false;
}
return true;
}
}
This is a very new and interesting subject, so I'm sure there's a lot of room for improvement, especially given the size of my lexify method -- it just kept growing and growing as I added in all the checks.
I'm definitely interested in:
- Stratifying this more, if possible.
- Ensuring it isn't wasteful.
- Accounting for edge cases I may have missed.
- Knowledge on conventional/superior libraries or methods to facilitate this process.
Of course, general feedback as always is welcome and appreciated.
Notes:
- I realize due to my approach the
singleLineCommentcan never really get to false, but one test case is one line, so it's a non-issue and simply included for completion. - Before the
haltPrintmethod I simply threwnew IllegalArgumentExceptionexceptions, but for the sake of simplicity and posting the trial runs that follow I added it in. - Depending on OS shell the
*operator may not work on the command line version, simply run through the program for those tests.
Trial cases:
Input 1:
a := 4 + /*CR is love*/ (3 - b)
Output 1:
IDENTIFIER: a
ASSIGN: :=
NUMBER: 4
PLUS: +
TIMES: *
LEFT PARENTHESES: (
NUMBER: 3
MINUS: -
IDENTIFIER: b
RIGHT PARENTHESES: )
Input 2:
a = derp + herp
Output 2:
Unmatched Assignment: '=' without ':'
Input 3:
a := 18 * (417 + (22 - 3)/2) // I like soup
Output 3:
IDENTIFIER: a
ASSIGN: :=
NUMBER: 18
TIMES: *
LEFT PARENTHESES: (
NUMBER: 417
PLUS: +
LEFT PARENTHESES: (
NUMBER: 22
MINUS: -
NUMBER: 3
RIGHT PARENTHESES: )
DIVIDES: /
NUMBER: 2
RIGHT PARENTHESES: )
