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

Groups > comp.lang.php > #16533

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

Show all headers | View raw

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.

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

  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>

  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.

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.

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

-- 
PointedEars
Zend Certified PHP Engineer 
<http://www.zend.com/en/yellow-pages/ZEND024953> | Twitter: @PointedEars2
Please do not cc me. / Bitte keine Kopien per E-Mail.

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