Recursive parsing and priorities

[msx80]

Hi there, i was trying to implement a simple "calculator language", to parse code like this:

var x = 10
var y = x+3
print y+5

Defining the parsing was pretty easy, in particular i defined expressions like usually done in AST for compilers:

	interface Expression {};
	record NumberExpression(Integer value) implements Expression {};
	record VariableExpression(String value) implements Expression {};
	record SumExpression(Expression a, Expression b) implements Expression {};

The parsers are defined like this:

private final Parser<Expression> expression(){
	return lazy(() -> choice(number.map(NumberExpression::new), identifier.map(VariableExpression::new), sum));
}
private final Parser<Expression> sum = expression().keepLeft(literal("+")).and(expression()).map(p -> new SumExpression(p.first(), p.second()));

The problem is: when i parse something like print 10+x, it gives an error because it reads the 10 as a NumberExpression and then doesn't know what to do with "+", infact the error is:

Failure: syntax error in Example Input at line 1 and column 13: unexpected character '+'

So is there a way to tell the system to try and be eager with the "sum" expression instead of returning the NumberExpression?
I've tried to change the order of the choice() elements, bringing sum to the front, but now the parser crashes with a stack overflow.

Here's the full example:

import java.util.List;

import jjparse.StringParsing;
import jjparse.input.Input;

public class Calculator extends StringParsing {
	
	interface Statement {};
	interface Expression {};
	record NumberExpression(Integer value) implements Expression {};
	record VariableExpression(String value) implements Expression {};
	record SumExpression(Expression a, Expression b) implements Expression {};
	record VarDecl(String name, Expression value) implements Statement {};
	record Print(Expression value) implements Statement {};
	
	
	private final Parser<Expression> expression(){
		return lazy(() -> choice(number.map(NumberExpression::new), identifier.map(VariableExpression::new), sum));
	}
	private final Parser<Expression> sum = expression().keepLeft(literal("+")).and(expression()).map(p -> new SumExpression(p.first(), p.second()));
	
	private final Parser<Statement> variable = literal("var").keepRight(identifier).and(literal("=").keepRight(expression())).map(p -> new VarDecl(p.first(), p.second()));
	
	private final Parser<Statement> print = literal("print").keepRight(expression()).map(Print::new);
	
	private final Parser<List<Statement>> instructions = 
			choice(variable, print)
			.keepLeft(literal(";"))
			.repeat();
	
	public static void main(String[] args)
	{
		Input<Character> input = Input.of("Example Input", 
"""
	   print 10+y

""");

	    	Calculator parser = new Calculator() {};
	        Result<?> result = parser.parse(parser.print, input);

	        switch (result) {
	            case Success<?> success:
	                System.out.printf("Success: %s\n", success.value);
	                break;
	            case Failure<?> failure:
	                System.err.printf("Failure: %s\n", failure.message);
	                break;
	        }
	    }	    
}

[BjoernLoetters]

Hi and thanks for this example!

In this case, it is actually "good" that the parser isn't greedy. Otherwise, you would encounter a StackOverflowError. This is a common misconception when switching from LR parsers (e.g., ANTLR) to LL parsers, recursive descent parsers or parser combinators like jjparse. The problem here is the hidden left recursion in your parser: an expression is either a number, an identifier or a sum, whereas a sum starts with an expression. So, if the order of your choice would be choice(sum, number.map(NumberExpression::new), identifier.map(VariableExpression::new)) instead (or if the parser would be more greedy here), the parser would infinitely loop in the cycle expression → sum → expression → sum → .... In order to avoid this unproductive loop, we have to restructure the grammar using a repetition parser instead:

private Parser<Expression> expression() { return lazy(() -> sum); }

private final Parser<Expression> atom = choice(
    number.map(NumberExpression::new), 
    identifier.map(VariableExpression::new), 
    expression().between(literal("("), literal(")"))
);

private final Parser<Expression> sum = atom.separate1(literal("+")).map(
    summands -> summands.stream().reduce(SumExpression::new).get()
);

Here, we use the separate1 parser to separate each summand (a number, an identifier or an expression enclosed by parentheses) with the + sign. In this way, we avoid using left recursion. And since this is a very common pattern in programming languages, there is even a shorter way to express this using the chainLeft, chainLeft1, chainRight or chainRight1 combinators:

private final Parser<Expression> sum = chainLeft1(atom, literal("+").map(ignore -> SumExpression::new));

The idea of these combinators is to separate the first parser (in this case atom) with the second parser (in this case literal("+")), where the result of the second parser is not just ignored. Instead it must correspond to a binary function that combines any two elements (which is already given by the constructor of SumExpression in your case). The addition Left and Right just tells the parser how to combine the individual elements: either from left to right or from right to left. The suffix 1 means: The first parser must succeed at least once (which is the reason, why it's safe to use get() in my first example).

In the future, I may also change the API such that we can write atom.chainl1(literal("+").map(ignore -> SumExpression::new)). In this case, the chain combinators are also suggested by common IDEs.

[msx80]

Thanks for your kind explanation!
Ok i think i see the problem. I managed to apply your solution and it works for arbitrary sequences of a+b+c+d+....

Now i've added subtraction, and the problem showed up again:

	private Parser<Expression> expression() { return lazy(() -> choice(sum, difference)); }
	
	private final Parser<Expression> sum = chainLeft1(atom, literal("+").map(ignore -> SumExpression::new));
	private final Parser<Expression> difference = chainLeft1(atom, literal("-").map(ignore -> DiffExpression::new));

Breaks for input 10-4+2 because 10 is interpreted as a sum (of a single element) and then "expression-something" is not a rule.
I guess i have to do something like this:

private final Parser<Expression> binaryOperand = chainLeft1(atom, literal("+").or(literal("-")).map(ignore -> BiOpExpression::new));

In general, the impression i have is that i need to study this kind of parsers better :) They require a different mindset then classic LR parsers. I'm wondering if real languages (like java, lua, phyton etc) can be parsed with this kind of parsers?

[BjoernLoetters]

I am glad I could help. Thanks for testing this library and sharing your experience!

It is as you say: working with parser combinators requires a slightly different mindset (more like working with LL parsers). If I had to break it down to one thing it would be this: An LR-Parser or generally a CFG has a relational character, while a PEG has a functional character.

That being said, the pattern you are searching for is something like this:

// Precedence level 1 (lowest level) with binary operators level1op1 to level1opK
Parser<BiFunction<Expression, Expression, Expression>> level1op = choice(
    literal("level1op1").map(ignore -> Level1Op1::new),
    ...
    literal("level1opK").map(ignore -> Level1OpK::new)
);
Parser<Expression> level1 = chainLeft1(level2, level1op);

// Precedence level 2 with binary operators level2op1 to level2opK
Parser<BiFunction<Expression, Expression, Expression>> level2op = choice(
    literal("level2op1").map(ignore -> Level2Op1::new),
    ...
    literal("level2opK").map(ignore -> Level2OpK::new)
);
Parser<Expression> level2 = chainLeft1(level3, level1op);

...

// Precedence level N (highest level) with binary operators levelNop1 to levelNopK
Parser<BiFunction<Expression, Expression, Expression>> levelNop = choice(
    literal("levelNop1").map(ignore -> LevelNOp1::new),
    ...
    literal("levelNopK").map(ignore -> LevelNOpK::new)
);
Parser<Expression> levelN = chainLeft1(atomic, levelNop);

Here, the choice between chainLeft and chainRight decides whether the respective precedence level is a left- or a right-associative level. It is also possible to extend this scheme by additional levels for postfix and prefix operators. In your case, we could instantiate this scheme as follows:

private Parser<Expression> expression() { return lazy(() -> level1); }

private final Parser<BiFunction<Expression, Expression, Expression>> level1ops = choice(
    literal("+").map(ignore -> SumExpression::new),
    literal("-").map(ignore -> DiffExpression::new)
);
private final Parser<Expression> level1 = chainLeft1(atom, level1ops);

I think these questions of yours are especially valuable for a wiki in the future (I suppose these are the questions anyone would ask when switching from LR-parsers to parser combinators). So thanks again for sharing!

[BjoernLoetters]

Regarding your last question: Yes, even the syntax of real languages like Java, Python or Lua can be implemented using parser combinators. In my daily work, I deal with programming languages a lot, and I can say that I almost exclusively use parser combinators to implement their syntax. I think the approach is more commonly used in functional programming languages like Scala (see the Scala Parser Combinators Library) or Haskell (see the Parsec Library).