{"id":1045,"date":"2018-09-02T11:10:59","date_gmt":"2018-09-02T05:40:59","guid":{"rendered":"http:\/\/www.rangakrish.com\/?p=1045"},"modified":"2018-09-02T13:17:47","modified_gmt":"2018-09-02T07:47:47","slug":"experimenting-with-lisp-based-monadic-parser-combinator","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2018\/09\/02\/experimenting-with-lisp-based-monadic-parser-combinator\/","title":{"rendered":"Experimenting with A Lisp-based Monadic Parser Combinator"},"content":{"rendered":"

Recently I came across a nice Lisp-based Monadic Parser Combinator library<\/a>\u00a0written by Massung. Unlike the traditional parser generators such as ANTLR, this library allows us to embed<\/strong><\/em> the parser in Lisp. Similar libraries are available for other languages too (see, for example ParsecJ<\/strong><\/em><\/a> for Java). The original idea of Monadic parser is from Haskell’s Parsec<\/a> library.<\/p>\n

For a very readable discussion on Functor<\/strong><\/em>, Applicative<\/strong><\/em>, and Monadic<\/strong><\/em> approaches, see this article<\/a>. There is a lot of material on the internet about this topic, so I am not going to get into the basics here.<\/p>\n

The important point to remember about the library (and those that fall in this category) is that it follows a top-down<\/strong><\/em>, recursive-descent<\/strong><\/em> strategy, and hence cannot handle left-recursive<\/strong><\/em> grammars (however, you can rewrite left-recursive grammars by eliminating left recursion).\u00a0<\/span><\/p>\n

The main usage scenario for this type of parsers would be mini embedded Domain Specific Languages<\/strong><\/em> (DSLs). Because of the inherent ability to backtrack, unless used carefully, these parsers can have performance issues. Memoization can help somewhat.<\/p>\n

Massung gives nontrivial parsing\u00a0examples<\/a>\u00a0(JSON, XML, etc.) using this library. I played with the library for a while, and as part of trying to understand it, applied it to build a simple English grammar. In today’s post I would like to discuss my example, and along the way, give you a glimpse of the nice library.\u00a0<\/span><\/p>\n

The main parse function is parse<\/strong><\/em>. It takes two arguments, a parser and a lexer. The task of the lexer is to keep supplying tokens to the parser as long as the input stream is non-empty.<\/p>\n

Take a look at the read-words<\/strong><\/em> function below.\u00a0<\/span><\/p>\n

\"read-words<\/a>
Function: read-words<\/strong><\/figcaption><\/figure>\n

It takes a list argument and returns a function that takes no arguments. This returned function is the lexer that the parser will use. As per the library’s documentation, the lexer must return 2 values, namely, the class<\/strong><\/em> of the in-coming token and the token itself (the latter is optional). However, in my case, because an English word can have multiple parts-of-speech<\/strong><\/em> (for example, sleep<\/strong><\/em> can be a Noun<\/strong><\/em> or Verb<\/strong><\/em> depending on the context), my lexer returns a list<\/strong><\/em> of potential POS categories, not just one.<\/p>\n

Another point worth mentioning is that the lexer could read the input from any source and not just from a list, as is the case in my example. As good design dictates, the parser is shielded from this logic.<\/p>\n

Let us turn our attention to the parser. In a parser combinator, we can build complex parser objects out of simpler ones. Perhaps the simplest parser in the library is .any<\/strong><\/em>. It matches any token and returns its value.<\/p>\n

PARSE-TEST 1 > (parse (.any) (read-words ‘(the dog is sleeping)))<\/span><\/p>\n

THE<\/span><\/p>\n

T<\/span><\/p><\/blockquote>\n

The first value printed is the value of the token and the second value indicates whether the parse was successful or not.<\/p>\n

Another parser is .many1<\/strong><\/em>. It takes a parser as its single argument and applies that parser one or more times. Let us combine .any<\/strong><\/em> and .many1<\/strong><\/em> thus:<\/p>\n

PARSE-TEST 2 > (parse (.many1 (.any)) (read-words ‘(the dog is sleeping)))<\/span><\/p>\n

(THE DOG IS SLEEPING)<\/span><\/p>\n

T<\/span><\/p><\/blockquote>\n

As expected, .many1<\/strong><\/em> causes the parser to consume .any<\/strong><\/em> token as long as<\/strong><\/em> there is input. So the complete input is read and returned by the parser.<\/p>\n

Let us look at a parser combinator I wrote. .is-cat?<\/strong><\/em> takes a POS type as argument and checks whether it matches the POS type of the in-coming token.<\/p>\n

PARSE-TEST 3 > (parse (.is-cat? :pron) (read-words ‘(my cat)))<\/span><\/p>\n

MY<\/span><\/p>\n

T<\/span><\/p><\/blockquote>\n

The above command checks if the first word is of type :pron<\/strong><\/em> (pronoun), and since my<\/strong><\/em> is a pronoun, the parser succeeds. We could also give a list of possible POS types, in which case, the input token must match one of the given POS types.<\/p>\n

PARSE-TEST 4 > (parse (.is-cat? ‘(:verb :noun)) (read-words ‘(sleeping is good)))<\/span><\/p>\n

SLEEPING<\/span><\/p>\n

T<\/span><\/p><\/blockquote>\n

You may be wondering how the lexer knows about the POS category of the different words it encounters. The answer is simple: I have a toy<\/strong><\/em> lexicon for this purpose (shown later).<\/p>\n

By the way, the .is-cat?<\/strong><\/em> parser I have written is slightly different from the library-provided .is<\/strong><\/em>, in that the latter only expects a single token type from the lexer, whereas .is-cat?<\/strong><\/em> permits multiple types (in our case, POS types).<\/p>\n

I wrote another parse combinator, a logical extension of the library-provided .do<\/strong><\/em> parser. Whereas .do<\/strong><\/em> applies multiple parsers in sequence and returns the result of the last<\/strong><\/em> parser, my .seq<\/strong><\/em> parser applies multiple parsers in sequence, collects their individual result and finally returns that as a list. As you will see later, this makes some parsing tasks easy.<\/p>\n

PARSE-TEST 5 > (parse (.seq (.is-cat? ‘(:det)) (.is-cat? ‘(:adj)) (.is-cat? ‘(:noun)))\u00a0<\/span><\/span><\/p>\n

\u00a0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 <\/span>(read-words ‘(the cute cat)))<\/span><\/p>\n

(THE CUTE CAT)<\/span><\/p>\n

T<\/span><\/p><\/blockquote>\n

In the above example, we are trying to match three tokens, a determiner<\/strong><\/em>, an adjective<\/strong><\/em> and a noun<\/strong><\/em>, in that order.<\/p>\n

The library has a macro<\/strong><\/em> called define-parser<\/strong><\/em> that allows us to define a parser combinator by stitching together other parsers. This comes in quite handy.<\/p>\n

With this background, let us turn our attention to the English parser I have put together for this post. To stress, the grammar is extremely simplified in order to illustrate the use of the library. Besides, there is no semantic check or action associated with the grammar.<\/p>\n

Let us start with the Lexicon, which is used by the Lexer:<\/p>\n

\"The<\/a>
The Lexicon<\/strong><\/figcaption><\/figure>\n

For each word, the lexicon associates a list of possible parts of speech corresponding to that word. The get-categories<\/strong><\/em> function, called by the lexer, looks up a word in the lexicon, and if found, returns the corresponding POS list.<\/p>\n

\"Function:<\/a>
Function: get-categories<\/strong><\/figcaption><\/figure>\n

To follow a uniform convention, I use define-parser<\/strong><\/em> to define a parser combinator for each of the POS categories, and use these to build the next level of Non-terminals.<\/p>\n

\"Basic<\/a>
Basic POS Categories<\/strong><\/figcaption><\/figure>\n

I have defined noungroup<\/strong><\/em> to encompass Noun<\/strong><\/em>, Pronoun<\/strong><\/em> and Proper Noun<\/strong><\/em>.<\/p>\n

\"Category:<\/a>
Category: noungroup<\/strong><\/figcaption><\/figure>\n

The .either+<\/strong><\/em> parser combinator is a simple extension of Massung’s built-in .either<\/strong><\/em>, in that it allows more than 2 parsers to be specified. Here is the code for .either+<\/strong><\/em>:<\/p>\n

\"Combinator:<\/a>
Combinator: .either+<\/strong><\/figcaption><\/figure>\n

Here are the other elements of our toy grammar of English:<\/p>\n

\"Other<\/a>
Other Rules<\/strong><\/figcaption><\/figure>\n

.many<\/strong><\/em> invokes a parse combinator zero or more times, while .many1<\/strong><\/em> invokes it one or more times.<\/p>\n

Now that our grammar is defined, let us try to parse some sentences.<\/p>\n

PARSE-TEST 6 > (parse ‘sentence (read-words ‘(my son is studying)))<\/span><\/p>\n

(MY SON IS STUDYING)<\/span><\/p>\n

T<\/span><\/p>\n

PARSE-TEST 7 > (parse ‘sentence (read-words ‘(my son is studying and I am talking to my friend)))<\/span><\/p>\n

(MY SON IS STUDYING AND I AM TALKING TO MY FRIEND)<\/span><\/p>\n

T<\/span><\/p>\n

PARSE-TEST 8 > (parse ‘sentence (read-words ‘(the big dog is playing with the small cute cat)))<\/span><\/p>\n

(THE BIG DOG IS PLAYING WITH THE SMALL CUTE CAT)<\/span><\/p>\n

T<\/span><\/p><\/blockquote>\n

What happens if we give an ungrammatical<\/strong><\/em> sentence? The parse<\/strong><\/em> function, by default, signals parse failure.<\/p>\n

PARSE-TEST 9 > (parse ‘sentence (read-words ‘(all men are mortal)))<\/span><\/p>\n

Error: Parse failure<\/span><\/p>\n

\u00a0 <\/span>1 (abort) Return to top loop level 0.<\/span><\/p>\n

Type :b for backtrace or :c <option number> to proceed.<\/span><\/p>\n

Type :bug-form “<subject>” for a bug report template or “:?” for other options.<\/span><\/p><\/blockquote>\n

We can use the errorp<\/strong><\/em> and error-value<\/strong><\/em> keyword arguments to control this behavior.<\/p>\n

PARSE-TEST 10 > (parse ‘sentence (read-words ‘(all men are mortal)) :errorp nil :error-value nil)<\/span><\/p>\n

NIL<\/span><\/p>\n

NIL<\/span><\/p><\/blockquote>\n

The way we have defined our parser functions, no parse tree is getting built during the parsing process. In a real parsing scenario, however, the parser needs to construct an intermediate representation of the parsed sentences in order to facilitate subsequent analysis. Massung’s library has several functions for keeping track of parsed state at every stage, but in order to keep the discussion simple, I have not used those in this simple example. If time permits, I will discuss this part in a future post.<\/p>\n

You can download the source for my example here<\/a>\u00a0.<\/p>\n

Have a great weekend!<\/p>\n","protected":false},"excerpt":{"rendered":"

Recently I came across a nice Lisp-based Monadic Parser Combinator library\u00a0written by Massung. Unlike the traditional parser generators such as ANTLR, this library allows us to embed the parser in Lisp. Similar libraries are available for other languages too (see, for example ParsecJ for Java). The original idea of Monadic parser is from Haskell’s Parsec […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[18,17],"tags":[152],"class_list":["post-1045","post","type-post","status-publish","format-standard","hentry","category-lisp","category-programming","tag-monadic-parser-combinator"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-gR","jetpack-related-posts":[{"id":1843,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/12\/22\/distributed-computing-with-linda\/","url_meta":{"origin":1045,"position":0},"title":"Distributed Computing with Linda","author":"admin","date":"December 22, 2019","format":false,"excerpt":"Linda, originally proposed by Nicholas Carriero and David Gelernter, is a model of process communication using a small set of well-defined primitives, operating on a tuple space.\u00a0 Interestingly, Sicstus Prolog\u00a0comes with a library that implements Linda (both Server and Client).\u00a0 I played with it a little bit and really enjoyed\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/www.rangakrish.com\/index.php\/category\/programming\/"},"img":{"alt_text":"The Simple Client","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/12\/Simple-client-source.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":1368,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/01\/08\/parsing-text-with-apache-opennlp\/","url_meta":{"origin":1045,"position":1},"title":"Parsing Text with Apache OpenNLP","author":"admin","date":"January 8, 2019","format":false,"excerpt":"In my earlier posts I have written about parsing text using spaCy\u00a0and MeaningCloud's parsing API. For today's article, I decided to take a look at OpenNLP, an open-source ML-based Java toolkit for parsing natural language text. OpenNLP is a fairly mature library and has been around since 2004 (source: Wikipedia).\u2026","rel":"","context":"In "Natural Language Processing"","block_context":{"text":"Natural Language Processing","link":"https:\/\/www.rangakrish.com\/index.php\/category\/natural-language-processing\/"},"img":{"alt_text":"Parse Tree","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/01\/Tree3.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":1792,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/11\/23\/using-augmented-transition-networks-atn-for-information-extraction\/","url_meta":{"origin":1045,"position":2},"title":"Using Augmented Transition Networks (ATN) for Information Extraction","author":"admin","date":"November 23, 2019","format":false,"excerpt":"After Wood\u2019s paper [1], Augmented Transition Networks\u00a0(ATN) became popular in the 1970s, for parsing text. An ATN is a generalized transition network with two major enhancements: Support for recursive transitions, including jumping to other ATNs Performing arbitrary actions when edges are traversed Remembering state through the use of registers See\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"ATN for Modality","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/11\/modality.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/11\/modality.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/11\/modality.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":541,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/06\/04\/definite-clause-grammars-in-lisp-part-2\/","url_meta":{"origin":1045,"position":3},"title":"Definite Clause Grammars in Lisp – Part 2","author":"admin","date":"June 4, 2017","format":false,"excerpt":"In the last post, I showed how we can implement DCGs in LispWorks using the KnowledgeWorks package. The grammar discussed in that post did not take into account subject\/predicate number agreement. This is one of the basic constraints in English grammar. Today I will show how easy it is to\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"Prolog Grammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/Prolog-Grammar.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2832,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/06\/12\/definite-clause-grammars-in-lisp-part-4\/","url_meta":{"origin":1045,"position":4},"title":"Definite Clause Grammars in Lisp – Part 4","author":"admin","date":"June 12, 2022","format":false,"excerpt":"In a series of articles\u00a0written earlier, I had shown how it is possible to model Definite Clause Grammars (DCG) in LispWorks Lisp (Enterprise Edition). We use defgrammar\u00a0in Common Prolog (available as part of KnowledgeWorks package) to define our grammar rules. Here is a toy English grammar represented using defgrammar: This\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"DCG Using Defgrammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/06\/defgrammar-version-300x177.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/06\/defgrammar-version-300x177.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/06\/defgrammar-version-300x177.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":575,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/08\/06\/text-generation-using-ilanggen-framework\/","url_meta":{"origin":1045,"position":5},"title":"Text Generation Using iLangGen Framework","author":"admin","date":"August 6, 2017","format":false,"excerpt":"The two primary areas in Natural Language processing are Natural Language Understanding and Natural Language Generation. The former is concerned with processing and making sense of natural language text, whereas the latter is concerned with synthesizing text, possibly from some deep representation. Both are fascinating and at the same time,\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"iLangGen Grammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/08\/Blog1.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/08\/Blog1.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/08\/Blog1.png?resize=525%2C300 1.5x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/1045","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=1045"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/1045\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=1045"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=1045"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=1045"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}