En plus des réponses ci-dessus, la différence entre les analyseurs individuels de la classe des analyseurs LR ascendants est de savoir s'ils entraînent des conflits shift/reduce ou reduce/reduce lors de la génération des tables d'analyse. Moins il y aura de conflits, plus la grammaire sera puissante (LR(0) < SLR(1) < LALR(1) < CLR(1)).
Par exemple, considérons la grammaire d'expression suivante :
E → E + T
E → T
T → F
T → T * F
F → ( E )
F → id
Ce n'est pas LR(0) mais SLR(1). En utilisant le code suivant, nous pouvons construire l'automate LR0 et construire la table d'analyse syntaxique (nous devons augmenter la grammaire, calculer le DFA avec fermeture, calculer les ensembles d'action et de goto) :
from copy import deepcopy
import pandas as pd
def update_items(I, C):
if len(I) == 0:
return C
for nt in C:
Int = I.get(nt, [])
for r in C.get(nt, []):
if not r in Int:
Int.append(r)
I[nt] = Int
return I
def compute_action_goto(I, I0, sym, NTs):
#I0 = deepcopy(I0)
I1 = {}
for NT in I:
C = {}
for r in I[NT]:
r = r.copy()
ix = r.index('.')
#if ix == len(r)-1: # reduce step
if ix >= len(r)-1 or r[ix+1] != sym:
continue
r[ix:ix+2] = r[ix:ix+2][::-1] # read the next symbol sym
C = compute_closure(r, I0, NTs)
cnt = C.get(NT, [])
if not r in cnt:
cnt.append(r)
C[NT] = cnt
I1 = update_items(I1, C)
return I1
def construct_LR0_automaton(G, NTs, Ts):
I0 = get_start_state(G, NTs, Ts)
I = deepcopy(I0)
queue = [0]
states2items = {0: I}
items2states = {str(to_str(I)):0}
parse_table = {}
cur = 0
while len(queue) > 0:
id = queue.pop(0)
I = states[id]
# compute goto set for non-terminals
for NT in NTs:
I1 = compute_action_goto(I, I0, NT, NTs)
if len(I1) > 0:
state = str(to_str(I1))
if not state in statess:
cur += 1
queue.append(cur)
states2items[cur] = I1
items2states[state] = cur
parse_table[id, NT] = cur
else:
parse_table[id, NT] = items2states[state]
# compute actions for terminals similarly
# ... ... ...
return states2items, items2states, parse_table
states, statess, parse_table = construct_LR0_automaton(G, NTs, Ts)
où la grammaire G, les symboles non-terminaux et terminaux sont définis comme suit
G = {}
NTs = ['E', 'T', 'F']
Ts = {'+', '*', '(', ')', 'id'}
G['E'] = [['E', '+', 'T'], ['T']]
G['T'] = [['T', '*', 'F'], ['F']]
G['F'] = [['(', 'E', ')'], ['id']]
Voici quelques autres fonctions utiles que j'ai implémentées avec les fonctions ci-dessus pour la génération de la table d'analyse LR(0) :
def augment(G, S): # start symbol S
G[S + '1'] = [[S, '$']]
NTs.append(S + '1')
return G, NTs
def compute_closure(r, G, NTs):
S = {}
queue = [r]
seen = []
while len(queue) > 0:
r = queue.pop(0)
seen.append(r)
ix = r.index('.') + 1
if ix < len(r) and r[ix] in NTs:
S[r[ix]] = G[r[ix]]
for rr in G[r[ix]]:
if not rr in seen:
queue.append(rr)
return S
La figure suivante (agrandir pour voir) montre le DFA LR0 construit pour la grammaire en utilisant le code ci-dessus :
![enter image description here]()
Le tableau suivant montre le tableau d'analyse syntaxique LR(0) généré sous forme de dataframe pandas, remarquez qu'il y a quelques conflits shift/reduce, indiquant que la grammaire n'est pas LR(0).
![enter image description here]()
L'analyseur SLR(1) évite les conflits shift / reduce ci-dessus en réduisant seulement si le prochain token d'entrée est un membre du Follow Set du non-terminal en cours de réduction. Le tableau d'analyse suivant est généré par SLR :
![enter image description here]()
L'animation suivante montre comment une expression d'entrée est analysée par la grammaire SLR(1) ci-dessus :
![enter image description here]()
La grammaire de la question n'est pas non plus LR(0) :
#S --> Aa | bAc | dc | bda
#A --> d
G = {}
NTs = ['S', 'A']
Ts = {'a', 'b', 'c', 'd'}
G['S'] = [['A', 'a'], ['b', 'A', 'c'], ['d', 'c'], ['b', 'd', 'a']]
G['A'] = [['d']]
comme on peut le voir dans le prochain DFA LR0 et la table d'analyse :
![enter image description here]()
il y a un changement / réduction du conflit à nouveau :
![enter image description here]()
Mais, la grammaire suivante qui accepte les chaînes de la forme a^ncb^n, n >= 1 est LR(0) :
A → a A b
A → c
S → A
# S --> A
# A --> a A b | c
G = {}
NTs = ['S', 'A']
Ts = {'a', 'b', 'c'}
G['S'] = [['A']]
G['A'] = [['a', 'A', 'b'], ['c']]
![enter image description here]()
Comme on peut le voir sur la figure suivante, il n'y a pas de conflit dans la table d'analyse générée.
![enter image description here]()
Voici comment la chaîne d'entrée a^2cb^2 peut être analysé à l'aide de la table d'analyse LR(0) ci-dessus, en utilisant le code suivant :
def parse(input, parse_table, rules):
input = 'aaacbbb$'
stack = [0]
df = pd.DataFrame(columns=['stack', 'input', 'action'])
i, accepted = 0, False
while i < len(input):
state = stack[-1]
char = input[i]
action = parse_table.loc[parse_table.states == state, char].values[0]
if action[0] == 's': # shift
stack.append(char)
stack.append(int(action[-1]))
i += 1
elif action[0] == 'r': # reduce
r = rules[int(action[-1])]
l, r = r['l'], r['r']
char = ''
for j in range(2*len(r)):
s = stack.pop()
if type(s) != int:
char = s + char
if char == r:
goto = parse_table.loc[parse_table.states == stack[-1], l].values[0]
stack.append(l)
stack.append(int(goto[-1]))
elif action == 'acc': # accept
accepted = True
df2 = {'stack': ''.join(map(str, stack)), 'input': input[i:], 'action': action}
df = df.append(df2, ignore_index = True)
if accepted:
break
return df
parse(input, parse_table, rules)
L'animation suivante montre comment la chaîne d'entrée a^2cb^2 est analysé avec l'analyseur LR(0) en utilisant le code ci-dessus :
![enter image description here]()
0 votes
Eh bien, même si je suis à la recherche d'une réponse appropriée à ce sujet, LALR(1) est juste une légère modification de LR(1), où la taille de la table est réduite de sorte que nous pouvons minimiser l'utilisation de la mémoire ...