Strange behaviour for `choice`

[typemeta]

Strange behaviour for `choice`

[jon-hanson]

The issue is that funcj.parser is a framework for LL(1) parsers, meaning parsers for grammars that can be parsed by looking only 1 character ahead at each stage. In your grammar the parser needs to look 5 characters ahead to determine that the token isn't "true" or "false".

You can usually work around this by deferring the decision as to which parse rule gets applied until you have read sufficient tokens. If I simplify your example for brevity and pretend that a boolean is either "aa" or "bb", then the following illustrates this approach:

private static Either<Boolean, String> left(boolean value) {
    return Either.left(value);
}

private static Either<Boolean, String> right(String value) {
    return Either.right(value);
}

static Parser<Chr, Boolean> aa = string("aa").map(F.konst(true));
static Parser<Chr, Boolean> bb = string("bb").map(F.konst(false));
static Parser<Chr, Boolean> bool = choice(aa, bb);
static Parser<Chr, String> word = alpha.many1().map(Chr::listToString);

static Parser<Chr, Either<Boolean, String>> trueOrWord =
        chr('a').andR(Combinators.any())
                .map(c -> c.equals('a') ? left(true) : right("a" + c));

static Parser<Chr, Either<Boolean, String>> falseOrWord =
        chr('b').andR(Combinators.any())
                .map(c -> c.equals('b') ? left(false) : right("a" + c));

static Parser<Chr, Either<Boolean, String>> boolOrWord =
        choice(trueOrWord, falseOrWord, word.map(Either::right));

public static void main(String[] args) {
    final var parser = boolOrWord;
    final var bool = Input.of("aa");
    final var anyWord = Input.of("zz");
    final var startsLikeBool = Input.of("ab");

    final var parsedTrue = parser.parse(bool).getOrThrow();
    System.out.println(parsedTrue.left());
    System.out.println("assert: " + (parsedTrue.left() == true));

    final var parsedWord = parser.parse(anyWord).getOrThrow();
    System.out.println(parsedWord.right());
    System.out.println("assert: " + parsedWord.right().equals("zz"));

    final var parsedLikeBool = parser.parse(startsLikeBool).getOrThrow();
    assert parsedLikeBool.right().equals("ab");
    System.out.println(parsedLikeBool.right());
    System.out.println("assert: " + parsedLikeBool.right().equals("ab"));
}

[vbrandl]

So in general a grammar like mine, which is not uniquely decidable, cannot be parsed by a LL(1) parser (my parsers and compilers course was 3 years ago so I don't remember the details...)

Requiring words that are not boolean values to be wrapped in "" might fix the ambiguity, too?

[jon-hanson]

You grammar in its current form is not an LL(1) grammar. The wikipedia page includes some strategies for resolving this. Alternatively, as you suggest, you can change the language syntax to make it more amenable to be being expressed in an LL(1) grammar, though most languages would lean towards putting the arbitrary string in quotes and leaving true and false as unquoted keywords. Another approach might be to tokenise the input first, and then have the parser operate on word tokens.

[vbrandl]

Thanks for the refreshing on some theoretical concepts :)

I think for now I'll take the lazy solution and do something like

alpha.many1().map(Chr::listToString).map(s -> {
  if (s.equals("true"))
    return Either.left(true);
  else if (s.equals("false"))
    return Either.left(false);
  else
    return Either.right(s);
})

But I might fix that in later™