8
$\begingroup$

Main Problem

I'm currently dealing with an document with some expression in the form

"some text <content1 a=1 b=22> some other <content2 c=3 d=45 e=5> rubbish"

and I would like to get a result like:

{{content1,{a->1,b->22}},{content2,{c->3,d->45,e->5}}}

It's easy to figure out the "" pattern by the following code:

patt = Shortest[Except[" " | "="] ..];

StringCases["some text <content1 a=1 b=22> some other <content2 c=3 d=45 e=5> rubbish",
 ("<" ~~ head : patt ~~ cont : ((" " ~~ patt ~~ "=" ~~ patt) ..) ~~ ">") :> {head, cont}]

Then I get something like {{"content1", " a=1 b=22"}, {"content2", " c=3 d=45 e=5"}}

I can write another program and apply another StringCases to the second argument and get the result, but I think it's quite unnecessary:

result[[;; , 2]] = StringCases[#, " " ~~ name : patt ~~ "=" ~~ value : patt :> (name -> value)] & /@result[[;; , 2]];

We can know that this process has been done by the previous StringCases.(Though I don't know how to track it......Normal method using pattern/;(Echo[result];True) won't work here, the reason it explained below)

So my question is, how to get the result all in one StringCases?


Some difficulty for me

I once tried to use pattern/;(Sow[variable],True) to get pattern test's result and then process it. but as far as I know, PatternTest test each character, thus cannot be used. but Condition requires "defined" pattern with a variable name assigned to it, like a__ or a:patt, the problem of this is that when using (a:patt).. it means the result must be in the form like a,a,a,a but not patt,patt,patt,patt where patt in different place could be different. It can be easily confirmed by simply adding a tiny a: in the code:

StringCases["some text <content1 a=1 b=22> some other <content2 c=3 d=45 e=5> rubbish",
 ("<" ~~ head : patt ~~ cont : ((" " ~~ a:patt ~~ "=" ~~ patt) ..) ~~ ">") :> {head, cont}]

{}

How to solve this problem?


Some other explanation

We can observe the whole pattern matching process of Repeated using a simpler example:

patt = Shortest[Except[" " | "="] ..];

StringCases["some text <content1 a=31 b=2> some other <content2 c=3 
d=34 e=2> rubbish", ("<" ~~ 
   head : patt ~~ (((" " ~~ patt ~~ "=" ~~ 
         patt)?((Echo@#; True) &)) ..) ~~ ">")]

We can see that pattern matcher will match the sequence by adding characters and really know when to stop and where is a proper match, and the only thing we need to do is to find out how to let it speak it out. in this example, simply adding ? will work and return us a series of characters. Here we can know each recurrence period easily, however, in more general cases, we cannot use this type of result.

So one solution to this problem is to write a PatternTest but let it use the whole expression as input instead of character by character.

$\endgroup$
  • $\begingroup$ Great question! I have always used multiple passes (i.e. nested StringCases) for this, and I know no other way. If WReach, who has always had a better understanding of the fundamentals than I, says "the goal is not achievable in general" I feel assured that this must be the case, barring some undocumented internal functionality. I think a phrase PatternTest for strings would be a wonderful addition to the language, allowing use more similar to that with common expressions. $\endgroup$ – Mr.Wizard Aug 6 '16 at 9:07
  • $\begingroup$ Related: (32515) $\endgroup$ – Mr.Wizard Aug 6 '16 at 10:51
  • $\begingroup$ Nearly a duplicate: (89160) (and more evidence of my failing memory that this did not come to hand sooner) $\endgroup$ – Mr.Wizard Aug 6 '16 at 10:52
  • $\begingroup$ Thanks for your praise @Mr.Wizard :) and 89160 is a really similar question, but this question is more general in some aspects I think. $\endgroup$ – Wjx Aug 6 '16 at 12:09
11
$\begingroup$

One solution would be to embed the second StringCases expression that parses the name/value pairs within the replacement rule of the first StringCases expression that extracts the elements:

$text = "some text <content1 a=1 b=22> some other <content2 c=3 d=45 e=5> rubbish";

patt = Shortest[Except[" " | "="] ..];

StringCases[$text
, ("<" ~~ head : patt ~~ cont : ((" " ~~ patt ~~ "=" ~~ patt) ..) ~~ ">") :>
  {head, StringCases[cont, " " ~~ name : patt ~~ "=" ~~ value : patt :> (name -> value)]}
]

(* {{content1, {a->1, b->2}}, {content2, {c->3, d->4, e->5}}} *)

Note that patt does not correctly extract the values (for example, b->2 should be b->22). Perhaps we should consider something like this:

StringCases[$text
, "<" ~~
   head : WordCharacter.. ~~
   cont : ((Whitespace ~~ WordCharacter.. ~~ "=" ~~ WordCharacter..) ..) ~~
   ">" :>
    { head
    , StringCases[cont
      , Whitespace ~~ name:WordCharacter.. ~~ "=" ~~ value:WordCharacter.. :>
        (name -> value)
      ]
    }
]

(* {{content1, {a->1, b->22}}, {content2, {c->3, d->45, e->5}}} *)

If the toy text is not representative of the actual data that will be processed, then the string patterns might need to be revised even further.

Is a single use of StringCases possible?

If we wish to parse the name-value pairs in a single pass through StringCases, we need to come up with something effectively like...

StringCases[$text
, (  "<"
  ~~ head:WordCharacter..
  ~~ Repeated[Whitespace~~name1:WordCharacter.. ~~ "=" ~~ value1:WordCharacter.., {0, 1}]
  ~~ Repeated[Whitespace~~name2:WordCharacter.. ~~ "=" ~~ value2:WordCharacter.., {0, 1}]
  ~~ Repeated[Whitespace~~name3:WordCharacter.. ~~ "=" ~~ value3:WordCharacter.., {0, 1}]
  ~~ Repeated[Whitespace~~name4:WordCharacter.. ~~ "=" ~~ value4:WordCharacter.., {0, 1}]
  ~~ Repeated[Whitespace~~name5:WordCharacter.. ~~ "=" ~~ value5:WordCharacter.., {0, 1}]
  ~~ ">"
  ) :>
  { head
  , {name1 -> value1, name2 -> value2, name3 -> value3, name4 -> value5} //
      DeleteCases["" -> ""]
  }
]

(* {{content1, {a->1, b->22}}, {content2, {c->3, d->45, e->5}}} *)

... except without having an upper limit on the number of pairs, and without it being so horribly verbose.

Mathematica presents numerous obstacles to this goal, most of which are noted in the question:

  • If a pattern is named within a repeating group, then all members of the group are constrained so that the named portions match. In the case at hand, this forces all the names within an element's name/value pairs to be the same (and similarly, all values the same).
  • If a pattern is not named within a repeating group, there is no way to access its value except by pattern test (even for regular expressions since the PCRE engine only remembers the last value for a repeated capture group).
  • But if a pattern test is used, it is called for each matched character individually instead of for the whole matched string.
  • Even if we use a pattern test, we cannot rely upon the order in which characters are supplied to it since the pattern-matcher may back-track and present us with any given character multiple times.

Given these considerations, the goal is not achievable in general.

However...

In this particular case, if the supplied string is well-formed, then the pattern matcher need never back-track. So this opens a tiny window through which we can squeeze a heinous hack:

Module[{name, value, rules}
, StringCases[
  $text
  , (  "<"
    ~~ (head:WordCharacter.. /; (rules = {}; True))
    ~~ (Whitespace /; (name = ""; True))
    ~~ (  WordCharacter.. ? ((name = StringJoin[name, #]; True)&)
       ~~ ("=" /; (value = ""; True))
       ~~ WordCharacter.. ? ((value = StringJoin[value, #]; True)&)
       ~~ (Whitespace|">") ? ((AppendTo[rules, name -> value]; name = ""; True)&)
       )..
    ) :> { head, rules}
  ]
]

Most of the subpatterns in this expression are guarded by either a condition or a pattern test. These will collectively be referred to as "tests". Each test is unconventional in that it incurs a side-effect before unconditionally returning true. These side-effects are used to gather up the matched parts and slowly assemble them into the final result. In particular:

  • As each "head" is matched, a list holding its set of rules is set to be empty.
  • When the following whitespace is matched, the name variable is set to the empty string.
  • As each name character is matched, it is appended to name variable.
  • When the equal sign is matched, the value variable is set to the empty string.
  • As each value character is matched, it is appended to the value variable.
  • When the space or greater-than character is reached at the end of a value, a rule of the form name -> value is appended to the rule list and the name variable is reset to blank ready for the next pair (if any).
  • Finally, when the entire element has been matched, the result is a list of the head along with its rules.

This whole process is crucially dependent upon there being no back-tracking within the pattern matcher. It may work in this particular case, but this strategy is not applicable to more complex patterns or input strings that could be considered ill-formed.

For my part, I consider this hack to be too tricky. I would recommend just accepting the fact that portions of the input string will need to be scanned at least twice in order to fully parse them. If such rescanning is impractical for the real application then I think a custom parser should be implemented.

Parse as HTML?

As a completely different strategy, we could observe that the input string very much resembles HTML and process it as such:

Cases[ImportString[$text, {"HTML", "XMLObject"}]
, XMLElement[tag_, attrs_, ___] :> {tag, attrs}
, {4, Infinity}
]

(* {{content1, {a->1, b->22}}, {content2, {c->3, d->45, e->5}}} *)

The level range {4, Infinity} was carefully chosen to ignore the html and body elements that the parser wraps around any HTML fragments.

$\endgroup$
  • $\begingroup$ The second solution is neat and fit my actual need I shall say. But I would like to go a bit further about the first solution. I suppose the first solution is similar as mine, but merge everything altogether with one sentence, but still, two StringCases is presented. I would like to have a solution with only one StringCases but with a modified pattern or some Reap and Sow outside the StringCases to do the accumulation job or so. $\endgroup$ – Wjx Aug 6 '16 at 5:21
  • $\begingroup$ My main point is, as the pattern matcher has already found out each recurrence, why should we write another piece of code doing it again? I suppose the pattern matcher works like: " a=1" is already a proper piece, then " b=22" is a proper piece, then ">" cannot be a beginning of a proper piece, repetition stops here. then the whole thing will be assigned to cont. While I want to interfere with this process and let the pattern matcher speak up and present me with those " a=1" stuffs. $\endgroup$ – Wjx Aug 6 '16 at 5:25
  • $\begingroup$ I've edited the question, please check the new explanation. $\endgroup$ – Wjx Aug 6 '16 at 5:47
  • 1
    $\begingroup$ I added the section "Is a single use of StringCases possible?" $\endgroup$ – WReach Aug 6 '16 at 7:28
  • $\begingroup$ This is AWESOME!!!!!! A thousand thanks! but I still believe there will be a neat way to do this. $\endgroup$ – Wjx Aug 6 '16 at 11:33
6
$\begingroup$

Here is a crude attempt at a PatternTest for phrases (sequences of characters). It is rather hacky and probably extremely fragile for the reasons given by WReach.

The syntax is phrasetest[pat, func]

The idea is to supply an unconditionally true PatternTest to the pattern pat, which assembles the individual characters into a string as a side effect. Once the pattern provisionally matches, the assembled string is tested by func in a Condition. If the test returns False the string is reset to empty and the Condition fails, otherwise the Condition succeeds and the pattern matches. An additional trivial PatternTest resets the string for next time.

phrasetest[pat_, func_] := Module[{s = ""},
  ((pat?((s = s <> #; True) &)) /; func[s] || (s = ""))?((s = ""; True) &)]

A simple example - the pattern is BlankSequence[] and the test is for a string length of 3:

pt = phrasetest[__, StringLength[#] == 3 &];

StringCases["123abc456", x : pt :> StringReverse[x]]
(* {"321", "cba", "654"} *)

With multiple phrasetests you could pick out the various parts of the string and collect them with Sow. In this example I've used Echo instead:

patt = Except@Characters[" =<>"] ..;

pt0 = phrasetest[patt, (Echo[#, "head"]; True) &];    
pt1 = phrasetest[patt, (Echo[#, "variable"]; True) &];    
pt2 = phrasetest[patt, (Echo[#, "value"]; True) &];

StringCases["some text <content1 a=31 b=2> some other <content2 c=3 d=34 e=2> rubbish",
 ("<" ~~ pt0 ~~ (" " ~~ pt1 ~~ "=" ~~ pt2) .. ~~ ">")]

enter image description here

Of course the result from StringCases is wrong, you would need to use Sow/Reap and do further processing on the output. It doesn't fulfil the desire to do everything inside a single StringCases, but it does show a sort of pattern test for substrings.

$\endgroup$
  • $\begingroup$ A good try! This is an great add on for @WReach's answer! $\endgroup$ – Wjx Aug 7 '16 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.