how this parsing engine works.
"""
-import copy
from contextlib import contextmanager
-
-# Local imports
-from . import grammar, token, tokenize
from typing import (
- cast,
+ TYPE_CHECKING,
Any,
- Optional,
- Text,
- Union,
- Tuple,
+ Callable,
Dict,
- List,
Iterator,
- Callable,
+ List,
+ Optional,
Set,
- TYPE_CHECKING,
+ Tuple,
+ Union,
+ cast,
)
+
from blib2to3.pgen2.grammar import Grammar
-from blib2to3.pytree import convert, NL, Context, RawNode, Leaf, Node
+from blib2to3.pytree import NL, Context, Leaf, Node, RawNode, convert
+
+# Local imports
+from . import grammar, token, tokenize
if TYPE_CHECKING:
- from blib2to3.driver import TokenProxy
+ from blib2to3.pgen2.driver import TokenProxy
-Results = Dict[Text, NL]
+Results = Dict[str, NL]
Convert = Callable[[Grammar, RawNode], Union[Node, Leaf]]
DFA = List[List[Tuple[int, int]]]
DFAS = Tuple[DFA, Dict[int, int]]
return Node(type=node[0], children=node[3], context=node[2])
+# A placeholder node, used when parser is backtracking.
+DUMMY_NODE = (-1, None, None, None)
+
+
+def stack_copy(
+ stack: List[Tuple[DFAS, int, RawNode]]
+) -> List[Tuple[DFAS, int, RawNode]]:
+ """Nodeless stack copy."""
+ return [(dfa, label, DUMMY_NODE) for dfa, label, _ in stack]
+
+
class Recorder:
def __init__(self, parser: "Parser", ilabels: List[int], context: Context) -> None:
self.parser = parser
self.context = context # not really matter
self._dead_ilabels: Set[int] = set()
- self._start_point = copy.deepcopy(self.parser.stack)
- self._points = {ilabel: copy.deepcopy(self._start_point) for ilabel in ilabels}
+ self._start_point = self.parser.stack
+ self._points = {ilabel: stack_copy(self._start_point) for ilabel in ilabels}
@property
def ilabels(self) -> Set[int]:
@contextmanager
def switch_to(self, ilabel: int) -> Iterator[None]:
- self.parser.stack = self._points[ilabel]
+ with self.backtrack():
+ self.parser.stack = self._points[ilabel]
+ try:
+ yield
+ except ParseError:
+ self._dead_ilabels.add(ilabel)
+ finally:
+ self.parser.stack = self._start_point
+
+ @contextmanager
+ def backtrack(self) -> Iterator[None]:
+ """
+ Use the node-level invariant ones for basic parsing operations (push/pop/shift).
+ These still will operate on the stack; but they won't create any new nodes, or
+ modify the contents of any other existing nodes.
+
+ This saves us a ton of time when we are backtracking, since we
+ want to restore to the initial state as quick as possible, which
+ can only be done by having as little mutatations as possible.
+ """
+ is_backtracking = self.parser.is_backtracking
try:
+ self.parser.is_backtracking = True
yield
- except ParseError:
- self._dead_ilabels.add(ilabel)
finally:
- self.parser.stack = self._start_point
+ self.parser.is_backtracking = is_backtracking
- def add_token(self, tok_type: int, tok_val: Text, raw: bool = False) -> None:
+ def add_token(self, tok_type: int, tok_val: str, raw: bool = False) -> None:
func: Callable[..., Any]
if raw:
func = self.parser._addtoken
args.insert(0, ilabel)
func(*args)
- def determine_route(self, value: Text = None, force: bool = False) -> Optional[int]:
+ def determine_route(
+ self, value: Optional[str] = None, force: bool = False
+ ) -> Optional[int]:
alive_ilabels = self.ilabels
if len(alive_ilabels) == 0:
*_, most_successful_ilabel = self._dead_ilabels
"""Exception to signal the parser is stuck."""
def __init__(
- self, msg: Text, type: Optional[int], value: Optional[Text], context: Context
+ self, msg: str, type: Optional[int], value: Optional[str], context: Context
) -> None:
Exception.__init__(
- self, "%s: type=%r, value=%r, context=%r" % (msg, type, value, context)
+ self, f"{msg}: type={type!r}, value={value!r}, context={context!r}"
)
self.msg = msg
self.type = type
self.context = context
-class Parser(object):
+class Parser:
"""Parser engine.
The proper usage sequence is:
self.grammar = grammar
# See note in docstring above. TL;DR this is ignored.
self.convert = convert or lam_sub
+ self.is_backtracking = False
+ self.last_token: Optional[int] = None
def setup(self, proxy: "TokenProxy", start: Optional[int] = None) -> None:
"""Prepare for parsing.
self.rootnode: Optional[NL] = None
self.used_names: Set[str] = set()
self.proxy = proxy
+ self.last_token = None
- def addtoken(self, type: int, value: Text, context: Context) -> bool:
+ def addtoken(self, type: int, value: str, context: Context) -> bool:
"""Add a token; return True iff this is the end of the program."""
# Map from token to label
ilabels = self.classify(type, value, context)
break
next_token_type, next_token_value, *_ = proxy.eat(counter)
+ if next_token_type in (tokenize.COMMENT, tokenize.NL):
+ counter += 1
+ continue
+
if next_token_type == tokenize.OP:
next_token_type = grammar.opmap[next_token_value]
return self._addtoken(ilabel, type, value, context)
- def _addtoken(self, ilabel: int, type: int, value: Text, context: Context) -> bool:
+ def _addtoken(self, ilabel: int, type: int, value: str, context: Context) -> bool:
# Loop until the token is shifted; may raise exceptions
while True:
dfa, state, node = self.stack[-1]
dfa, state, node = self.stack[-1]
states, first = dfa
# Done with this token
+ self.last_token = type
return False
else:
# No success finding a transition
raise ParseError("bad input", type, value, context)
- def classify(self, type: int, value: Text, context: Context) -> List[int]:
+ def classify(self, type: int, value: str, context: Context) -> List[int]:
"""Turn a token into a label. (Internal)
Depending on whether the value is a soft-keyword or not,
return [self.grammar.keywords[value]]
elif value in self.grammar.soft_keywords:
assert type in self.grammar.tokens
+ # Current soft keywords (match, case, type) can only appear at the
+ # beginning of a statement. So as a shortcut, don't try to treat them
+ # like keywords in any other context.
+ # ('_' is also a soft keyword in the real grammar, but for our grammar
+ # it's just an expression, so we don't need to treat it specially.)
+ if self.last_token not in (
+ None,
+ token.INDENT,
+ token.DEDENT,
+ token.NEWLINE,
+ token.SEMI,
+ token.COLON,
+ ):
+ return [self.grammar.tokens[type]]
return [
- self.grammar.soft_keywords[value],
self.grammar.tokens[type],
+ self.grammar.soft_keywords[value],
]
ilabel = self.grammar.tokens.get(type)
raise ParseError("bad token", type, value, context)
return [ilabel]
- def shift(self, type: int, value: Text, newstate: int, context: Context) -> None:
+ def shift(self, type: int, value: str, newstate: int, context: Context) -> None:
"""Shift a token. (Internal)"""
- dfa, state, node = self.stack[-1]
- rawnode: RawNode = (type, value, context, None)
- newnode = convert(self.grammar, rawnode)
- assert node[-1] is not None
- node[-1].append(newnode)
- self.stack[-1] = (dfa, newstate, node)
+ if self.is_backtracking:
+ dfa, state, _ = self.stack[-1]
+ self.stack[-1] = (dfa, newstate, DUMMY_NODE)
+ else:
+ dfa, state, node = self.stack[-1]
+ rawnode: RawNode = (type, value, context, None)
+ newnode = convert(self.grammar, rawnode)
+ assert node[-1] is not None
+ node[-1].append(newnode)
+ self.stack[-1] = (dfa, newstate, node)
def push(self, type: int, newdfa: DFAS, newstate: int, context: Context) -> None:
"""Push a nonterminal. (Internal)"""
- dfa, state, node = self.stack[-1]
- newnode: RawNode = (type, None, context, [])
- self.stack[-1] = (dfa, newstate, node)
- self.stack.append((newdfa, 0, newnode))
+ if self.is_backtracking:
+ dfa, state, _ = self.stack[-1]
+ self.stack[-1] = (dfa, newstate, DUMMY_NODE)
+ self.stack.append((newdfa, 0, DUMMY_NODE))
+ else:
+ dfa, state, node = self.stack[-1]
+ newnode: RawNode = (type, None, context, [])
+ self.stack[-1] = (dfa, newstate, node)
+ self.stack.append((newdfa, 0, newnode))
def pop(self) -> None:
"""Pop a nonterminal. (Internal)"""
- popdfa, popstate, popnode = self.stack.pop()
- newnode = convert(self.grammar, popnode)
- if self.stack:
- dfa, state, node = self.stack[-1]
- assert node[-1] is not None
- node[-1].append(newnode)
+ if self.is_backtracking:
+ self.stack.pop()
else:
- self.rootnode = newnode
- self.rootnode.used_names = self.used_names
+ popdfa, popstate, popnode = self.stack.pop()
+ newnode = convert(self.grammar, popnode)
+ if self.stack:
+ dfa, state, node = self.stack[-1]
+ assert node[-1] is not None
+ node[-1].append(newnode)
+ else:
+ self.rootnode = newnode
+ self.rootnode.used_names = self.used_names
projects / etc / vim.git / blobdiff