gno/usr.bin/awk/tests/sentgen2

# sentgen2 - random sentence generator (nonrecursive)
#   input:  grammar file; sequence of nonterminals
#   output: random sentences generated by the grammar

BEGIN {  # read rules from grammar file
    while (getline < "grammar" > 0)
        if ($2 == "->") {
            i = ++lhs[$1]              # count lhs
            rhscnt[$1, i] = NF-2       # how many in rhs
            for (j = 3; j <= NF; j++)  # record them
               rhslist[$1, i, j-2] = $j
        } else
            print "illegal production: " $0
}

{   if ($1 in lhs) {  # nonterminal to expand
        push($1)
        gen()
        printf("\n")
    } else 
        print "unknown nonterminal: " $0   
}

function gen(    i, j) {
    while (stp >= 1) {
        sym = pop()
        if (sym in lhs) {       # a nonterminal
            i = int(lhs[sym] * rand()) + 1   # random production
            for (j = rhscnt[sym, i]; j >= 1; j--) # expand rhs's
                push(rhslist[sym, i, j])
        } else
            printf("%s ", sym)
    }
}

function push(s) { stack[++stp] = s }

function pop() { return stack[stp--] }