A programming problem solution.

[r. clayton]

A while back I posted a programming problem about generating the languages
associated with regular expressions. Here's the solution, written in gawk
3.1.5 on a debian testing system.

If you think you understand the code, you might want to check yourself by
implementing list repetition, which is left unimplemented in this solution.

--

#! /usr/bin/awk -f
#
# regexp-gen - read from std-in regular expressions and write to std-out the
# strings in the language associated with the regexp read.
#
# echo 'a ? b | c d * ( e f ) g *, h i' | regexp-gen

function do_a_choice(start, i, o, o1) {

# If the regular expression at the given input index is an choice, then
# append to output the strings generated by the choice and return the
# index one past the end of the choice; otherwise return -1.

if (input[start++] != "|")
return -1

for (i in output)
o[i] = 1

start = do_a_regexp(start)

for (i in output)
o1[i] = 1
delete output
for (i in o)
output[i] = 1

start = do_a_regexp(start)

for (i in o1)
output[i] = 1

return start
}

function do_a_group(start) {

# If the regular expression at the given input index is the start of a
# group, then append to output the strings generated by the group and
# return the index one past the end of the group; otherwise just return
# -1.

if (input[start++] != "(")
return -1

while (input[start] != ")")
start = do_a_regexp(start)

return start + 1
}

function do_an_item(start, i, sep) {

# If the regular expression at the given input index is an item, then
# append it to output and return the index one past the end of the item;
# otherwise die with an error.

if (start > NF) {
print "running off the end of the regular expression" >> "/dev/stderr"
exit(1)
}

for (i in output) {
delete output[i]
sep = ""
if (i != "")
sep = " "
output[i sep input[start]] = 1
}

return start + 1
}

function do_a_regexp(start, s) {

# Append to output the language associated by the regular expression at
# the given input index and return the index one past the end of the
# regexp.

if ((s = do_an_option(start)) > 0) return s;
if ((s = do_a_group(start)) > 0) return s;
if ((s = do_a_repetition(start)) > 0) return s;
if ((s = do_a_choice(start)) > 0) return s;

return do_an_item(start)
}

function do_a_repetition(start, i, o) {

# If the regular expression at the given input index is a repetition,
# then append to output the strings generated by the repetition and
# return the index one past the end of the repetition; otherwise return
# -1.

if (input[start++] != "*")
return -1

for (i in output)
o[i] = 1

do_a_regexp(start)

for (i in output)
o[i] = 1

start = do_a_regexp(start)

for (i in o)
output[i] = 1

return start
}

function do_an_option(start, i, o) {

# If the regular expression at the given input index is an option, then
# append to output the strings generated by the option and return the
# index one past the end of the option; otherwise return -1.

if (input[start++] != "?")
return -1

for (i in output)
o[i] = 1

start = do_a_regexp(start)

for (i in o)
output[i] = 1

return start
}

{NF = split("( " $0 " )", input)
delete output
output[""] = 1
do_a_group(1)
for (i in output)
print i
}

# $Log: regexp-gen,v $
# Revision 1.2 2006/11/19 13:20:48 rclayton
# Call awk directly.
#
# Revision 1.1 2006/11/15 19:51:43 rclayton
# Initial revision
#

[Janis]

r. clayton wrote:
>
> for (i in output) {
> delete output[i]
> sep = ""
> if (i != "")
> sep = " "
> output[i sep input[start]] = 1
> }

Does anybody know whether awk shows deterministic behaviour in the
case that a set (associative array) is updated while iterating over
it? Will the iteration extend to the newly inserted array elements?

Let me answer that by inspecting the gawk manual; which says...

"The order in which elements of the array are accessed by this
statement is determined by the internal arrangement of the array
elements within awk and cannot be controlled or changed. This can lead
to problems if new elements are added to array by statements in the
loop body; it is not predictable whether the for loop will reach them.
Similarly, changing var inside the loop may produce strange results.
It is best to avoid such things."

Janis