On Tue, 11 May 2004, Meng Weng Wong wrote:
The syntax of the SPF macro language can be described by a context-free
grammar.
It can be described with a regular grammar too -- there aren't any nesting
constructs in the SPF record.
But the SPF macro language does not support operations beyond a regular
grammar.
The second point is more important than the first. An SPF interpreter
can be implemented as a DFA. Therefore SPF is not Turing-complete,
with or without macros.
Actually, if the SPF macros could implement arbitrary regex
transformations it *would* be Turing complete. Note that SPF cannot be
implemented as a pure DFA because it has an auxiliary memory in the form
of the <current-domain>.
--
Tony Finch <dot(_at_)dotat(_dot_)at> http://dotat.at/