 |
|||
| HSG |
|
Beispiel 1
S --> ABcC A --> aA A --> λ B --> bbB B --> λ C --> BA
Welche terminalen Zeichen könnten in einer Ableitung von B vorne stehen? Die Ableitung B --> bbB belegt, dass das Zeichen ein b sein könnte. Weil man von B auch an das Ende einer Ableitung gelangen könnte, wird das notiert indem man λ zu diesen Zeichen dazunimmt.
Welche terminalen Zeichen könnten in einer Ableitung von C vorne stehen? Hier liegt der Fall insofern anders, dass zunächst keine Ableitung existiert, die ein Terminal vorne stehen hat. Aber es wäre denkbar, in der Produktion C --> BA das B durch λ zu ersetzen. Dann würde A weiter abgeleitet werden. In der Produktion A --> aA steht a vorne, in der Produktion A --> λ steht λ vorne, also sind a und λ in FIRST(C). Man hätte aber das B auch durch bbB ersetzen können, dann stünde b vorne. Da keine weiteren Ersetzungen in Frage kommen, gilt FIRST(C) = {a, b, λ}.
Aufgabe
Bestimme mit JFlap zu oben genannter Grammatik die FIRST-Mengen.
Definition
FIRST-Mengen können zu beliebigen Folgen β von Grammatiksymbolen gebildet werden. FIRST(β) besteht aus all den Terminalsymbolen t, mit denen ein aus β abgeleiteteter Satz beginnen kann.
FIRST(β) = {t ∈ T | β ⇒ ... ⇒ tγ}
Kann man ε (ε und λ werden synonym verwendet) aus β ableiten, so gehört auch ε zu First(β).
Algorithmus
Die FIRST-Mengen für die nonterminalen Symbole einer Grammatik werden parallel nach folgenden Regeln berechnet. Die Regeln sind solange anzuwenden, bis sich die FIRST-Mengen nicht mehr ändern.
- Für terminale Symbole a gilt: FIRST(a) = {a}
- Gibt es eine Produktion X → ε, so füge ε zu FIRST(X) hinzu.
- Gibt es eine Produktion X → Y1Y2...Yn, so füge zunächst FIRST(Y1)\{ε} zu FIRST(X) hinzu. Sollte gelten ε ∈ FIRST(Y1), d.h. Y1 lässt sich zu ε reduzieren, so füge auch FIRST(Y2)\{ε} hinzu. Sollte wiederum Y2 ε-ableitbar sein, fahre wie gehabt fort, bis du auf ein Yi stößt, das nicht ε-ableitbar ist. Sollten alle Yi ε-ableitbar sein, dann (und nur dann) füge auch ε zu FIRST(X) hinzu.
Beispiel
S → Ac A → Bd A → ccB B → λ
Schrittweise Ermittlung der FIRST-Mengen
S | {} | {} | {c} | {c,d} | {c,d} |
A | {} | {c} | {c,d} | {c,d} | {c,d} |
B | {} | {λ} | {λ} | {λ} | {λ} |
Compilertools
# nichtterminale Symbole sind Großbuchstaben
# alle anderen Zeichen sind terminale Symbole
# das Startsymbol steht ganz oben links
# '' steht fuer epsilon
G0 = [('S','Ac'),('A','Bd'),('A','ccB'),('B','')]
G1 = [('Z','S'),('S','Sb'),('S','bAa'),('A','aSc'),('A','a'),('A','aSb')] # Kunert
G2 = [('S','aAS'),('S','b'),('A','cAS'),('A','')] # Beispiel zu LL(1)
G3 = [('S','ABcC'),('A','aA'),('A',''),('B','bbB'),('B',''),('C','BA')] # j103
G4 = [('S','BAc'),('A','Aa'),('A','a'),('B','AB'),('B','bB'),('B','d')]
G5 = [('S','Sb'),('S','bAa'),('A','aSc'),('A','a'),('A','aSb')] #Kunert 1.3
G6 = [('S','Sb'),('S','Ac'),('A','b')]
G7 = [('S','bS'),('S','Ac'),('A','b'),('A','')]
G8 = [('A','B'),('A','BcA'),('B','d')]
G9 = [('S','A'),('A','aaA'),('A','b')]
G10 = [('S','aBC'),('A','bAc'),('A','b'),('B','AB'),('B','Cd'),('C','e'),('C','Bf')]
G11 = [('S','ABb'),('A','Bcd'),('A','a'),('B','Be'),('B','Af')]
G12 = [('S','BA'),('S','CS'),('A','Aa'),('A','b'),('B','CB'),('B','A'),('C','cC'),('C','c')]
G13 = [('S','ABc'),('A','AaB'),('A',''),('B','Cd'),('B','C'),('C','b'),('C','')]
G14 = [('S','aABc'),('A','bA'),('A','d'),('B','Be'),('B','')]
Grossbuchstaben = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def Zeichen(G):
"""
gibt Liste der in G vorkommenden Zeichen zurueck
"""
def s(G):
"""
fuegt alle Zeichen zu einem String zusammen
"""
if G == []:
return ''
else:
return G[0][0]+G[0][1]+s(G[1:])
return sorted(set(s(G)))
def Terminale(G):
"""
gibt die Liste der Terminalsymbole zurueck
"""
return sorted(set([c for c in Zeichen(G) if not c in Grossbuchstaben]))
def NonTerminale(G):
"""
gibt die Liste der NonTerminalsymbole zurueck
"""
return sorted(set([c for c in Zeichen(G) if c in Grossbuchstaben]))
def Start(G):
"""
ermittelt das Startsymbol der Grammatik
"""
sym = G[0][0]
if sym in NonTerminale(G):
return sym
else:
raise Exception
def rechteSeiten(X,G):
"""
gibt die Liste aller rechten Seiten aus G zurueck, die
X auf der linken Seite haben
"""
return [p[1] for p in G if p[0]==X]
import copy
def FIRST_Mengen(G):
"""
ermittelt fuer die Symbole der Grammatik G die FIRST-Mengen,
die Mengen werden in einem Dictionary zurueckgegeben
"""
F = {} # Dictionary fuer FIRST-Mengen
T = Terminale(G)
for t in T:
F.update({t:{t}}) # FIRST-Mengen von Terminalen t = {t}
N = NonTerminale(G)
for n in N:
F.update({n:set()}) # FIRST-Mengen von NonTerminalen sind zunaechst leer
while True:
Fa = copy.copy(F) # Fa ist eine echte Kopie das alten Zustands von F
# print(Fa) # DEBUG
for p in G:
X = p[0] # X ist linke Seite der Produktion
f = F.get(X) # f ist die bisherige FIRST-Menge von X
if p[1] == '': # rechte Seite ist leer
f = f|{''} # lambda hinzufuegen
F.update({X:f})
else:
for y in p[1]: # y durchlaueft alle Symbole der rechten Seite
fy = F.get(y) # fy ist bisherige FIRST-Menge von y
f = f|(fy-{''})
F.update({X:f})
if (y == p[1][-1]) and ('' in fy):
f = f|{''}
F.update({X:f})
if not '' in fy: break
if F == Fa: break # es hat sich nichts geaendert
return F
def FIRST(X,G):
"""
gibt die FIRST-Menge zu einer Zeichenkette X bestehend aus Terminal-
bzw. NonTerminal-Symbolen aus einer Grammatik G an
"""
assert type(X) == str
if X == '':
return {''}
else:
F = FIRST_Mengen(G)
f = set()
for y in X:
fy = F.get(y)
f = f|(fy-{''})
if (y == X[-1]) and ('' in fy):
f = f|{''}
if not '' in fy: break
return f
def folgt(B,w):
"""
gibt für eine Satzform w=αBβ β zurueck,
dabei sind α und β die Teile vor und nach B
"""
if B in w:
return w[w.index(B)+1:]
else:
raise Exception
def FOLLOW_Mengen(G):
"""
gibt die FOLLOW-Mengen zu den NonTerminalen der Grammatik G an,
die Mengen werden in einem Dictionary zurueckgegeben
"""
N = NonTerminale(G)
S = Start(G)
F = {}
for n in N:
if n == S:
F.update({n:{'$'}})
else:
F.update({n:set()})
while True:
Fa = copy.copy(F)
# print(Fa) # DEBUG
for p in G:
if len(p[1]) > 0:
for y in p[1]:
if y in N:
beta = p[1][p[1].index(y)+1:] # alles hinter y
fy = F.get(y) # bisherige FOLLOW-Menge von y
fy = fy|(FIRST(beta,G)-{''})
F.update({y:fy})
if (beta == '') or ('' in FIRST(beta,G)):
fA = F.get(p[0]) # fA FOLLOW-Menge der linken Seite
fy = fy|fA
F.update({y:fy})
if Fa == F: break
return F
def FOLLOW(X,G):
"""
gibt die FOLLOW-Menge zu einem NonTerminal X aus G zurueck
"""
return FOLLOW_Mengen(G).get(X)
def LL_Tabelle(G):
"""
gibt - wenn moeglich - die LL(1)-Tabelle zur Grammatik G zurueck,
die Tabelle ist ein Dictionary mit Indizes der Form ('A','b')
"""
T = {}
for p in G:
f = FIRST(p[1],G)
for a in f-{''}:
if (p[0],a) in T:
if T[(p[0],a)] != p[1]:
print('Fehler in 1 ',(p[0],a),' : ',T[(p[0],a)],p[1]) # DEBUG
# raise Exception
else:
T.update({(p[0],a):p[1]})
print('1 ',(p[0],a),' : ',T[(p[0],a)]) # DEBUG
if '' in f:
for b in FOLLOW(p[0],G):
if (p[0],b) in T:
if T[(p[0],b)] != p[1]:
print('Fehler in 2 ',(p[0],b),' : ',T[(p[0],b)],p[1]) #DEBUG
# raise Exception
else:
T.update({(p[0],b):p[1]})
print('2 ',(p[0],b),' : ',T[(p[0],b)]) # DEBUG
return T
def LL_parse(s,G):
"""
parst den String s zur Grammatik G anhand der LL-Tabelle
"""
T = LL_Tabelle(G)
stack = [Start(G)]
remaining = s+'$'
lookahead = remaining[0]
while (len(stack) > 0) or (len(remaining) > 1):
top = stack[-1]
print('---------------------------')
if top in NonTerminale(G):
N = stack.pop()
if not (N,lookahead) in T:
print('Fehler: kein Eintrag in LL-Tabelle!')
break
r = T[(N,lookahead)]
print('rechte Seite: ',r)
while len(r) > 0:
stack.append(r[-1])
r = r[0:-1]
else:
if top == remaining[0]:
print('matching: ',top)
stack.pop()
remaining = remaining[1:]
lookahead = remaining[0]
else:
print('Fehler: Stack und remaining matchen nicht!')
break
print('lookahead: ',lookahead)
print('stack: ',stack)
print('remaining: ',remaining)
ct0.py - Problem mit Rekursion (Gegenbeispiel G11), ct1.py
Zweck
FIRST-Mengen benötigt man zum Aufstellen der Parser-Tabellen beim LL(1)- oder SLR(1)-Verfahren. Soll man sich z.B. im Laufe einer Parse-Aktion für die Produktion A → aaA oder für die Produktion A → b entscheiden, wenn das lookahead-Zeichen ein a ist? Natürlich kann nur die erste Produktion die richtige sein, weil a ∈ FIRST(aaA) und a ∉ FIRST(b). Kennt man die FIRST-Mengen von α und β kann man eventuell genauso leicht zwischen A → α und A → β wählen.
First-Mengen benötigt man z.B. auch, um Follow-Mengen zu berechnen.
Links
- Parser - wikipedia
