#!/bin/sh

# This script transforms a Deterministic Finite Automaton (DFA)
# into a dd/sh function

# usual dd/sh intro

PATH=''
rm=/bin/rm
dd=/bin/dd
tmp=/tmp/dfa2ddsh.$$
trap "$rm -f $tmp.?" 0 1 2 3

# the input file consists of three sections, separated by one single
# blank line

# the first section lists the input alphabet, one symbol per line

# the second section lists the internal states, one per line,
# in the format "F state" for final states and "N state" for
# nonfinal states

# the third section lists the transitions, in the format
# "state symbol new-state". The symbol "*" is allowed as an
# abbreviation, and it means "one transition per each input symbol"

# The output consists of a few shell functions. The important one
# is read_string which gets some symbols from standard input and returns
# true if the string is in the regular language defined by the DFA.

true () { return 0 }
false () { return 1 }

# read the input alphabet. Since the output alphabet is the same, write
# it out at the same time

go=true
intsymbol='is_symbol () {
    case "$1" in'
symbols=''

while $go && read symbol
do
    case "$symbol" in
	*\ *) echo "Symbol cannot contain spaces" >&2
	    exit 1
	    ;;
    	'*') echo "Invalid symbol '*'" >&2
	    exit 1
	    ;;
    	?*) intsymbol="$intsymbol
	$symbol) return 0 ;;" ; symbols="$symbols $symbol" ;;
	*) go=false ;;
    esac
done

intsymbol="$intsymbol
    	*) return 1 ;;
    esac
}"

eval "$intsymbol"
echo "$intsymbol"

# now read the state table

go=true
out=''
finstate='is_final () {
    case "$1" in'
nonfinstate='is_state () {
    case "$1" in'
states=''

# if you understand the code please don't comment it.

while $go && read fin state
do
    case "$fin" in
    	f*|F*) finstate="$finstate
	$state) return 0 ;;" ; nonfinstate="$nonfinstate
	$state) return 0 ;;" ; states="$states $state"
		out="0$out" ;;
    	n*|N*) nonfinstate="$nonfinstate
	$state) return 0 ;;" ; states="$states $state"
		out="0$out" ;;
	?*) ;;
	*) go=false ;;
    esac
done

finstate="$finstate
    	*) return 1 ;;
    esac
}"

nonfinstate="$nonfinstate
    	*) return 1 ;;
    esac
}"

eval "$finstate"
echo "$finstate"
eval "$nonfinstate"
echo "$nonfinstate"

# read transition table

echo 'do_trans () {'
echo '    case "$1 $2" in'

while read state symbol next
do
    if is_state "$state" && is_state "$next"
    then
    	:
    else
    	echo "Invalid state name in transition '$state $symbol $next'" >&2
	exit 1
    fi
    case "$symbol" in
        '*') for symbol in $symbols
	    do
		echo "	$state\ $symbol) new_state='$next'; return ;;"
	    done
	    ;;
	*) if is_symbol "$symbol"
	    then
		echo "	$state\ $symbol) new_state='$next'; return ;;"
	    else
	    	echo "Invalid symbol in transition '$state $symbol $next'" >&2
		exit 1
	    fi
	    ;;
    esac
done

echo '    esac'
echo '    return 1'
echo '}'
set $states
echo 'read_string () {'
echo "    state=$1"
echo "    while read symb"
echo "    do"
echo '        if is_symbol "$symb"'
echo '        then'
echo '            do_trans $state $symb'
echo '            state=$new_state'
echo '        else'
echo '            echo "Symbol $symb not in input alphabet >&2"'
echo '            exit 1'
echo '        fi'
echo "    done"
echo '    if is_final $state'
echo '    then'
echo '        return 0'
echo '    else'
echo '        return 1'
echo '    fi'
echo '}'