Quick help: JMES Path parsing - recursive problem

[pratikpparikh]

Hi @renggli ,

I need some quick help and direction. I am trying to implement JMES PATH Specification, currently expression in the grammar is used recursively. How do i create a parse so it does not run into cyclic problems?

below is an example, not sure what i can do to address the situation:

Parser STAR() => ref(token, '*'); Parser DOT() => ref(token, '.'); Parser expressionSegment() => ref(sub_expressionSegment); Parser sub_expressionSegment() => ref(expressionSegment) & ref(DOT) & ref(STAR);

The parser create stack overflow with below stack:

package:petitparser/src/parser/repeater/possesive.dart 56:3 PossessiveRepeatingParser.parseOn package:petitparser/src/parser/combinator/sequence.dart 41:34 SequenceParser.parseOn package:petitparser/src/parser/combinator/choice.dart 45:28 ChoiceParser.parseOn package:petitparser/src/parser/repeater/possesive.dart 61:31 PossessiveRepeatingParser.parseOn package:petitparser/src/parser/combinator/sequence.dart 41:34 SequenceParser.parseOn package:petitparser/src/parser/combinator/choice.dart 45:28 ChoiceParser.parseOn package:petitparser/src/parser/repeater/possesive.dart 61:31 PossessiveRepeatingParser.parseOn package:petitparser/src/parser/combinator/sequence.dart 41:34 SequenceParser.parseOn package:petitparser/src/parser/combinator/choice.dart 45:28 ChoiceParser.parseOn package:petitparser/src/parser/repeater/possesive.dart 61:31 PossessiveRepeatingParser.parseOn package:petitparser/src/parser/combinator/sequence.dart 41:34 SequenceParser.parseOn package:petitparser/src/parser/combinator/choice.dart 45:28 ChoiceParser.parseOn package:petitparser/src/parser/repeater/possesive.dart 61:31 PossessiveRepeatingParser.parseOn package:petitparser/src/parser/combinator/sequence.dart 41:34 SequenceParser.parseOn package:petitparser/src/parser/combinator/choice.dart 45:28 ChoiceParser.parseOn package:petitparser/src/parser/repeater/possesive.dart 61:31 PossessiveRepeatingParser.parseOn package:petitparser/src/parser/combinator/sequence.dart 41:34 SequenceParser.parseOn package:petitparser/src/parser/combinator/choice.dart 45:28 ChoiceParser.parseOn package:petitparser/src/parser/repeater/possesive.dart 61:31 PossessiveRepeatingParser.parseOn

Any help is appreciated or direction.

Regards, Pratik Parikh

[renggli]

Your grammar is left-recursive, meaning it references itself without consuming any input. Also your expression has no termination condition, thus it never stops.

Typically you can reorder the productions so that input is consumed before the recursion is closed:

Parser expressionSegment() => ref(sub_expressionSegment).optional();   // (2) teminate
Parser sub_expressionSegment() => ref(DOT) & ref(STAR) & ref(expressionSegment);   // (1) consume input first

Alternatively, it is usually easier to use one of the repeaters (star, plus, separatedBy, ...):

Parser expressionSegment() => (ref(DOT) & ref(STAR)).star()

[pratikpparikh]

@renggli I see you point won't change the grammar syntax?

Parser sub_expressionSegment() => ref(DOT) & ref(STAR) & ref(expressionSegment); // (1) consume input first

Are you recommending to interpret in correct order after parsing?

[renggli]

True, both of my proposals change the generated parse trees. The first proposal with recursion is kind of difficult to fix after the fact; the second one with the the repeaters producing flat lists is much simpler to interpret.

In any case, if you have more complicated expression parsers to build and interpret it is probably the simplest to use the ExpressionBuilder. It allows you to easily specify priorities and left/right associative operators.

[Dokotela]

@pratikpparikh Did you ever get this to work? If so, I'd be interested in discussing it more with you as I'm trying to do something similar, thanks!

[pratikpparikh]

@Dokotela I did it was not pretty then null safety came and thus I change course. It was becoming hard to maintain.