Hoa central
BoundedExhaustive.php
Go to the documentation of this file.
1 <?php
2 
38 
39 use Hoa\Compiler;
40 use Hoa\Iterator;
41 use Hoa\Visitor;
42 
55  extends Sampler
56  implements Iterator
57 {
63  protected $_todo = null;
64 
70  protected $_trace = null;
71 
77  protected $_key = -1;
78 
84  protected $_current = null;
85 
91  protected $_length = 5;
92 
93 
94 
102  public function __construct(
103  Compiler\Llk\Parser $compiler,
104  Visitor\Visit $tokenSampler,
105  $length = 5
106  ) {
107  parent::__construct($compiler, $tokenSampler);
108  $this->setLength($length);
109 
110  return;
111  }
112 
118  public function current()
119  {
120  return $this->_current;
121  }
122 
128  public function key()
129  {
130  return $this->_key;
131  }
132 
138  public function next()
139  {
140  return;
141  }
142 
148  public function rewind()
149  {
150  $ruleName = $this->_rootRuleName;
151  $this->_current = null;
152  $this->_key = -1;
153  $this->_trace = [];
154  $handle = new Compiler\Llk\Rule\Ekzit($ruleName, 0);
155  $this->_todo = [
156  $handle,
157  new Compiler\Llk\Rule\Entry($ruleName, 0, [$handle])
158  ];
159 
160  return;
161  }
162 
168  public function valid()
169  {
170  if (false === $this->unfold()) {
171  return false;
172  }
173 
174  $handle = null;
175 
176  foreach ($this->_trace as $trace) {
177  if ($trace instanceof Compiler\Llk\Rule\Token) {
178  $handle .= $this->generateToken($trace);
179  }
180  }
181 
182  ++$this->_key;
183  $this->_current = $handle;
184 
185  return $this->backtrack();
186  }
187 
193  protected function unfold()
194  {
195  while (0 < count($this->_todo)) {
196  $pop = array_pop($this->_todo);
197 
198  if ($pop instanceof Compiler\Llk\Rule\Ekzit) {
199  $this->_trace[] = $pop;
200  } else {
201  $ruleName = $pop->getRule();
202  $next = $pop->getData();
203  $rule = $this->_rules[$ruleName];
204  $out = $this->boundedExhaustive($rule, $next);
205 
206  if (true !== $out && true !== $this->backtrack()) {
207  return false;
208  }
209  }
210  }
211 
212  return true;
213  }
214 
222  protected function boundedExhaustive(Compiler\Llk\Rule $rule, $next)
223  {
224  $content = $rule->getContent();
225 
226  if ($rule instanceof Compiler\Llk\Rule\Repetition) {
227  if (0 === $next) {
228  $this->_trace[] = new Compiler\Llk\Rule\Entry(
229  $rule->getName(),
230  $rule->getMin()
231  );
232 
233  array_pop($this->_todo);
234  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
235  $rule->getName(),
236  $rule->getMin(),
238  );
239 
240  for ($i = 0, $min = $rule->getMin(); $i < $min; ++$i) {
241  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
242  $content,
243  0
244  );
245  $this->_todo[] = new Compiler\Llk\Rule\Entry(
246  $content,
247  0
248  );
249  }
250  } else {
251  $nbToken = 0;
252 
253  foreach ($this->_trace as $trace) {
254  if ($trace instanceof Compiler\Llk\Rule\Token) {
255  ++$nbToken;
256  }
257  }
258 
259  $max = $rule->getMax();
260 
261  if (-1 != $max && $next > $max) {
262  return false;
263  }
264 
265  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
266  $rule->getName(),
267  $next,
269  );
270  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
271  $content,
272  0
273  );
274  $this->_todo[] = new Compiler\Llk\Rule\Entry(
275  $content,
276  0
277  );
278  }
279 
280  return true;
281  } elseif ($rule instanceof Compiler\Llk\Rule\Choice) {
282  if (count($content) <= $next) {
283  return false;
284  }
285 
286  $this->_trace[] = new Compiler\Llk\Rule\Entry(
287  $rule->getName(),
288  $next,
290  );
291  $nextRule = $content[$next];
292  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
293  $nextRule,
294  0
295  );
296  $this->_todo[] = new Compiler\Llk\Rule\Entry(
297  $nextRule,
298  0
299  );
300 
301  return true;
302  } elseif ($rule instanceof Compiler\Llk\Rule\Concatenation) {
303  $this->_trace[] = new Compiler\Llk\Rule\Entry(
304  $rule->getName(),
305  $next
306  );
307 
308  for ($i = count($content) - 1; $i >= 0; --$i) {
309  $nextRule = $content[$i];
310  $this->_todo[] = new Compiler\Llk\Rule\Ekzit(
311  $nextRule,
312  0
313  );
314  $this->_todo[] = new Compiler\Llk\Rule\Entry(
315  $nextRule,
316  0
317  );
318  }
319 
320  return true;
321  } elseif ($rule instanceof Compiler\Llk\Rule\Token) {
322  $nbToken = 0;
323 
324  foreach ($this->_trace as $trace) {
325  if ($trace instanceof Compiler\Llk\Rule\Token) {
326  ++$nbToken;
327  }
328  }
329 
330  if ($nbToken >= $this->getLength()) {
331  return false;
332  }
333 
334  $this->_trace[] = $rule;
335  array_pop($this->_todo);
336 
337  return true;
338  }
339 
340  return false;
341  }
342 
348  protected function backtrack()
349  {
350  $found = false;
351 
352  do {
353  $last = array_pop($this->_trace);
354 
355  if ($last instanceof Compiler\Llk\Rule\Entry) {
356  $rule = $this->_rules[$last->getRule()];
357  $found = $rule instanceof Compiler\Llk\Rule\Choice;
358  } elseif ($last instanceof Compiler\Llk\Rule\Ekzit) {
359  $rule = $this->_rules[$last->getRule()];
360  $found = $rule instanceof Compiler\Llk\Rule\Repetition;
361  }
362  } while (0 < count($this->_trace) && false === $found);
363 
364  if (false === $found) {
365  return false;
366  }
367 
368  $rule = $last->getRule();
369  $next = $last->getData() + 1;
370  $this->_todo = $last->getTodo();
371  $this->_todo[] = new Compiler\Llk\Rule\Entry(
372  $rule,
373  $next,
374  $this->_todo
375  );
376 
377  return true;
378  }
379 
387  public function setLength($length)
388  {
389  if (0 >= $length) {
390  throw new Exception(
391  'Length must be greater than 0, given %d.',
392  0,
393  $length
394  );
395  }
396 
397  $old = $this->_length;
398  $this->_length = $length;
399 
400  return $old;
401  }
402 
408  public function getLength()
409  {
410  return $this->_length;
411  }
412 }
__construct(Compiler\Llk\Parser $compiler, Visitor\Visit $tokenSampler, $length=5)
generateToken(Compiler\Llk\Rule\Token $token)
Definition: Sampler.php:188
$content
Definition: Hoa.php:119
boundedExhaustive(Compiler\Llk\Rule $rule, $next)