How would it be possible to look ahead more than one token?

[springcomp]

The Peek() method allows to look ahead one token in advance.

However, there does not seem to be a way to look ahead more than one token?

My use case is parsing JMESPath expressions.
Please, consider the following tokens:

T_STAR = "*"
T_LBRACKET = "["
T_RBRACKET = "]"

The following token sequence is ambiguous T_LBRACKET, T_STAR, … :

• It could be the start of a "[" "*" "]" list-wildcard-projection expression, or
• It could be the start of a "[" ( expression *("," expression) ) "]" multi-select-list expression whose first item is a hash-wildcard-projection.

When parsing this expression, I have a parselet for the prefixed token T_LBRACKET where I can look ahead the next token using Peek() to identify the T_STAR token. However, this does not allow me to disambiguate between the two constructs. I tried to Read() the token and then using Peek() again but then I potentially find myself in the middle of an infix token and I can see no way to have the parser carry on with its task since I consumed the token.

Maybe I’m using TDOP wrong?

[atifaziz]

I wonder if you could disambiguate at the tokenization level in this particular case. In other words, what if you tried treating "[" "*" "]" as a single token along? As in:

T_STAR = "*"
T_LBRACKET = "["
T_RBRACKET = "]"
T_BRACKETED_STAR = "[" "*" "]"

If just two tokens are sufficient to disambiguate then you could just go with:

T_STAR = "*"
T_LBRACKET = "["
T_RBRACKET = "]"
T_LBRACKET_STAR = "[" "*"

This way, you could easily do your lookaheads at the character level during tokenization rather than needing to do it during parsing.

[springcomp]

Yes, that will definitely solve that issue. 👍

As you know, I was trying to upgrade step by step, first by swapping out the lexer and/or then swapping out the parser to better identify root performance issues.

I guess I did not anticipate to have to slightly change the tokenization as the corresponding lex/yacc implementation does not have the issue with this ambiguity. And it turns out that the Python implementation of TDOP from which I get my inspiration is indeed using more than one lookahead symbol — exactly two in fact – from the same tokenization process.

[springcomp]

I had to definitely implement lookaheads in Gratt because it is eventually impossible to parse the JMESPath grammar unambiguously using a Vaughn Pratt parser without lookaheads. ☹

Is so happens that JMESPath has the following expression [*] which can be parsed in either of two ways (depending on the preceding expressions):

• Either a list-wildcard-projection that projects each item from the preceding array to the downstream expressions.
• Or a multi-select-list that produces a JSON array with a single entry, that consists in a hash-wildcard-projection that projects the preceding object properties to downstream expressions.

For instance, consider the following input JSON document:

{
    "foo": [
        { "name": "bar" },
        { "name": "baz" }
    ],
   "bar": {
       "baz": "qux"
   }
}

Using JMESPath gives the following respective results:

• search(foo[*], …) -> [ {"name": "bar"}, {"name": "baz"} ] (where [*] is a list-wildcard-projection)
• search(bar.[*], …) -> [ [ "qux" ] ] (where [*] is a multi-select-list with a single entry)

Creating a dedicated token T_LISTWILDCARD = `[*]` prevents parsing the second use case.
So I definitely have to lookahead and proceed depending on context.

I’m a bit ashamed at my code that I cobbled together quite quickly.
I can, however, spend more time and write unit-tests if you would you be interested in a proper pull request ?

[atifaziz]

I’m a bit ashamed at my code that I cobbled together quite quickly.
I can, however, spend more time and write unit-tests if you would you be interested in a proper pull request ?

I've opened issue #7 to track this. Thanks for your offer to contribute and write tests. I spiked an implementation and would love to get your review and help on unit tests.