1 files changed, 74 insertions, 17 deletions
diff --git a/parsing/codegen.sh b/parsing/codegen.sh
index c28ffca..0e32987 100644
--- a/parsing/codegen.sh
+++ b/parsing/codegen.sh
@@ -1,4 +1,10 @@
-toktext=''
+sc=
+
+sgetc()
+{
+	sc="$(dd bs=1 count=1 2>/dev/null; printf '.')"
+	sc="${sc%.}"
+}
 
 toktext()
 {
@@ -57,29 +63,80 @@ toktext()
 		*) n='';;
 	esac
 
-	toktext="${n}"
+	printf '%s' "${n}"
 }
 
-codegen()
+codegen_sub()
 {
-	local toks="${1}"
+	local array="${1}"
 	shift 1
-	local subtoks=
-	local t=
-
-	case "${toks}" in
-		*"${STX}"*"${ETX}"*)
-			subtoks="${toks#*${STX}}"
-			subtoks="${subtoks%${ETX}*}"
-			toks="${toks%%${STX}*}$(codegen \
-				"${subtoks}")${toks##*${ETX}}"
-			;;
-	esac
 
 	IFS="${RS}"
-	for t in ${toks}; do
+	for t in ${array}; do
 		toktext "${t}"
-		printf '%s ' "${toktext}"
+		printf ' '
 	done
 	unset IFS
 }
+
+# The token stack is encoded in a string in the following grammar:
+#     Terminal symbols:
+#         TOKEN
+#     Production rules:
+#         stack  = tokens [ '<SOH>' type '<STX>' stack '<ETX>' [ tokens ] ] ;
+#         tokens = TOKEN { '<RS>' TOKEN } ;
+#         type   = 'C' | 'A' ;
+# We need to recurse through this stack to get to all the tokens.
+# Each element in the stack (an array of tokens) gets run through the codegen to
+# become text that is inserted into the array below.
+parse_stack()
+{
+	local array=
+
+	array=''
+	while :; do
+		sgetc
+		case "${sc}" in
+			'')
+				# EOF
+				break
+				;;
+			"${SOH}")
+				# New stack element
+				sgetc
+				case "${sc}" in
+					'C')
+						# Command substitution
+						sgetc  # STX
+						array="${array}$(parse_stack)"
+						;;
+					'A')
+						# Arithmetic expansion
+						sgetc  # STX
+						;;
+				esac
+				;;
+			"${ETX}")
+				# End of stack element
+				break
+				;;
+			*)
+				# Token character
+				array="${array}${sc}"
+				;;
+		esac
+	done
+	codegen_sub "${array}"
+}
+
+codegen()
+{
+	local toks="${1}"
+	shift 1
+
+	if printf '%s' "${toks}" | parse_stack; then
+		return 0
+	else
+		return 1
+	fi
+}