[PHP] Recursieve LIFO-parser

zaterdag 13 december 2003 00:38

Acties:

0 Henk 'm!

Tux

Topicstarter

Zo ik ben weer even uit #devschuur gekropen om een topic op te stellen

Ik probeer al tijden een Stack based parser te maken voor UBB-codes (sorry dat ik het zo noem .oisyn

) en dat mislukte steeds. Aan het begin kwam er helemaal niets uit en mijn laatste probeersel werkte op zich wel maar zit vol met kleine bugjes.

Ik heb er een hele tijd niets aan gedaan maar toen ik zag dat Prammenhanger bezig was met een recursieve FIFO parser kreeg ik ineens weer inspiratie en besloot ik een parser te schrijven (een stukje code geleend uit de parser van Pram voor maken van stack en de regexes ook gepikt

)
Deze moest natuurlijk wel LIFO worden, dus ik aan de slag

Het bouwen van de stack gaat goed, het parsen gaat op zich goed en de rechten of een tag wel als child mag werken goed. Alleen als ik bijvoorbeeld een code invoer als:

Spef! dan krijg ik als output:

code:

1	<u><b>Spef!</b></u>

En dat is natuurlijk niet helemaal wat ik wil

Het probleem zit hem bij het wegschrijven van de data in de buffer, waar het dus niet in de goede volgorde wordt neergezet.

Ik heb het op de gewone manier geprobeerd door de allemaal achter elkaar op een string te gooien, dat werkte niet. Toen probeerde ik het in een array te gooien array (predata, content, postdata) zodat ik het steeds in het midden kan zetten. Maar dit werkt ook niet

Ik ben inmiddels een beetje wanhopig geworden van iets wat waarschijnlijk makkelijk op te lossen is maar ik kan het echt niet vinden.

Hier is de source:

PHP:

<?php

define ("TML_OPEN_TAG", "/\\[([a-zA-Z]+)([^\\[\]]*)\]/");
define ("TML_CLOSE_TAG", "/\\[\/([a-zA-Z]+)([^\\[\]]*)\]/");
define ("TML_LEFT_DELIMITER", "[");
define ("TML_RIGHT_DELIMITER", "]");
define ("TML_CLOSE", "/");

class Tml
{
    var $tags = array (
            'b' => array ('<b>', '</b>', array ('u','i','s')),
            'u' => array ('<u>', '</u>', array ('b','i','s')),
            'i' => array ('<i>', '</i>', array ('u','b','s')),
            's' => array ('<s>', '</s>', array ('u','b','i'))
            
            );
            
    var $queue = array ();
    var $stack = array ();
    var $temp;
    var $output;
        
    function make_stack ( $input )
    {
        return preg_split ('/(\\[[^\\[\]]+\]|[\r\n])/', $input, -1, 
PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY );
    }
    
    function is_allowed ( $input )
    {
        foreach ( $this->stack as $parent )
        {
            if ( !isset ( $this->tags[ $parent ] ) || !in_array ( $input, $this->tags[$parent][2] ) )
            {
                return false;
            }
        }
        return true;
    }
    
    function flatten ( $input )
    {
        
        foreach ( $input as $key => $value )
        {
            if (is_array ( $value ))
            {
                $this->flatten ( $value );
            }
            else 
            {
                $this->output .= $value;
            }
        }
        return $this->output;
    }
    
    function parse ( $input )
    {
        $this->queue = array_reverse ( $this->make_stack ( $input ) );
        return $this->flatten ($this->recurse ());
        //print_r ($this->recurse ());
    }
    
    function recurse ()
    {
        $buffer = array ('','','');
        
        while ( $token = array_shift ( $this->queue ) )
        {
            if ( preg_match ( TML_CLOSE_TAG, $token, $match ) )
            {
                if ( $this->is_allowed ( $match[1] ) )
                {
                    array_push ( $this->stack, $match[1] );                 
                }
            }
            elseif ( preg_match ( TML_OPEN_TAG, $token, $match ) )
            {
                $tag = $match[1];
                
                if ( in_array ( $tag, $this->stack ) )
                {                   
                    array_pop ( $this->stack );
                    
                    if ( count ( $this->stack ) > 0 )
                    {
                        
                        $buffer = array ($buffer[0] . $this->tags[ $tag ][0] . $buffer[1],
 $this->recurse (), $this->tags[ $tag ][1] . $buffer[2]);
                        print_r ($buffer);
                        $this->temp = "";                       
                    }
                    else 
                    {
                        $buffer = array ($buffer[0] . $this->tags[ $tag ][0] . $buffer[1], $this->temp .
 $this->flatten ($this->recurse ()), $this->tags[ $tag ][1] . $buffer[2]);
                        //print_r ($buffer);
                        $this->temp = "";                           
                    }
                }
                else 
                {
                    $buffer = array ($buffer[0] . TML_LEFT_DELIMITER . $token . TML_RIGHT_DELIMITER,
 $buffer[1] .
 $this->temp . $this->recurse (), TML_LEFT_DELIMITER . $tag . TML_RIGHT_DELIMITER . $buffer[2]);                    
                }
            }
            else 
            {
                $this->temp .= $token;
            }
        }       
        return $buffer;
    }
}
?>

Ik hoop dat iemand me kan helpen hiermee want de search levert op dit punt niets op.

edit:
Argh layout fucking

[ Voor 10% gewijzigd door Tux op 13-12-2003 00:38 ]

The NS has launched a new space transportation service, using German trains which were upgraded into spaceships.

zaterdag 13 december 2003 09:29

Acties:

0 Henk 'm!

MisterData

Wat ik bij m'n templateparser doe is een tree bouwen met al die tags erin. Ik heb drie typen tags: START_TAG, END_TAG en CONTENT_TAG (en eigenlijk ook ESCAPE_TAG, maar das een ander verhaal). In de parse functie loop ik door die lijst met elementen heen. Op het moment da t ik een START_TAG tegenkom, push ik die op de stack. Bij een END_TAG controleer ik of de laatst gepushte START_TAG overeenkomt met de eindtag. Is dit zo dan output ik die eindtag, en is dat niet zo, dan output ik net zolang een eindtag voor de START_TAG op de stack totdat ik bij de goede zit

zaterdag 13 december 2003 10:27

Acties:

0 Henk 'm!

Verwijderd

Hmm, die code komt me wel enigszins bekend voor

Heb jij de sprintf's eruit gesloopt, of heeft Prammenhanger dat gedaan? Die code was trouwens nog lang niet af natuurlijk, maar het was een leuk voorbeeld van een manier waarop je zoiets kunt maken.

Bovendien had ik 2 array's: 1 voor de configuratie van toelaatbare tags, en 1 voor de output van elk ubb element. Als je dat in 1 array doet, maakt dat je code veel ingewikkelder dan nodig is, en dan verdwaal je in de array[1][6][9] wirwar van code.

Met andere woorden: ik snap niet alle modificaties van de code.

Voor het overige publiek: hieronder de originele code, het resultaat van een paar uurtjes prutsen.

PHP:

define ( 'UBB_TOKEN',          '/(\\[[^\\[\]]+\]|[\r\n])/' );
define ( 'UBB_OPEN_TAG',       '/\\[([a-zA-Z]+)([^\\[\]]*)\]/' );
define ( 'UBB_CLOSE_TAG',      '/\\[\/([a-zA-Z]+)([^\\[\]]*)\]/' );
define ( 'UBB_SPECIAL',        '/\\[\*\]/' );
define ( 'UBB_DEFAULT_OUTPUT', '[%2$s]%1$s[/%2$s]' );
   
   
   
class UBBParser
{
   var $tag_hierarchy = array (
      'quote' => array ( 'b', 'i', 'url', 'img', 'list', 'code', 'quote' ),
      'b'     => array ( 'i', 'url', 'img' ),
      'i'     => array ( 'b', 'url', 'img' ),
      'url'   => array ( 'b', 'i', 'img' ),
      'list'  => array ( 'b', 'i', 'url', 'img', '*', 'list' ),
      '*'     => array ( 'b', 'i', 'url', 'img', '*', 'list' )
   );
   
   var $tag_output = array (
      'img'   => '[img]"%s"[/img]',
      'quote' => '<blockquote>%s</blockquote>',
      'b'     => '<strong>%s</strong>',
      'i'     => '<em>%s</em>'
   );
   
   var $queue;
   var $stack;

   
   
   function UBBParser ( $input )
   {
      $this->queue  = preg_split ( UBB_TOKEN, $input, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY );
      $this->stack  = array ();
   }
   
   
   
   function parse ( $input )
   {
      $parser = new UBBParser ( $input );
      
      return $parser->recurse ();
   }
   
   
   
   function recurse ()
   {
      $buffer = NULL;
      
      while ( $token = array_shift ( $this->queue ) )
      {
         if ( preg_match ( UBB_SPECIAL, $token, $match ) )
         {
            $buffer .= htmlentities ( $token );
         }
         else if ( preg_match ( UBB_OPEN_TAG, $token, $match ) )
         {
            $allowed = $this->is_allowed ( $match [ 1 ] );
            
            array_push ( $this->stack, $match [ 1 ] );
            
            if ( $allowed && isset ( $this->tag_output [ $match [ 1 ] ] ) )
            {
               $buffer .= sprintf ( $this->tag_output [ $match [ 1 ] ], $this->recurse () );
            }
            else
            {
               $buffer .= sprintf ( UBB_DEFAULT_OUTPUT, $this->recurse (), htmlentities ( $match [ 1 ] ) );
            }
         }
         else if ( preg_match ( UBB_CLOSE_TAG, $token, $match ) )
         {
            array_pop ( $this->stack );
            
            return $buffer;
         }
         else
         {
            $buffer .= htmlentities ( $token );
         }
      }

      return $buffer;
   }
   
   
   
   function is_allowed ( $tag )
   {
      foreach ( $this->stack as $parent )
      {
         if ( !isset ( $this->tag_hierarchy [ $parent ] ) || !in_array ( $tag, $this->tag_hierarchy [ $parent ] ) )
         {
            return false;
         }
      }
      
      return true;
   }
}

zaterdag 13 december 2003 11:34

Acties:

0 Henk 'm!

Tux

Topicstarter

Ik heb Prammenhanger ook netjes genoemd in m'n startpost Cheatah

En ik claim nergens een copyright, dat moet Prammenhanger maar doen. Ik doe het alleen om van te leren.

MisterData schreef op 13 december 2003 @ 09:29:
Wat ik bij m'n templateparser doe is een tree bouwen met al die tags erin. Ik heb drie typen tags: START_TAG, END_TAG en CONTENT_TAG (en eigenlijk ook ESCAPE_TAG, maar das een ander verhaal). In de parse functie loop ik door die lijst met elementen heen. Op het moment da t ik een START_TAG tegenkom, push ik die op de stack. Bij een END_TAG controleer ik of de laatst gepushte START_TAG overeenkomt met de eindtag. Is dit zo dan output ik die eindtag, en is dat niet zo, dan output ik net zolang een eindtag voor de START_TAG op de stack totdat ik bij de goede zit

Je bedoelt die functie die een whileloopje doet en strtok() gebruikt om de tags te splitsen?

Die preg_split() _{© Prammenhanger, Cheatah} doet precies hetzelfde.

[ Voor 88% gewijzigd door Tux op 13-12-2003 11:38 ]

The NS has launched a new space transportation service, using German trains which were upgraded into spaceships.

zaterdag 13 december 2003 14:16

Acties:

0 Henk 'm!

chris

Misschien offtopic, maar: is het niet veel makkelijker om je code door een xslt-parser te laten halen? Het scheelt je zelf veel programmeerwerk, en het is meestal veel makkelijker uitbreidbaar. Ook staat het constructies toe die een stuk ingewikkelder zijn dan met een relatief simpele stack-based ubb parser. Maarja

.

Voor meer info over de mogelijkheden zou je natuurlijk op w3schools 's een paar tutorials kunnen lezen om een idee te krijgen wat het ongeveer inhoudt.

Onderwerpen