Parser of CCG (Combinatory Categorial Grammar) implemented in Haskell
HaskellによるCCG (組み合わせ範疇文法) パーサーの実装
CCGはProfessor. Mark Steedmanによって提案された文法理論の一つである。CFG(文脈自由文法)などに代表される文法との違いは各単語が各カテゴリ(自然言語でいえば形態素など)に加えてセマンティクスを担う部分として型付きラムダ式を保持している点であるといえる。
CCG is a grammatical theory proposed by Professor. Mark Steedman, which differs from grammars such as CFG (Context-Free Grammar) in that each word has a typed lambda expression as its semantics in addition to its category (e.g. part of speech tag in natural language).
例(example):
A/B = function which takes category B at the right side and return category A
A\B = function which takes category B at the left side and return category A
There is several gramatical rules:
Application combinators
">" = forward composition applying function forward (left to right)
"<" = backward composition applying function backward (right to left)
Composition combinators
Type-raising combinators
Substitution
(X/Y)/Z Y/Z => X/Z
(X/Y)\Z Y\Z => X\Z
Y\Z (X\Y)\Z => X\Z
Y/Z (X\Y)/Z => X/Z
retireved from https://qiita.com/q-ikawa/items/cf1bb593185333d88d66
Example of Proof:
In the above steps, we only forcused on category of the each words and (sub-)sentence since we only concentrated on the category of the word and sentences. However by combining semantic lambda function, it is possible to construct the semantic of the whole sentence from semantic of each words.
Example of Proof with semantic:
image from (Lee, K. et al, 2014)
- images and gramatical rules retrieved from https://en.wikipedia.org/wiki/Combinatory_categorial_grammar
- implementation hint retrieved from https://qiita.com/q-ikawa/items/cf1bb593185333d88d66
- implementation hint retrieved from https://qiita.com/q-ikawa/items/233d877b9412bf3b1cd8
- Lee, K., Artzi, Y., Dodge, J., & Zettlemoyer, L. (2014). Context-dependent Semantic Parsing for Time Expressions. ACL.