Mon Nov 9 08:21:38 CET 2009
LL and LR parsing vs. binary protocol design
Both LL(k) and LR(k) have finite lookahead and no backtracking. This
means that the parsing decisions need to be made based only on the
next k input symbols.
LL is top-down (recursive descent) and LR is bottom-up (recursive
ascent). In their simplest forms (only one state?) they correspond to
a prefix and a postfix language. This is useful for building
serialization protocols optimized for minimal parser complexity,
i.e. to run in hardware or small 8-bit uCs.
I've determined 4 important design decisions for a protocol:
- delimited vs. prefixed token stream
- representing quotation + construction tokens
- bottom-up (postfix) or top-down (prefix) structure
- constructor arity tagging