Farkle fails to parse input when grammar contains certain possibly empty non-terminal

[bavibi]

Describe the bug

Grammar can contain optional non-terminal, but Farkle will treat it as required and fail to match empty string.

To Reproduce

Run following F# script:

#r "nuget: Farkle, 6.5.1"
open Farkle
open Farkle.Builder

let A = literal "a"
let B = literal "b"
let C = literal "c"
let D = literal "d"
let E = literal "e"

let opt_D = "opt_D" ||= [
    empty =% "empty D"
    !% D =% "D"
]

let opt_CD = "opt_CD" ||= [
    !% C =% "C"
    !@ opt_D |> asIs
]

let opt_B = "opt_B" ||= [
    empty =% "empty B"
    !% B =% "B"
]

let root = "root" ||= [
    !% A .>>. opt_B .>>. opt_CD .>> E => (fun x y -> (x, y))
]

let parser = RuntimeFarkle.build root

let showResult (input: string) =
    printfn $"Result for '{input}'"
    match RuntimeFarkle.parseString parser input with
    | Ok b -> printfn $"Success: got {b}"
    | Error err -> printfn $"Error: {err}"
    printfn ""

showResult "ae"
showResult "abe"
showResult "ace"
showResult "ade"
showResult "abce"
showResult "abde"

The script outputs:

Result for 'ae'
Error: (1, 2) Found e while expecting one of the following tokens: b, c, d.

Result for 'abe'
Error: (1, 3) Found e while expecting one of the following tokens: c, d.

Result for 'ace'
Success: got (empty B, C)

Result for 'ade'
Success: got (empty B, D)

Result for 'abce'
Success: got (B, C)

Result for 'abde'
Success: got (B, D)

Expected behavior

Farkle should successfully parse strings 'ae' and 'abe'.

[teo-tsirpanis]

There appears to be a bug in the builder. Upon inspection of the built grammar, State 2 does not have an action for e.

I could not reproduce this in the in-development Farkle 7 whose builder is rewritten and uses a different algorithm, where all six cases parse successfully. I checked that you can work around it in Farkle 6 by inlining opt_D inside opt_CD like this:

let opt_CD = "opt_CD" ||= [
    empty =% "empty D"
    !% C =% "C"
    !% D =% "D"
]

Considering that the development of Farkle 7's main library is nearing completion and a preview release is likely to release by the end of this year, I don't think it's worth the effort to investigate and service a fix.

Let me know if you have any further questions.

[teo-tsirpanis]

Fixed in version 6.5.2.