# chapter=3 variant=non-det 
not_yet_parsed = None
def member(item, x):
    return (None if is_none(x)
            else x if item == head(x)
            else member(item, tail(x)))
def parse_word(word_list):
    require( not is_none(not_yet_parsed))
    require( not is_none(member(head(not_yet_parsed), tail(word_list))))
    found_word = head(not_yet_parsed)
    not_yet_parsed = tail(not_yet_parsed)
    return llist(head(word_list), found_word)
prepositions = llist("prep", "for", "to", "in", "by", "with")
def parse_prepositional_phrase():
    return llist("prep-phrase", parse_word(prepositions), parse_noun_phrase())
nouns = llist("noun", "student", "professor", "cat", "class")
verbs = llist("verb", "studies", "lectures", "eats", "sleeps")
articles = llist("article", "the", "a")
def parse_simple_noun_phrase():
    return llist("simple-noun-phrase", parse_word(articles), parse_word(nouns))
def parse_noun_phrase():
    def maybe_extend(noun_phrase):
        return amb(noun_phrase, maybe_extend(llist("noun-phrase", noun_phrase, parse_prepositional_phrase())))
    return maybe_extend(parse_simple_noun_phrase())
def parse_sentence():
    return llist("sentence", parse_noun_phrase(), parse_verb_phrase())
def parse_verb_phrase():
    def maybe_extend(verb_phrase):
        return amb(verb_phrase, maybe_extend(llist("verb-phrase", verb_phrase, parse_prepositional_phrase())))
    return maybe_extend(parse_word(verbs))
def parse_input(input):
    not_yet_parsed = input
    sent = parse_sentence()
    require(is_none(not_yet_parsed))
    return sent
