3

I'm developing a BNF parser in PHP, for my own flavor of BNF. To keep the resulting parse tree, consisting of objects, as lightweight as possible, I decided to use the flyweight pattern for literals (terminals):

class Literal
{
  private static $cache = array();

  private $string = '';

  // private constructor for flyweight pattern
  private function __construct( $string ) {
    $this->setString( $string );
  }

  // flyweight pattern
  public static function fromString( $string ) {
    if( !isset( self::$cache[ $string ] ) ) {
      self::$cache[ $string ] = new Literal( $string );
    }

    return self::$cache[ $string ];
  }

  public function match( SourceInterface $source ) {
    /* algorithm to match source against $this->string */
  }

  /* ... */
}

Literals are denoted as strings between (single or double) quotes, e.g.: "A" or 'A'.

My flavor of BNF, however, will also support encoded representations of single character literals, denoted by a percentage sign and either a decimal or hexadecimal demarcation symbol followed by a value, e.g.: %d48 or %x30.

To implement this I'd, preferably, like to extend the Literal class, inheriting some of the Literal's functionality, like its match method, because ultimately EncodedLiteral represents the Literal string, that the input source will be matched against.

So, what I played around with was something like the following, but because the Literal's constructor should be kept private for the flyweight pattern, I became confused with what to do inside the EncodedLiteral's constructor.

class EncodedLiteral
  extends Literal
{
  private static $cache = array();

  private $encodedString;

  // private constructor for its own flyweight pattern
  private function __construct( $encodedString ) {

    // this won't work, since parent::__construct() is private
    // and it would bypass the flyweight pattern if it was protected
    parent::__construct( $this->decodeEncodedString( $encodedString ) );

    // ... and this doesn't make sense, since it would become composition
    // losing the inherited functionality
    $this->literal = Literal::fromString( $this->decodeEncodedString( $encodedString ) );
  }

  // flyweight pattern
  public static function fromString( $encodedString ) {
    if( !isset( self::$cache[ $encodedString ] ) ) {
      self::$cache[ $encodedString ] = new EncodedLiteral( $encodedString );
    }

    return self::$cache[ $encodedString ];
  }

  private function decodeEncodedString( $encodedString ) {
    /* implementation */
  }

  /* ... */
}

So, as you can see, I'm kind of stuck here.

Is there a way to solve this, in an elegant manner, without losing the flyweight advantages? Is this a case of choosing composition over inheritance, perhaps? Should I go with the decorator pattern? I kind of dread having to proxy to the methods I'd otherwise inherit with extending Literal, though.

  • Can't you just keep the decoding of single character literals out of the Literal class, leaving it to the code that calls fromString? – user7043 Mar 2 '16 at 10:28
  • @delnan Sorry if I caused possible confusion, but decodeEncodedString() would be a method of EncodedLiteral, not Literal. But, to address your actual point: I'm afraid not — I want to be able to reconstruct (print) the BNF grammar from the parse tree with __toString() methods. Therefor I need EncodedLiteral in the parse tree as well, to reconstruct the encoding symbols. – Decent Dabbler Mar 2 '16 at 10:38
  • In this case, I would consider having an "encoding" object as a member of each literal that contained methods to convert a literal too or from its original form, and then picking that at construction time. Decorator seems to be overkill for this situation. – Jules Mar 2 '16 at 13:49
  • @DecentDabbler Exactly what behavior do you want to share between Literal and EncodedLiteral ? Static method polymorphism doesn't exist and PHP doesn't have generics as far as I know, so I guess you're out of luck if you want to share flyweight behavior that relies on a static cache. – guillaume31 Mar 2 '16 at 15:20
  • @guillaume31 I want to share the match() method. Since EncodedLiteral ultimately is just a Literal under the hood. – Decent Dabbler Mar 2 '16 at 22:11
2

Since you only want to share the match() method, I would take all the flyweight/cache related behavior out of the Literals into a Factory class. This is static behavior so it couldn't have been inherited anyways.

Something along these lines (pardon my lousy PHP)

public class Literal {

  protected $string = '';

  protected function __construct( $string ) {
    $this->setString( $string );
  }

  protected function getString() {
    return $this->string;
  }

  protected function setString($value) {
    $this->string = $value;
  }

  public function match( SourceInterface $source ) {
    // ...
  }
}

public class EncodedLiteral extends Literal {

  protected function setString($value) {
    parent::setString($this->decodeEncodedString($value)) ;
  }

  private function decodeEncodedString( $encodedString ) {
    // ...
  }
}

public class LiteralFactory {
  private static $cache = array();

  public static function fromString($string) {
    // use private cache here and return a Literal
  }
}

public class EncodedLiteralFactory {
  private static $cache = array();

  public static function fromString($string) {
    // use private cache here and return an EncodedLiteral
  }
}
  • Ooooh, I think I like this, yes! I'll look into this closer later on, today. But this looks very promising! Thanks! – Decent Dabbler Mar 3 '16 at 8:38
0

Whenever you extend a concrete class, it's a code smell. Usually you want all concrete classes to be leaves in the hierarchy.

Move the common code to an abstract base class, then have your two types of literal encoding ( quoted or numeric ) be equal base classes, specialising their textual representations only.

You might also want to move your cache to its own class as you'll find yourself repeating the pattern for all the types of literal your grammar caters for.

Alternatively, change your BNF tokeniser and pass the whole literal to the cache rather than just the part between the quotes, and it can determine from the first character being ", ' or % how to decode it, so you don't need two classes.

  • 1
    Usually you want all concrete classes to be leaves in the hierarchy. -- Really? Wouldn't that make all of your class hierarchies one-level deep? – Robert Harvey Mar 2 '16 at 19:48
  • I don't agree with your statements about class hierarchy, but I like your proposals. I'm going to experiment with some or all. – Decent Dabbler Mar 2 '16 at 22:19
  • @RobertHarvey no, you can any number of levels of abstract classes. See the second part of stackoverflow.com/a/16725093/1527 for non C++ specific reasons – Pete Kirkham Mar 4 '16 at 9:00

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.