Parser for Annotated expressions generated by FFTW's genfft tool.

dft12.alst

(:= T1 xi[0])
(:= T6 xi[6])
(:= T2 xi[4])
(:= T3 xi[8])
(:= T4 (+ T2 T3))
(:= T32 (+ T3 (- T2)))
(:= T7 xi[10])
(:= T8 xi[2])
(:= T9 (+ T7 T8))
(:= T33 (+ T8 (- T7)))
(:= T5 (+ T1 T4))
(:= T10 (+ T6 T9))
(:= T45 (+ T32 T33))
(:= T34 (* KP866025403 (+ T32 (- T33))))
(:= T26 (+ T6 (- (* KP500000000 T9))))
(:= T25 (+ T1 (- (* KP500000000 T4))))
(:= T12 xi[3])
(:= T17 xi[9])
(:= T13 xi[7])
(:= T14 xi[11])
(:= T15 (+ T13 T14))
(:= T28 (+ T14 (- T13)))
(:= T18 xi[1])
(:= T19 xi[5])
(:= T20 (+ T18 T19))
(:= T29 (+ T19 (- T18)))
(:= T16 (+ T12 T15))
(:= T21 (+ T17 T20))
(:= T44 (+ T28 T29))
(:= T36 (+ T17 (- (* KP500000000 T20))))
(:= T35 (+ T12 (- (* KP500000000 T15))))
(:= T30 (* KP866025403 (+ T28 (- T29))))
(:= T11 (+ T5 (- T10)))
(:= T22 (* I (+ T16 (- T21))))
(:= xo[9] (+ T11 (- T22)))
(:= xo[3] (+ T11 T22))
(:= T23 (+ T5 T10))
(:= T24 (+ T16 T21))
(:= xo[6] (+ T23 (- T24)))
(:= xo[0] (+ T23 T24))
(:= T27 (+ T25 (- T26)))
(:= T31 (+ T27 (- T30)))
(:= T40 (+ T27 T30))
(:= T37 (+ T35 (- T36)))
(:= T38 (* I (+ T34 T37)))
(:= T39 (* I (+ T34 (- T37))))
(:= xo[5] (+ T31 (- T38)))
(:= xo[11] (+ T40 (- T39)))
(:= xo[7] (+ T38 T31))
(:= xo[1] (+ T39 T40))
(:= T46 (* I (* KP866025403 (+ T44 (- T45)))))
(:= T48 (* I (* KP866025403 (+ T45 T44))))
(:= T41 (+ T25 T26))
(:= T42 (+ T35 T36))
(:= T43 (+ T41 (- T42)))
(:= T47 (+ T41 T42))
(:= xo[10] (+ T43 (- T46)))
(:= xo[4] (+ T47 T48))
(:= xo[2] (+ T43 T46))
(:= xo[8] (+ T47 (- T48)))
DVK(KP500000000, +0.500000000000000000000000000000000000000000000);
DVK(KP866025403, +0.866025403784438646763723170752936183471402627);

dft12.go

package main

const (
	KP500000000 = +0.500000000000000000000000000000000000000000000
	KP866025403 = +0.866025403784438646763723170752936183471402627
	I           = 1i
)

func DFT(xi, xo []complex128) {
	T1 := xi[0]
	T6 := xi[6]
	T2 := xi[4]
	T3 := xi[8]
	T4 := T2 + T3
	T32 := T3 - T2
	T7 := xi[10]
	T8 := xi[2]
	T9 := T7 + T8
	T33 := T8 - T7
	T5 := T1 + T4
	T10 := T6 + T9
	T45 := T32 + T33
	T34 := KP866025403 * (T32 - T33)
	T26 := T6 - (KP500000000 * T9)
	T25 := T1 - (KP500000000 * T4)
	T12 := xi[3]
	T17 := xi[9]
	T13 := xi[7]
	T14 := xi[11]
	T15 := T13 + T14
	T28 := T14 - T13
	T18 := xi[1]
	T19 := xi[5]
	T20 := T18 + T19
	T29 := T19 - T18
	T16 := T12 + T15
	T21 := T17 + T20
	T44 := T28 + T29
	T36 := T17 - (KP500000000 * T20)
	T35 := T12 - (KP500000000 * T15)
	T30 := KP866025403 * (T28 - T29)
	T11 := T5 - T10
	T22 := I * (T16 - T21)
	xo[9] = T11 - T22
	xo[3] = T11 + T22
	T23 := T5 + T10
	T24 := T16 + T21
	xo[6] = T23 - T24
	xo[0] = T23 + T24
	T27 := T25 - T26
	T31 := T27 - T30
	T40 := T27 + T30
	T37 := T35 - T36
	T38 := I * (T34 + T37)
	T39 := I * (T34 - T37)
	xo[5] = T31 - T38
	xo[11] = T40 - T39
	xo[7] = T38 + T31
	xo[1] = T39 + T40
	T46 := I * (KP866025403 * (T44 - T45))
	T48 := I * (KP866025403 * (T45 + T44))
	T41 := T25 + T26
	T42 := T35 + T36
	T43 := T41 - T42
	T47 := T41 + T42
	xo[10] = T43 - T46
	xo[4] = T47 + T48
	xo[2] = T43 + T46
	xo[8] = T47 - T48
}

parse.go

package main

import (
	"bufio"
	"fmt"
	"go/format"
	"log"
	"os"
	"regexp"
	"strings"
)

// An expression consists of either an Operator or a Literal. Operators have
// at least one operand which are Expressions.
type Expression struct {
	Op    string
	Lit   string
	OpIdx int
	Expr  []*Expression
}

// Determines if an operator is unary based on the number of operands.
func (expr Expression) IsUnary() bool {
	return len(expr.Expr) == 1
}

// Produces valid Go string representation of the expression.
func (expr Expression) String() string {
	return expr.stringHelper(0)
}

// String() provides default depth value, this is the actual function.
func (expr Expression) stringHelper(depth int) (r string) {
	// If the expression is an Operand, just print the literal.
	if expr.Op == "" {
		return expr.Lit
	}

	// Only print parenthesis if we're not at the top level.
	if depth > 1 {
		r += "("
		defer func() {
			r += ")"
		}()
	}

	// Only use the combined declaration//assignment operator if we're assigning to a T\d+ variable.
	if expr.Op == "=" && strings.HasPrefix(expr.Expr[0].Lit, "T") {
		expr.Op = ":="
	}

	// If the expression is unary then print the operator before it's operand.
	if expr.IsUnary() {
		r += expr.Op
		r += expr.Expr[0].stringHelper(depth + 1)
	} else {
		// For each operand.
		for idx := range expr.Expr {
			// Don't print an operator on the first operand.
			if idx != 0 {
				// If the operator is addition and the current operand is unary subtraction, simplify.
				if expr.Op == "+" && expr.Expr[idx].IsUnary() && expr.Expr[idx].Op == "-" {
					r += "-"
					r += expr.Expr[idx].Expr[0].stringHelper(depth + 1)
					continue
				} else {
					// Else, append the operator.
					r += expr.Op
				}
			}
			// Recurse for each operand. This is skipped if we did unary simplification.
			r += expr.Expr[idx].stringHelper(depth + 1)
		}
	}

	return
}

// Parse an expression into an expression tree.
func (expr *Expression) Parse(line string) {
	// Skip '(:'
	expr.parse(line[2:])
}

// Parse(line string) skips first two characters of each expression, this is
// the actual function.
func (expr *Expression) parse(line string) (idx int) {
	// Operators always have at least one operand.
	// Empty expressions will never appear in String() output but we may want
	// to conditionally create this later for large parse trees.
	expr.Expr = append(expr.Expr, new(Expression))

	// While there are characters left to parse.
	for idx = 0; idx < len(line); idx++ {
		switch line[idx] {
		// Opening parenthesis represent the beginning of a new expression.
		// Recursively parse it and update index with number of characters
		// consumed.
		case '(':
			idx += expr.Expr[expr.OpIdx].parse(line[idx+1:])
		// Colons are the first character in the assignment operator, we don't need it so skip it.
		case ':':
			continue
		// Operators are appended to Op field and space following is consumed.
		case '=', '+', '-', '*':
			expr.Op = line[idx : idx+1]
			idx += 1
		// Spaces will only ever be encountered between operands, so make a
		// new operand and increment the operand index.
		case ' ':
			expr.Expr = append(expr.Expr, new(Expression))
			expr.OpIdx++
		// Closing parenthesis represent termination of an expression. Return
		// consumed character count + 1 to include this character.
		case ')':
			return idx + 1
		// Anything else must be part of a literal, append it.
		default:
			expr.Expr[expr.OpIdx].Lit += line[idx : idx+1]
		}
	}

	return
}

func init() {
	log.SetFlags(log.Lshortfile)
}

func main() {
	// Print usage if user didn't pass the right number of arguments.
	if len(os.Args) != 2 {
		fmt.Println("Usage: parse [filename]")
		os.Exit(1)
	}

	// Open input file for reading.
	inputFile, err := os.Open(os.Args[1])
	if err != nil {
		log.Fatal("Error opening input file", err)
	}
	defer inputFile.Close()

	// Create a line scanner, we only need input one line at a time.
	inputScanner := bufio.NewScanner(inputFile)

	var (
		body      string
		constants [][]string
	)

	// Regular expression matches constants.
	constRe := regexp.MustCompile(`DVK\((K[NP]\d+), ([+-][\d\.]+)\);`)

	// For each line in the input.
	for idx := 0; inputScanner.Scan(); idx++ {
		// Get the current line.
		line := inputScanner.Text()

		// If the line has the prefix we expect on a constant, try parsing it.
		if strings.HasPrefix(line, "DVK") {
			// If the regex matches we have a constant.
			if constRe.MatchString(line) {
				// Append the matching groups from the constant to the constant list.
				constants = append(constants, constRe.FindStringSubmatch(line)[1:])
			}
			// Continue so we don't try parsing this as an expression.
			continue
		}

		// Parse the line and append it to the body.
		var expr Expression
		expr.Parse(line)
		body += expr.String() + "\n"
	}

	// Lay out some boilerplate for the go formatter.
	source := "package main\n"

	// Append the constants we parsed including the imaginary constant.
	source += "const (\n"
	constants = append(constants, []string{"I", "1i"})
	for _, constant := range constants {
		source += fmt.Sprintf("%s = %s\n", constant[0], constant[1])
	}
	source += ")\n"

	// Append the function signature, body and enclosing brackets.
	source += "func DFT(xi, xo []complex128) {\n" + body + "}"

	// Format the source.
	formatted, err := format.Source([]byte(source))
	if err != nil {
		log.Fatal("Error formatting go source:", err)
	}

	// Display the formatted source.
	fmt.Println(string(formatted))
}