Pattern matching resources

Lots of text manipulation programs naturally fall into three phases:

1. extract data from text by pattern matching,
2. perform calculations with the data,
3. write the answers back into new text using a template.

Phase 3 is, to a certain extent, catered for by SWI OS_SubstituteArgs, but there appear to be no native RISC OS resources for phase 1. The PCRE (Perl Compatible Regular Expression) library is rather large and not all that efficient compared to the leaner and more modern PEGs (Parser Expression Grammars), which have only become more popular since 2004. If one were to have a relocatable module providing a PEG virtual machine what would its interface look like? Perhaps an SWI with entry:

R0 pointer to string to be analyzed,
R1 pointer to PEG pattern,
R2 pointer to buffer for captured indices
R3 length of buffer

R0 number of characters matched.

More software for RISCOS is always good. With the speed of ARM processors it could be done very quickly…I must admit I don’t have an immidiate use for it.

There is the RegEx module which is available from Stefan Bellon.

I have a StrongHelp manual, and a manual for Regex itself, on my site .

I use the module with Basalt to provide keywords such as SEARCH, MATCH and REPLACE

Martin Avison has a application for testing regex patterns.

I have a StrongHelp manual …

I have just realised that I have an updated manual that I have not uploaded. This is not significantly different, but adds details about Stefan and Martin.

I wrote an article in Drag’nDrop Vol 2 No 2 about PEGs.

The notion of a PEG has been around, under different names, since the 1970s. Birman (1970/73) called it a TMG Recognition Schema, where TMG stood for Techniques and Methodologies Group. Aho (1972) called it a TDPL or Top Down Parsing Language. The name PEG was coined by Bryan Ford (2004), who revived the concept and pointed out its advantages.
PEGs do have considerable advantages over Regular Expression Grammars for most computing problems. They run faster, they recognize a wider class of strings, and they require far fewer lines of code to
implement. The source code for the PCRE (Perl Compatible Regular Expression) library is nearly a megabyte in size. That for Lpeg is 50K. The trouble with the traditional pattern-matching syntax is that it conflates patterns with strings, in which certain characters, the magic characters, carry a special meaning. That means, because those characters are also needed in their unmagical sense, that an escape-character convention is needed; and that is a recipe for unreadability. Lpeg has a much cleaner syntax because it recognizes that patterns and strings are different datatypes.

So PEGs, though around since 1970, did not gain much traction till 2004, long after the early days of RISC OS. I noticed recently that they seem to be becoming more popular, and as they look easier to code than RegExes, maybe this would be an interesting project for an ARM assembler enthusiast? There are one or two papers detailing the instructions for a simple virtual machine for parsing, with state given by an index into the text to be parsed, an index into the VM instructions (program counter), a stack for saving indices when backtracking is needed, and a boolean for success/failure.

An observation. What is the best programming language to use for a project? Usually the answer is “whichever one you’re least likely to screw up in”.

regexps are notoriously opaque, and we already have a number of different ones (in effect) under RISC OS – GSTrans, ReadArgs, Zap, StrongEd (I presume) – and they’re all different.

If one were going to abstract that (and it’s a good idea) I would like to see it completely abstracted, so the API allows choice of syntax, rather than imposing a new one.

If I have to write a regexp, I’d like to write one in the syntax I’m most familiar with. Probably.

I am writing up some notes on pattern matching which I will put on my website soon. The idea at the back of my head is a library of BASIC assembler routines. The patterns are Parser Expression Grammars – slightly different from regexps because alternatives are prioritized. Thus

A|B
match with A and if that fails try B

Which is great, but for efficiency one would want a Create/Use/Discard API, in addition to a DoItAllInOneGo convenience call.

My suggestion was to not limit the API to one particular syntax:

SYS"Pattern_Create","regexp","s/this/that" TO pattern SYS"Pattern_Replace","Fancy this?",pattern TO a$ SYS"Pattern_Discard",pattern

SYS"Pattern_Create","PEG","A|B" TO pegpattern SYS"Pattern_Create","Zap","\< \%" TO zappattern SYS"Pattern_Create","file","!Spr*" TO filepattern

I think I see what you are getting at. But a pattern is like a program source; it must be compiled or interpreted to act on a piece of text. I am not too bothered about the concrete syntax – that is window dressing. But the abstract syntax is another matter. That has to be fixed before one sets out. Simpler to test out a pattern matcher as a standalone application first. Too complicated to jump in with a relocatable module until an application is sorted.

basically one captures where things match, rather than what , which one can do afterwards anyway by extracting a substring.

Which is how the RegEx module presents results, except the pointers are in group registers, not stacked. RegEx is an implementation of the Posix RegexLib.

Which is great, but for efficiency one would want a Create/Use/Discard API

Basalt using RegEx has, among other ways:

pattern%=COMPILE(pattern$)
SEARCH target$,pattern%
COMPILE CLEAR pattern%

in addition to a DoItAllInOneGo convenience call.

And Basalt has:

SEARCH target$,pattern$

[nemo] My suggestion was to not limit the API to one particular syntax
[Gavin] But the abstract syntax is another matter.

Of course, but my point is that as far as regexp goes this already exists, and can be used with a BASIC veneer. If you do not want Basalt you can use a library.

It is another question as to whether the more general cases, including PEG, are important.

It is another question as to whether the more general cases, including PEG, are important.

Probably not. But I thought the exercise of implementing a PEG VM would appeal to ARM assembler enthusiasts.

I read a bit about PEG and it seemed to me to be a case of swings and roundabouts in comparison to regular expressions. Nevertheless, an implementation of PEG is going to be interesting.

The problem of the various regexp systems already in RO programs, and their incompatible syntax, is real for the user. Because they are integral, I am not sure that there is scope to unify them in the way proposed. It is a case of: “I would not start from here”.

“If I were going there I wouldn’t start here”

Well, RO has been in need of a motto…

Steve, where’s your website these days? kappa.me.uk seems neglected.

I wish this woeful forum had sigs.

Beginnings of notes here.

Gavin wrote, elsewhere

X_enter STR PC, [stack, #-4]!

Pretty sure that’s not what you meant.