Bug: RuntimeError: Earley should not generate multiple start symbol items! Please report this bug.

[wstevick]

Describe the bug

Upon trying to test my toy language, I was given the error "RuntimeError: Earley should not generate multiple start symbol items! Please report this bug."

To Reproduce
"orca.lark"

start: (declaration _NL)+ declaration?

?declaration: function

function: "func" NAME arg_list ["->" type] block

arg_list: "(" _commasep{arg}? ")"
arg: NAME [":" type]

block: "{" (statement _NL)* statement? "}"

?statement: expr
          | assign
          | block
          | if
          | for
          | while

assign: "let" NAME "=" conditional_expr -> let
      | "const" NAME "=" conditional_expr -> const

if: "if" expr block _NL? elseif* else?
elseif: "else" "if" expr block _NL?
else: "else" block

for: "for" [expr] ";" [expr] ";" [expr] block

while: "while" expr block


// operator precedence stuff
?assignable: NAME
           | call_expr "." (NAME | INT)

INC: "++"
DEC: "--"

?atom: assignable
     | DEC assignable -> pre_dec_expr
     | assignable DEC -> post_dec_expr
     | INT
     | FLOAT
     | "(" expr ")"
     | "func" arg_list ["->" type] block _NL? -> lambda_expr

?call_expr: atom
          | call_expr "(" _commasep{expr}? ")"

?pow_expr: call_expr
         | call_expr "**" pow_expr

?unary_expr: pow_expr
           | "-" pow_expr -> neg_expr
           | "!" pow_expr -> not_expr

?mult_expr: unary_expr
          | mult_expr "*" unary_expr
          | mult_expr "/" unary_expr -> div_expr
          | mult_expr "%" unary_expr -> mod_expr

?add_expr: mult_expr
         | add_expr "+" mult_expr
         | add_expr "-" mult_expr -> sub_expr

?shift_expr: add_expr
           | shift_expr "<<" add_expr -> leftshift_expr
           | shift_expr ">>" add_expr -> rightshift_expr

?bit_and_expr: shift_expr
             | bit_and_expr "&" shift_expr

?bit_xor_expr: bit_and_expr
             | bit_xor_expr "^" bit_and_expr

?bit_or_expr: bit_xor_expr
            | bit_or_expr "|" bit_xor_expr

?comp_expr: _separated{bit_or_expr, COMP_OP}
COMP_OP: "==" | "!=" | ">" | "<" | ">=" | "<="

?logical_and_expr: comp_expr
                 | logical_and_expr "&&" comp_expr

?logical_or_expr: logical_and_expr
                | logical_or_expr "||" logical_and_expr

?conditional_expr: logical_or_expr
                 | logical_or_expr "?" conditional_expr ":" conditional_expr

?expr: conditional_expr
     | assignable ASSIGN_OP expr -> assign_expr

ASSIGN_OP: ["**"
          | "*" | "/" | "%"
          | "+" | "-"
          | "<<" | ">>"
          | "&" | "^" | "|"
          | "&&" | "||"] "="

fqn: NAME ("." (NAME|INT))*
type: fqn

_separated{x, sep}: x (sep x)*
_commasep{x}: x ("," x)* ","?

_NL.1: (/\r?\n/ WS_INLINE*)+

// a name is a letter, followed by 0 or more letters or numbers,
// but not any keyword
NAME: /\b(?!(func|if|else|for|while|let|const)\b)[a-zA-Z][a-zA-Z0-9]*\b/

%import common (INT, WS_INLINE, FLOAT)

%import common (WS, C_COMMENT, CPP_COMMENT)
%ignore WS
%ignore C_COMMENT
%ignore CPP_COMMENT

"main.py"

import logging

from lark import Lark, logger

logger.setLevel(logging.DEBUG)


orca_parser = Lark.open(
    "orca.lark",
    rel_to=__file__,
    debug=True,
    #parser="lalr",
    #lexer="contextual",
)

with open("t.orca") as f:
    print(orca_parser.parse(f.read()).pretty())

"t.orca"

func f(functy: t.x.0) {
    t(func (a, b) -> t {}
    )
    // one comment
    while a {
        /* another comment */
        let x = d
        const y = b
    }


    if 0.3e8 {}
    else if 14 {}
    else {
        for a; 0; 8.2 {}
    }
    if a {
        y
    } else if b {
        z
    } else {


    }
    if elsey {}}

func other() -> c {}

func c() {
    c.3.x = 4
}

"pyproject.toml"

[project]
name = "orca"
version = "0.1.0"
description = "Add your description here"
readme = "README.md"
requires-python = ">=3.13"
dependencies = [
    "lark[interegular,interregular]>=1.3.1",
]

[dependency-groups]
dev = [
    "python-lsp-ruff>=2.3.1",
]

Output

Unused terminals: [Token('TERMINAL', 'WS_INLINE'), 'INC']
Traceback (most recent call last):
  File "/home/finally/orca/main.py", line 17, in <module>
    print(orca_parser.parse(f.read()).pretty())
          ~~~~~~~~~~~~~~~~~^^^^^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/lark.py", line 677, in parse
    return self.parser.parse(text, start=start, on_error=on_error)
           ~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/parser_frontends.py", line 131, in parse
    return self.parser.parse(stream, chosen_start, **kw)
           ~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/parsers/earley.py", line 290, in parse
    raise RuntimeError('Earley should not generate multiple start symbol items! Please report this bug.')
RuntimeError: Earley should not generate multiple start symbol items! Please report this bug.

[erezsh]

Hello, thanks for reporting.

Can you please verify it still happens with the master version? (i.e. latest commit, not latest version)

[wstevick]

Now I have

Cannot find dependency 'pydot', will not generate sppf debug image
Traceback (most recent call last):
  File "/home/finally/orca/main.py", line 17, in <module>
    print(orca_parser.parse(f.read()).pretty())
          ~~~~~~~~~~~~~~~~~^^^^^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/lark.py", line 737, in parse
    return self.parser.parse(text, start=start, on_error=on_error)
           ~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/parser_frontends.py", line 131, in parse
    return self.parser.parse(stream, chosen_start, **kw)
           ~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/parsers/earley.py", line 309, in parse
    return transformer.transform(solution)
           ~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/parsers/earley_forest.py", line 392, in transform
    self.visit(root)
    ~~~~~~~~~~^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/parsers/earley_forest.py", line 528, in visit
    self.prioritizer.visit(root)
    ~~~~~~~~~~~~~~~~~~~~~~^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/parsers/earley_forest.py", line 335, in visit
    vino(current)
    ~~~~^^^^^^^^^
  File "/home/finally/orca/.venv/lib/python3.13/site-packages/lark/parsers/earley_forest.py", line 478, in visit_symbol_node_out
    node.priority = max(child.priority for child in node.children)
                    ~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ValueError: max() iterable argument is empty

BTW I know the grammar has an error which I've since fixed. The questions now is just whether Lark's handling it in the way you want.

[erezsh]

I see. So you're saying that when the grammar is correct, everything works fine?

[wstevick]

With:

Just tested with correct (lalr) grammar, and I still get the same error. Originally the grammar is supposed to be used with LALR - I switched to earley to debug the reduce/reduce problem I was getting. But it seems I ran into a problem with Earley and a lalr-compatible grammar

[erezsh]

@wstevick Can you please check if this PR solves your issue?

#1601

(you can pip install the PR directly)

[wstevick]

Fixed.