{"id":2832,"date":"2022-06-12T09:29:15","date_gmt":"2022-06-12T03:59:15","guid":{"rendered":"https:\/\/www.rangakrish.com\/?p=2832"},"modified":"2022-06-12T09:29:15","modified_gmt":"2022-06-12T03:59:15","slug":"definite-clause-grammars-in-lisp-part-4","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2022\/06\/12\/definite-clause-grammars-in-lisp-part-4\/","title":{"rendered":"Definite Clause Grammars in Lisp – Part 4"},"content":{"rendered":"

In a series of articles<\/strong><\/em><\/a>\u00a0written earlier, I had shown how it is possible to model Definite Clause Grammars<\/strong><\/em> (DCG<\/strong><\/em>) in LispWorks Lisp (Enterprise Edition)<\/strong><\/em>. We use defgrammar<\/strong><\/em>\u00a0in Common Prolog<\/strong><\/em> (available as part of KnowledgeWorks<\/strong><\/em><\/a> package) to define our grammar rules.<\/p>\n

Here is a toy English grammar represented using defgrammar<\/strong><\/em>:<\/p>\n

\"DCG<\/a>
DCG Using Defgrammar<\/strong><\/figcaption><\/figure>\n

This corresponds to the following Prolog DCG<\/strong><\/em> grammar:<\/p>\n

\"Corresponding<\/a>
Corresponding Prolog DCG<\/strong><\/figcaption><\/figure>\n

You will notice that the Prolog<\/strong><\/em> syntax is less verbose and hence more expressive than the defgrammar<\/strong><\/em>\u00a0version (you can ignore the minor difference in the naming of non-terminal names).<\/span><\/p>\n

We need not lose heart because Lisp<\/strong><\/em> is a “programmable programming language”<\/strong><\/em>, and we can improve the existing syntax to suite our preference!<\/p>\n

Here is the improved<\/strong><\/em>\u00a0version of the same defgrammar<\/strong><\/em>:<\/p>\n

\"Simplified<\/a>
Simplified Defgrammar<\/strong><\/figcaption><\/figure>\n

If you look at the grammar carefully, you will notice that it does not\u00a0explicitly<\/strong><\/em>\u00a0build the\u00a0parse tree<\/strong><\/em>, whereas the other two versions do! The tree building happens inside the generated defgrammar<\/strong><\/em>\u00a0code.<\/p>\n

So, what is the trick<\/strong><\/em>? The trick is that we write suitable macros<\/strong><\/em>\u00a0to convert our simpler syntax to the corresponding defgrammar<\/strong><\/em>\u00a0version:<\/p>\n

\"The<\/a>
The Core Macros<\/strong><\/figcaption><\/figure>\n

The above shows the core logic involved in the syntax transformation. The full source code is available here<\/strong><\/em><\/a>.<\/p>\n

Let us now check the grammar with some sample sentence fragments:<\/p>\n

\"Sample<\/a>
Sample Session<\/strong><\/figcaption><\/figure>\n

Here is a sample session in Sicstus Prolog 4.7.0<\/strong><\/em><\/a> for the Prolog<\/strong> <\/em>DCG:<\/p>\n

\"Sample<\/a>
Sample Session – Prolog<\/strong><\/figcaption><\/figure>\n

You can see that the outputs match.<\/p>\n

Here comes an important question: If I have to implement an NLP<\/strong><\/em> parser in DCG<\/strong><\/em>, is it better to do this in Prolog<\/strong><\/em> directly, or use defgrammar<\/strong><\/em> (perhaps using the tricks shown here) in Lisp<\/strong><\/em>?<\/p>\n

I guess the answer is not straightforward. If you are a Lisp<\/strong><\/em> programmer (using LispWorks<\/strong><\/em>) and you are not comfortable with Prolog<\/strong><\/em>, then defgrammar<\/strong><\/em> is probably the natural approach. The other advantage is that you can easily integrate this with other Lisp<\/strong><\/em> code, if needed. In my case, I would prefer using Prolog<\/strong><\/em> directly (especially Sicstus Prolog<\/strong><\/em>) since I can get better performance on large grammars.\u00a0<\/span><\/p>\n

This article concludes the series on using DCG<\/strong><\/em> in Lisp<\/strong><\/em>. Hope you find this series useful.<\/p>\n

The Lisp<\/strong><\/em> source is available here<\/strong><\/em><\/a>\u00a0.<\/p>\n

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

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 corresponds to the following Prolog […]<\/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_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},"jetpack_post_was_ever_published":false},"categories":[18,107,17,147],"tags":[100,101,19,148],"class_list":["post-2832","post","type-post","status-publish","format-standard","hentry","category-lisp","category-natural-language-processing","category-programming","category-prolog","tag-dcg","tag-definite-clause-grammar","tag-lisp","tag-prolog"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-JG","jetpack-related-posts":[{"id":534,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/05\/22\/definite-clause-grammars-dcg-in-lisp\/","url_meta":{"origin":2832,"position":0},"title":"Definite Clause Grammars (DCG) in Lisp","author":"admin","date":"May 22, 2017","format":false,"excerpt":"Definite Clause Grammars (DCG) are an elegant formalism for specifying context free grammars, and part of their popularity is due to their support in the Prolog language. Most books on Natural Language processing usually include a brief coverage of DCGs, even though Natural languages are not context-free. Because of the\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"DCG Grammar","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/05\/DCG-Grammar.png?resize=525%2C300 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":2832,"position":1},"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":548,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/06\/23\/definite-clause-grammars-in-lisp-part-3\/","url_meta":{"origin":2832,"position":2},"title":"Definite Clause Grammars in Lisp – Part 3","author":"admin","date":"June 23, 2017","format":false,"excerpt":"In today's post, let us see how we can enhance the grammar representation discussed so far to include both Number constraint and Parse Tree. Fortunately, this turns out to be quite straightforward. Just as we do in Prolog, we need to include additional parameters, as needed, to each grammar rule.\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"POS Functions","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/POS-Function.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/POS-Function.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2017\/06\/POS-Function.png?resize=525%2C300 1.5x"},"classes":[]},{"id":1659,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/08\/04\/generating-poetry-in-prolog\/","url_meta":{"origin":2832,"position":3},"title":"Generating Poetry in Prolog","author":"admin","date":"August 4, 2019","format":false,"excerpt":"In an earlier article, I showed how we can generate poetry (with limitations, of course!) using my iLangGen framework. That implementation (in Lisp) made use of iLexicon, a large dictionary of English words, which I have been building over the years. I subsequently ported iLexicon to Prolog and it now\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":"Generation Logic","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/08\/Code3.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/08\/Code3.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/08\/Code3.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":1817,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/12\/08\/using-definite-clause-grammars-dcg-for-information-extraction\/","url_meta":{"origin":2832,"position":4},"title":"Using Definite Clause Grammars (DCG) for Information Extraction","author":"admin","date":"December 8, 2019","format":false,"excerpt":"In the previous article, I showed how we can use ATNs for extracting key information from natural language text. I also pointed out in that article that Definite Clause Grammars (DCG) are a more compact formalism for doing this. That will be the focus of today's article. For a nice\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":"Processing the Text","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/12\/Processing-file-code.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/12\/Processing-file-code.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2019\/12\/Processing-file-code.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":2366,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/03\/28\/implementing-ilexicon-using-litedb\/","url_meta":{"origin":2832,"position":5},"title":"Implementing iLexicon using LiteDB","author":"admin","date":"March 28, 2021","format":false,"excerpt":"iLexicon is an \"intelligent\" dictionary that can be used to build Natural Language applications. I have two implementations, one in Lisp and another in Prolog. Both implementations are memory-based, in order to speed up performance. I have written several articles referencing it, for example see this. \u00a0 LiteDB is a\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":"Sample Commands","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/03\/Session1.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/2832","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=2832"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/2832\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=2832"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=2832"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=2832"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}