tailieunhanh - Lecture Programming languages (2/e): Chapter 15c - Tucker, Noonan
Logic (declarative) programming emerged as a distinct paradigm in the 1970s. Logic programming is distinct from the other paradigms because it requires the programmer to declare the goals of the computation, rather than the detailed algorithm by which these goals can be achieved. Chapter 15c presents the following content: Natural language processing, semantics of clite, eight queens problem. | Programming Languages 2nd edition Tucker and Noonan Chapter 15 Logic Programming Q: How many legs does a dog have if you call its tail a leg? A: Four. Calling a tail a leg doesn’t make it one. Abraham Lincoln Contents Logic and Horn Clauses Logic Programming in Prolog Prolog Program Elements Practical Aspects of Prolog Prolog Examples Symbolic Differentiation Solving Word Puzzles Natural Language Processing Semantics of Clite 5 Eight Queens Problem Natural Language Processing BNF can define natural language (., English) syntax. This was the original purpose of BNF when it was invented by Chomsky in 1957. A Prolog program can model a BNF grammar. This was an original purpose of Prolog when it was designed in the 1970s. A Prolog list can model a sentence. ., [the, giraffe, dreams] So running the program can parse a sentence. NLP Example Consider the following BNF grammar and parse tree: s np vp np det n vp tv np iv det the n giraffe apple iv dreams tv eats Here, s, np, vp, det, n , iv, and tv denote “sentence,” “noun phrase,” “verb phrase,” “determiner,” “noun,” “intransitive verb,” and “transitive verb.” Prolog Encoding (naïve version) s(X, Y) :- np(X, U), vp(U, Y). np(X, Y) :- det(X, U), n(U, Y). vp(X, Y) :- iv(X, Y). vp(X, Y) :- tv(X, U), np(U, Y). det([the | Y], Y). n([giraffe | Y], Y). n([apple | Y], Y). iv([dreams | Y], Y). tv([eats | Y], Y). The first rule reads, “list X is a sentence leaving tail Y if X is a noun phrase leaving tail U and U is a verb phrase leaving tail Y.” Example Trace ?- s([the, giraffe, dreams],[]). Call: ( 7) s([the, giraffe dreams], []) ? Call: ( 8) np([the, giraffe, dreams], _L131) ? Call: ( 9) det([the, giraffe, dreams], _L143) ? Exit: ( 9) det([the, giraffe, dreams], [giraffe, dreams]) ? Call: ( 9) n([giraffe, dreams], _L131) ? Exit: ( 9) n([giraffe, dreams], [dreams]) ? Exit: ( 8) np([the, giraffe, dreams], [dreams]) ? Call: ( 8) . | Programming Languages 2nd edition Tucker and Noonan Chapter 15 Logic Programming Q: How many legs does a dog have if you call its tail a leg? A: Four. Calling a tail a leg doesn’t make it one. Abraham Lincoln Contents Logic and Horn Clauses Logic Programming in Prolog Prolog Program Elements Practical Aspects of Prolog Prolog Examples Symbolic Differentiation Solving Word Puzzles Natural Language Processing Semantics of Clite 5 Eight Queens Problem Natural Language Processing BNF can define natural language (., English) syntax. This was the original purpose of BNF when it was invented by Chomsky in 1957. A Prolog program can model a BNF grammar. This was an original purpose of Prolog when it was designed in the 1970s. A Prolog list can model a sentence. ., [the, giraffe, dreams] So running the program can parse a sentence. NLP Example Consider the following BNF grammar and parse tree: s np vp np det n vp
đang nạp các trang xem trước