Requisito previo: construcción de la tabla de análisis LL(1) , clasificación de analizadores de arriba hacia abajo, conjunto PRIMERO , conjunto SEGUIR
En este artículo, vamos a ver cómo diseñar el compilador LL(1) Parser usando Python.
LL(1) gramática
La primera ‘L’ en LL(1) significa escanear la entrada de izquierda a derecha, la segunda ‘L’ significa producir una derivación más a la izquierda y el ‘1’ para usar un símbolo de entrada de anticipación en cada paso para realizar el análisis decisiones de acción. La gramática LL(1) sigue el método de análisis de arriba hacia abajo. Para una clase de gramáticas llamada LL(1) podemos construir un analizador predictivo de gramáticas. Eso funciona con el concepto de analizador de descenso recursivo que no requiere retroceso.
Eliminación de recursividad izquierda
Una gramática se deja recursiva si tiene un no terminal A tal que hay una derivación A → A α | β. Los métodos de análisis de arriba hacia abajo no pueden manejar gramáticas recursivas a la izquierda, por lo que se necesita una transformación para eliminar la recursividad a la izquierda. La recursión a la izquierda se puede eliminar modificando la regla de la siguiente manera: (A’ es un nuevo no terminal y ε representa a épsilon).
A → β A’ A’ → α A’ | ε
Factoraje a la izquierda
Es una transformación gramatical que es útil para producir una gramática adecuada para el análisis predictivo o de arriba hacia abajo. Cuando la elección entre dos producciones alternativas no está clara, reescribimos las producciones para diferir la decisión de hacer la elección correcta.
For example, if we have grammar rule A → α β1 | α β2 A → α A’ A’ → β1 | β2
Concepto de primero y seguimiento
La construcción de un analizador de arriba hacia abajo es asistida por las funciones PRIMERO y SEGUIR, que están asociadas con una gramática G. Durante el análisis de arriba hacia abajo, PRIMERO y SEGUIR nos permiten elegir qué producción aplicar, según el siguiente símbolo de entrada.
Reglas para el primer cómputo:
1) Si x es terminal, entonces PRIMERO(x)={x}
2) Si X→ ε es producción, entonces agregue ε a FIRST(X)
3) Si X no es terminal y X → PQR entonces PRIMERO(X)=PRIMERO(P)
Si PRIMERO(P) contiene ε, entonces
PRIMERO(X) = (PRIMERO(P) – {ε}) U PRIMERO(QR)
Reglas para el cálculo de seguimiento:
Nota: Epsilon (ε) nunca puede estar presente en SEGUIMIENTO de ningún símbolo que no sea terminal.
1) Para el símbolo de inicio, coloque $en SEGUIR(S)
2) Si A→ α B, entonces SIGUE(B) = SIGUE(A)
3) Si A→ α B β, entonces
Si ε no está en PRIMERO(β),
SEGUIR (B) = PRIMERO (β)
más hacer,
SEGUIR(B) = (PRIMERO(β)-{ε}) U SEGUIR(A)
tabla de análisis
Después de la construcción de la tabla de análisis, si para cualquier símbolo no terminal en la tabla tenemos más de una regla de producción para cualquier símbolo terminal en la columna de la tabla, la gramática no es LL(1). De lo contrario, la gramática se considera como LL(1).
Reglas para la construcción de la tabla de análisis:
Paso 1: Para cada producción A → α , de la gramática dada, realice el Paso 2 y el Paso 3.
Paso 2: Para cada símbolo de terminal ‘a’ en FIRST(α), AGREGAR A → α en la tabla T[A,a], donde ‘A’ determina la fila y ‘a’ determina la columna.
Paso 3: Si ε está presente en PRIMERO(α), busque SEGUIR(A), AGREGAR A → ε, en todas las columnas ‘b’, donde ‘b’ es SEGUIR(A). (Pestaña])
Paso 4: Si ε está en PRIMERO(α) y $es el SIGUIENTE(A), AGREGAR A → α a T[A,$].
La suposición hecha en el código:
a) El símbolo LHS de la Primera regla se considera como símbolo de inicio.
b) ‘#’ representa el símbolo épsilon.
Acercarse
- Hay siete funciones y el código del controlador, juntos ejecutan los cálculos. El código toma reglas gramaticales como entrada. El usuario debe determinar qué símbolos son terminales (lista: term_userdef) y cuáles no son terminales (lista: nonterm_userdef).
- El código se ejecuta en el conjunto de muestra 5 con fines de demostración, como se muestra en el código, esta gramática ha abandonado la recursividad, se llama a la función computeAllFirsts(). Esta función es responsable de llamar a las funciones removeLeftRecursion() y LeftFactoring(). Estas funciones funcionan según las reglas mencionadas anteriormente, respectivamente. Ahora, se llama a la función first() para cada no terminal. La lógica recursiva implementada se basa únicamente en las reglas mencionadas de FIRST cálculo solamente.
- La condición base de first() es si está presente un símbolo épsilon o terminal, para cada código no terminal ingresa una lógica recursiva y si el PRIMERO tiene múltiples símbolos, se devuelve una lista; de lo contrario, se devuelve una string. Por lo tanto, entre líneas de código solo se hace que el programa tenga seguridad de tipo.
- El cálculo FIRST es el requisito previo para el cálculo FOLLOW ya que la función follow() tiene varias llamadas a la función first(). Un símbolo_de_inicio es el símbolo LHS de la Primera regla dada en la lista de ‘reglas’. (Esto se puede modificar), para el cálculo de SEGUIMIENTO se llama a la función computeAllFollows(). Esto conduce a la llamada de la función follow() en todos los no terminales. La función follow() tiene una lógica recursiva con una condición base, la función invocada en start_symbol que devolverá el símbolo $.
- Resto, todas las condiciones se manejan según las reglas mencionadas anteriormente en el cálculo de SEGUIMIENTO. Para el objetivo no terminal, se recorren todas las reglas y se calculan los primeros requeridos y los siguientes circulares. Todos los resultados intermedios se acumulan durante el recorrido y la lista final de seguimiento calculado se devuelve al final del recorrido. Aquí también, el caso base devuelve una string, pero si hay varios símbolos en el resultado, se devuelve una lista. Por lo tanto, entre líneas adicionales de código se agregan para seguridad de tipo.
- Después de calcular FIRST y FOLLOW, se llama a la función createPaseTable(). Aquí, los primeros y los siguientes se emiten de forma formateada. Luego, para la tabla de análisis, se prepara una lista 2D llamada ‘mat’, los no terminales forman filas y los terminales forman columnas, con ‘$’ como una columna adicional. Las reglas mencionadas anteriormente para la construcción de la tabla de análisis forman la base de la lógica implementada.
Enfoque para la validación de strings
- Después de generar la tabla de análisis, debemos validar la string de entrada para la gramática dada. Hacemos uso de la pila y el búfer para este propósito. Si la gramática no es LL(1), no se puede realizar la validación de strings. Ingrese lo siguiente del SÍMBOLO DE INICIO, ‘$’ tanto en la pila como en el búfer. En primer lugar, ingrese la string de entrada en orden inverso en el búfer. Luego agregue el SÍMBOLO DE INICIO en la parte superior de la pila.
- Luego, recorremos iterativamente el estado actual de la pila y el búfer y hacemos coincidir las entradas de Table[x][y], donde ‘x’ es un símbolo en la parte superior de la pila e ‘y’ es un símbolo en la parte posterior del búfer. . Tomamos la regla correspondiente de la tabla y expandimos No terminal en TOS en la siguiente iteración.
- Si x e y ambos símbolos son los mismos terminales, entonces los sacamos de la pila y del búfer y continuamos con el cálculo. Si la pila y el búfer permanecen solo con el símbolo ‘$’, esto muestra que todos los símbolos de string de entrada se han emparejado y la string pertenece a la gramática dada. Si Rule no está presente en la tabla de análisis o x e y son símbolos terminales desiguales, entonces la string no pertenece a la gramática dada.
A continuación se muestra la implementación completa:
Python3
# LL(1) parser code in python
def removeLeftRecursion(rulesDiction):
# for rule: A->Aa|b
# result: A->bA',A'->aA'|#
# 'store' has new rules to be added
store = {}
# traverse over rules
for lhs in rulesDiction:
# alphaRules stores subrules with left-recursion
# betaRules stores subrules without left-recursion
alphaRules = []
betaRules = []
# get rhs for current lhs
allrhs = rulesDiction[lhs]
for subrhs in allrhs:
if subrhs[0] == lhs:
alphaRules.append(subrhs[1:])
else:
betaRules.append(subrhs)
# alpha and beta containing subrules are separated
# now form two new rules
if len(alphaRules) != 0:
# to generate new unique symbol
# add ' till unique not generated
lhs_ = lhs + "'"
while (lhs_ in rulesDiction.keys()) \
or (lhs_ in store.keys()):
lhs_ += "'"
# make beta rule
for b in range(0, len(betaRules)):
betaRules[b].append(lhs_)
rulesDiction[lhs] = betaRules
# make alpha rule
for a in range(0, len(alphaRules)):
alphaRules[a].append(lhs_)
alphaRules.append(['#'])
# store in temp dict, append to
# - rulesDiction at end of traversal
store[lhs_] = alphaRules
# add newly generated rules generated
# - after removing left recursion
for left in store:
rulesDiction[left] = store[left]
return rulesDiction
def LeftFactoring(rulesDiction):
# for rule: A->aDF|aCV|k
# result: A->aA'|k, A'->DF|CV
# newDict stores newly generated
# - rules after left factoring
newDict = {}
# iterate over all rules of dictionary
for lhs in rulesDiction:
# get rhs for given lhs
allrhs = rulesDiction[lhs]
# temp dictionary helps detect left factoring
temp = dict()
for subrhs in allrhs:
if subrhs[0] not in list(temp.keys()):
temp[subrhs[0]] = [subrhs]
else:
temp[subrhs[0]].append(subrhs)
# if value list count for any key in temp is > 1,
# - it has left factoring
# new_rule stores new subrules for current LHS symbol
new_rule = []
# temp_dict stores new subrules for left factoring
tempo_dict = {}
for term_key in temp:
# get value from temp for term_key
allStartingWithTermKey = temp[term_key]
if len(allStartingWithTermKey) > 1:
# left factoring required
# to generate new unique symbol
# - add ' till unique not generated
lhs_ = lhs + "'"
while (lhs_ in rulesDiction.keys()) \
or (lhs_ in tempo_dict.keys()):
lhs_ += "'"
# append the left factored result
new_rule.append([term_key, lhs_])
# add expanded rules to tempo_dict
ex_rules = []
for g in temp[term_key]:
ex_rules.append(g[1:])
tempo_dict[lhs_] = ex_rules
else:
# no left factoring required
new_rule.append(allStartingWithTermKey[0])
# add original rule
newDict[lhs] = new_rule
# add newly generated rules after left factoring
for key in tempo_dict:
newDict[key] = tempo_dict[key]
return newDict
# calculation of first
# epsilon is denoted by '#' (semi-colon)
# pass rule in first function
def first(rule):
global rules, nonterm_userdef, \
term_userdef, diction, firsts
# recursion base condition
# (for terminal or epsilon)
if len(rule) != 0 and (rule is not None):
if rule[0] in term_userdef:
return rule[0]
elif rule[0] == '#':
return '#'
# condition for Non-Terminals
if len(rule) != 0:
if rule[0] in list(diction.keys()):
# fres temporary list of result
fres = []
rhs_rules = diction[rule[0]]
# call first on each rule of RHS
# fetched (& take union)
for itr in rhs_rules:
indivRes = first(itr)
if type(indivRes) is list:
for i in indivRes:
fres.append(i)
else:
fres.append(indivRes)
# if no epsilon in result
# - received return fres
if '#' not in fres:
return fres
else:
# apply epsilon
# rule => f(ABC)=f(A)-{e} U f(BC)
newList = []
fres.remove('#')
if len(rule) > 1:
ansNew = first(rule[1:])
if ansNew != None:
if type(ansNew) is list:
newList = fres + ansNew
else:
newList = fres + [ansNew]
else:
newList = fres
return newList
# if result is not already returned
# - control reaches here
# lastly if eplison still persists
# - keep it in result of first
fres.append('#')
return fres
# calculation of follow
# use 'rules' list, and 'diction' dict from above
# follow function input is the split result on
# - Non-Terminal whose Follow we want to compute
def follow(nt):
global start_symbol, rules, nonterm_userdef, \
term_userdef, diction, firsts, follows
# for start symbol return $ (recursion base case)
solset = set()
if nt == start_symbol:
# return '$'
solset.add('$')
# check all occurrences
# solset - is result of computed 'follow' so far
# For input, check in all rules
for curNT in diction:
rhs = diction[curNT]
# go for all productions of NT
for subrule in rhs:
if nt in subrule:
# call for all occurrences on
# - non-terminal in subrule
while nt in subrule:
index_nt = subrule.index(nt)
subrule = subrule[index_nt + 1:]
# empty condition - call follow on LHS
if len(subrule) != 0:
# compute first if symbols on
# - RHS of target Non-Terminal exists
res = first(subrule)
# if epsilon in result apply rule
# - (A->aBX)- follow of -
# - follow(B)=(first(X)-{ep}) U follow(A)
if '#' in res:
newList = []
res.remove('#')
ansNew = follow(curNT)
if ansNew != None:
if type(ansNew) is list:
newList = res + ansNew
else:
newList = res + [ansNew]
else:
newList = res
res = newList
else:
# when nothing in RHS, go circular
# - and take follow of LHS
# only if (NT in LHS)!=curNT
if nt != curNT:
res = follow(curNT)
# add follow result in set form
if res is not None:
if type(res) is list:
for g in res:
solset.add(g)
else:
solset.add(res)
return list(solset)
def computeAllFirsts():
global rules, nonterm_userdef, \
term_userdef, diction, firsts
for rule in rules:
k = rule.split("->")
# remove un-necessary spaces
k[0] = k[0].strip()
k[1] = k[1].strip()
rhs = k[1]
multirhs = rhs.split('|')
# remove un-necessary spaces
for i in range(len(multirhs)):
multirhs[i] = multirhs[i].strip()
multirhs[i] = multirhs[i].split()
diction[k[0]] = multirhs
print(f"\nRules: \n")
for y in diction:
print(f"{y}->{diction[y]}")
print(f"\nAfter elimination of left recursion:\n")
diction = removeLeftRecursion(diction)
for y in diction:
print(f"{y}->{diction[y]}")
print("\nAfter left factoring:\n")
diction = LeftFactoring(diction)
for y in diction:
print(f"{y}->{diction[y]}")
# calculate first for each rule
# - (call first() on all RHS)
for y in list(diction.keys()):
t = set()
for sub in diction.get(y):
res = first(sub)
if res != None:
if type(res) is list:
for u in res:
t.add(u)
else:
t.add(res)
# save result in 'firsts' list
firsts[y] = t
print("\nCalculated firsts: ")
key_list = list(firsts.keys())
index = 0
for gg in firsts:
print(f"first({key_list[index]}) "
f"=> {firsts.get(gg)}")
index += 1
def computeAllFollows():
global start_symbol, rules, nonterm_userdef,\
term_userdef, diction, firsts, follows
for NT in diction:
solset = set()
sol = follow(NT)
if sol is not None:
for g in sol:
solset.add(g)
follows[NT] = solset
print("\nCalculated follows: ")
key_list = list(follows.keys())
index = 0
for gg in follows:
print(f"follow({key_list[index]})"
f" => {follows[gg]}")
index += 1
# create parse table
def createParseTable():
import copy
global diction, firsts, follows, term_userdef
print("\nFirsts and Follow Result table\n")
# find space size
mx_len_first = 0
mx_len_fol = 0
for u in diction:
k1 = len(str(firsts[u]))
k2 = len(str(follows[u]))
if k1 > mx_len_first:
mx_len_first = k1
if k2 > mx_len_fol:
mx_len_fol = k2
print(f"{{:<{10}}} "
f"{{:<{mx_len_first + 5}}} "
f"{{:<{mx_len_fol + 5}}}"
.format("Non-T", "FIRST", "FOLLOW"))
for u in diction:
print(f"{{:<{10}}} "
f"{{:<{mx_len_first + 5}}} "
f"{{:<{mx_len_fol + 5}}}"
.format(u, str(firsts[u]), str(follows[u])))
# create matrix of row(NT) x [col(T) + 1($)]
# create list of non-terminals
ntlist = list(diction.keys())
terminals = copy.deepcopy(term_userdef)
terminals.append('$')
# create the initial empty state of ,matrix
mat = []
for x in diction:
row = []
for y in terminals:
row.append('')
# of $ append one more col
mat.append(row)
# Classifying grammar as LL(1) or not LL(1)
grammar_is_LL = True
# rules implementation
for lhs in diction:
rhs = diction[lhs]
for y in rhs:
res = first(y)
# epsilon is present,
# - take union with follow
if '#' in res:
if type(res) == str:
firstFollow = []
fol_op = follows[lhs]
if fol_op is str:
firstFollow.append(fol_op)
else:
for u in fol_op:
firstFollow.append(u)
res = firstFollow
else:
res.remove('#')
res = list(res) +\
list(follows[lhs])
# add rules to table
ttemp = []
if type(res) is str:
ttemp.append(res)
res = copy.deepcopy(ttemp)
for c in res:
xnt = ntlist.index(lhs)
yt = terminals.index(c)
if mat[xnt][yt] == '':
mat[xnt][yt] = mat[xnt][yt] \
+ f"{lhs}->{' '.join(y)}"
else:
# if rule already present
if f"{lhs}->{y}" in mat[xnt][yt]:
continue
else:
grammar_is_LL = False
mat[xnt][yt] = mat[xnt][yt] \
+ f",{lhs}->{' '.join(y)}"
# final state of parse table
print("\nGenerated parsing table:\n")
frmt = "{:>12}" * len(terminals)
print(frmt.format(*terminals))
j = 0
for y in mat:
frmt1 = "{:>12}" * len(y)
print(f"{ntlist[j]} {frmt1.format(*y)}")
j += 1
return (mat, grammar_is_LL, terminals)
def validateStringUsingStackBuffer(parsing_table, grammarll1,
table_term_list, input_string,
term_userdef,start_symbol):
print(f"\nValidate String => {input_string}\n")
# for more than one entries
# - in one cell of parsing table
if grammarll1 == False:
return f"\nInput String = " \
f"\"{input_string}\"\n" \
f"Grammar is not LL(1)"
# implementing stack buffer
stack = [start_symbol, '$']
buffer = []
# reverse input string store in buffer
input_string = input_string.split()
input_string.reverse()
buffer = ['$'] + input_string
print("{:>20} {:>20} {:>20}".
format("Buffer", "Stack","Action"))
while True:
# end loop if all symbols matched
if stack == ['$'] and buffer == ['$']:
print("{:>20} {:>20} {:>20}"
.format(' '.join(buffer),
' '.join(stack),
"Valid"))
return "\nValid String!"
elif stack[0] not in term_userdef:
# take font of buffer (y) and tos (x)
x = list(diction.keys()).index(stack[0])
y = table_term_list.index(buffer[-1])
if parsing_table[x][y] != '':
# format table entry received
entry = parsing_table[x][y]
print("{:>20} {:>20} {:>25}".
format(' '.join(buffer),
' '.join(stack),
f"T[{stack[0]}][{buffer[-1]}] = {entry}"))
lhs_rhs = entry.split("->")
lhs_rhs[1] = lhs_rhs[1].replace('#', '').strip()
entryrhs = lhs_rhs[1].split()
stack = entryrhs + stack[1:]
else:
return f"\nInvalid String! No rule at " \
f"Table[{stack[0]}][{buffer[-1]}]."
else:
# stack top is Terminal
if stack[0] == buffer[-1]:
print("{:>20} {:>20} {:>20}"
.format(' '.join(buffer),
' '.join(stack),
f"Matched:{stack[0]}"))
buffer = buffer[:-1]
stack = stack[1:]
else:
return "\nInvalid String! " \
"Unmatched terminal symbols"
# DRIVER CODE - MAIN
# NOTE: To test any of the sample sets, uncomment ->
# 'rules' list, 'nonterm_userdef' list, 'term_userdef' list
# and for any String validation uncomment following line with
# 'sample_input_String' variable.
sample_input_string = None
# sample set 1 (Result: Not LL(1))
# rules=["A -> S B | B",
# "S -> a | B c | #",
# "B -> b | d"]
# nonterm_userdef=['A','S','B']
# term_userdef=['a','c','b','d']
# sample_input_string="b c b"
# sample set 2 (Result: LL(1))
# rules=["S -> A | B C",
# "A -> a | b",
# "B -> p | #",
# "C -> c"]
# nonterm_userdef=['A','S','B','C']
# term_userdef=['a','c','b','p']
# sample_input_string="p c"
# sample set 3 (Result: LL(1))
# rules=["S -> A B | C",
# "A -> a | b | #",
# "B-> p | #",
# "C -> c"]
# nonterm_userdef=['A','S','B','C']
# term_userdef=['a','c','b','p']
# sample_input_string="a c b"
# sample set 4 (Result: Not LL(1))
# rules = ["S -> A B C | C",
# "A -> a | b B | #",
# "B -> p | #",
# "C -> c"]
# nonterm_userdef=['A','S','B','C']
# term_userdef=['a','c','b','p']
# sample_input_string="b p p c"
# sample set 5 (With left recursion)
# rules=["A -> B C c | g D B",
# "B -> b C D E | #",
# "C -> D a B | c a",
# "D -> # | d D",
# "E -> E a f | c"
# ]
# nonterm_userdef=['A','B','C','D','E']
# term_userdef=["a","b","c","d","f","g"]
# sample_input_string="b a c a c"
# sample set 6
# rules=["E -> T E'",
# "E' -> + T E' | #",
# "T -> F T'",
# "T' -> * F T' | #",
# "F -> ( E ) | id"
# ]
# nonterm_userdef=['E','E\'','F','T','T\'']
# term_userdef=['id','+','*','(',')']
# sample_input_string="id * * id"
# example string 1
# sample_input_string="( id * id )"
# example string 2
# sample_input_string="( id ) * id + id"
# sample set 7 (left factoring & recursion present)
rules=["S -> A k O",
"A -> A d | a B | a C",
"C -> c",
"B -> b B C | r"]
nonterm_userdef=['A','B','C']
term_userdef=['k','O','d','a','c','b','r']
sample_input_string="a r k O"
# sample set 8 (Multiple char symbols T & NT)
# rules = ["S -> NP VP",
# "NP -> P | PN | D N",
# "VP -> V NP",
# "N -> championship | ball | toss",
# "V -> is | want | won | played",
# "P -> me | I | you",
# "PN -> India | Australia | Steve | John",
# "D -> the | a | an"]
#
# nonterm_userdef = ['S', 'NP', 'VP', 'N', 'V', 'P', 'PN', 'D']
# term_userdef = ["championship", "ball", "toss", "is", "want",
# "won", "played", "me", "I", "you", "India",
# "Australia","Steve", "John", "the", "a", "an"]
# sample_input_string = "India won the championship"
# diction - store rules inputed
# firsts - store computed firsts
diction = {}
firsts = {}
follows = {}
# computes all FIRSTs for all non terminals
computeAllFirsts()
# assuming first rule has start_symbol
# start symbol can be modified in below line of code
start_symbol = list(diction.keys())[0]
# computes all FOLLOWs for all occurrences
computeAllFollows()
# generate formatted first and follow table
# then generate parse table
(parsing_table, result, tabTerm) = createParseTable()
# validate string input using stack-buffer concept
if sample_input_string != None:
validity = validateStringUsingStackBuffer(parsing_table, result,
tabTerm, sample_input_string,
term_userdef,start_symbol)
print(validity)
else:
print("\nNo input String detected")
# Author: Tanmay P. Bisen
Producción
Rules:
S->[['A', 'k', 'O']]
A->[['A', 'd'], ['a', 'B'], ['a', 'C']]
C->[['c']]
B->[['b', 'B', 'C'], ['r']]
After elimination of left recursion:
S->[['A', 'k', 'O']]
A->[['a', 'B', "A'"], ['a', 'C', "A'"]]
C->[['c']]
B->[['b', 'B', 'C'], ['r']]
A'->[['d', "A'"], ['#']]
After left factoring:
S->[['A', 'k', 'O']]
A->[['a', "A''"]]
A''->[['B', "A'"], ['C', "A'"]]
C->[['c']]
B->[['b', 'B', 'C'], ['r']]
A'->[['d', "A'"], ['#']]
Calculated firsts:
first(S) => {'a'}
first(A) => {'a'}
first(A'') => {'c', 'r', 'b'}
first(C) => {'c'}
first(B) => {'r', 'b'}
first(A') => {'d', '#'}
Calculated follows:
follow(S) => {'$'}
follow(A) => {'k'}
follow(A'') => {'k'}
follow(C) => {'d', 'c', 'k'}
follow(B) => {'d', 'c', 'k'}
follow(A') => {'k'}
Firsts and Follow Result table
Non-T FIRST FOLLOW
S {'a'} {'$'}
A {'a'} {'k'}
A'' {'c', 'r', 'b'} {'k'}
C {'c'} {'d', 'c', 'k'}
B {'r', 'b'} {'d', 'c', 'k'}
A' {'d', '#'} {'k'}
Generated parsing table:
k O d a c b r $
S S->A k O
A A->a A''
A'' A''->C A' A''->B A' A''->B A'
C C->c
B B->b B C B->r
A' A'-># A'->d A'
Validate String => a r k O
Buffer Stack Action
$O k r a S $ T[S][a] = S->A k O
$O k r a A k O $ T[A][a] = A->a A''
$O k r a a A'' k O $ Matched:a
$O k r A'' k O $ T[A''][r] = A''->B A'
$O k r B A' k O $ T[B][r] = B->r
$O k r r A' k O $ Matched:r
$O k A' k O $ T[A'][k] = A'->#
$O k k O $ Matched:k
$O O $ Matched:O
$ $ Valid
Valid String!
Inferencia
El conjunto de muestras 7 se utiliza para representar la salida del código y cubre todos los aspectos del análisis LL(1). Se imprime la gramática después de la eliminación de la recursividad por la izquierda y después de la factorización por la izquierda. Después de eso, también tenemos los primeros y siguientes resultados de cálculo. Luego generamos la tabla de análisis, si no hay entradas múltiples en ninguna posición (Tabla[NT][T]) en la tabla, decimos que la gramática es LL(1). Finalmente, la string de entrada de muestra se valida mediante la validación del búfer de pila.
Publicación traducida automáticamente
Artículo escrito por tanmaybisen2001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA