|
1
|
|
|
<?php |
|
2
|
|
|
namespace Wandu\Compiler\Math; |
|
3
|
|
|
|
|
4
|
|
|
use Wandu\Compiler\Exception\UndefinedNontermException; |
|
5
|
|
|
|
|
6
|
|
|
class Grammar |
|
7
|
|
|
{ |
|
8
|
|
|
/** @var \Wandu\Compiler\Math\Set */ |
|
9
|
|
|
protected $nonterms; |
|
10
|
|
|
|
|
11
|
|
|
/** @var array */ |
|
12
|
|
|
protected $products; |
|
13
|
|
|
|
|
14
|
|
|
/** @var string */ |
|
15
|
|
|
protected $startSymbol; |
|
16
|
|
|
|
|
17
|
|
|
public function __construct(array $nonterms, array $products, $startSymbol) |
|
18
|
|
|
{ |
|
19
|
|
|
$this->nonterms = new Set(...$nonterms); |
|
20
|
|
|
$this->products = $this->normalizeProducts($products, $nonterms); |
|
21
|
|
|
$this->startSymbol = $startSymbol; |
|
22
|
|
|
} |
|
23
|
|
|
|
|
24
|
|
|
/** |
|
25
|
|
|
* @param array $symbols |
|
26
|
|
|
* @return \Wandu\Compiler\Math\Set |
|
27
|
|
|
*/ |
|
28
|
|
|
public function first(array $symbols = []) |
|
29
|
|
|
{ |
|
30
|
|
|
if (count($symbols) === 0) { |
|
31
|
|
|
return new Set(); |
|
32
|
|
|
} |
|
33
|
|
|
|
|
34
|
|
|
// if $x[0] is terminal symbol, return self. |
|
|
|
|
|
|
35
|
|
|
if (!$this->nonterms->has($symbols[0])) { |
|
36
|
|
|
return new Set($symbols[0]); |
|
37
|
|
|
} |
|
38
|
|
|
|
|
39
|
|
|
if (!array_key_exists($symbols[0], $this->products)) { |
|
40
|
|
|
return new Set(); |
|
41
|
|
|
} |
|
42
|
|
|
|
|
43
|
|
|
$setToReturn = new Set; |
|
44
|
|
|
foreach ($this->products[$symbols[0]] as $product) { |
|
45
|
|
|
if ($product[0] !== $symbols[0]) { |
|
46
|
|
|
$setToReturn->union($this->first($product)); |
|
47
|
|
|
} |
|
48
|
|
|
} |
|
49
|
|
|
|
|
50
|
|
|
return $setToReturn; |
|
51
|
|
|
} |
|
52
|
|
|
|
|
53
|
|
|
/** |
|
54
|
|
|
* @example. |
|
55
|
|
|
* |
|
56
|
|
|
* S -> ABe |
|
57
|
|
|
* A -> dB | aS | c |
|
58
|
|
|
* B -> AS | b |
|
59
|
|
|
* then, $items ares.. |
|
60
|
|
|
* [ |
|
61
|
|
|
* ['S', ['A', 'B', 'e']], |
|
62
|
|
|
* ['A', ['d', 'B']], |
|
63
|
|
|
* ['A', ['a', 'S']], |
|
64
|
|
|
* ['A', ['c']], |
|
65
|
|
|
* ['B', ['A', 'S']], |
|
66
|
|
|
* ['B', ['b']], |
|
67
|
|
|
* ] |
|
68
|
|
|
* @return array |
|
69
|
|
|
*/ |
|
70
|
|
|
public function computeFirsts() |
|
71
|
|
|
{ |
|
72
|
|
|
// G = (V_N, V_T, P, S) 를 기반으로 First라는 매서드를 만들어야 할지도.. |
|
73
|
|
|
$result = []; |
|
74
|
|
|
// for each A in V_N do FIRST(A) := [] |
|
75
|
|
|
foreach ($this->products as $nonterm) { |
|
76
|
|
|
$result[$nonterm] = []; // initialize |
|
77
|
|
|
} |
|
78
|
|
|
|
|
79
|
|
|
return []; |
|
80
|
|
|
} |
|
81
|
|
|
|
|
82
|
|
|
protected function normalizeProducts(array $products, array $nonterms) |
|
83
|
|
|
{ |
|
84
|
|
|
$normalizedProducts = []; |
|
85
|
|
|
foreach ($products as $product) { |
|
86
|
|
|
if (!in_array($product[0], $nonterms, true)) { |
|
87
|
|
|
throw new UndefinedNontermException($product[0]); |
|
88
|
|
|
} |
|
89
|
|
|
if (!array_key_exists($product[0], $normalizedProducts)) { |
|
90
|
|
|
$normalizedProducts[$product[0]] = new Set(); |
|
91
|
|
|
} |
|
92
|
|
|
$normalizedProducts[$product[0]]->insert($product[1]); |
|
93
|
|
|
} |
|
94
|
|
|
return $normalizedProducts; |
|
95
|
|
|
} |
|
96
|
|
|
} |
|
97
|
|
|
|
Wandu /
Framework
Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it.
The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production.
This check looks for comments that seem to be mostly valid code and reports them.