Character search Algorithm
Donald 'Paddy' McCarthy
paddy3118 at netscape.net
Sat May 29 03:46:54 EDT 2004
Hi,
My problem is I'm trying to learn about the implementation of assertion
languages like PSL/Sugar in digital logic simulators.
The assertion language allows you to more easily say "if this signal
combination/sequence follows that signal combination/sequence then ..."
I feel that you should be able to think of this as the simulator
providing a stream of signal values over simulator time that could be
translated into a string of characters interleaved with clock cycle
markers. Then the temporal assertion could be translated into a regular
expression acting on the string.
When I make the mental analogy above, then I think of the practicle
problems of such an implementation. The first is, if you have a finite
bounded re - e.g. no infinite matches i.e. no plus or star characters in
the RE, but you have a simulator churning out a huge sequence of
characters, how do you do the RE match efficiently?
I am thinking of a program skeleton that looks something like this
psl_re = PSL_subset_to_RE(PSL)
simulator.start(psl_re.clock, psl_re.signals_to_capture)
for cycles_psl_signals in simulator.next_cycle():
if psl_re.optimised_search(cycles_psl_signals):
raise PSL_PRE_CONDITION_FOUND
It is the psl_re.optimised_search() routine that I am after.
Is there any way of computing how big a string buffer needs to be (call
it B), so that you could then maybe keep a sliding buffer of a minimum
of just the last 2*B characters, sliding along and matching in B
character increments and guarantee to find the matches?
Help, or alternative algorithms would be appreciated.
Thanks, Paddy.
More information about the Python-list
mailing list