from random import choice grammar = dict( S = [['NP','VP']], NP = [['Art', 'N']], VP = [['V', 'NP']], Art = ['the', 'a'], N = ['man', 'ball', 'woman', 'table'], V = ['hit', 'took', 'saw', 'liked'] ) def generate(phrase): "Generate a random sentence or phrase" if isinstance(phrase, list): return mappend(generate, phrase) elif phrase in grammar: return generate(choice(grammar[phrase])) else: return [phrase] def generate_tree(phrase): """Generate a random sentence or phrase, with a complete parse tree.""" if isinstance(phrase, list): return map(generate_tree, phrase) elif phrase in grammar: return [phrase] + generate_tree(choice(grammar[phrase])) else: return [phrase] def mappend(fn, list): "Append the results of calling fn on each element of list." return reduce(lambda x,y: x+y, map(fn, list))
Running the Lisp Program Running the Python Program
> (generate 'S) (the man saw the table)
>>> generate('S') ['the', 'man', 'saw', 'the', 'table']>>> ' '.join(generate('S')) 'the man saw the table'
Python中的grammer比Lisp中的丑陋，这让我很担心，所以我考虑在Python中写一个解析器（后来发现已经有一些写好的，并且可以免费获得的），以及重载一些内置的操作符。第二种方法在一些应用中是可行的，例如我写Expr class， 这是用来表现和操纵逻辑表达式的。但是对于这个应用而言，一个简单、定制的语法规则解析器就够了：一个语法规则是一个用“|”分开的，可选部分的列表，每 个可选部分都是由空格（" ")分隔的单词列表。把grammar程序重写为一个更加符合Python惯用法的程序，而不是Lisp程序的翻译，下面就是该程序：
Python Program simple.py (idiomatic version)"""Generate random sentences from a grammar. The grammar consists of entries that can be written as S = 'NP VP | S and S', which gets translated to {'S': [['NP', 'VP'], ['S', 'and', 'S']]}, and means that one of the top-level lists will be chosen at random, and then each element of the second-level list will be rewritten; if it is not in the grammar it rewrites as itself. The functions rewrite and rewrite_tree take as input a list of symbols. The functions generate and generate_tree are convenient interfaces to rewrite and rewrite_tree that accept a string (which defaults to 'S') as input."""
import random
def make_grammar(**grammar):
"Create a dictionary mapping symbols to alternatives."
for (cat, rhs) in grammar.items():
grammar[cat] = [alt.split() for alt in rhs.split('|')] r
eturn grammar
grammar = make_grammar(
S = 'NP VP', NP = 'Art N', VP = 'V NP', Art = 'the | a', N = 'man | ball | woman | table', V = 'hit | took | saw | liked' )
def rewrite(symbols):
"Replace each non-terminal symbol in the list with a random entry in grammar (recursively)."
return [terminal for symbol in symbols
for terminal in (rewrite(random.choice(grammar[symbol]))
if symbol in grammar else [symbol])] def rewrite_tree(symbols): "Replace the list of symbols into a random tree, chosen from grammar."
return [{symbol: rewrite_tree(random.choice(grammar[symbol]))}
if symbol in grammar else symbol