Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.php > #16552

Re: Any recommendations on using PHP to parse marked-up text?

Show all headers | View raw

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Ben Bacarisse wrote:
>
>> "Christoph M. Becker" <cmbecker69@arcor.de> writes:
>>> Anyhow, what Thomas most likely wanted to convey is that
>>> preg_replace_callback() is not general enough to process all markup
>>> languages.
>> 
>> Seems unlikely. 
>
> How did you get that idea?  Christoph has understood me correctly.

Hmm... I wonder why you just cut, then, without comment my explanation
of why that's wrong.  Do you have nothing to say about that part?

>> Since his reference was to a theoretical article, the answer would be
>> equally theoretical, […]
>
> It is theoretical, but it has important implications in practice.  A 
> mathematician (or, at least an individual that – the record shows – appears 
> to have much interest in mathematics) like yourself should be able to 
> appreciate that.  And I had expected such a person to understand the 
> implications without needing to be spelled out for them.  Do not blame me 
> for your obtuseness.
>
>> I wonder if he'll ever say?
>
> Since some people need to have it spelled out for them, the not-so-new 
> argument (not even new in this newsgroup) goes as follows:
>
>   0. The Chomsky hierarchy classifies formal languages into four types,
>      depending on the type of formal grammars that they can be produced
>      with: Recursively enumerable (0), context-sensitive (1),
>      context-free (2), and regular (3).
>
>   1. (It can be showed by application of the pumping lemma for context-free
>      languages that) markup languages are context-free languages.
>
>      For example, the simplest markup language (that IMO deserves that
>      designation) consists of words in Latin letters that are surrounded by 
>      pairs of matching parentheses (also called a “bracket language”;
>      it helps to think of those parentheses as start-tag and end-tag of
>      an element, and the words as its content, respectively).  A context
>      free grammar that produces it contains the following productions:
>
>        S → (S)
>        S → SS
>        S → a
>        …
>        S → z
>
>      [Example application: S → (S) → (SS) → (SSS) → (foo)]

And yet '/( [a-z]+ | \( (?R) \) )+/x' matches the strings of this
language.  Maybe you just thought that saying "pumping lemma" would
sound intimidating?  I may have got the details wrong -- it's late --
but it is well known that a PCRE can match the strings (and only the
strings) of your example language.

>   2. From the Chomsky hierarchy follows by applying *set theory*: While 
>      “every regular language is context-free” (ibid.), not every
>      context-free language is regular.
>
>   3. *Regular* expressions are (WLOG) a way to describe *regular*
>      languages *only*.
>
>   4. It can be showed by application of the pumping lemma for regular
>      languages that there are markup (and programming) languages that
>      are not regular.  For example, XML, despite its well-formedness,
>      is not a regular language.
>
>   5. Therefore, *regular* expressions are in general not suited to parse 
>      arbitrary *markup* (or programming) languages; instead, implementations
>      of non-deterministic push-down automata (stacks) are.
>
>   6. preg_replace_callback(), as all preg_*() functions in PHP, supports 
>      Perl-Compatible *Regular* Expressions (PCRE).
>      <http://php.net/pcre>

All this is just bluster.  Regular languages are not relevant here.
What regular language does '/([ab]*)\1/' match?  Can you even say where
in Chomsky's hierarchy the languages matched by PCREs lie?

>   7. While PCRE support recursion to some extent (which implements a stack),
>      and therefore can to some extent solve the problem that regular
>      expressions when applied to arbitrary bracket languages always either
>      match too much (greedy) or too little (non-greedy), a *single* PCRE
>      fails to parse an arbitrary markup language at a fundamental
>      level: For a non-trivial markup language you would have to use 
>      alternation, and the *first* *next* match wins, not the *next* 
>      *longest* one, different to what would be required by a markup
>      parser.

And this just shows you didn't read what I wrote, or, if you did, you
loaded it up with your own inferences.  There was no suggestion that
somehow a single PCRE was to be used.  Nor was there any suggestion that
all the parsing should be done by the matching engine -- that's where
the callback comes in.

> With that said, regular expressions can be useful in parsing markup 
> languages (BTDT).  But they should not be the first consideration when 
> attempting to do that.  There are tools better suited to the purpose.

That's so vague as to be almost content-free.  The only concrete remark
is either wrong or assumes facts not yet established.  PCREs have been,
for some time, my first consideration when processing some kinds of
markup -- particularly when, as here, I can choose the notation myself.
As you say, BTDT.  Obviously YMMV.

These posts all occurred within a specific context but you often like to
strip remarks from their natural home.  My reply was to a post that
suggested using explode or character-by-character processing.  That does
not suggest that a complex grammar was going to be involved.  Using
multiple PCREs with callbacks is a good way to process simple languages,
but as soon as it because clear the something more sophisticated might
be envisaged, I suggested using XML and leveraging existing tools.  Even
if James goes with a new syntax that is a bit XML-like, processing with
the PCRE functions might still be a good way forward since the tags
don't need to nest (note: tags not elements, and XML-like not XML).

> See also <http://stackoverflow.com/a/1732454/855543> :)

No thanks.

-- 
Ben.

Back to comp.lang.php | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-18 12:47 +0000
  Re: Any recommendations on using PHP to parse marked-up text? Arno Welzel <usenet@arnowelzel.de> - 2016-02-18 15:52 +0100
    Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-20 18:28 +0000
  Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-18 14:56 +0000
    Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-18 22:14 +0100
      Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-18 21:45 +0000
        Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-18 23:09 +0100
          Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-19 01:15 +0000
            Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-19 02:45 +0100
              Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-19 12:03 +0000
                Re: Any recommendations on using PHP to parse marked-up text? Tim Streater <timstreater@greenbee.net> - 2016-02-19 12:17 +0000
                Re: Any recommendations on using PHP to parse marked-up text? "Christoph M. Becker" <cmbecker69@arcor.de> - 2016-02-19 14:18 +0100
                Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-19 14:02 +0000
                Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-20 20:31 +0100
                Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-21 01:39 +0000
                Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-21 11:33 +0100
                Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-21 12:53 +0000
    Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-20 18:29 +0000
      Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-20 20:32 +0100
  Re: Any recommendations on using PHP to parse marked-up text? Jerry Stuckle <jstucklex@attglobal.net> - 2016-02-18 10:43 -0500
    Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-20 18:51 +0000
      Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-20 20:08 +0000
        Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-20 21:22 +0100
          Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-20 23:40 +0000
            Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-21 11:39 +0100
              Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-21 13:09 +0000
        Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-20 20:24 +0000
          Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-20 22:35 +0000
            Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-21 08:37 +0000
              Re: Any recommendations on using PHP to parse marked-up text? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-02-21 10:55 +0000
                Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-21 13:25 +0000
          Re: Any recommendations on using PHP to parse marked-up text? Jerry Stuckle <jstucklex@attglobal.net> - 2016-02-20 17:50 -0500
            Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-21 08:49 +0000
              Re: Any recommendations on using PHP to parse marked-up text? Jerry Stuckle <jstucklex@attglobal.net> - 2016-02-21 10:05 -0500
      Re: Any recommendations on using PHP to parse marked-up text? Jerry Stuckle <jstucklex@attglobal.net> - 2016-02-20 17:45 -0500
        Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-21 09:01 +0000
          Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-21 11:46 +0100
            Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-21 12:36 +0000
              Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-21 14:39 +0100
                Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-21 13:40 +0000
                Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-21 14:46 +0100
                Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-21 14:57 +0000
          Re: Any recommendations on using PHP to parse marked-up text? Jerry Stuckle <jstucklex@attglobal.net> - 2016-02-21 10:10 -0500
            Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-21 17:50 +0000
              Re: Any recommendations on using PHP to parse marked-up text? Jerry Stuckle <jstucklex@attglobal.net> - 2016-02-21 14:08 -0500
      Re: Any recommendations on using PHP to parse marked-up text? Arno Welzel <usenet@arnowelzel.de> - 2016-02-21 18:35 +0100
        Re: Any recommendations on using PHP to parse marked-up text? James Harris <james.harris.1@gmail.com> - 2016-02-21 17:55 +0000
          Re: Any recommendations on using PHP to parse marked-up text? Arno Welzel <usenet@arnowelzel.de> - 2016-02-22 16:38 +0100
  Re: Any recommendations on using PHP to parse marked-up text? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-18 22:06 +0100
  Re: Any recommendations on using PHP to parse marked-up text? Ian Collins <ian-news@hotmail.com> - 2016-02-27 15:58 +1300

csiph-web