4 * @author Niklas Laxström, Tim Starling
6 * @copyright Copyright © 2010-2012, Niklas Laxström
7 * @license http://www.gnu.org/copyleft/gpl.html GNU General Public License 2.0 or later
14 * Helper class for converting rules to reverse polish notation (RPN).
16 class CLDRPluralRuleConverter
{
25 * The current position
32 * The past-the-end position
43 public $operators = array();
50 public $operands = array();
53 * Precedence levels. Note that there's no need to worry about associativity
54 * for the level 4 operators, since they return boolean and don't accept
57 static $precedence = array(
72 * A character list defining whitespace, for use in strspn() etc.
74 const WHITESPACE_CLASS
= " \t\r\n";
77 * Same for digits. Note that the grammar given in UTS #35 doesn't allow
78 * negative numbers or decimal separators.
80 const NUMBER_CLASS
= '0123456789';
83 * A character list of symbolic operands.
85 const OPERAND_SYMBOLS
= 'nivwft';
88 * An anchored regular expression which matches a word at the current offset.
90 const WORD_REGEX
= '/[a-zA-Z@]+/A';
93 * Convert a rule to RPN. This is the only public entry point.
95 * @param string $rule The rule to convert
96 * @return string The RPN representation of the rule
98 public static function convert( $rule ) {
99 $parser = new self( $rule );
100 return $parser->doConvert();
104 * Private constructor.
106 protected function __construct( $rule ) {
109 $this->end
= strlen( $rule );
115 * @return string The RPN representation of the rule (e.g. "5 3 mod n is")
117 protected function doConvert() {
118 $expectOperator = true;
120 // Iterate through all tokens, saving the operators and operands to a
121 // stack per Dijkstra's shunting yard algorithm.
122 /** @var CLDRPluralRuleConverter_Operator $token */
123 while ( false !== ( $token = $this->nextToken() ) ) {
124 // In this grammar, there are only binary operators, so every valid
125 // rule string will alternate between operator and operand tokens.
126 $expectOperator = !$expectOperator;
128 if ( $token instanceof CLDRPluralRuleConverter_Expression
) {
130 if ( $expectOperator ) {
131 $token->error( 'unexpected operand' );
133 $this->operands
[] = $token;
137 if ( !$expectOperator ) {
138 $token->error( 'unexpected operator' );
140 // Resolve higher precedence levels
141 $lastOp = end( $this->operators
);
142 while ( $lastOp && self
::$precedence[$token->name
] <= self
::$precedence[$lastOp->name
] ) {
143 $this->doOperation( $lastOp, $this->operands
);
144 array_pop( $this->operators
);
145 $lastOp = end( $this->operators
);
147 $this->operators
[] = $token;
151 // Finish off the stack
152 while ( $op = array_pop( $this->operators
) ) {
153 $this->doOperation( $op, $this->operands
);
156 // Make sure the result is sane. The first case is possible for an empty
157 // string input, the second should be unreachable.
158 if ( !count( $this->operands
) ) {
159 $this->error( 'condition expected' );
160 } elseif ( count( $this->operands
) > 1 ) {
161 $this->error( 'missing operator or too many operands' );
164 $value = $this->operands
[0];
165 if ( $value->type
!== 'boolean' ) {
166 $this->error( 'the result must have a boolean type' );
169 return $this->operands
[0]->rpn
;
173 * Fetch the next token from the input string.
175 * @return CLDRPluralRuleConverter_Fragment The next token
177 protected function nextToken() {
178 if ( $this->pos
>= $this->end
) {
183 $length = strspn( $this->rule
, self
::WHITESPACE_CLASS
, $this->pos
);
184 $this->pos +
= $length;
186 if ( $this->pos
>= $this->end
) {
191 $length = strspn( $this->rule
, self
::NUMBER_CLASS
, $this->pos
);
192 if ( $length !== 0 ) {
193 $token = $this->newNumber( substr( $this->rule
, $this->pos
, $length ), $this->pos
);
194 $this->pos +
= $length;
198 // Two-character operators
199 $op2 = substr( $this->rule
, $this->pos
, 2 );
200 if ( $op2 === '..' ||
$op2 === '!=' ) {
201 $token = $this->newOperator( $op2, $this->pos
, 2 );
206 // Single-character operators
207 $op1 = $this->rule
[$this->pos
];
208 if ( $op1 === ',' ||
$op1 === '=' ||
$op1 === '%' ) {
209 $token = $this->newOperator( $op1, $this->pos
, 1 );
215 if ( !preg_match( self
::WORD_REGEX
, $this->rule
, $m, 0, $this->pos
) ) {
216 $this->error( 'unexpected character "' . $this->rule
[$this->pos
] . '"' );
218 $word1 = strtolower( $m[0] );
220 $nextTokenPos = $this->pos +
strlen( $word1 );
221 if ( $word1 === 'not' ||
$word1 === 'is' ) {
222 // Look ahead one word
223 $nextTokenPos +
= strspn( $this->rule
, self
::WHITESPACE_CLASS
, $nextTokenPos );
224 if ( $nextTokenPos < $this->end
225 && preg_match( self
::WORD_REGEX
, $this->rule
, $m, 0, $nextTokenPos )
227 $word2 = strtolower( $m[0] );
228 $nextTokenPos +
= strlen( $word2 );
232 // Two-word operators like "is not" take precedence over single-word operators like "is"
233 if ( $word2 !== '' ) {
234 $bothWords = "{$word1}-{$word2}";
235 if ( isset( self
::$precedence[$bothWords] ) ) {
236 $token = $this->newOperator( $bothWords, $this->pos
, $nextTokenPos - $this->pos
);
237 $this->pos
= $nextTokenPos;
242 // Single-word operators
243 if ( isset( self
::$precedence[$word1] ) ) {
244 $token = $this->newOperator( $word1, $this->pos
, strlen( $word1 ) );
245 $this->pos +
= strlen( $word1 );
249 // The single-character operand symbols
250 if ( strpos( self
::OPERAND_SYMBOLS
, $word1 ) !== false ) {
251 $token = $this->newNumber( $word1, $this->pos
);
257 if ( $word1 === '@integer' ||
$word1 === '@decimal' ) {
258 // Samples are like comments, they have no effect on rule evaluation.
259 // They run from the first sample indicator to the end of the string.
260 $this->pos
= $this->end
;
264 $this->error( 'unrecognised word' );
268 * For the binary operator $op, pop its operands off the stack and push
269 * a fragment with rpn and type members describing the result of that
272 * @param CLDRPluralRuleConverter_Operator $op
274 protected function doOperation( $op ) {
275 if ( count( $this->operands
) < 2 ) {
276 $op->error( 'missing operand' );
278 $right = array_pop( $this->operands
);
279 $left = array_pop( $this->operands
);
280 $result = $op->operate( $left, $right );
281 $this->operands
[] = $result;
285 * Create a numerical expression object
287 * @param string $text
289 * @return CLDRPluralRuleConverter_Expression The numerical expression
291 protected function newNumber( $text, $pos ) {
292 return new CLDRPluralRuleConverter_Expression( $this, 'number', $text, $pos, strlen( $text ) );
296 * Create a binary operator
298 * @param string $type
301 * @return CLDRPluralRuleConverter_Operator The operator
303 protected function newOperator( $type, $pos, $length ) {
304 return new CLDRPluralRuleConverter_Operator( $this, $type, $pos, $length );
310 protected function error( $message ) {
311 throw new CLDRPluralRuleError( $message );