recursive_decent_parser.py

"""A recursive decent parser of CFG."""

from typing import List, Iterable, Tuple, Optional, Hashable

from .cfg import CFG
from .parse_tree import ParseTree, NotParsableError
from ..objects.cfg_objects import CFGObject, Variable, Terminal, Epsilon
from ..objects.cfg_objects.utils import to_terminal

ExpansionSymbol = Tuple[CFGObject, ParseTree]
Expansion = List[ExpansionSymbol]


def _get_index_to_extend(current_expansion: Expansion, left: bool) \
        -> Tuple[int, Optional[ExpansionSymbol]]:
    order = enumerate(current_expansion)
    if not left:
        order = reversed(list(order))
    for i, symbol in order:
        if isinstance(symbol[0], Variable):
            return i, symbol
    return -1, None


class RecursiveDecentParser:
    """A recursive Top-Down parser of CFG.

    Parameters
    ----------
    cfg:
        A Context-Free Grammar to parse.
    """

    def __init__(self, cfg: CFG) -> None:
        """Initializes the parser."""
        self._cfg = cfg

    def get_parse_tree(self, word: Iterable[Hashable], left: bool = True) \
            -> ParseTree:
        """Gets a parse tree of the given word.

        Parameters
        ----------
        word:
            The word to parse.
        left:
            If we do the recursive from the left or the right
            (left by default).

        Returns
        -------
        The parse tree of the given word.

        Raises
        ------
        NotParsableError
            When the word cannot be parsed.
        """
        if not self._cfg.start_symbol:
            raise NotParsableError
        word = [to_terminal(x) for x in word if x != Epsilon()]
        parse_tree = ParseTree(self._cfg.start_symbol)
        starting_expansion: Expansion = [(self._cfg.start_symbol, parse_tree)]
        if self._get_parse_tree_sub(word, starting_expansion, left):
            return parse_tree
        raise NotParsableError

    def _match(self,
               word: List[Terminal],
               current_expansion: Expansion,
               idx_word: int = 0,
               idx_current_expansion: int = 0) -> bool:
        if idx_word == len(word) and \
                idx_current_expansion == len(current_expansion):
            return True
        if idx_word > len(word):
            return False
        if idx_current_expansion == len(current_expansion):
            return False
        if isinstance(current_expansion[idx_current_expansion][0], Variable):
            return self._match(word, current_expansion, idx_word + 1,
                               idx_current_expansion) or \
                   self._match(word, current_expansion, idx_word,
                               idx_current_expansion + 1)
        if idx_word < len(word) and \
                word[idx_word] == current_expansion[idx_current_expansion][0]:
            return self._match(word, current_expansion, idx_word + 1,
                               idx_current_expansion + 1)
        return False

    def _get_parse_tree_sub(self,
                            word: List[Terminal],
                            current_expansion: Expansion,
                            left: bool = True) -> bool:
        if not self._match(word, current_expansion):
            return False
        extend_idx, to_expand = _get_index_to_extend(current_expansion, left)
        # Nothing else to extend, we are done
        if to_expand is None:
            return True
        begin = current_expansion[:extend_idx]
        end = current_expansion[extend_idx + 1:]
        for production in self._cfg.productions:
            if production.head == to_expand[0]:
                replacement = [(x, ParseTree(x)) for x in production.body]
                new_expansion = begin + replacement + end
                if self._get_parse_tree_sub(word, new_expansion, left):
                    to_expand[1].sons = [x[1] for x in replacement]
                    return True
        return False

    def is_parsable(self, word: Iterable[Hashable], left: bool = True) -> bool:
        """Whether the given word is parsable or not.

        Parameters
        ----------
        word:
            The word to parse.
        left:
            If we do the recursive from the left or the right
            (left by default).

        Returns
        -------
        Whether the word is parsable.

        Raises
        ------
        RecursionError
            If the recursion goes too deep. This error occurs because some
            the algorithm is not guaranteed to terminate with left/right
            recursive grammars.
        """
        try:
            self.get_parse_tree(word, left)
        except NotParsableError:
            return False
        return True