Grammaires LL(1) : calculer First et Follow

Le principe

LL(1) signifie : lecture de gauche à droite (Left-to-right), dérivation la plus à gauche (Leftmost), un token de lookahead. À chaque non-terminal, le parser décide quelle règle appliquer d’après le prochain token de l’entrée.

First et Follow

• First(α) : les terminaux par lesquels peut commencer une chaîne dérivée de α. On y ajoute ε si α peut disparaître (être « annulable »).
• Follow(A) : les terminaux qui peuvent suivre le non-terminal A dans une dérivation. $ marque la fin de l’entrée.

Un exemple

La grammaire classique des expressions arithmétiques, déjà débarrassée de la récursion à gauche :

E  -> T E'
E' -> + T E' | ε
T  -> F T'
T' -> * F T' | ε
F  -> ( E ) | id

Les ensembles obtenus :

First(E) = First(T) = First(F) = { (, id }
First(E') = { +, ε }          First(T') = { *, ε }

Follow(E) = Follow(E') = { $, ) }
Follow(T) = Follow(T')  = { +, $, ) }
Follow(F) = { *, +, $, ) }

Le calcul par point fixe

On applique les règles en boucle jusqu’à ce qu’aucun ensemble ne grandisse. Le programme ci-dessous recalcule exactement les ensembles ci-dessus.

EPS = "ε"

grammar = {
    "E":  [["T", "E'"]],
    "E'": [["+", "T", "E'"], [EPS]],
    "T":  [["F", "T'"]],
    "T'": [["*", "F", "T'"], [EPS]],
    "F":  [["(", "E", ")"], ["id"]],
}


def first_sets(g):
    first = {a: set() for a in g}
    changed = True
    while changed:
        changed = False
        for a, prods in g.items():
            for prod in prods:
                before = len(first[a])
                for sym in prod:
                    if sym == EPS:
                        first[a].add(EPS)
                        break
                    if sym not in g:                 # terminal
                        first[a].add(sym)
                        break
                    first[a] |= first[sym] - {EPS}
                    if EPS not in first[sym]:
                        break
                else:                                # tous les symboles sont annulables
                    first[a].add(EPS)
                changed |= len(first[a]) != before
    return first


def follow_sets(g, first, start):
    follow = {a: set() for a in g}
    follow[start].add("$")
    changed = True
    while changed:
        changed = False
        for a, prods in g.items():
            for prod in prods:
                for i, sym in enumerate(prod):
                    if sym not in g:
                        continue
                    before = len(follow[sym])
                    rest_nullable = True
                    for nxt in prod[i + 1:]:
                        if nxt not in g:             # terminal
                            follow[sym].add(nxt)
                            rest_nullable = False
                            break
                        follow[sym] |= first[nxt] - {EPS}
                        if EPS not in first[nxt]:
                            rest_nullable = False
                            break
                    if rest_nullable:
                        follow[sym] |= follow[a]
                    changed |= len(follow[sym]) != before
    return follow

L’appel est first_sets(grammar), puis follow_sets(grammar, first, "E").

Table d’analyse et conflits

Pour chaque règle A → α, on place la règle dans la case M[A, a] pour chaque terminal a de First(α). Si α est annulable, on la place aussi dans M[A, b] pour chaque b de Follow(A).

M[E,  id] = E  -> T E'      M[E,  (] = E  -> T E'
M[E', +]  = E' -> + T E'    M[E', )] = E' -> ε    M[E', $] = E' -> ε
M[T,  id] = T  -> F T'      M[T,  (] = T  -> F T'
M[T', *]  = T' -> * F T'    M[T', +] = T' -> ε    M[T', )] = T' -> ε    M[T', $] = T' -> ε
M[F,  id] = F  -> id        M[F,  (] = F  -> ( E )

La grammaire est LL(1) si aucune case ne reçoit deux règles. Deux causes de conflit reviennent sans cesse : la récursion à gauche (E → E + T boucle indéfiniment) et les préfixes communs entre alternatives. On les corrige en éliminant la récursion à gauche, comme ci-dessus avec E → T E', et en factorisant à gauche.

Sources

• Wikipédia : LL parser