{"uid":"cap_y2Xyl1siEhHxMBZmlRGAb","slug":"earley-cfg-nullable-left-recursive-packed-parse-forest-82889136","name":"Earley CFG Nullable Left-Recursive Packed Parse Forest","description":"Recover recognition and the complete finite or cyclic packed parse forest for a supplied word and nullable/left-recursive context-free grammar, rather than LL1 prediction or language-finiteness checks.","url":"https://detect.halowerk.com/v1/F-TD2000-DATASTRUCTURES-10/earley-cfg-nullable-leftrecursive-packed-parse-forest?utm_source=zero.xyz","method":"POST","headers":{},"bodySchema":{"type":"object","properties":{"artifact":{"type":"object","$defs":{"json":{"anyOf":[{"type":"null"},{"type":"boolean"},{"type":"number"},{"type":"string","maxLength":6000},{"type":"array","items":{"$ref":"#/properties/input/properties/body/properties/artifact/%24defs/json"},"maxItems":512},{"type":"object","maxProperties":128,"additionalProperties":{"$ref":"#/properties/input/properties/body/properties/artifact/%24defs/json"}}]}},"required":["earleyForest"],"properties":{"earleyForest":{"type":"object","required":["data","claim"],"properties":{"data":{"type":"object","required":["nonterminals","productions","start","word"],"properties":{"word":{"type":"array","items":{"$ref":"#/properties/input/properties/body/properties/artifact/%24defs/json"},"maxItems":512},"start":{"type":"number"},"productions":{"type":"array","items":{"$ref":"#/properties/input/properties/body/properties/artifact/%24defs/json"},"maxItems":512},"nonterminals":{"type":"number"}},"additionalProperties":false},"claim":{"$ref":"#/properties/input/properties/body/properties/artifact/%24defs/json"}},"additionalProperties":false}},"additionalProperties":false}}},"responseSchema":null,"example":null,"exampleRequest":null,"tags":["x402"],"displayCostAmount":"0.003","displayCostAsset":"USDC","priceDynamic":false,"priceHint":null,"priceStatus":"priced","priceSource":"probe","requiresHandshake":false,"reviewCount":0,"rating":{"score":"0.00","successRate":"0.00","reviews":0,"stars":null,"state":"unrated"},"availabilityStatus":"unknown","priceObserved":null,"sessionDeposit":null,"pricing":{"kind":"static","summary":"$0.003/call","primary":{"kind":"static","protocol":"x402","network":"base","amountUsd":"0.003","per":"call","confidence":"exact"},"accepted":[{"kind":"static","protocol":"x402","network":"base","amountUsd":"0.003","per":"call","confidence":"exact"}]},"paymentMethods":[{"uid":"pm_-_3c4pSFkQt7vQ4SxRm4U","protocol":"x402","methodType":"crypto","chain":"base","mode":"charge","costAmount":"0.003","costPer":"request","priority":0,"asset":"0x833589fCD6eDb6E08f4c7C32D4f71b54bdA02913","unit":"request","depositMicros":null,"planRef":null}],"brandName":null,"brandSlug":null,"brandBaseUrl":null,"brandDocsUrl":null,"whatItDoes":"Runs the Earley parsing algorithm on a supplied word and context-free grammar (supporting nullable and left-recursive rules) to recover recognition status and the complete finite packed parse forest.","exampleAgentPrompt":"Parse the word ['a','b','a'] against my left-recursive CFG with 3 nonterminals whose productions are [[0,1,0],[0,2],[1,3]] starting at nonterminal 0, and return the complete packed parse forest and whether the word is recognized.","exampleUseCases":[{"title":"Ambiguous grammar parse forest recovery","prompt":"I have an ambiguous context-free grammar with 4 nonterminals and left-recursive rules, and I want to parse the token sequence ['x','+','x','*','x'] — can you run Earley parsing on it and give me every possible parse tree packed into a forest?"},{"title":"Nullable grammar recognition verification","prompt":"My grammar has nullable nonterminals and I need to verify that the empty word is accepted by it — the grammar has 2 nonterminals, productions [[0],[0,1,0]], starts at 0, and the claim is that it recognizes the empty input. Can you check that claim and return the parse forest?"},{"title":"Left-recursive CFG correctness check","prompt":"I'm building a parser for a left-recursive arithmetic expression grammar with 3 nonterminals and I want to confirm that the string ['num','op','num','op','num'] is in the language — run Earley parsing and show me the full packed parse forest so I can inspect all derivations."}],"resultDescription":"Returns the recognition result (whether the input word is accepted) and the complete finite packed parse forest representing all valid parse derivations of the word under the supplied context-free grammar, including support for ambiguous, nullable, and left-recursive grammars.","failureModes":["Invalid grammar encoding (malformed productions array or out-of-range nonterminal indices) returns an error","Word exceeds maxItems limit of 512 tokens","Productions array exceeds maxItems limit of 512","Malformed claim object causes schema validation failure","Grammar is well-formed but word is not in the language — returns recognition failure with empty forest"],"whenToPreferThis":"Use this endpoint when you need to parse input against a context-free grammar that is nullable, left-recursive, or ambiguous — cases where LL(1), LR, or recursive-descent parsers fail. It is the right choice when you need the complete packed parse forest (all derivations) rather than a single parse tree, and when you cannot restrict your grammar to meet LL or LR constraints.","instructions":null,"reviewSummary":null,"reviewSummaryHighlights":null,"reviewSummaryConcerns":null,"reviewSummaryGeneratedAt":null,"activationCount":0,"lastUsedAt":null,"lastSuccessfullyRanAt":null,"lastHealthCheckAt":"2026-11-04T06:40:55.908Z","isFirstParty":false,"canonicalSlug":"earley-cfg-nullable-left-recursive-packed-parse-forest-82889136"}