4
\$\begingroup\$

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:

  1. Stratifying this more, if possible.
  2. Ensuring it isn't wasteful.
  3. Accounting for edge cases I may have missed.
  4. 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 singleLineComment can 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 haltPrint method I simply threw new IllegalArgumentException exceptions, 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: )

\$\endgroup\$
3
\$\begingroup\$

Parentheses checking not complete

Your program currently checks that open parentheses are balanced numberswise with close parentheses. However, it does not check that the parentheses occur in the correct sequence or even in syntactically correct situations. For example, all of the following test cases are considered correct:

  a := ) b + c (
  a := b + c ()
  a := (b + ) c

Expand your grammar

I think that in order to correctly handle parentheses and other syntactical errors, you need to define a more complete grammar. Something like this:

<statement>  -> <id> := <expression>
<expression> -> <term> | <term> "+" <expression> | <term> "-" <expression>
<term>       -> <factor> | <term> "*" <factor> | <term> "/" <factor>
<factor>     -> <id> | "(" <expression> ")"
<id>         -> (your current syntax for id)

Then you need to attempt to parse a "statement" and print an error if the input doesn't match the grammar for a statement.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.