gll icon indicating copy to clipboard operation
gll copied to clipboard

Bidirectional parsing

Open eddyb opened this issue 7 years ago • 0 comments

Right now only "forward" parsing is supported but some infrastructure exists for "backward" parsing. Everything is the same except:

  • A B changes order
  • lookahead turns into lookbehind and vice-versa
  • cons lists become snoc lists
    • can probably avoid doing this, at a performance cost
    • can't use iterator API for a snoc list (since only "reverse" iteration exists)
  • GSS ranges would be input_start..rule_end instead of rule_start..input_end

If we use the same SPPF nodes (keeping e.g. cons lists), then we can reuse SPPF nodes between forward and backward parsing, but the GSS would still have to be separate.

N.B.: "LTR"/"RTL" would be convenient terms but as per https://github.com/rust-lang/rust/issues/30459 they're incorrect.

eddyb avatar Aug 21 '18 19:08 eddyb