8
\$\begingroup\$

The following program is a lexical analyser for a simple and small grammar.

Please read my code and answer me these questions:

  1. Is my code easy to understand?
  2. Is my code well organized?
  3. Are there bugs in my code?
  4. Is the lack of comments a problem?
  5. Can you make my code more performatic without modifying all the structure?

A general criticism is also welcome.

A note about performance: The program is really bad in performance. I already coded lexical analysers much better in this point, but this one is easier to extend and understand, so I do not want to lose the current structure.

Token.java

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public enum Token {
    LET_KEYWORD ("let"),
    IF_KEYWORD ("if"),
    WHILE_KEYWORD ("while"),
    ELSE_KEYWORD ("else"),

    SEMICOLON (";"),
    COMMA (","),

    OPEN_BRACKET ("\\{"),
    CLOSE_BRACKET ("\\}"),
    OPEN_PARENTHESIS ("\\("),
    CLOSE_PARENTHESIS ("\\)"),

    EQUAL ("=="),
    DIFFERENT ("<>"),
    GREATER_EQUAL (">="),
    LESSER_EQUAL ("<="),
    ATTRIBUTION ("="),
    GREATER (">"),
    LESSER ("<"),

    ADDITION ("\\+"),
    SUBTRACTION ("-"),
    MULTIPLICATION ("\\*"),
    DIVISION ("/"),
    MODULUS ("%"),

    STRING ("\"[^\"]+\""),
    NUMBER ("\\d+(\\.\\d+)?"),
    IDENTIFIER ("\\w+");    

    private final Pattern pattern;

    Token(String regex) {
        pattern = Pattern.compile("^" + regex);
    }

    int endOfMatch(String s) {
        Matcher m = pattern.matcher(s);

        if (m.find()) {
            return m.end();
        }

        return -1;
    }
}

Lexer.java

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Stream;

public class Lexer {
    private StringBuilder input = new StringBuilder();
    private Token token;
    private String lexema;
    private boolean exausthed = false;
    private String errorMessage = "";
    private Set<Character> blankChars = new HashSet<Character>();

    public Lexer(String filePath) {
        try (Stream<String> st = Files.lines(Paths.get(filePath))) {
            st.forEach(input::append);
        } catch (IOException ex) {
            exausthed = true;
            errorMessage = "Could not read file: " + filePath;
            return;
        }

        blankChars.add('\r');
        blankChars.add('\n');
        blankChars.add((char) 8);
        blankChars.add((char) 9);
        blankChars.add((char) 11);
        blankChars.add((char) 12);
        blankChars.add((char) 32);

        moveAhead();
    }

    public void moveAhead() {
        if (exausthed) {
            return;
        }

        if (input.length() == 0) {
            exausthed = true;
            return;
        }

        ignoreWhiteSpaces();

        if (findNextToken()) {
            return;
        }

        exausthed = true;

        if (input.length() > 0) {
            errorMessage = "Unexpected symbol: '" + input.charAt(0) + "'";
        }
    }

    private void ignoreWhiteSpaces() {
        int charsToDelete = 0;

        while (blankChars.contains(input.charAt(charsToDelete))) {
            charsToDelete++;
        }

        if (charsToDelete > 0) {
            input.delete(0, charsToDelete);
        }
    }

    private boolean findNextToken() {
        for (Token t : Token.values()) {
            int end = t.endOfMatch(input.toString());

            if (end != -1) {
                token = t;
                lexema = input.substring(0, end);
                input.delete(0, end);
                return true;
            }
        }

        return false;
    }

    public Token currentToken() {
        return token;
    }

    public String currentLexema() {
        return lexema;
    }

    public boolean isSuccessful() {
        return errorMessage.isEmpty();
    }

    public String errorMessage() {
        return errorMessage;
    }

    public boolean isExausthed() {
        return exausthed;
    }
}

You probably want to run my code, so use this:

Start.java

public class Start {
    public static void main(String s[]) {
        Lexer lexer = new Lexer("C:/teste/font.txt");

        while (!lexer.isExausthed()) {
            System.out.printf("%-18s %s\n", lexer.currentToken(), lexer.currentLexema());
            lexer.moveAhead();
        }

        if (lexer.isSuccessful()) {
            System.out.println("Ok! :D");
        } else {
            System.out.println(lexer.errorMessage());
        }
    }
}

As you can see, the lexer reads C:/teste/font.txt. The content is:

let i = 0;

let do_task (name, secs) = {
    if secs == 0 {
        write("Completed" + name + "instantaneously");
    } else {
        sleep(secs * 1000);
        write("After" + secs + "completed" + name);
    }
}

while i <= 10 {
    do_task(i, "some task");
    i = i + 1;
}
\$\endgroup\$
  • \$\begingroup\$ Hi @kamoroso94. I think your comment could be an answer. \$\endgroup\$ – Gabriel Aug 15 '16 at 3:01
  • \$\begingroup\$ I did have to edit the comment to fit under the character limit, so maybe that should've been a sign haha. Thanks for the advice, I've reposted my previous comment as an answer below. I hope it helps. \$\endgroup\$ – kamoroso94 Aug 15 '16 at 3:08
  • 3
    \$\begingroup\$ Personally, I don't write enough comments, so won't tell you to. However, I will say that future you will appreciate javadoc comments: these documentation comments show up in your IDE to tell you what each function does. \$\endgroup\$ – CAD97 Aug 15 '16 at 7:56
12
\$\begingroup\$

Nitpick

    private boolean exausthed = false;

Pedantic, but this should be spelled exhausted.

Class vs. Object

    private Set<Character> blankChars = new HashSet<Character>();

And then later in the constructor

        blankChars.add('\r');
        blankChars.add('\n');
        blankChars.add((char) 8);
        blankChars.add((char) 9);
        blankChars.add((char) 11);
        blankChars.add((char) 12);
        blankChars.add((char) 32);

This creates a separate one of these for each instance of the class, but all of them have the same values. Instead

    private static Set<Character> blankChars = new HashSet<Character>();

    static {
        blankChars.add('\r');
        blankChars.add('\n');
        blankChars.add((char) 8);
        blankChars.add((char) 9);
        blankChars.add((char) 11);
        blankChars.add((char) 12);
        blankChars.add((char) 32);
    }

Now we just have one copy for all instances of the class. The static block handles initialization.

Iterator

        while (!lexer.isExausthed()) {
            System.out.printf("%-18s %s\n", lexer.currentToken(), lexer.currentLexema());
            lexer.moveAhead();
        }

This pattern almost matches an iterator, albeit with different names. Consider

        while (lexer.hasNext()) {
            System.out.printf("%-18s %s\n", lexer.currentToken(), lexer.currentLexema());
            lexer.next();
        }

Now it's the same names but the behavior is slightly off.

        while (lexer.hasNext()) {
            System.out.printf("%-18s %s\n", lexer.next(), lexer.currentLexema());
        }

And you'd drop the moveAhead from the constructor, as it is no longer necessary to prime the pump that way. Actually implementing Iterable<Token> would allow you to say

        for (Token token : lexer) {
            System.out.printf("%-18s %s\n", token, lexer.currentLexema());
        }

Build for unit testing

    private boolean findNextToken() {

This would be difficult to unit test.

    static boolean findNextToken(StringBuilder input) {

This would be easier. Its visibility is less restricted and it is possible to call it as

    findNextToken(new StringBuilder("foo"));

It doesn't rely on object state.

Performance

The thing that looks non-performant to me is

        for (Token t : Token.values()) {
            int end = t.endOfMatch(input.toString());

            if (end != -1) {
                token = t;
                lexema = input.substring(0, end);
                input.delete(0, end);
                return true;
            }
        }

This seems inefficient. Rather than trying each token, consider building a data structure that goes the other way.

        for (Token t : possibleTokens.get(input.charAt(0))) {

So for a given character, what tokens could possibly match? For example, if the first character is a "w", then the token might be while or it might be an identifier. It's not going to be a comma or relational operator. So that drops twenty-five comparisons down to just two. And in many cases, there would be only one.

Bug?

I didn't try it, but I think that you might mishandle an identifier like

let letter = "a";

I think that this would get tokenized as

let
let
ter
=
"a"
;

Presumably you'd prefer that the second lexema be letter.

You may want to make "let" be "let\\b" instead. That should force it not to match if the word continues. You should also do this for other keywords, although this would be a less common problem for while or else.

Are numbers valid identifiers?

    IDENTIFIER ("\\w+");

This would match, e.g. 9f. But you'll never get a chance to see, as the 9 will get parsed as a number.

If that's an intentional behavior, you should comment it. Even better, unit test it. Then you are protected from a later edit putting IDENTIFIER before NUMBER.

Personally, I'd prefer that the regular expression only accept what it is supposed to accept. So if an identifier must start with a letter or underscore, the regular expression should capture that.

\$\endgroup\$
  • \$\begingroup\$ I know I should avoid this kind of comment, but... Well, thanks. You helped me a lot. \$\endgroup\$ – Gabriel Aug 15 '16 at 4:44
5
\$\begingroup\$

I've never learned about lexers, so I can only answer 1-4 confidently. I hope this helps to answer some of your questions.

  1. I found your code quite easy to follow. I was able to read from top to bottom, and jumping to the other method definitions and back. It seems very well organized.
  2. Yes, having all the right sections of code nestled into their own methods made comprehending the whole process very simple.
  3. I didn't see any bugs, but I'd take that with a grain of salt, given that I don't know all the ins and outs of lexers.
  4. I'm just like you; I almost never use comments unless I need to remind myself of the functionality of some code that's hard to understand. That said, I didn't have problems going through the code without comments, but maybe when you finish, it'd be nice to put some here and there to explain different sections.
\$\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.