Как превратить открывающие / закрывающие теги в ассоциативный массив в PHP?

Question

У меня есть дерево синтаксического анализа обработки естественного языка как

(S
  (NP I)
  (VP
    (VP (V shot) (NP (Det an) (N elephant)))
    (PP (P in) (NP (Det my) (N pajamas)))))

, и я хочу сохранить его в ассоциативном массиве, но тамне является функцией в PHP, так как NLP обычно делается в Python.

Таким образом, я должен разобрать открывающую и закрывающую скобки, чтобы построить древовидный ассоциативный массив.Я могу вспомнить два варианта

1. Замена круглых скобок произвольными тегами XML или HTML и синтаксический анализ его как документа XML или HTML.
2. Использование регулярного выражения.

Я думаю, что первый подход нестандартен, и шаблон регулярных выражений может сломаться в сложных случаях.

Можете ли вы предложить надежный подход для этого?

Ассоциативный массив можетиметь любую форму, так как манипулировать ею не сложно (мне это нужно в цикле), но это может быть что-то вроде

Array (
[0] = > word => ROOT, tag => S, children => Array (
    [0] word => I, tag = > NP, children => Array()
    [1] word => ROOT, tag => VP, children => Array (
        [0] => word => ROOT, tag => VP, children => Array ( .... )
        [1] => word => ROOT, tag => PP, children => Array ( .... )
)
)
)

или

Array (
[0] = > Array([0] => S, [1] => Array (
    [0] Array([0] => NP, [1] => 'I') // child array is replaced by a string
    [1] Array([0] => VP, [1] => Array (
        [0] => Array([0] => VP, [1] => Array ( .... )
        [1] => Array([0] => PP, [1] => Array ( .... )
    )
)

Answer 1

Используйте генератор лексических анализаторов, как бизон или flex или просто напишите свой собственный лексер руками. Этот ответ содержит некоторую полезную информацию, которая вам нужна.

Вот быстрые и грязные фрагменты POC, написанные на PHP, которые выведут ассоциативный массив, как и ожидалось.

$data =<<<EOL
(S
  (NP I)
  (VP
    (VP (V shot) (NP (Det an) (N elephant)))
    (PP (P in) (NP (Det my) (N pajamas)))))
EOL;

$lexer = new Lexer($data);
$array = buildTree($lexer, 0);
print_r($array);

function buildTree($lexer, $level)
{
    $subtrees = [];
    $markers = [];
    while (($token = $lexer->nextToken()) !== false) {
        if ($token == '(') {
            $subtrees[] = buildTree($lexer, $level);
        } elseif ($token == ')') {
            return buildNode($markers, $subtrees);
        } else {
            $markers[] = $token;
        }
    }

    return buildNode($markers, $subtrees);
}

function buildNode($markers, $subtrees)
{
    if (count($markers) && count($subtrees)) {
        return [$markers[0], $subtrees];
    } elseif (count($subtrees)) {
        return $subtrees;
    } else {
        return $markers;
    }
}

class Lexer
{
    private $data;

    private $matches;

    private $index = -1;

    public function __construct($data)
    {
        $this->data = $data;
        preg_match_all('/[\w]+|\(|\)/', $data, $matches);
        $this->matches = $matches[0];
    }

    public function nextToken()
    {
        $index = ++$this->index;
        if (isset($this->matches[$index]) === false) {
            return false;
        }
        return $this->matches[$index];
    }
}

Вывод

Array
(
    [0] => Array
        (
            [0] => S
            [1] => Array
                (
                    [0] => Array
                        (
                            [0] => NP
                            [1] => I
                        )

                    [1] => Array
                        (
                            [0] => VP
                            [1] => Array
                                (
                                    [0] => Array
                                        (
                                            [0] => VP
                                            [1] => Array
                                                (
                                                    [0] => Array
                                                        (
                                                            [0] => V
                                                            [1] => shot
                                                        )

                                                    [1] => Array
                                                        (
                                                            [0] => NP
                                                            [1] => Array
                                                                (
                                                                    [0] => Array
                                                                        (
                                                                            [0] => Det
                                                                            [1] => an
                                                                        )

                                                                    [1] => Array
                                                                        (
                                                                            [0] => N
                                                                            [1] => elephant
                                                                        )

                                                                )

                                                        )

                                                )

                                        )

                                    [1] => Array
                                        (
                                            [0] => PP
                                            [1] => Array
                                                (
                                                    [0] => Array
                                                        (
                                                            [0] => P
                                                            [1] => in
                                                        )

                                                    [1] => Array
                                                        (
                                                            [0] => NP
                                                            [1] => Array
                                                                (
                                                                    [0] => Array
                                                                        (
                                                                            [0] => Det
                                                                            [1] => my
                                                                        )

                                                                    [1] => Array
                                                                        (
                                                                            [0] => N
                                                                            [1] => pajamas
                                                                        )

                                                                )

                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

)