python/.goutputstream-8DMKF0
# walter's erster versuch mit Python
#
# starten mit python -i basics.py
def err(*e):
raise Exception('error:' + ', '.join(e))
exit()
dbgLev = 0
dbgTime = 0
def dbg(l, *e):
if dbgLev >= l:
print(*e)
from datetime import * ;
import re;
class PObj:
n2o = []
lahStr = True # lah is true ==> a string, False => tuple of strings
def __init__(self, nm = ''):
self.no = len(self.n2o)
self.name = f"{self.__class__.__name__ if nm == '' else nm}#{self.no}"
self.n2o.append(self)
def __str__ (self):
return self.name
def __repr__ (self, at=''):
return self.name
def sExp (self, at=''):
return self.name if at == '' else f'{self.name}{{{at}}}'
@staticmethod
def dbg(l, m):
if dbgLev >= l:
print(m)
p = '['
for o in PObj.n2o:
print(f"{p} {o.sExp()}")
p = ','
print(']')
class Parser(PObj):
end = '@'
rStart = 'start'
lrK = 0
useDflt = True
states = None
pCnt = 0
@staticmethod
def makeSA(*grammar):
"make Rule, Sym and Pos for given grammer in SA form"
Parser.lrK = 0
Rule.clear()
Rule.addSA(*grammar)
Rule.makeSymPos()
def makeWN(*grammar):
"make Rule, Sym and Pos for given grammer in WN form"
Parser.lrK = 0
Rule.clear()
Rule.addWN(*grammar)
Rule.makeSymPos()
@staticmethod
def clearXState():
if RulePos.poss != None:
oL = RulePos.poss[-1].no + 1
del PObj.n2o[oL:]
TState.tstates = None
UState.ustates = None
UState.pa2u.clear()
@staticmethod
def parse(inp, states = None):
if states == None:
states = Parser.states
st = [[states[0], 'st 0']]
stateFi = states[1]
stateCl = type(stateFi)
useDflt = Parser.useDflt
lahLen = max(1, Parser.lrK)
lahStr = PObj.lahStr or stateCl == PosState
if lahStr:
lahEnd = lahLen * Parser.end
inI = iter(inp + lahLen * [Parser.end])
dbg(3, f"iter coll {inp + lahLen * [Parser.end]}")
lah = ''.join([next(inI) for i in range(lahLen)])
else:
lahEnd = Parser.lrK * (Parser.end, )
inI = iter(inp + list(lahEnd))
lah = tuple([next(inI) for i in range(lahLen)])
dbg(3, f"????? lrK={Parser.lrK} len={lahLen} lah={lah}")
Parser.pCnt = -1
cntL = (len(inp) + lahLen) * len(Rule.rules)
ls = ''
while True:
Parser.pCnt += 1
if Parser.pCnt > cntL:
err("too many loops cnt={Parser.pCnt}, lah={lah} st={st}")
tos = st[-1]
dbg(2, f'run{Parser.pCnt} {ls} --> lah={lah} tos={tos}, st={len(st)} {st}')
m = tos[0]
go = m.to[lah] if lah in m.to else m.dflt if useDflt else None
if go == None:
return(f"bad lah={lah} expected {list(m.to.keys())} at {m.sExp()}")
elif isinstance(go, stateCl): #shift
ls = "shift"
if not lahStr:
st.append([go, lah[0]])
lah = lah[1:] + (next(inI), )
elif lahLen == 1:
st.append([go, lah])
lah = next(inI)
else:
st.append([go, lah[0]])
lah = lah[1:] + next(inI)
elif isinstance(go, Rule):
ls = f"red {go}"
n = [go]
if len(go.body) > 0:
nx = len(st) - len(go.body)
for i in range(nx, len(st)):
n.append(st[i][1])
del st[nx+1:]
else:
nx = len(st)
n.append('')
st.append(None)
pa = st[nx-1][0]
if go.sym not in pa.to:
if lah == lahEnd and len(st) == 2 and st[1][0] == stateFi:
return st[1][1]
return f'lah={lah} sym {go.sym} missing in pa {pa}, stack {st}'
dbg(2, f'run{Parser.pCnt}go {ls} --> pa={pa} go.sym={go.sym}')
st[nx] = [pa.to[go.sym], n]
else:
err(f"bad go {go}, lah={lah}, st={st}")
@staticmethod
def test0(nm, tsts):
"test for the current grammar, named nm the tests tsts"
if tsts == None:
tsts = ['2', '1 + 2 * 0', '2 * ( 1 * 2 + 0 )', '1 + 2 (']
trS = 0
def treeSplit(nd, pr):
nonlocal trS
trS += 1
if isinstance(nd, str):
return pr + nd
r = pr + str(nd[0]) + '/' + str(len(nd[0].body))
for ch in nd[1:]:
r += treeSplit(ch, pr + ' ')
return r
def treeSpli2(nd, of):
nonlocal trS
trS += 1
if isinstance(nd, str):
return nd
r = str(nd[0]) + '/' + str(len(nd[0].body)) + ' '
of += len(r)
r += treeSpli2(nd[1], of)
for ch in nd[2:]:
r += "\n" + of * ' ' + treeSpli2(ch, of)
return r
for i in range(len(tsts)) :
print(f"{nm} test {i} --- {tsts[i]} ---")
sT = [x for x in re.split(r'\s+', tsts[i]) if x != ''] # void empty strings, e.g. for ''
ast = Parser.parse(sT)
if isinstance(ast, str):
print(f'error run: {ast}')
else:
#print('run', tsts[i] , ' ==>', treeSplit(ast, "\n "))
print('run', tsts[i] , ' ==2\n ' + treeSpli2(ast, 2))
print(f" stats pCnt {Parser.pCnt}, inp {len(sT)}, lrK {Parser.lrK}, Rules {len(Rule.rules)}")
@staticmethod
def testSAT(nm, syn, *cs):
"""test named nm, with grammar syn (in form SA) and testcases cs"""
print(f"{nm} --- begin test -----------")
Parser.makeSA(*syn)
Parser.testT(nm, *cs)
@staticmethod
def testWNT(nm, syn, *cs):
"""test named nm, with grammar syn (in form WN) and testcases cs"""
print(f"{nm} --- begin test -----------")
Parser.makeWN(*syn)
Parser.testT(nm, *cs)
@staticmethod
def testT(nm, *cs):
"""test testcases cs named nm"""
st = f"{len(RuleSym.syms)} syms, {len(Rule.rules)} rules, {len(RulePos.poss)} rulePos"
tS = datetime.now()
k = 0
while True:
k += 1
res = UState.make(k)
el = (datetime.now() - tS).total_seconds()
elT = f"after {el}sec: " if dbgTime else ''
if res == None:
break
print(f"{res}: {elT}{st} {len(UState.ustates)} ustates")
if el > 7:
print("stop by timeout, do not check next LR(k)")
return
if k > 20:
print("stop by k >Y 20, do not check next LR(k)")
return
if k == 1:
res = UState.checkLR0()
if res == None:
k=0
else:
print(f"{res}: {elT}")
print(f'grammar is LR({k}): {elT}{st} {len(UState.ustates)} ustates')
PObj.dbg(1, 'UState 0')
Parser.test0(nm, cs)
@staticmethod
def test1():
"""my tests """
g = ["s = s '+' p", "s = p", "p = p '*' i", "p = i", "i = '(' s ')'", "i = '0'", "i = '1'", "i = '2'"]
Parser.testSAT('arithExpr', g
,'2', '1 + 2 * 0', '2 * ( 1 * 2 + 0 )', '1 + 2 (', '1 + 2 +')
g2 = g[1:-3] + ["s = s pm p", "p = p '/' i", "i = epm d", "i = epm i d", "epm = pm", "epm ="
, "pm = '+'", "pm = '-'", "d = '0'", "d = '1'", "d = '2'"]
g = g[1:-3] + ["s = s pm p", "p = p '/' i", "i = epm d", "i = i d", "epm = pm epm", "epm ="
, "pm = '+'", "pm = '-'", "d = '0'", "d = '1'", "d = '2'"]
# Parser.testSAT('arithExprPM' ,g
# ,'2', '1 + 2 * 0', '2 * ( 1 * 2 + 0 )', '1 + 2 (', '1 + 2 +'
# , '1 0 / - - 1 1 + + - 1 2 / ( 1 - - 2 / + 0 )')
Parser.testWNT('arithExprPM' , ["s=s pm p", "s=p", "p=p*i", "p=p/i", "p=i", "i=( s ) "
, "i=epm d", "i=i d", "epm = pm epm", "epm = ", "pm=+", "pm=-", "d=0", "d=1", "d = 2 "]
,'2', '1 + 2 * 0', '2 * ( 1 * 2 + 0 )', '1 + 2 (', '1 + 2 +'
, '1 0 / - - 1 1 + + - 1 2 / ( 1 - - 2 / + 0 )')
Parser.testSAT('LR(2)?' , ["S = AA 'a' 'a'", "S = AB 'a' 'b'", "AA =", "AB ="]
,"a a", "a b", "a c", "b a")
@staticmethod
def testKnuth():
"""some of the examples given by Donald E. Knuth. 1965. On the Translation of Languages from Left to Right """
Parser.testSAT('knuth(1)'
, ["S = A D", "A = 'a' C", "B = 'b' 'c' 'd'", "C = B E", "D =", "E = 'e'"]
, "a b c d e", "a b x d e", "a b", "a b c d e f")
Parser.testSAT('knuth(6)'
, ["S = 'a' A 'c'", "A = 'b' A 'b'", "A = 'b'"]
, "a b b b c", "a b c", "a b b c", "a b b b b b b b c e")
Parser.testSAT('knuth(7) lr(0)'
, ["S = 'a' A 'c'", "A = A 'b' 'b'", "A = 'b'"]
, "a b b b c", "a b c", "a b b c", "a b b b b b b b c e")
global dbgLev
dbgLev=3
Parser.testWNT('knuth(16x) lr(3)'
, ["S=B C", "B=C e", "B = ", "C=D", "C=D c", "D=", "D=d"]
, "", "c", "c e", "c e d")
dbgLev=0
Parser.testSAT('knuth(24)'
, ["S =", "S = 'a' A 'b' S", "S = 'b' B 'a' S", "A =", "A = 'a' A 'b' A", "B =", "B = 'b' B 'a' B"]
, "", "a b", "b a", "a b b", "a a b b", "a b a b", "b a a b")
class Rule (PObj):
rules = None
def __init__(self, sy, ty, bd):
self.sym = sy
super().__init__(f"R#{sy}")
self.body = bd
self.pos = ty
self.lah = set()
self.prd = set()
def sExp (self, at=''):
return super().sExp(f'sym={self.sym!s} body={self.body} pos0={self.pos[0] if self.pos != None else "-"}')
@staticmethod
def clear():
rules = None
Parser.clearXState()
PObj.n2o.clear()
RuleSym.n2y.clear()
RuleSym.syms = None
RulePos.poss = None
Rule(Parser.rStart, 'n', ["?"])
@staticmethod
def addSA(*src):
"add new rules: each rule is a string, elements separated by one or more spaces, terminals enclosed in apostrophs"
for s in src:
spl = re.split(r'\s+', s)
assert(spl[1] == '=')
Rule(spl[0], 'a', spl[2:])
@staticmethod
def addWN(*src):
"add new rules: each rule is a string, elements are Words or special chars, terminals those not a rule name"
for s in src:
spl = re.findall(r'\w+|\S', s)
assert(spl[1] == '=')
Rule(spl[0], 'n', spl[2:])
@staticmethod
def makeSymPos():
PObj.n2o[0].body[0] = PObj.n2o[1].sym
Rule.rules = Rule.n2o.copy()
PObj.dbg(4, 'made rules')
RuleSym.make()
PObj.dbg(4, 'made sym')
RulePos.make()
PObj.dbg(3, 'made pos')
@staticmethod
def makeLah(k):
""" compute for all rules
prd = productions of length <= k and
lah = prefixes of lenght k of all productions with length > k
in the outer loop increases lrK 1 by 1 """
tS = datetime.now()
assert not PObj.lahStr or k <= 1 or (len(Parser.end) == 1
and all([len(y) == 1 for r in Rule.rules for y in r.body if not isinstance(y, RuleSym)]))
cnt = 0
upd = True
while upd: # recomute all rules, until no change
upd = False
for r in Rule.rules:
cnt += 1
if r.mPrd(k):
upd = True
elT = f"{(datetime.now() - tS).total_seconds()}sec, " if dbgTime else ''
print(f"Rule.makeLah k={k}: {cnt} {elT}{len(r.prd)} {len(r.lah)} {r}")
if dbgLev >= 3:
for r in Rule.rules:
dbg(3, f"{r} {r.body} ---prd {r.prd} ---lah {r.lah}")
Parser.lrK = k
@staticmethod
def makeLahOld(toK):
""" compute for all rules
prd = productions of length <= toK and
lah = prefixes of lenght toK of all productions with length > toK
in the outer loop increases lrK 1 by 1 """
tS = datetime.now()
assert not PObj.lahStr or toK <= 1 or (len(Parser.end) == 1
and all([len(y) == 1 for r in Rule.rules for y in r.body if not isinstance(y, RuleSym)]))
cnt = 0
for k in range(Parser.lrK+1, toK+1): # increase toK by one
upd = True
while upd: # recomute all rules, until no change
upd = False
for r in Rule.rules:
lahO = r.lah.copy()
prdO = r.prd.copy()
r.mLah(k)
cnt += 1
if __debug__:
assert prdO <= r.prd
u = r.lah | r.prd
if not (lahO <= (u | {s[0: k-1] for s in u if len(s) == k})):
assert False, f"lah not increasing k={k} lahO={lahO} r.lah={r.lah} r.prd={r.prd}"
if not upd:
upd = lahO != r.lah or prdO != r.prd
assert all([len(s) == k for s in r.lah for r in Rule.rules])
elT = f"{(datetime.now() - tS).total_seconds()}sec, " if dbgTime else ''
print(f"Rule.makeLah k={k}: {cnt} {elT}{len(r.prd)} {len(r.lah)} {r}")
if dbgLev >= 3:
for r in Rule.rules:
dbg(3, f"{r} {r.body} ---prd {r.prd} ---lah {r.lah}")
Parser.lrK = k
def mLah(self, k):
"compute lah and prd from (shorter) lah and prd from used rules and literals"
assert k >= 1
assert k == Parser.lrK + 1
lP = { '' if PObj.lahStr else ()}
for y in self.body:
if isinstance(y, str):
aP = { y if PObj.lahStr else (y,) }
aL = set()
else:
aP = set()
aL = set()
for r in y.rules:
aP |= r.prd
aL |= r.lah
lQ = set()
for p in lP:
for a in aL:
if len(p) + len(a) >= k:
self.lah.add((p + a)[0 : k])
for a in aP:
if len(p) + len(a) > k:
self.lah.add((p + a)[0 : k])
else:
lQ.add(p+a)
lP = lQ
assert self.prd <= lP
self.prd = lP
self.lah -= lP | {e[0: k-1] for e in lP } | {e[0: -1] for e in self.lah}
def mPrd(self, k):
"compute lah and prd from (shorter) lah and prd from used rules and literals"
ee = set()
oL = self.lah.copy()
lP = { '' if PObj.lahStr else ()}
hNew = False
for y in self.body:
if isinstance(y, str):
aP = { y if PObj.lahStr else (y,) }
aL = ee
else:
aP = ee.union(*[r.prd for r in y.rules])
aL = ee.union(*[r.lah for r in y.rules])
lQ = set()
for p in lP:
for a in aP:
n = p + a
if len(n) <= k:
lQ.add(n)
else:
self.lah.add(n[0:k])
for a in aL:
if len(p) + len(a) >= k:
self.lah.add((p + a)[0:k])
lP = lQ
assert lP >= self.prd
assert self.lah >= oL
lF = self.lah - lP
s = {x for x in lF if len(x) < k}
if len(s) > 0:
rm = lF + lP
lF -= s
while True:
rm = {x[0:-1] for x in rm if len(x) > 0}
s -= rm
if len(s) == 0 or len(rm) == 0:
break
lF += s
upd = lP != self.prd or oL != lF
self.prd = lP
self.lah = lF
dbg(4, f"self {self} upd{upd} prd {self.prd} lah {self.lah}")
return upd
class RuleSym (PObj):
n2y = {}
syms = None
def __init__(self, sym):
self.sym = sym
super().__init__(f"Y#{sym}")
self.rules = []
self.lah = set()
def sExp (self):
return super().sExp(f"sym={self.sym!s} {self.rules} lah={self.lah}")
@staticmethod
def make():
i0 = len(PObj.n2o)
for r in Rule.rules:
if r.sym not in RuleSym.n2y:
RuleSym.n2y[r.sym] = RuleSym(r.sym)
RuleSym.n2y[r.sym].rules.append(r)
r.sym = RuleSym.n2y[r.sym]
RuleSym.syms = PObj.n2o[i0:]
assert Rule.n2o[0].sym == RuleSym.syms[0]
assert RuleSym.syms[0].sym == Parser.rStart
assert RuleSym.n2y[Parser.rStart] == RuleSym.syms[0]
assert len(RuleSym.n2y[Parser.rStart].rules) == 1
for r in Rule.rules:
b = r.body
if r.pos == 'a':
for ix in range(len(b)):
v = b[ix]
if v[0] == "'" and v[-1] == "'":
b[ix] = v[1: len(v)-1]
assert b[ix] != Parser.end
elif v in RuleSym.n2y:
b[ix] = RuleSym.n2y[v]
else:
err(f"rule {v} in {r} not in {Rule.rules}")
elif r.pos == 'n':
for ix in range(len(b)):
v = b[ix]
if v in RuleSym.n2y:
b[ix] = RuleSym.n2y[v]
else:
err(f'bad pos {r.pos} in {r.sExp()}')
class RulePos (PObj):
poss = None
def __init__(self, r, p):
super().__init__('P')
self.rule = r
self.pos = p
self.next = None
self.lah = None
def sExp (self):
return super().sExp(f"{self.rule!s} {self.pos} next={self.next!s}")
@staticmethod
def make():
l = len(PObj.n2o)
for r in Rule.rules:
b = r.body
r.pos = [RulePos(r, ix) for ix in range(len(b)+1)]
for ix in range(len(b)):
r.pos[ix].next = r.pos[ix+1]
RulePos.poss = PObj.n2o[l:]
def makeLah(k):
# compute lah for RuleSym and RulePos using lah from Rule
# lah = production of len <= k and prefix of len k of all production longer k
Rule.makeLah(k)
for y in RuleSym.syms:
y.lah = set().union(*[r.lah | r.prd for r in y.rules])
dbg(3, f"{y} {y.lah}")
for r in Rule.rules:
r.pos[-1].lah = {'' if PObj.lahStr else ()}
for pX in range(len(r.body)-1, -1, -1): # backward through the positions
p = r.pos[pX]
e = r.body[pX]
lS = e.lah if isinstance(e, RuleSym) else {e if PObj.lahStr else (e,)}
n = set()
for l in lS:
if len(l) == k:
n.add(l)
else:
for o in p.next.lah:
dbg(9, f"n.add(({l}+{o})[0:k])")
n.add((l+o)[0:k])
p.lah = n
dbg(3, f"{r} {pX} {p} {p.lah}")
assert r.pos[0].lah == r.prd | r.lah, (f"rule {r.sExp()} fails \npos[0].lah={r.pos[0].lah}"
f" \n== prd={r.prd} \n| lah={r.lah}"
f",\ndifference lah-..={r.pos[0].lah-r.prd-r.lah}, ..-lah={(r.prd|r.lah)-r.pos[0].lah}")
class PosState (PObj):
p2s = {}
pstates = None
def __init__(self, ps):
super().__init__('S')
assert isinstance(ps, frozenset)
self.pos = ps
self.to = {}
self.dflt = None
# self.stack = None
# self.red = {}
self.lah = 0
self.p2s[self.pos] = self
for p in self.pos:
self.addPos(p)
def sExp (self):
return super().sExp(f"{self.pos} to={self.to} dflt={self.dflt} lah={self.lah}")
def addPos(self, p):
if p.next == None:
self.to[p.rule] = p.rule.sym
else:
e = p.rule.body[p.pos]
if e in self.to:
self.to[e].add(p.next)
else:
self.to[e] = {p.next}
if isinstance(e, RuleSym):
for r in e.rules:
self.addPos(r.pos[0])
def addTrans(self):
for k, v in self.to.items():
if isinstance(v, set):
w = frozenset(v)
if w in PosState.p2s:
self.to[k] = PosState.p2s[w]
else:
n = PosState(w)
self.to[k] = n
n.addTrans()
@staticmethod
def make():
b = PosState(frozenset({Rule.rules[0].pos[0]}))
e = PosState(frozenset(b.to[RuleSym.syms[1]]))
b.addTrans()
e.addTrans()
PosState.pstates = PObj.n2o[b.no:]
Parser.states = PosState.pstates
print("PosState make b={b} e={e} pstates={len(PosState.pstates} states={len(Parser.states}")
class TState (PObj):
s2l = {}
tstates = None
def __init__(self, s):
super().__init__('T')
assert isinstance(s, PosState)
self.pst = s
self.pa = set()
self.to = {}
TState.s2l[s] = self
def sExp (self):
return super().sExp(f"{self.pst} pa={self.pa} to={self.to}")
def addPosA(self, p, a):
#assert p in self.pst.pos
pa = (p, a)
if pa in self.pa:
return
self.pa.add(pa)
if p.next == None:
if a not in self.to:
self.to[a] = p.rule
elif self.to[a] != p.rule:
err(f"lrK mismatch [{a}]={self.to[a]} != t={t}")
else:
e = p.rule.body[p.pos]
k = Parser.lrK
t = TState.s2l[self.pst.to[e]]
t.addPosA(p.next, a)
if isinstance(e, str):
for l in p.lah:
if l[0] == e:
if len(l) != k:
l = (l+a)[0:k]
if l in self.to:
if self.to[l] != t:
err("mismatch")
else:
self.to[l] = t
else:
if e in self.to:
if self.to[e] != t:
err("mismatch")
else:
self.to[e] = t
for n in p.next.lah:
if len(n) != k:
n = (n+a)[0:k]
for r in e.rules:
self.addPosA(r.pos[0], n)
@staticmethod
def make(k):
Parser.clearXState()
oL = len(PObj.n2o)
Parser.useDflt = False
RulePos.makeLah(k)
for s in PosState.pstates:
TState(s)
TState.tstates = PObj.n2o[oL:]
Parser.states = TState.tstates
TState.tstates[0].addPosA(Rule.rules[0].pos[0], k * (Parser.end if PObj.lahStr else (Parser.end, )))
class UState (PObj):
pa2u = {}
ustates = None
lrErr = None
def __init__(self, pa):
super().__init__('U')
assert isinstance(pa, frozenset)
assert pa not in UState.pa2u
self.pa = pa
self.to = {}
dbg(3, f"UState {self.sExp()}")
UState.pa2u[pa] = self
for a in pa:
self.addPosA(a)
def sExp (self):
return super().sExp(f"{self.pa} to={self.to}")
def addPosA(self, pa):
p, a = pa
if UState.lrErr != None:
return
if p.next == None:
if a not in self.to:
self.to[a] = p.rule
elif self.to[a] != p.rule:
UState.lrErr = f"lrK mismatch [{a}]={self.to[a]} != p={p.sExp()}"
print(UState.lrErr)
else:
e = p.rule.body[p.pos]
k = Parser.lrK
t = (p.next, a)
if isinstance(e, str):
for l in p.lah:
if l[0] == e:
if UState.lrErr != None:
return
elif len(l) != k:
l = (l+a)[0:k]
if l not in self.to:
self.to[l] = {t}
elif not isinstance(self.to[l], set):
UState.lrErr = f"lrK mismatch [{l}]->{self.to[l]} cannot add {t}"
print(UState.lrErr)
else:
self.to[l].add(t)
else:
if e not in self.to:
self.to[e] = {t}
elif t in self.to[e]:
return
else:
self.to[e].add(t)
for n in p.next.lah:
if len(n) != k:
n = (n+a)[0:k]
for r in e.rules:
self.addPosA((r.pos[0], n))
if UState.lrErr != None:
return
def addTrans(self):
for k, v in self.to.items():
if isinstance(v, Rule):
continue
pa = frozenset(v)
if pa in self.pa2u:
self.to[k] = self.pa2u[pa]
elif UState.lrErr != None:
return
else:
n = type(self)(pa)
self.to[k] = n
n.addTrans()
@staticmethod
def make(kArg):
k = kArg if kArg > 1 else 1
Parser.clearXState()
Parser.useDflt = False
RulePos.makeLah(k)
UState.lrErr = None
b = UState(frozenset([(Rule.rules[0].pos[0], k * (Parser.end if PObj.lahStr else (Parser.end, )))]))
e = UState(frozenset(b.to[RuleSym.syms[1]]))
b.addTrans()
e.addTrans()
UState.ustates = PObj.n2o[b.no: ]
Parser.states = UState.ustates
if UState.lrErr != None:
return f"grammar not LR({k}), because of {UState.lrErr}"
@staticmethod
def checkLR0():
""" check if the current LR(1) grammar is even LR(0)
return None if it is, otherwsie a string describing the conflicting state
LR(0) means, that a reduce step does not depend on lookahead.
a shift step however uses the char shifted (== lookahead) to determine the next state """
assert Parser.lrK == 1
for u in UState.ustates:
assert len(u.to) > 0
fi = None
for k,v in u.to.items():
if not isinstance(k, RuleSym):
if fi == None:
fi = v
elif v != fi if isinstance(v, Rule) else not (isinstance(v, UState) and isinstance(fi, UState)):
return f"grammar not LR(0) because of {u.sExp()}"
def testRe():
x = ' ab cd e?f *+??'
print(f"x={x}")
print("re: lookahead assertion and lookbehind assertions to find boundaries between words and or special character")
for y in re.finditer(r'\s+|(?<=\S)(?=\S)((?<=\W)|(?=\W))', x):
print([y.start(),y.end(), x[y.start(): y.end()+1]])
print("easier and more stable against leading/trailing spaces: use findall for words or special chars")
for y in re.finditer(r'\w+|\S', x):
print([y.start(),y.end(), x[y.start(): y.end()]])
print(re.findall(r'\w+|\S', x))
x += "' '' b 'oder1''1.2und. 3 ' '.a.234 4.. single' !"
print('mit strings and numbers:', x)
print(re.findall(r"""'(?:''|[^'])*' # single quoted strings, doubble apostrophs for a single
# non capturing group (?:...) otherwise findall will return groups!
|\d+(?:\.\d*) # number with leading digits and possible decimal point/digits
|\.\d+ # number with leading decimal points and digits
|\w+ # words
|\S""" # special chars
, x
, re.X)) # re.X = re.VERBOSE flag
if 0:
testRe()
exit()
if 0:
l = [0, 1, 2]
s = '012'
print([(i, l[0:i], s[0:i]) for i in range(6)])
print([(x, y) for x in range(3) for y in range(2)])
print([(x, y) for x in range(3) for y in range(3*x, 4*x+1)])
print([(x, y) for x in range(3) if x > 0 for y in range(3*x, 4*x+1) if y > x])
exit()
Parser.test1()
Parser.testKnuth()
print('end', __file__)