Arithmetic evaluator in pure Bash using Pratt parsing

pratt.sh

#!/usr/bin/env bash

#
# RESOURCES
#
#  - https://tdop.github.io/
#  - https://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/
#  - https://martin.janiczek.cz/2023/07/03/demystifying-pratt-parsers.html
#

shopt -so errexit
shopt -so nounset
shopt -so pipefail
shopt -s  lastpipe

# null denotation
nud() {
	if ! [[ -v tokens[tokeni] ]]; then return 1; fi

	local token value
	read -r token value <<<"${tokens[tokeni]}"

	case "$token" in
		NUM)
			(( tokeni++, results[resulti++] = value ))
			;;

		SUB)
			(( tokeni++ ))
			nudled 0
			(( results[resulti - 1] = -results[resulti - 1] ))
			;;
	esac
}

# left denotation
led() {
	local -ri max_precedence=$1

	if ! [[ -v tokens[tokeni] ]]; then return 1; fi

	local token value
	read -r token value <<<"${tokens[tokeni]}"
	if (( max_precedence >= precedece_table[$token] )); then return 1; fi

	# precedence's good; advance token
	(( tokeni++ ))

	# Handle right associativity
	if [[ "${assoc_table[$token]}" == R ]]; then
		nudled $(( precedece_table[$token] - 1))
	else
		nudled $(( precedece_table[$token] ))
	fi

	local -i a b

	case "$token" in
		ADD | SUB | MUL | DIV | EXP)
			(( b = results[resulti - 1], a = results[resulti - 2] ))

			case "$token" in
				ADD) (( results[resulti - 2] = a  + b )) ;;
				SUB) (( results[resulti - 2] = a  - b )) ;;
				MUL) (( results[resulti - 2] = a  * b )) ;;
				DIV) (( results[resulti - 2] = a  / b )) ;;
				EXP) (( results[resulti - 2] = a ** b )) ;;
			esac

			unset "results[$(( --resulti ))]"
			;;
	esac
}

nudled() {
	local -ri max_precedence=$1
	nud
	while led "$max_precedence"; do :; done
}

parse() {
	local -A precedece_table=(
		['ADD']=1
		['SUB']=1
		['MUL']=2
		['DIV']=2
		['EXP']=3
	)

	local -A assoc_table=(
		['ADD']=L
		['SUB']=L
		['MUL']=L
		['DIV']=L
		['EXP']=R
	)

	local -i resulti=0
	local -a results=()

	local -i tokeni=0
	local -a tokens=()
	readarray -t tokens

	if ! nudled 0; then return 1; fi

	printf '%d\n' "${results[0]}"
}

tokenize() {
	local -ar token_regexes=(
		'ADD,\+'
		'SUB,-'
		'MUL,\*'
		'DIV,/'
		'EXP,\^'
		'NUM,[[:digit:]]+'
		'WS,[[:space:]]+'
	)

	local token_re
	local -ra tokens=("${token_regexes[@]%%,*}")
	printf -v token_re '|(^%s)' "${token_regexes[@]##*,}"
	token_re=${token_re:1}

	local -i line=0
	local -i char=0

	while IFS= read -r token; do
		(( ++line ))
		char=1
		while [[ -n "$token" ]]; do
			if ! [[ "$token" =~ $token_re ]]; then
				printf 'unrecognized token at line %d, char %d: %s\n' "$line" "$char" "${token:0:5} ..." >&2
				return 1
			fi

			token="${token:${#BASH_REMATCH[0]}}"
			char+=${#BASH_REMATCH[0]}

			for (( token_i = 1; token_i < "${#tokens[@]}"; token_i++ )); do
				if [[ -v BASH_REMATCH[token_i] && -n "${BASH_REMATCH[token_i]}" ]]; then
					printf '%s %s\n' "${tokens[token_i - 1]}" "${BASH_REMATCH[token_i]}"
				fi
			done
		done
	done
}

test-case-1() {
	local -i wanted=7
	local actual

	actual=$(
		tokenize <<-'SRC' | parse
			1 + 2 * 3
		SRC
	)

	if (( wanted != actual )); then
		printf 'test failed: wanted %d; got %d\n' "$wanted" "$actual"
	fi
}

test-case-2() {
	local -i wanted=6
	local actual

	actual=$(
		tokenize <<-'SRC' | parse
			2 ^ 3 - 2
		SRC
	)

	if (( wanted != actual )); then
		printf 'test failed: wanted %d; got %d\n' "$wanted" "$actual"
	fi
}

test-case-3() {
	local -i wanted=512
	local actual

	actual=$(
		tokenize <<-'SRC' | parse
			2^3^2
		SRC
	)

	if (( wanted != actual )); then
		printf 'test failed: wanted %d; got %d\n' "$wanted" "$actual"
	fi
}

test-case-4() {
	local -i wanted=-81
	local actual

	actual=$(
		tokenize <<-'SRC' | parse
			1 + 2 - 3 * 4 + 5 / 6^7 - 8 * 9
		SRC
	)

	if (( wanted != actual )); then
		printf 'test failed: wanted %d; got %d\n' "$wanted" "$actual"
	fi
}

test-case-5() {
	local -i wanted=-4
	local actual

	actual=$(
		tokenize <<-'SRC' | parse
			2 * -2
		SRC
	)

	if (( wanted != actual )); then
		printf 'test failed: wanted %d; got %d\n' "$wanted" "$actual"
	fi
}

all-tests() {
	local -i tests=0
	local -i passed=0
	local -i failed=0

	compgen -A function test- | while read -r fn; do
		(( ++tests ))
		if "$fn"; then
			printf '.'
			(( ++passed ))
		else
			(( ++failed ))
		fi
	done
	printf '\n\n'
	printf 'Result: %d tests; %d passed; %d failed\n' "$tests" "$passed" "$failed"
}

all-tests

$ ./pratt.sh 
.....

Result: 5 tests; 5 passed; 0 failed