Parsing Lisp S-Expressions with known schema in C#
- by Drew Noakes
I'm working with a service that provides data as a Lisp-like S-Expression string. This data is arriving thick and fast, and I want to churn through it as quickly as possible, ideally directly on the byte stream (it's only single-byte characters) without any backtracking. These strings can be quite lengthy and I don't want the GC churn of allocating a string for the whole message.
My current implementation uses CoCo/R with a grammar, but it has a few problems. Due to the backtracking, it assigns the whole stream to a string. It's also a bit fiddly for users of my code to change if they have to. I'd rather have a pure C# solution. CoCo/R also does not allow for the reuse of parser/scanner objects, so I have to recreate them for each message.
Conceptually the data stream can be thought of as a sequence of S-Expressions:
(item 1 apple)(item 2 banana)(item 3 chainsaw)
Parsing this sequence would create three objects. The type of each object can be determined by the first value in the list, in the above case "item". The schema/grammar of the incoming stream is well known.
Before I start coding I'd like to know if there are libraries out there that do this already. I'm sure I'm not the first person to have this problem.