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.

6
  • 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
    Commented Mar 2, 2016 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. Commented Mar 2, 2016 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
    Commented Mar 2, 2016 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. Commented Mar 2, 2016 at 15:20
  • @guillaume31 I want to share the match() method. Since EncodedLiteral ultimately is just a Literal under the hood. Commented Mar 2, 2016 at 22:11

2 Answers 2

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
  }
}
1
  • Ooooh, I think I like this, yes! I'll look into this closer later on, today. But this looks very promising! Thanks! Commented Mar 3, 2016 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.

3
  • 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? Commented Mar 2, 2016 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. Commented Mar 2, 2016 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 Commented Mar 4, 2016 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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