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.

Submitter:  Kaz Kylheku <kkylheku>
Submitted:  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
Assigned to:  None Percent Complete:  0%
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>
Group administrator

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

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)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    No changes have been made to this item

    Back to the top

    Powered by Savane 3.13-3230.
    Corresponding source code