{"id":534,"date":"2017-05-22T13:14:19","date_gmt":"2017-05-22T13:14:19","guid":{"rendered":"http:\/\/www.rangakrish.com\/?p=534"},"modified":"2017-08-10T03:34:32","modified_gmt":"2017-08-10T03:34:32","slug":"definite-clause-grammars-dcg-in-lisp","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2017\/05\/22\/definite-clause-grammars-dcg-in-lisp\/","title":{"rendered":"Definite Clause Grammars (DCG) in Lisp"},"content":{"rendered":"

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 ability to attach arbitrary actions on the RHS of the grammar, DCGs can do more than most context-free parsers.<\/p>\n

As readers of my blogs know, I am a great fan of Lisp. The good news is that LispWorks Enterprise Edition comes with an add-on package called KnowledgeWorks<\/strong><\/em><\/a>\u00a0that facilitates the building of complex knowledge-based systems. One component of this package is a Prolog engine implemented in Lisp. This engine even supports DCG! That means I can build language recognizers using DCG in Lisp. What more could one ask?<\/p>\n

In today\u2019s blog, I will show a toy DCG grammar for recognizing simple English sentences. If you are interested in learning more about DCG in Prolog, the following books might help:<\/p>\n

    \n
  1. Clive Mathews, An Introduction to Natural Language Processing Through Prolog, Addison Wesley Longman, 1998.<\/strong><\/li>\n
  2. Michael A. Covington, Natural Language Processing for Prolog programmers, Prentice Hall, 1994.<\/strong><\/li>\n
  3. Pierre M.Nugues, Language processing with Perl and Prolog: Theories, Implementation, and Application (2nd<\/sup> Edition), Springer Verlag, 2014. \u00a0<\/strong><\/li>\n<\/ol>\n

    Let us look at one grammar rule:<\/p>\n

    (defgrammar det<\/span><\/p>\n

    \u00a0 ((det (det ?Word)) ?Word ((is-det? ?Word) t) ))<\/span><\/p>\n

    This says, in essence, that if the input word satisfies the function is-det?<\/strong><\/em>, then it is a determiner. In addition, it builds a parse structure (det <input-word>)<\/strong><\/em> and is associated with the non-terminal det<\/strong><\/em>.<\/p>\n

    The function is-det?<\/strong><\/em> takes an argument and returns t (True)<\/strong><\/em> if it is a determiner. In this example, I am trivially checking for membership in a simple list, but in an actual implementation, this has to interface to a huge lexicon of many thousand words, containing detailed description (including semantic annotations) of each word.<\/p>\n

    Here is a slightly more interesting rule:<\/p>\n

    (defgrammar np<\/span><\/p>\n

    \u00a0 ((np (np ?N)) (noun ?N))<\/span><\/p>\n

    \u00a0 ((np (np ?D ?N)) (det ?D) (noun ?N))<\/span><\/p>\n

    \u00a0 ((np (np ?D ?A ?N)) (det ?D) (adj ?A) (noun ?N))<\/span>\u00a0)<\/span><\/p>\n

    This says that the non-terminal np<\/strong><\/em> (stands for Noun Phrase<\/strong><\/em>) is any one of the following:<\/p>\n

    NP -> Noun<\/span><\/p>\n

    NP -> Det Noun<\/span><\/p>\n

    NP -> Det Adj Noun<\/span><\/p>\n

    When the NP is satisfied by the input, it results in an appropriate parse tree.<\/p>\n

    The main entry point for the grammar is s<\/strong><\/em>, which defines the complete\u00a0sentence. In our case, the rule is quite simple:<\/p>\n

    S -> NP VP<\/span><\/p>\n

    That is, a sentence<\/strong><\/em> is defined as a noun phrase<\/strong><\/em> followed by a verb phrase<\/strong><\/em>.<\/p>\n

    The full grammar is shown\u00a0in the following image:<\/p>\n

    \"DCG<\/a>
    DCG Grammar<\/strong><\/figcaption><\/figure>\n

    Let us try to parse some sentences:<\/p>\n

    CP-USER 2 > (parse-grammar ‘s ‘(the big dog chased the small cat))<\/span><\/p>\n

    (S (NP (DET THE) (ADJ BIG) (NOUN DOG)) (VP (VERB CHASED) (NP (DET THE) (ADJ SMALL) (NOUN CAT))))<\/span><\/p>\n

    The sentence the big dog chased the small cat<\/strong><\/em> is correct as per our grammar and the corresponding parse tree is returned.<\/p>\n

    CP-USER 3> (parse-grammar ‘s ‘(mohan saw mary))<\/span><\/p>\n

    (S (NP (NOUN MOHAN)) (VP (VERB SAW) (NP (NOUN MARY))))<\/span><\/p>\n

    This is also a valid sentence. You can see the difference between these two sentences in terms of Noun Phrase<\/strong><\/em>. The first sentence uses Det Adj Noun<\/strong><\/em> combination, whereas the second sentences just uses Noun<\/strong><\/em>.<\/p>\n

    Quite obviously, this is a toy grammar, and has been created just to show the DCG formalism in Lisp. English grammar is quite complex with many constraints coming into play, for example number agreement, semantic correctness, and so on. I will try to cover some of these topics in future posts.<\/p>\n

    For now, you can download<\/a> the Lisp version of my grammar (remember this requires LispWorks Enterprise Edition).<\/p>\n","protected":false},"excerpt":{"rendered":"

    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 ability to attach arbitrary actions […]<\/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":false,"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],"tags":[100,101,99],"class_list":["post-534","post","type-post","status-publish","format-standard","hentry","category-lisp","category-natural-language-processing","category-programming","tag-dcg","tag-definite-clause-grammar","tag-lispworks"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-8C","jetpack-related-posts":[{"id":2832,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/06\/12\/definite-clause-grammars-in-lisp-part-4\/","url_meta":{"origin":534,"position":0},"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":541,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/06\/04\/definite-clause-grammars-in-lisp-part-2\/","url_meta":{"origin":534,"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":1659,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/08\/04\/generating-poetry-in-prolog\/","url_meta":{"origin":534,"position":2},"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":534,"position":3},"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":548,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/06\/23\/definite-clause-grammars-in-lisp-part-3\/","url_meta":{"origin":534,"position":4},"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":2922,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/10\/06\/why-learn-prolog\/","url_meta":{"origin":534,"position":5},"title":"Why Learn Prolog?","author":"admin","date":"October 6, 2022","format":false,"excerpt":"There are several programming languages in use today and a simple google search will throw up interesting recommendations of a subset of these languages to learn, usually based on popularity ranking. As is expected, the popularity of a programming language varies over time and hence a language that was in\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/www.rangakrish.com\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/534","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=534"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/534\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=534"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=534"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=534"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}