Skip to content

Earley Parser handles epsilon productions incorrectly #169

@rasc00001

Description

@rasc00001

When parsing strings that contain the result of epsilon productions with EarleyParser,
the parsed subtree containing the nullable nonterminal has an empty children list,
as if the nonterminal was a terminal.
(see description of Derivation Trees at https://www.fuzzingbook.org/html/GrammarFuzzer.html#Derivation-Trees)

To Reproduce
Steps to reproduce the behavior:
Run

from fuzzingbook.Parser import EarleyParser
next(EarleyParser({"<start>": [""]}).parse(""))

The return value is

('<start>', [])

Expected behavior
The return value is expected to be

('<start>', [('', [])])  

Additional context
This issue might cause #153

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions