Lambda the Ultimate

inactiveTopic Perl Style Regular Expressions in Prolog
started 1/20/2001; 3:41:16 AM - last post 1/22/2001; 12:20:19 PM
Ehud Lamm - Perl Style Regular Expressions in Prolog  blueArrow
1/20/2001; 3:41:16 AM (reads: 663, responses: 1)
Perl Style Regular Expressions in Prolog
A Prolog system for processing Perl style regular expressions can be implemented via the following steps.

  1. Defining the BNF grammar of Perl-style regular expressions.
  2. Defining a Prolog representation of Perl regular expressions.
  3. Build a DCG parser for Perl regular expressions.
  4. Building a regular expression matcher in Prolog.

This is a useful case study of symbolic computing in Prolog and also an exploration of the semantics of regular expressions.

This seems like fun. It connect well with our recent discussions of SNOBOL, Icon and Rexx.

Notice, once more, that we should be careful with the term 'regular expressions.' When you start adding things like backtracking, and context you soon exceed the power of what computer science calls REs.

There are several beautiful SNOBOL examples showing how SNOBOL pattern matching can be used for recognizing CFLs.
Posted to "" by Ehud Lamm on 1/20/01; 3:43:05 AM

andrew cooke - Re: Perl Style Regular Expressions in Prolog  blueArrow
1/22/2001; 12:20:19 PM (reads: 694, responses: 0)
This is very like the approach described here - I think you could even get the "less greedy" matches if you were careful (with lazy evaluation replacing backtracking). It's also similar (but less so) to the ML regexp code I posted way back and the approach used in chapter 8 of Cousineau and Mauny (although they have much less backtracking available).

(By similar I mean a bottom-up constructive approach that combines functions that match particular chunks - quite a contrast to the yacc world.)