{"id":5438,"date":"2018-04-01T13:00:08","date_gmt":"2018-04-01T13:00:08","guid":{"rendered":"http:\/\/writeasync.net\/?p=5438"},"modified":"2018-03-27T06:56:45","modified_gmt":"2018-03-27T06:56:45","slug":"basic-complications-parser-combinators","status":"publish","type":"post","link":"http:\/\/writeasync.net\/?p=5438","title":{"rendered":"BASIC complications: parser combinators"},"content":{"rendered":"

When I wrote about creating a GW-BASIC translator<\/a>, I admit I didn’t fully grasp what I was getting myself into. Even a simple language like BASIC has a relatively involved syntax, which makes parsing a challenge (doubly so because I never did take that compilers class in school!). Add to that the difficulty of producing sensible C# code for each construct, using the unbelievably verbose Roslyn API<\/a>. (On this journey, I have become fond of Kirill Osenkov<\/a>‘s Roslyn Quoter<\/a> to automate some of the arcana.)<\/p>\n

My initial throwaway attempt involved a simplistic parsing scheme that started to break down as the expressions became more recursive; e.g. “DIM R$(NR),MA(NR,ND)” involves parsing a comma-separated list of variable and subscript pairs, where the subscripts can themselves be expressions, and also comma-separated (for multi-dimensional arrays). After grinding away, I came up with a strategy which boiled down to using a class to read parsed items from a line of text while keeping track of the unprocessed tail. Doing some more research, I realized I was essentially building a very primitive monadic parser<\/a>. Ultimately it was too primitive, but along the way I found a great tool to crack this parsing problem without reinventing the wheel: Sprache<\/a>.<\/p>\n

Sprache has made it quite easy to code up the parsing rules directly in the target language — no messing with EBNF grammars<\/a> and compiler-compiler<\/a> toolchains. For example, here is a snippet of my code which shows how to define expressions referring to BASIC single-precision and string variables:<\/p>\n

\r\nvar dollar = Parse.Char('$');\r\nvar identifierPrefix = Parse.Identifier(Parse.Letter, Parse.LetterOrDigit);\r\nvar singleIdentifier =\r\n    from prefix in identifierPrefix\r\n    select new BasicIdentifier(prefix, TypeCode.Single);\r\nvar stringIdentifier =\r\n    from prefix in identifierPrefix\r\n    from d in dollar\r\n    select new BasicIdentifier(prefix, TypeCode.String);\r\nvar identifier = stringIdentifier.Or(singleIdentifier);\r\n<\/pre>\n
These fancy LINQ expressions ultimately build up sets of parser combinators<\/a> — functions that produce higher level parsers composed from simpler ones. This should become clearer with a commented version of the code:<\/p>\n
\r\n\/\/ Note: I use the 'var' syntax throughout, but be aware that the data\r\n\/\/ type for each parser is the special Sprache delegate type Parser<T>.\r\n\/\/ Most built-in Sprache parsers are of type Parser<char> or\r\n\/\/ Parser<string>, meaning that they can produce a char or string from\r\n\/\/ a given parsing input (generally a string, wrapped in an interface).\r\n\r\n\/\/ A parser that reads a single literal char '$'.\r\nvar dollar = Parse.Char('$');\r\n\r\n\/\/ Sprache has a built-in Identifier parser where you specify two inner\r\n\/\/ parsers, one for the 'head' and one for the 'tail'. Here we are saying\r\n\/\/ we want a parser that reads one or more characters where the start\r\n\/\/ must be a letter, followed by one or more letters or digits.\r\nvar identifierPrefix = Parse.Identifier(Parse.Letter, Parse.LetterOrDigit);\r\n\r\n\/\/ This is where the fancy LINQ syntax comes in. These "list comprehensions"\r\n\/\/ as they are known allow a fairly readable way to describe a parse\r\n\/\/ sequence.\r\n\/\/\r\n\/\/ Read this as, "produce a parser that first reads an identifier prefix\r\n\/\/ (as above) and returns an instance of my BasicIdentifier class\r\n\/\/ referring to a single-precision variable, accepting the prefix as a\r\n\/\/ string."\r\nvar singleIdentifier =\r\n    from prefix in identifierPrefix\r\n    select new BasicIdentifier(prefix, TypeCode.Single);\r\n\r\n\/\/ This is very much like the above, with an intervening step which reads\r\n\/\/ a literal dollar sign using the 'dollar' parser defined above. The\r\n\/\/ dollar sign denotes a string variable (e.g. "ABC$").\r\nvar stringIdentifier =\r\n    from prefix in identifierPrefix\r\n    from d in dollar\r\n    select new BasicIdentifier(prefix, TypeCode.String);\r\n\r\n\/\/ Finally, we compose the above parsers to produce one that can read\r\n\/\/ any identifier. This one uses the Sprache 'Or' extension method to\r\n\/\/ represent "alternation," i.e. the choice between more than one parser.\r\n\/\/ VERY IMPORTANT: Order matters here! You must always put the parser\r\n\/\/ which reads the longer prefix first. Otherwise, the final parser will\r\n\/\/ not understand that "ABC$" is really a string identifier and not just a\r\n\/\/ single-precision identifier followed by an orphaned '$' char. Think of\r\n\/\/ it as applying the next parser in the list only if the previous one\r\n\/\/ "fails."\r\nvar identifier = stringIdentifier.Or(singleIdentifier);\r\n<\/pre>\n
About the most complicated thing I’ve had to do so far involved recursive rules. In Backus-Naur form, one could write the following to recognize a comma-separated list of zeroes and ones:<\/p>\n
<bit>  ::= \"0\" | \"1\"\r\n<list> ::= <bit> \",\" <list> | <bit><\/pre>\n
The production rule for <list><\/code> is “right recursive” since <list><\/code> itself appears on the right side of its first expansion. (This is the common recursion case, as left recursion<\/a> is generally a ticket to infinite descent<\/a> for most parsers.) Trying to do the same directly in Sprache will lead to trouble since you cannot reference a variable in the declaration and assignment of that same variable. Instead, you would do something like this:<\/p>\n
\r\nvar comma = Parse.Char(',');\r\nvar zero = Parse.Char('0');\r\nvar one = Parse.Char('1');\r\n\r\nvar bit = zero.Or(one);\r\n\r\n\/\/ Read: "Produce a parser that reads one bit, and then reads zero\r\n\/\/ or more occurrences of a comma followed by a bit." The extension\r\n\/\/ method 'Then' handles the "followed by" logic, while 'Many' handles\r\n\/\/ the "zero or more." The final step is to concatenate these terms\r\n\/\/ into a single sequence (see definition of 'Concat' below).\r\nvar list =\r\n    from head in bit\r\n    from rest in comma.Then(_ => bit).Many()\r\n    select Concat(head, rest);\r\n\r\n\/\/ ...\r\nprivate static IEnumerable<T> Concat<T>(T head, IEnumerable<T> rest) =>\r\n    new T[] { head }.Concat(rest);\r\n<\/pre>\n
Sadly, although Sprache has improved my productivity quite a bit, I’m not really that close to finishing my translator. I guess compilers are hard<\/a>, after all.<\/p>\n","protected":false},"excerpt":{"rendered":"
When I wrote about creating a GW-BASIC translator, I admit I didn’t fully grasp what I was getting myself into. Even a simple language like BASIC has a relatively involved syntax, which makes parsing a challenge (doubly so because I… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[91],"tags":[],"class_list":["post-5438","post","type-post","status-publish","format-standard","hentry","category-design"],"_links":{"self":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5438","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5438"}],"version-history":[{"count":5,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5438\/revisions"}],"predecessor-version":[{"id":5443,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5438\/revisions\/5443"}],"wp:attachment":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5438"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5438"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5438"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}