taskText Extractor TXR - Tasks: task #11437, Implement structural pattern...


You are not allowed to post comments on this tracker with your current authentication level.

task #11437: Implement structural pattern matching and possibly unification.

Submitted by:  Kaz Kylheku <kkylheku>
Submitted on:  Thu 13 Oct 2011 01:07:54 AM UTC  
Should Start On:  Wed 12 Oct 2011 07:00:00 AM UTC Should be Finished on:  Wed 12 Oct 2011 07:00:00 AM UTC
Category:  None Priority:  5 - Normal
Status:  None Privacy:  Public
Percent Complete:  0% Assigned to:  None
Open/Closed:  Open Effort:  64.00

Thu 13 Oct 2011 01:07:54 AM UTC, original submission:

The syntactic ground work is already laid for this. In the TXR syntax, within the parenthesized Lisp expressions, it is possible to use the notation @ABC and @( ... ). These inner @ symbols have a different meaning from the outer ones, but a similar spirit. They indicate "I am meta". Everything not prefixed by @ represents itself.

The purpose of this syntax is to support future work in pattern matching.

For instance the structure @(a @b c) means "match the symbol A, then match something and bind it to the variable B, then match the symbol B". The A and B are literals representing themselves, but @b is a metavariable. Similarly something like (a @(skip) b c) could mean "match the symbol A, then skip any number of objects until there is a match for B and C". But (a (skip) b c) means match the literal structure (a (skip) b c).

The meta syntax translates like this:

@A -> (sys:var A)

@(ITEM ...) -> (sys:expr ITEM ...)

So the meta pieces are easy to identify in a recursive walk of the structure structure.

It would be nice to have a pattern matcher with a rich set of primitives for doing various things. E.g.

@(pmatch ("foo" @a "bar") x)

Succeed if x matches the list ("foo" <something> "bar") and bind the a variable to the <something>.

It would also be nice to have full two-way unifier:

@(unify ("foo" @a) (@b "bar"))

whereby b ends up with "foo" and a ends up with "bar", if this succeeds. The unifier doesn't have to have as rich a syntax for doing complicated matches.

With this in place, it might not be a bad idea to have a way of representing a knowledge database in TXR which can be queried, paving the way for logic programming interleaved with text extraction.

The knowledge database can work with backracking. That is, as text is being matched, something can be inserted into the database. But the newly learned knowledge is forgotten if the matching backtracks, just like the way variables are thrown away.

Kaz Kylheku <kkylheku>
Project Administrator


No files currently attached


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by kkylheku (Submitted the item)

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.




    No changes have been made to this item

    Back to the top

    Powered by Savane 3.3