well formed brackets of many types! python is awesome! hooray for noam chomsky + regular grammars! :D

CFGProd.py

# Jerome Martinez
# 19 February 2013
# Context-free grammar production

# This is our grammar:
#
#   S -> SS  		[NonTerm, NonTerm]
#   S -> ( S )		[LPAREN, NonTerm, RPAREN]
#   S -> [ S ]		[LBRACK, NonTerm, RBRACK]
#   S -> { S }		[LBRACE, NonTerm, RBRACE]
#   S -> ( )		[LPAREN, RPAREN]
#   S -> [ ]		[LBRACK, RBRACK]
#   S -> { }		[LBRACE, RBRACE]

import re, sys, random
from pprint import pprint


## ======== ##
##  TOKENS  ##
## ======== ## 

# our terminal tokens
LPAREN = '('
RPAREN = ')'
LBRACK = '['
RBRACK = ']'
LBRACE = '{'
RBRACE = '}'

# our non terminal token
NonTerm = 'S'


## ========= ##
##  GRAMMAR  ##
## ========= ##

# non-terminal sequences
non_terminal_seqs = (	
	[NonTerm, NonTerm],
	[LPAREN, NonTerm, RPAREN],
	[LBRACK, NonTerm, RBRACK],
	[LBRACE, NonTerm, RBRACE],
)

# terminating sequences
terminal_seqs = (
	[LPAREN, RPAREN],
	[LBRACK, RBRACK],
	[LBRACE, RBRACE]
)


## ============ ##
##  PRODUCTION  ##
## ============ ##

# produce a random grammar production
# based on the grammar rules given
# and for a given length of recursive calls.
# produces only terminating sequences once
# it passes expiration
def random_production (prod_length):

	# base case: if the production length is 0
	if prod_length == 0:
		rand = random.randint(0, len(terminal_seqs)-1)
		seq = terminal_seqs[rand]

		# return a terminal sequence instead
		return seq

	else:
		# pick a random nonterminal sequence
		rand = random.randint(0, len(non_terminal_seqs)-1)
		this_seq = non_terminal_seqs[rand]

		# for every nonterminal in the picked sequence
		for i in range(len(this_seq)):
			token = this_seq[i]

			# replace it with another random production
			if token == NonTerm:
				this_seq[i] = random_production(prod_length-1)
		
		# return a flattened list of tokens
		return flatten(this_seq)

# helper function that flattens shallow-nested lists only
# example of a shallow-nested list: ((1, 2), (3, 4))
def flatten (l):
	thingys = []
	for y in l:
		for x in y:
			thingys.append(x)
	return thingys

# pretty prints the production list
def print_production(production):
	for p in production:
		sys.stdout.write(str(p) + ' ')
	print ''


## ============= ##
##  RNA FOLDING  ##
## ============= ##

# associate a random number to each of the items in the production list
# numbers should be associated in ascending order from left to right
# in the production list
def associate_score (production, limit):
	# upper bound must be greater than the production
	assert limit > len(production)

	# collect a list of unique and random number
	# collect as many as there are in the production list
	rand_list = set([])
	while len(rand_list) < len(production):
		rand = random.randint(0, limit)
		rand_list.add(rand)

	return rand_list

prod = random_production(5)
randlist = associate_score(prod, 40)

print_production(prod)
print randlist