lex
	ignore /[\t\n ]+/
	literal '^', '|', '-', ',', ':', '!', '?', '.'
	literal '(', ')', '{', '}', '*', '&', '+'

	literal '--', ':>', ':>>', '<:', '->', '**'

	token word /[a-zA-Z_][a-zA-Z0-9_]*/
	token uint /[0-9]+/
end


def start [expression]

def expression [term expression_op*]

def expression_op
	['|' term]
|	['&' term]
|	['-' term]
|	['--' term]

def term [factor_rep term_rest]

# This list is done manually to get shortest match.
def term_rest
	[]
|	[term_op term_rest]

def term_op
	[factor_rep]
|	['.' factor_rep]
|	[':>' factor_rep]
|	[':>>' factor_rep]
|	['<:' factor_rep]

def factor_rep 
	[factor_neg factor_rep_op*]

def factor_rep_op
	['*']
|	['**']
|	['?']
|	['+']
|	['{' factor_rep_num '}']
|	['{' ',' factor_rep_num '}']
|	['{' factor_rep_num ',' '}']
|	['{' factor_rep_num ',' factor_rep_num '}']

def factor_rep_num [uint]

def factor_neg 
	['!' factor_neg]
|	['^' factor_neg]
|	[factor]

def factor 
	[alphabet_num]
|	[word]
|	['(' expression ')']

def alphabet_num 
	[uint]

parse SP: start[stdin]
S: start = SP.tree

#
# Top-Down, Left-Right
#

int do_topdown_leftright( T: ref any )
{
	for C:any in child(T) {
		yield C
		do_topdown_leftright( C )
	}
}

iter topdown_leftright( T: ref any )
{
	do_topdown_leftright( T )
}

#
# Bottom-Up, Left-Right
#

int do_bottomup_leftright( T: ref any )
{
	for C:any in child(T) {
		do_bottomup_leftright( C )
		yield C
	}
}

iter bottomup_leftright( T: ref any )
{
	do_bottomup_leftright( T )
}


#
# Top-Down, Right-Left
#

int do_topdown_rightleft( T: ref any )
{
	for C:any in rev_child(T) {
		yield C
		do_topdown_rightleft( C )
	}
}

iter topdown_rightleft( T: ref any )
{
	do_topdown_rightleft( T )
}

#
# Bottom-Up, Right-Left
#

int do_bottomup_rightleft( T: ref any )
{
	for C:any in rev_child(T) {
		do_bottomup_rightleft( C )
		yield C
	}
}

iter bottomup_rightleft( T: ref any )
{
	do_bottomup_rightleft( T )
}

#
# Testing
#

print( 'bottomup_leftright\n' )
for T1: any in bottomup_leftright( S ) 
{
	print( ^T1 '\n' )
}

print( 'bottomup_rightleft\n' )
for T2: any in bottomup_rightleft( S ) 
{
	print( ^T2 '\n' )
}

print( 'topdown_leftright\n' )
for T3: any in topdown_leftright( S ) 
{
	print( ^T3 '\n' )
}

print( 'topdown_rightleft\n' )
for T4: any in topdown_rightleft( S ) 
{
	print( ^T4 '\n' )
}