Probably the simplest way to do this is to use the option
mathescape in a
\lstset command. This will not only allow you to use superscripts and subscripts, but will also give you access to other things you can do in mathmode. It may also do subtle and strange things to your formatting, but you can perhaps account for this where it matters to you.
R -> ε | $\ell$ | (R|R) | (RR) | R$^\ast$
$\ell\,$ -> a | b | c | $\cdots$