# lisp nilの代わり
NIL = []

# ============================
# grammar
# ============================
Sentence = 'Sentence'
NP = 'NP'
VP = 'VP'
Art = 'Art'
Noun = 'Noun'
Verb = 'Verb'
the = 'the'
a = 'a'
#
man = 'man'
ball = 'ball'
woman = 'woman'
table = 'table'
noun = 'noun'
verb = 'verb'
#
hit = 'hit'
took = 'took'
saw = 'saw'
liked = 'liked'

grammar = [
     [Sentence, '->', [NP, VP]]
    ,[NP, '->', [Art, Noun]]
    ,[VP, '->', [Verb, NP]]
    ,[Art, '->', the]
    ,[Art, '->', a]
    ,[Noun, '->', man]
    ,[Noun, '->', ball]
    ,[Noun, '->', woman]
    ,[Noun, '->', table]
    ,[Noun, '->', noun]
    ,[Noun, '->', verb]
    ,[Verb, '->', hit]
    ,[Verb, '->', took]
    ,[Verb, '->', saw]
    ,[Verb, '->', liked]
]

# ============================
# rule構造体
# rule : lhs -> rhs
# (defstruct (rule (:type list)) lhs -> rhs sem)
# (pythonにdefstructの:type listがない為に生やした)
# ============================
def rule_lhs(rule):
    lhs, _, rhs = rule
    return lhs

def rule_rhs(rule):
    lhs, _, rhs = rule
    return rhs

# ============================
# tree(dot対)
# tree : cat rhs
# ============================
#(defun new-tree (cat rhs) (cons cat rhs))
def new_tree(cat, rhs):
    return [cat, rhs]

#(defun tree-lhs (tree) (first tree))
def tree_lhs(tree):
    return tree[0]

#(defun tree-rhs (tree) (rest tree))
def tree_rhs(tree):
    return tree[1:]

# ============================
# parse構造体
# parse : tree rem
# (defstruct (parse) "A parse tree and a remainder." tree rem)
# ============================
def make_parse(tree, rem):
    return [tree, rem]

def parse_tree(parse):
    tree, rem = parse
    return tree

def parse_rem(parse):
    tree, rem = parse
    return rem

# 構造体treeの詳細のrem取得
#(defun parse-lhs (parse) (tree-lhs (parse-tree parse)))
def parse_lhs(parse):
    tree = parse_tree(parse)
    lhs = tree_lhs(tree)
    return lhs

# ============================
# ルール検索
# ============================
# --------------------------------
# 単語をキーに、ルールの展開結果に
# 単語が含まれるルール群を取得
# --------------------------------
#(defun lexical-rules (word)
#  "Return a list of rules with word on the right hand side."
#  (or (find-all word *grammar* :key #'rule-rhs :test #'equal)
#      (mapcar #'(lambda (cat) `(,cat -> ,word)) *open-categories*)))
#open_categories = [N, V, A, Name]
open_categories = []
def lexical_rules(word):
    # 右展開部にwordが含まれるルールを *grammar* から選択
    rules_find = [rule
                  for rule in grammar
                  if rule_rhs(rule) == word]

    # ルールが見つからない未知語の場合に
    # 可能なopen_categoriesを充ててルールを仮作する
    if len(rules_find) > 0:
        return rules_find
    def make_rule(cat):
        re = [cat, '->', word]
        return re
    rules_make = [make_rule(cat) for cat in open_categories]
    return rules_make

# --------------------------------
# 品詞や句種類のカテゴリーをキーに
# ルールの展開結果にそのカテゴリが
# 含まれるルール群の先頭を取得
# --------------------------------
#(defun rules-starting-with (cat)
#  "Return a list of rules where cat starts the rhs."
#  (find-all cat *grammar*
#            :key #'(lambda (rule) (first-or-nil (rule-rhs rule)))))
def rules_starting_with(cat):
    def first_rhs(rule):
        _rhs = rule_rhs(rule)
        _rhs_first = first_or_nil(_rhs)
        return _rhs_first
    _rules = [_rule
              for _rule in grammar
              if first_rhs(_rule) == cat]
    return _rules

# ============================
# ボトムアップパーサー
# ============================
# --------------------------------
# 単語リストのすべての解析結果
# (余りの単語が残らない様に解析
#  残った場合は、解析不良として弾く)
# --------------------------------
#(defun parser (words)
#  "Return all complete parses of a list of words."
#  (mapcar #'parse-tree (complete-parses (parse words))))
def parser(words):
    # パース結果
    # (rem(残り)が含まれることがある)
    _parses = parse(words)
    # パース結果
    # (rem(残り)が含まれる結果が取り除かれている)
    _parses_comp = complete_parses(_parses)
    # 解析結果のパース構造体から構文木以外のデータを除いたtreeのリスト
    _trees = [parse_tree(_parse) for _parse in _parses_comp]
    return _trees

# --------------------------------
# 解析結果のリストから
# 解析不良のものを弾く
# --------------------------------
#(defun complete-parses (parses)
#  "Those parses that are complete (have no remainder)."
#  (find-all-if #'null parses :key #'parse-rem))
def complete_parses(parses):
    #（余りのない）全部そろったパース結果
    _parses = [_parse
               for _parse in parses
               for _rem in [parse_rem(_parse)]
               if is_null(_rem)]
    return _parses

# --------------------------------
# 単語リストの先頭から展開されていく
# 可能性のある、すべての解析結果を
# リストアップ
# --------------------------------
#(defun parse (words)
#  "Bottom-up parse, returning all parses of any prefix of words."
#  (unless (null words)
#    (mapcan #'(lambda (rule)
#                (extend-parse (rule-lhs rule) (list (first words))
#                              (rest words) nil))
#            (lexical-rules (first words)))))
def parse(words):
    # 解析対象の単語が無いならNILで終了
    if is_null(words):
        return NIL

    # wordsの先頭を右辺の展開部とする
    # ルールを集めて
    # 各ルールにconsume_wordを適用
    word_first = words[0]
    lex_rules = lexical_rules(word_first)
    def consume_word(rule):
        # wordsの先頭を消費してextend_parseする
        # 例) rule: lhs:Art rhs:the
        #     words: [the, table]
        #     ⇒(lhs=Art, rhs=the, rem=[table], needed=NIL)
        words_rest = words[1:]
        _lhs = rule_lhs(rule)
        _parse = extend_parse(lhs=_lhs, rhs=word_first
                            , rem=words_rest, needed=NIL)
        return _parse
    _parses = flatmap(consume_word, lex_rules)
    return _parses

# --------------------------------
# 単語リストの先頭から展開されていく
# 可能性のある、すべての解析結果を
# リストアップ
# --------------------------------
#(defun extend-parse (lhs rhs rem needed)
#  "Look for the categories needed to complete the parse."
#  (if (null needed)
#      ;; If nothing needed, return parse and upward extensions
#      (省略)
#      ;; otherwise try to extend rightward
#      (省略)
def extend_parse(lhs, rhs, rem, needed):
    if is_null(needed):
        # parse作成
        _tree = new_tree(lhs, rhs)
        _parse = make_parse(tree=_tree, rem=rem)
        # lhsを右辺展開部の先頭とするルールを集めて
        # 各ルールにconsume_rhsを適用
        # (消費するのはgrammarから取り出した右辺展開部の先頭(_rhs[0]))
        _rules = rules_starting_with(lhs)
        def consume_rhs(rule):
            # 解決済のルールの右辺展開部の先頭と
            # 解決予定の右辺展開部の先頭除く残りで
            # 再帰呼び出しで残りを解決
            _tree2 = parse_tree(_parse)
            _rhs2 = rule_rhs(rule)
            _rhs2_rest = _rhs2[1:]
            # 各ルールの左辺頭部をlhsとし
            # 呼び出し元のflatmapのルートのtreeをrhsとし
            # 各ルールの右辺展開部の先頭を取り除いたものをneededとして
            # extend_parseを実行
            # このルートのtreeは、呼び出し元のlhsとrhsを合わせたもの
            # 例)(lhs:NP, rhs:[[Art, the]], rem:[table], needed:[Noun])
            #    neededはArt解析済時点で、単語の残りがtableで、パターンの残りのNounになる
            # grammar = [
            #      .....
            #     ,[NP,   '->', [Art, Noun]]
            #      .....
            # ]
            _lhs=rule_lhs(rule)
            _parse2 = extend_parse(lhs=_lhs, rhs=[_tree]
                                 , rem=rem, needed=_rhs2_rest)
            return _parse2
        _parses = flatmap(consume_rhs, _rules)
        return [_parse] + _parses
    else:
        # 残りの単語(未解析)を解析する
        # 同じ単語でも、複数の役割の可能性がある
        # (動詞にも名詞にもなり得る場合がある)
        # すべての可能性のルールが採取される為
        # 解析結果は複数になりflatmap(mapcan)する
        # 選好は一切していないので、すべて出る
        _parses = parse(rem)

        # parseした結果の新しい_remを消費
        # (消費してNILになる場合もあり)
        # その役割と同値なneededの先頭を消費
        def consume_needed(parse):
            # neededの先頭とparseした結果のlhsが
            # 一致したらneededの先頭を消費して
            # parseした結果をrhsに追加して更に解析
            # 一致しければ不発の意味のNIL
            # また、parseした結果の新しい_remを使用する(消費してNILになる場合もあり)
            _lhs = parse_lhs(parse)
            _needed_first = needed[0]
            if _lhs == _needed_first:
                # 例)(lhs:NP, rhs:[[Art, the], [Noun, table]], rem:NIL, needed:NIL)
                #     parse([table]) ⇒ [[Noun, table]:tree,[]:rem]
                #     _needed_rest ⇒ [Noun][1:] = [] = NIL
                _tree = parse_tree(parse)
                _rhs_add = append1(rhs, _tree)
                _rem = parse_rem(parse)
                _needed_rest = needed[1:]
                _parse = extend_parse(lhs=lhs, rhs=_rhs_add
                                    , rem=_rem, needed=_needed_rest)
                return _parse
            return NIL
        _parses_new = flatmap(consume_needed, _parses)
        return _parses_new

# ============================
# 下請け関数群
# (読めば分かるなんてことないものたち)
# ============================
def append1(items, item):
    re = items + [item]
    return re

def first_or_nil(x):
    if isinstance(x, list):
        if len(x) > 0:
            return x[0]
    return NIL

def flatmap(fun, lst):
    matrix2d = [fun(_rule) for _rule in lst]
    lst_new = flatten(matrix2d)
    return lst_new

def flatten(target):
    flat = [x
            for row in target
            for x in row]
    return flat

def is_null(x):
    if x is None or x == NIL:
        return True
    else:
        return False


if __name__ == '__main__':
    input_ = [the, table]
    expect = [[NP
               , [ [Art, the]
                 , [Noun, table]]]]
    assert parser(input_) == expect

    input_ = [the, ball, hit, the, table]
    expect = [
        [Sentence
            , [  [NP, [  [Art, the]
                         , [Noun, ball]]]
               , [VP, [  [Verb, hit]
                         , [NP, [  [Art, the]
                                   , [Noun, table]]]]]]]]
    assert parser(input_) == expect