Remorhaz\UniLex\Parser\LL1\Lookup\TableConflictChecker

Complexity

Total Complexity

15

Size/Duplication

Total Lines	111
Duplicated Lines	0 %

Importance

Changes

0

8 Methods

Rating	Name	Duplication	Size	Complexity
A	checkConflict()	0	6	2
A	checkProductionConflicts()	0	7	2
A	check()	0	4	2
A	checkFirstFollowConflict()	0	9	2
A	checkFirstFirstConflict()	0	6	1
A	checkSymbolConflicts()	0	7	3
A	__construct()	0	5	1
A	checkMultipleEpsilons()	0	8	2

<?php

declare(strict_types=1);

namespace Remorhaz\UniLex\Parser\LL1\Lookup;

use Remorhaz\UniLex\Exception;
use Remorhaz\UniLex\Grammar\ContextFree\GrammarInterface;
use Remorhaz\UniLex\Grammar\ContextFree\Production;

class TableConflictChecker
{
    private $grammar;

    private $first;

    private $follow;

    public function __construct(GrammarInterface $grammar, FirstInterface $first, FollowInterface $follow)
    {
        $this->grammar = $grammar;
        $this->first = $first;
        $this->follow = $follow;
    }

    /**
     * @throws Exception
     */
    public function check(): void
    {
        foreach ($this->grammar->getNonTerminalList() as $symbolId) {
            $this->checkSymbolConflicts($symbolId);
        }
    }

    /**
     * @param int $symbolId
     * @throws Exception
     */
    private function checkSymbolConflicts(int $symbolId): void
    {
        $productionList = $this->grammar->getProductionList($symbolId);
        $this->checkMultipleEpsilons($symbolId, ...$productionList);
        foreach ($productionList as $alpha) {
            foreach ($productionList as $beta) {
                $this->checkProductionConflicts($alpha, $beta);
            }
        }
    }

    /**
     * @param Production $alpha
     * @param Production $beta
     * @throws Exception
     */
    private function checkProductionConflicts(Production $alpha, Production $beta): void
    {
        if ($alpha->getIndex() == $beta->getIndex()) {
            return;
        }
        $this->checkFirstFirstConflict($alpha, $beta);
        $this->checkFirstFollowConflict($alpha, $beta);
    }

    /**
     * @param int $symbolId
     * @param Production ...$productionList
     * @throws Exception
     */
    private function checkMultipleEpsilons(int $symbolId, Production ...$productionList): void
    {
        $isEpsilonProduction = function (Production $production): bool {
            return $production->isEpsilon();
        };
        $epsilonProductionList = array_filter($productionList, $isEpsilonProduction);
        if (count($epsilonProductionList) > 1) {
            throw new Exception("Symbol {$symbolId} has multiple ε-productions");
        }
    }

    /**
     * @param Production $alpha
     * @param Production $beta
     * @throws Exception
     */
    private function checkFirstFirstConflict(Production $alpha, Production $beta): void
    {
        $firstAlpha = $this->first->getProductionTokens(...$alpha->getSymbolList());
        $firstBeta = $this->first->getProductionTokens(...$beta->getSymbolList());
        $message = "FIRST({$alpha})/FIRST({$beta}) conflict";
        $this->checkConflict($firstAlpha, $firstBeta, $message);
    }

    /**
     * @param Production $alpha
     * @param Production $beta
     * @throws Exception
     */
    private function checkFirstFollowConflict(Production $alpha, Production $beta): void
    {
        if (!$this->first->productionHasEpsilon(...$beta->getSymbolList())) {
            return;
        }
        $follow = $this->follow->getTokens($alpha->getHeaderId());
        $firstAlpha = $this->first->getProductionTokens(...$alpha->getSymbolList());
        $message = "FIRST({$alpha})/FOLLOW({$alpha->getHeaderId()}) conflict (ε ∈ {$beta})";
        $this->checkConflict($follow, $firstAlpha, $message);
    }

    /**
     * @param array $tokenListA
     * @param array $tokenListB
     * @param string $message
     * @throws Exception
     */
    private function checkConflict(array $tokenListA, array $tokenListB, string $message): void
    {
        $conflict = array_intersect($tokenListA, $tokenListB);
        if (!empty($conflict)) {
            $conflictText = implode(', ', $conflict);
            throw new Exception("{$message}: {$conflictText}");
        }
    }
}