rules = [ 
    (  'S', ['NP', 'VP']),
    ( 'NP', ['DET', 'N']),
    ( 'NP', ['NP', 'PP']),
    ( 'VP', ['V']),
    ( 'VP', ['V', 'NP']),
    ( 'VP', ['VP', 'PP']),
    ( 'PP', ['P', 'NP']),
    (  'V', ['works']),
    (  'V', ['sleeps']),
    (  'V', ['reads']),
    (  'N', ['student']),
    (  'N', ['book']),
    (  'N', ['cat']),
    (  'N', ['roof']),
    (  'N', ['house']),
    (  'N', ['library']),
    (  'N', ['university']),
    (  'P', ['in']),
    (  'P', ['of']),
    (  'P', ['on']),
    (  'P', ['near']),
    ('DET', ['the']),
    ('DET', ['a'])
]

def shift(stack, sent):
    return (stack + [sent[0]], sent[1:])

def reduce(stack, sent, lhs, rhs):
    return (stack[:-len(rhs)] + [lhs], sent) 

def matches(stack, rhs):
    for (s, r) in zip(stack[-len(rhs):], rhs):
        if s != r:
            return False
    return True

def recognize(sent, verbose = False):
    agenda = [([], sent)]
    while agenda:
        (stack, sent) = agenda.pop()
        if verbose:
            print('<[%s] [%s]>' % (' '.join(stack), ' '.join(sent)))
        if sent == [] and stack == ['S']:
            return True
        if sent != []:
            agenda.append(shift(stack, sent))
        for (lhs, rhs) in rules:
            if len(stack) >= len(rhs):
                if matches(stack, rhs):
                    agenda.append(reduce(stack, sent, lhs, rhs))
    return False

def _test(sent):
    print(sent)
    print(recognize(sent.split()))

def test1():
    _test('the student works')
    _test('the student works in the library')
    _test('the student reads a book')
    _test('the student reads a book in the library')
    _test('the cat on the roof of the house near the library of the university sleeps')

def test2():
    _test('the cat on the roof of the house near the library of the university')

if __name__ == '__main__':
    import sys
    if len(sys.argv) == 2:
        print(recognize(sys.argv[1].split(), verbose = True))