]>
git.madduck.net Git - etc/vim.git/blobdiff - blib2to3/pgen2/pgen.py
madduck's git repository
Every one of the projects in this repository is available at the canonical
URL git://git.madduck.net/madduck/pub/<projectpath> — see
each project's metadata for the exact URL.
All patches and comments are welcome. Please squash your changes to logical
commits before using git-format-patch and git-send-email to
patches@ git. madduck. net .
If you'd read over the Git project's submission guidelines and adhered to them,
I'd be especially grateful.
SSH access, as well as push access can be individually
arranged .
If you use my repositories frequently, consider adding the following
snippet to ~/.gitconfig and using the third clone URL listed for each
project:
[url "git://git.madduck.net/madduck/"]
insteadOf = madduck:
# Pgen imports
from . import grammar, token, tokenize
# Pgen imports
from . import grammar, token, tokenize
+from typing import (
+ Any,
+ Dict,
+ IO,
+ Iterable,
+ Iterator,
+ List,
+ Optional,
+ Text,
+ Tuple,
+ Union,
+ Sequence,
+ NoReturn,
+)
+from blib2to3.pgen2 import grammar
+from blib2to3.pgen2.tokenize import GoodTokenInfo
+import os
+
+
+Path = Union[str, "os.PathLike[str]"]
+
+
class PgenGrammar(grammar.Grammar):
pass
class PgenGrammar(grammar.Grammar):
pass
class ParserGenerator(object):
class ParserGenerator(object):
- def __init__(self, filename, stream=None):
+ filename: Path
+ stream: IO[Text]
+ generator: Iterator[GoodTokenInfo]
+ first: Dict[Text, Optional[Dict[Text, int]]]
+
+ def __init__(self, filename: Path, stream: Optional[IO[Text]] = None) -> None:
close_stream = None
if stream is None:
stream = open(filename)
close_stream = None
if stream is None:
stream = open(filename)
self.filename = filename
self.stream = stream
self.generator = tokenize.generate_tokens(stream.readline)
self.filename = filename
self.stream = stream
self.generator = tokenize.generate_tokens(stream.readline)
- self.gettoken() # Initialize lookahead
+ self.gettoken() # Initialize lookahead
self.dfas, self.startsymbol = self.parse()
if close_stream is not None:
close_stream()
self.dfas, self.startsymbol = self.parse()
if close_stream is not None:
close_stream()
- self.first = {} # map from symbol name to set of tokens
+ self.first = {} # map from symbol name to set of tokens
- def make_grammar(self):
+ def make_grammar(self) -> PgenGrammar :
c = PgenGrammar()
names = list(self.dfas.keys())
names.sort()
c = PgenGrammar()
names = list(self.dfas.keys())
names.sort()
c.start = c.symbol2number[self.startsymbol]
return c
c.start = c.symbol2number[self.startsymbol]
return c
- def make_first(self, c, name) :
+ def make_first(self, c: PgenGrammar, name: Text) -> Dict[int, int] :
rawfirst = self.first[name]
rawfirst = self.first[name]
+ assert rawfirst is not None
first = {}
for label in sorted(rawfirst):
ilabel = self.make_label(c, label)
first = {}
for label in sorted(rawfirst):
ilabel = self.make_label(c, label)
first[ilabel] = 1
return first
first[ilabel] = 1
return first
- def make_label(self, c, label) :
+ def make_label(self, c: PgenGrammar, label: Text) -> int :
# XXX Maybe this should be a method on a subclass of converter?
ilabel = len(c.labels)
if label[0].isalpha():
# XXX Maybe this should be a method on a subclass of converter?
ilabel = len(c.labels)
if label[0].isalpha():
return ilabel
else:
# An operator (any non-numeric token)
return ilabel
else:
# An operator (any non-numeric token)
- itoken = grammar.opmap[value] # Fails if unknown token
+ itoken = grammar.opmap[value] # Fails if unknown token
if itoken in c.tokens:
return c.tokens[itoken]
else:
if itoken in c.tokens:
return c.tokens[itoken]
else:
c.tokens[itoken] = ilabel
return ilabel
c.tokens[itoken] = ilabel
return ilabel
- def addfirstsets(self):
+ def addfirstsets(self) -> None :
names = list(self.dfas.keys())
names.sort()
for name in names:
if name not in self.first:
self.calcfirst(name)
names = list(self.dfas.keys())
names.sort()
for name in names:
if name not in self.first:
self.calcfirst(name)
- #print name, self.first[name].keys()
+ # print name, self.first[name].keys()
- def calcfirst(self, name) :
+ def calcfirst(self, name: Text) -> None :
- self.first[name] = None # dummy to detect left recursion
+ self.first[name] = None # dummy to detect left recursion
+ totalset: Dict[str, int] = {}
overlapcheck = {}
for label, next in state.arcs.items():
if label in self.dfas:
overlapcheck = {}
for label, next in state.arcs.items():
if label in self.dfas:
else:
self.calcfirst(label)
fset = self.first[label]
else:
self.calcfirst(label)
fset = self.first[label]
+ assert fset is not None
totalset.update(fset)
overlapcheck[label] = fset
else:
totalset[label] = 1
overlapcheck[label] = {label: 1}
totalset.update(fset)
overlapcheck[label] = fset
else:
totalset[label] = 1
overlapcheck[label] = {label: 1}
+ inverse: Dict[str, str] = {}
for label, itsfirst in overlapcheck.items():
for symbol in itsfirst:
if symbol in inverse:
for label, itsfirst in overlapcheck.items():
for symbol in itsfirst:
if symbol in inverse:
- raise ValueError("rule %s is ambiguous; %s is in the"
- " first sets of %s as well as %s" %
- (name, symbol, label, inverse[symbol]))
+ raise ValueError(
+ "rule %s is ambiguous; %s is in the"
+ " first sets of %s as well as %s"
+ % (name, symbol, label, inverse[symbol])
+ )
inverse[symbol] = label
self.first[name] = totalset
inverse[symbol] = label
self.first[name] = totalset
+ def parse(self) -> Tuple[Dict[Text, List["DFAState"]], Text] :
+ startsymbol: Optional[str] = None
# MSTART: (NEWLINE | RULE)* ENDMARKER
while self.type != token.ENDMARKER:
while self.type == token.NEWLINE:
# MSTART: (NEWLINE | RULE)* ENDMARKER
while self.type != token.ENDMARKER:
while self.type == token.NEWLINE:
self.expect(token.OP, ":")
a, z = self.parse_rhs()
self.expect(token.NEWLINE)
self.expect(token.OP, ":")
a, z = self.parse_rhs()
self.expect(token.NEWLINE)
- #self.dump_nfa(name, a, z)
+ # self.dump_nfa(name, a, z)
dfa = self.make_dfa(a, z)
dfa = self.make_dfa(a, z)
- #self.dump_dfa(name, dfa)
+ # self.dump_dfa(name, dfa)
oldlen = len(dfa)
self.simplify_dfa(dfa)
newlen = len(dfa)
dfas[name] = dfa
oldlen = len(dfa)
self.simplify_dfa(dfa)
newlen = len(dfa)
dfas[name] = dfa
- #print name, oldlen, newlen
+ # print name, oldlen, newlen
if startsymbol is None:
startsymbol = name
if startsymbol is None:
startsymbol = name
+ assert startsymbol is not None
- def make_dfa(self, start, finish) :
+ def make_dfa(self, start: "NFAState", finish: "NFAState") -> List["DFAState"] :
# To turn an NFA into a DFA, we define the states of the DFA
# to correspond to *sets* of states of the NFA. Then do some
# state reduction. Let's represent sets as dicts with 1 for
# values.
assert isinstance(start, NFAState)
assert isinstance(finish, NFAState)
# To turn an NFA into a DFA, we define the states of the DFA
# to correspond to *sets* of states of the NFA. Then do some
# state reduction. Let's represent sets as dicts with 1 for
# values.
assert isinstance(start, NFAState)
assert isinstance(finish, NFAState)
- def closure(state):
- base = {}
+
+ def closure(state: NFAState) -> Dict[NFAState, int]:
+ base: Dict[NFAState, int] = {}
addclosure(state, base)
return base
addclosure(state, base)
return base
- def addclosure(state, base):
+
+ def addclosure(state: NFAState, base: Dict[NFAState, int]) -> None:
assert isinstance(state, NFAState)
if state in base:
return
assert isinstance(state, NFAState)
if state in base:
return
for label, next in state.arcs:
if label is None:
addclosure(next, base)
for label, next in state.arcs:
if label is None:
addclosure(next, base)
states = [DFAState(closure(start), finish)]
states = [DFAState(closure(start), finish)]
- for state in states: # NB states grows while we're iterating
- arcs = {}
+ for state in states: # NB states grows while we're iterating
+ arcs: Dict[str, Dict[NFAState, int]] = {}
for nfastate in state.nfaset:
for label, next in nfastate.arcs:
if label is not None:
for nfastate in state.nfaset:
for label, next in nfastate.arcs:
if label is not None:
st = DFAState(nfaset, finish)
states.append(st)
state.addarc(st, label)
st = DFAState(nfaset, finish)
states.append(st)
state.addarc(st, label)
- return states # List of DFAState instances; first one is start
+ return states # List of DFAState instances; first one is start
- def dump_nfa(self, name, start, finish) :
+ def dump_nfa(self, name: Text, start: "NFAState", finish: "NFAState") -> None :
print("Dump of NFA for", name)
todo = [start]
for i, state in enumerate(todo):
print("Dump of NFA for", name)
todo = [start]
for i, state in enumerate(todo):
else:
print(" %s -> %d" % (label, j))
else:
print(" %s -> %d" % (label, j))
- def dump_dfa(self, name, dfa) :
+ def dump_dfa(self, name: Text, dfa: Sequence["DFAState"]) -> None :
print("Dump of DFA for", name)
for i, state in enumerate(dfa):
print(" State", i, state.isfinal and "(final)" or "")
for label, next in sorted(state.arcs.items()):
print(" %s -> %d" % (label, dfa.index(next)))
print("Dump of DFA for", name)
for i, state in enumerate(dfa):
print(" State", i, state.isfinal and "(final)" or "")
for label, next in sorted(state.arcs.items()):
print(" %s -> %d" % (label, dfa.index(next)))
- def simplify_dfa(self, dfa) :
+ def simplify_dfa(self, dfa: List["DFAState"]) -> None :
# This is not theoretically optimal, but works well enough.
# Algorithm: repeatedly look for two states that have the same
# set of arcs (same labels pointing to the same nodes) and
# This is not theoretically optimal, but works well enough.
# Algorithm: repeatedly look for two states that have the same
# set of arcs (same labels pointing to the same nodes) and
while changes:
changes = False
for i, state_i in enumerate(dfa):
while changes:
changes = False
for i, state_i in enumerate(dfa):
- for j in range(i+ 1, len(dfa)):
+ for j in range(i + 1, len(dfa)):
state_j = dfa[j]
if state_i == state_j:
state_j = dfa[j]
if state_i == state_j:
del dfa[j]
for state in dfa:
state.unifystate(state_j, state_i)
changes = True
break
del dfa[j]
for state in dfa:
state.unifystate(state_j, state_i)
changes = True
break
+ def parse_rhs(self) -> Tuple["NFAState", "NFAState"] :
# RHS: ALT ('|' ALT)*
a, z = self.parse_alt()
if self.value != "|":
# RHS: ALT ('|' ALT)*
a, z = self.parse_alt()
if self.value != "|":
z.addarc(zz)
return aa, zz
z.addarc(zz)
return aa, zz
+ def parse_alt(self) -> Tuple["NFAState", "NFAState"] :
# ALT: ITEM+
a, b = self.parse_item()
# ALT: ITEM+
a, b = self.parse_item()
- while (self.value in ("(", "[") or
- self.type in (token.NAME, token.STRING)):
+ while self.value in ("(", "[") or self.type in (token.NAME, token.STRING):
c, d = self.parse_item()
b.addarc(c)
b = d
return a, b
c, d = self.parse_item()
b.addarc(c)
b = d
return a, b
+ def parse_item(self) -> Tuple["NFAState", "NFAState"] :
# ITEM: '[' RHS ']' | ATOM ['+' | '*']
if self.value == "[":
self.gettoken()
# ITEM: '[' RHS ']' | ATOM ['+' | '*']
if self.value == "[":
self.gettoken()
+ def parse_atom(self) -> Tuple["NFAState", "NFAState"] :
# ATOM: '(' RHS ')' | NAME | STRING
if self.value == "(":
self.gettoken()
# ATOM: '(' RHS ')' | NAME | STRING
if self.value == "(":
self.gettoken()
self.gettoken()
return a, z
else:
self.gettoken()
return a, z
else:
- self.raise_error("expected (...) or NAME or STRING, got %s/%s",
- self.type, self.value)
+ self.raise_error(
+ "expected (...) or NAME or STRING, got %s/%s", self.type, self.value
+ )
+ assert False
- def expect(self, type, value=None) :
+ def expect(self, type: int, value: Optional[Any] = None) -> Text :
if self.type != type or (value is not None and self.value != value):
if self.type != type or (value is not None and self.value != value):
- self.raise_error("expected %s/%s, got %s/%s",
- type, value, self.type, self.value)
+ self.raise_error(
+ "expected %s/%s, got %s/%s", type, value, self.type, self.value
+ )
value = self.value
self.gettoken()
return value
value = self.value
self.gettoken()
return value
+ def gettoken(self) -> None :
tup = next(self.generator)
while tup[0] in (tokenize.COMMENT, tokenize.NL):
tup = next(self.generator)
self.type, self.value, self.begin, self.end, self.line = tup
tup = next(self.generator)
while tup[0] in (tokenize.COMMENT, tokenize.NL):
tup = next(self.generator)
self.type, self.value, self.begin, self.end, self.line = tup
- #print token.tok_name[self.type], repr(self.value)
+ # print token.tok_name[self.type], repr(self.value)
- def raise_error(self, msg, *args) :
+ def raise_error(self, msg: str, *args: Any) -> NoReturn :
if args:
try:
msg = msg % args
except:
msg = " ".join([msg] + list(map(str, args)))
if args:
try:
msg = msg % args
except:
msg = " ".join([msg] + list(map(str, args)))
- raise SyntaxError(msg, (self.filename, self.end[0],
- self.end[1], self.line))
+ raise SyntaxError(msg, (self.filename, self.end[0], self.end[1], self.line))
+
+ arcs: List[Tuple[Optional[Text], "NFAState"]]
- def __init__(self):
- self.arcs = [] # list of (label, NFAState) pairs
+ def __init__(self) -> None :
+ self.arcs = [] # list of (label, NFAState) pairs
- def addarc(self, next, label=None) :
+ def addarc(self, next: "NFAState", label: Optional[Text] = None) -> None :
assert label is None or isinstance(label, str)
assert isinstance(next, NFAState)
self.arcs.append((label, next))
assert label is None or isinstance(label, str)
assert isinstance(next, NFAState)
self.arcs.append((label, next))
+ nfaset: Dict[NFAState, Any]
+ isfinal: bool
+ arcs: Dict[Text, "DFAState"]
- def __init__(self, nfaset, final) :
+ def __init__(self, nfaset: Dict[NFAState, Any], final: NFAState) -> None :
assert isinstance(nfaset, dict)
assert isinstance(next(iter(nfaset)), NFAState)
assert isinstance(final, NFAState)
self.nfaset = nfaset
self.isfinal = final in nfaset
assert isinstance(nfaset, dict)
assert isinstance(next(iter(nfaset)), NFAState)
assert isinstance(final, NFAState)
self.nfaset = nfaset
self.isfinal = final in nfaset
- self.arcs = {} # map from label to DFAState
+ self.arcs = {} # map from label to DFAState
- def addarc(self, next, label) :
+ def addarc(self, next: "DFAState", label: Text) -> None :
assert isinstance(label, str)
assert label not in self.arcs
assert isinstance(next, DFAState)
self.arcs[label] = next
assert isinstance(label, str)
assert label not in self.arcs
assert isinstance(next, DFAState)
self.arcs[label] = next
- def unifystate(self, old, new) :
+ def unifystate(self, old: "DFAState", new: "DFAState") -> None :
for label, next in self.arcs.items():
if next is old:
self.arcs[label] = new
for label, next in self.arcs.items():
if next is old:
self.arcs[label] = new
- def __eq__(self, other) :
+ def __eq__(self, other: Any) -> bool :
# Equality test -- ignore the nfaset instance variable
assert isinstance(other, DFAState)
if self.isfinal != other.isfinal:
# Equality test -- ignore the nfaset instance variable
assert isinstance(other, DFAState)
if self.isfinal != other.isfinal:
- __hash__ = None # For Py3 compatibility.
+ __hash__: Any = None # For Py3 compatibility.
+
-def generate_grammar(filename="Grammar.txt") :
+def generate_grammar(filename: Path = "Grammar.txt") -> PgenGrammar :
p = ParserGenerator(filename)
return p.make_grammar()
p = ParserGenerator(filename)
return p.make_grammar()
projects / etc / vim.git / blobdiff