nearley

Why is my Nearley grammar causing a loop?

I am playing around with nearley.js and something is confusing me. As a test I am trying to build a parser parsing poker ranks.

Now, this grammar is working as expected:

@{% function nuller() { return null; } %}

main -> _ composition _                         {% nuller %}

composition -> _ expression _                   {% nuller %}
    | composition _ "," _ rank                  {% nuller %}

expression -> _ rank _                          {% nuller %}
rank -> [a, k, q, j, t, A, K, Q, J, T, 2-9]     {% nuller %}

_ -> [\s]:*                                     {% nuller %}

However, the second I change | composition _ "," _ rank to | composition _ "," _ expression then I end up with a loop:

@{% function nuller() { return null; } %}

main -> _ composition _                         {% nuller %}

composition -> _ expression _                   {% nuller %}
    | composition _ "," _ expression            {% nuller %}

expression -> _ rank _                          {% nuller %}
rank -> [a, k, q, j, t, A, K, Q, J, T, 2-9]     {% nuller %}

_ -> [\s]:*                                     {% nuller %}

Can somebody explain me why that is? Code can quickly be tested at the playground: https://omrelli.ug/nearley-playground/

The test string I use is: a, k, q, j, t, 9, 8, 7, 6, 5, 4, 3, 2

Thank you very much in advance!

Solution

  • Well, there are multiple interpretations possible for each of the values in your string, this is because you both have optional whitespace before your expression and rank:

    If you look at the second element k, this can be interpreted as:

    Since you have 2 possibilities for 12 items in your string, you will get 144 possible combinations.

    This returns one solution (i have left out the optional whitespace before expression):

    
main -> _ composition _                         {% nuller %}

composition -> _ expression _                   {% nuller %}
    | composition _ "," expression              {% nuller %}

expression -> _ rank _                          {% nuller %}
rank -> [a, k, q, j, t, A, K, Q, J, T, 2-9]     {% nuller %}

_ -> [\s]:*                                     {% nuller %}