Recognize sentences with a tiny context-free grammar (S→NP VP, NP→Det N, VP→V) via recursive descent, and print the parse tree for accepted sentences. Test one ACCEPT and one REJECT.

Answer

GRAMMAR = { 'S': [['NP', 'VP']], 'NP': [['Det', 'N']], 'VP': [['V']], } LEX = {'Det': {'the', 'a'}, 'N': {'dog', 'cat'}, 'V': {'runs', 'sleeps'}} def parse(symbol, tokens, i): # returns (tree, next_index) on success, or (None, i) on failure if symbol in LEX: # terminal category if i < len(tokens) and tokens[i] in LEX[symbol]: return (tokens[i], i + 1) return (None, i) for production in GRAMMAR[symbol]: # try each rule for this nonterminal children, j, ok = [], i, True for sym in production: tree, j = parse(sym, tokens, j) if tree is None: ok = False break children.append(tree) if ok: return ([symbol] + children, j) return (None, i) def show(tree): if isinstance(tree, str): return tree label = tree[0] return f"({label} " + ' '.join(show(c) for c in tree[1:]) + ')' def recognize(sentence): tokens = sentence.split() tree, j = parse('S', tokens, 0) if tree is not None and j == len(tokens): print(f"'{sentence}' -> ACCEPT parse: {show(tree)}") else: print(f"'{sentence}' -> REJECT") recognize('the dog runs') recognize('dog the runs')