{"id":548,"date":"2017-06-23T11:00:59","date_gmt":"2017-06-23T11:00:59","guid":{"rendered":"http:\/\/www.rangakrish.com\/?p=548"},"modified":"2017-08-10T03:34:58","modified_gmt":"2017-08-10T03:34:58","slug":"definite-clause-grammars-in-lisp-part-3","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2017\/06\/23\/definite-clause-grammars-in-lisp-part-3\/","title":{"rendered":"Definite Clause Grammars in Lisp – Part 3"},"content":{"rendered":"

In today’s post, let us see how we can enhance the grammar representation discussed so far to include both Number<\/strong><\/em> constraint and Parse Tree<\/strong><\/em>.<\/p>\n

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.<\/p>\n

In the earlier two posts, we trivially included the terminal<\/strong><\/em> words in the grammar. This is not practical. In a real application, we would have a lexicon that contains parts of speech and other features of each word, and will supply the same to the parser as and when needed. So if we wish to know if sleeps<\/strong><\/em> is a singular verb, we consult the lexicon and it will say yes<\/strong><\/em>. Building a comprehensive lexicon is very useful in NLP research (of course, quite a challenge) and this is one of the projects I have been working on for a few years now.<\/p>\n

Anyway, for our simple grammar, we will write functions that will interface to the lexicon. In fact, our functions will work with just a few words!<\/p>\n

Here are the POS utility functions that get called during parsing.<\/p>\n

\"POS<\/a>
POS Functions<\/strong><\/figcaption><\/figure>\n

The updated grammar rules are shown here.<\/p>\n

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

If you look at the non-terminals np<\/strong><\/em>, vp<\/strong><\/em>, etc., you will notice that they have two arguments – one for building the parse tree and the other for enforcing number agreement.<\/p>\n

The other point to note is that terminal categories such as pn<\/strong><\/em> and n<\/strong><\/em> call our POS utility functions to check the word category and to get the corresponding number<\/strong><\/em>.<\/p>\n

The beauty of unification<\/strong><\/em> is apparent here. For example, while parsing np<\/strong><\/em>, its number<\/strong><\/em> is determined by the constituent n<\/strong><\/em> or pn<\/strong><\/em> and this eventually gets passed on to the vp<\/strong><\/em>, where the choice of a verb (iv<\/strong><\/em> or tv<\/strong><\/em>) is constrained by the number transmitted by np<\/strong><\/em>.<\/p>\n

Let us try a few sample sentences.<\/p>\n

CP-USER 2 > (parse-grammar ‘s ‘(he sleeps))<\/span><\/p>\n

(S (NP (PN HE)) (VP (IV SLEEPS)))<\/span><\/p>\n

CP-USER 3 > (parse-grammar ‘s ‘(they sleep))<\/span><\/p>\n

(S (NP (PN THEY)) (VP (IV SLEEP)))<\/span><\/p>\n

CP-USER 4 > (parse-grammar ‘s ‘(they write books))<\/span><\/p>\n

(S (NP (PN THEY)) (VP (TV WRITE) (NP (N BOOKS))))<\/span><\/p>\n

Looks like number<\/strong><\/em> agreement is correctly enforced. Let us confirm by giving some invalid sentences.<\/p>\n

CP-USER 5 > (parse-grammar ‘s ‘(he sleep))<\/span><\/p>\n

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

CP-USER 6 > (parse-grammar ‘s ‘(they sleeps))<\/span><\/p>\n

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

Let us see if transitive<\/strong><\/em> vs intransitive<\/strong><\/em> verb rule is enforced.<\/p>\n

CP-USER 7 > (parse-grammar ‘s ‘(he writes))<\/span><\/p>\n

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

Since writes<\/strong><\/em> is a transitive<\/strong><\/em> verb, our grammar expects a np<\/strong><\/em> to follow it. In the above case, none follows, hence the sentence is rejected. Quite correct!<\/p>\n

So that is it! We now know how to implement grammars that take constraints and also build the parse tree along the way! How can we improve the above DCG grammar expressed in Common Prolog of LispWorks?<\/p>\n

Obviously, we can enhance the grammar to include more variations, but the more striking possibility is to be able to simplify the syntax<\/strong><\/em> of the grammar itself! If you look carefully at each grammar rule, you will see a lot of redundancy<\/strong><\/em>. Much of this can be eliminated if we choose a simpler syntax and translate that to this syntax. Since this is Lisp, anything is indeed possible! I have such a working version and if time permits, I will share that implementation in a future post.<\/p>\n

You can download the Lisp source code for the above grammar here<\/a>.<\/p>\n

That is it for now. Bye.<\/p>\n","protected":false},"excerpt":{"rendered":"

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. In the earlier two posts, […]<\/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_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_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,19,74,102],"class_list":["post-548","post","type-post","status-publish","format-standard","hentry","category-lisp","category-natural-language-processing","category-programming","tag-dcg","tag-definite-clause-grammar","tag-lisp","tag-nlp","tag-parsing"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-8Q","jetpack-related-posts":[{"id":534,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/05\/22\/definite-clause-grammars-dcg-in-lisp\/","url_meta":{"origin":548,"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":2832,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/06\/12\/definite-clause-grammars-in-lisp-part-4\/","url_meta":{"origin":548,"position":1},"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":548,"position":2},"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":2366,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/03\/28\/implementing-ilexicon-using-litedb\/","url_meta":{"origin":548,"position":3},"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":[]},{"id":575,"url":"https:\/\/www.rangakrish.com\/index.php\/2017\/08\/06\/text-generation-using-ilanggen-framework\/","url_meta":{"origin":548,"position":4},"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":[]},{"id":1792,"url":"https:\/\/www.rangakrish.com\/index.php\/2019\/11\/23\/using-augmented-transition-networks-atn-for-information-extraction\/","url_meta":{"origin":548,"position":5},"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":[]}],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/548","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=548"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/548\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=548"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=548"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=548"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}