Quelle est la différence entre les analyses LR(0) et SLR ?

Question

Je travaille sur mes concepts de compilateurs mais je suis un peu perdu... La recherche sur Google ne m'a pas permis de trouver de réponse définitive.

Les analyseurs SLR et LR(0) sont-ils identiques ? Si non, quelle est la différence ?

Answer 1

Les analyseurs syntaxiques LR(0) et SLR(1) sont tous deux analyseurs ascendants, directionnels et prédictifs . Cela signifie que

• Les analyseurs syntaxiques tentent d'appliquer les productions en sens inverse pour ramener la phrase d'entrée au symbole de départ ( ascendant )
• Les analyseurs syntaxiques parcourent l'entrée de gauche à droite ( directionnel )
• Les analyseurs syntaxiques tentent de prédire les réductions à appliquer sans nécessairement voir toute l'entrée ( prédictif )

Les deux LR(0) et SLR(1) sont analyseurs syntaxiques de type shift/reduce c'est-à-dire qu'ils traitent les jetons du flux d'entrée en les plaçant sur une pile, et à chaque point, soit déplacement un jeton en le poussant sur la pile ou en réduisant une séquence de terminaux et de non-terminaux au sommet de la pile jusqu'à un symbole non-terminal. On peut montrer que toute grammaire peut être analysée de bas en haut à l'aide d'un analyseur shift/reduce, mais cet analyseur ne sera peut-être pas déterministe . En d'autres termes, l'analyseur peut avoir à "deviner" s'il doit appliquer un décalage ou une réduction, et peut finir par devoir revenir en arrière pour réaliser qu'il a fait le mauvais choix. Quelle que soit la puissance de l'analyseur déterministe shift/reduce que vous construisez, il ne sera jamais capable d'analyser toutes les grammaires.

Lorsqu'un analyseur déterministe shift/reduce est utilisé pour analyser une grammaire qu'il ne peut pas traiter, il en résulte que conflits de déplacement/réduction o réduire/réduire les conflits L'analyseur syntaxique peut se retrouver dans un état où il ne sait pas quelle action entreprendre. Dans un conflit shift/reduce, il ne peut pas dire s'il doit ajouter un autre symbole à la pile ou effectuer une réduction sur les symboles supérieurs de la pile. Dans un conflit réduction/réduction, l'analyseur sait qu'il doit remplacer les symboles du haut de la pile par un non-terminal, mais il ne peut pas dire quelle réduction utiliser.

Je m'excuse si c'est un long exposé, mais nous en avons besoin pour pouvoir aborder la différence entre l'analyse syntaxique LR(0) et SLR(1). Un analyseur LR(0) est un analyseur shift/reduce qui utilise zéro tokens de lookahead pour déterminer l'action à entreprendre (d'où le 0). Cela signifie que dans n'importe quelle configuration de l'analyseur, celui-ci doit avoir une action non ambiguë à choisir - soit il décale un symbole spécifique, soit il applique une réduction spécifique. S'il y a deux choix ou plus à faire, l'analyseur syntaxique échoue et nous disons que la grammaire n'est pas LR(0).

Rappelons que les deux conflits LR possibles sont shift/reduce et reduce/reduce. Dans ces deux cas, il y a au moins deux actions que l'automate LR(0) pourrait prendre, et il ne peut pas dire laquelle utiliser. Puisqu'au moins une des actions conflictuelles est une réduction, une ligne d'attaque raisonnable serait d'essayer de faire en sorte que l'analyseur soit plus prudent quant au moment où il effectue une réduction particulière. Plus précisément, supposons que l'analyseur soit autorisé à regarder le prochain token d'entrée pour déterminer s'il doit décaler ou réduire. Si nous autorisons l'analyseur à réduire uniquement lorsque cela "a du sens" (pour une certaine définition de "a du sens"), alors nous pourrions être en mesure d'éliminer le conflit en faisant en sorte que l'automate choisisse spécifiquement de décaler ou de réduire dans une étape particulière.

Dans SLR(1) ("Simplified LR(1)"), l'analyseur syntaxique est autorisé à regarder un token de lookahead lorsqu'il décide s'il doit décaler ou réduire. En particulier, lorsque l'analyseur veut essayer de réduire quelque chose de la forme A → w (pour le non-terminal A et la chaîne w), il regarde le prochain token d'entrée. Si ce token peut légalement apparaître après le non-terminal A dans une dérivation, l'analyseur syntaxique réduit. Sinon, il ne le fait pas. L'intuition ici est que dans certains cas, cela n'a pas de sens de tenter une réduction, car étant donné les jetons que nous avons vus jusqu'à présent et le jeton à venir, il n'y a aucune possibilité que la réduction soit correcte.

La seule différence entre LR(0) et SLR(1) est cette capacité supplémentaire à aider à décider de l'action à entreprendre en cas de conflit. De ce fait, toute grammaire qui peut être analysée par un analyseur LR(0) peut être analysée par un analyseur SLR(1). Cependant, les analyseurs SLR(1) peuvent analyser un plus grand nombre de grammaires que LR(0).

En pratique, cependant, SLR(1) est toujours une méthode d'analyse syntaxique assez faible. Plus souvent, vous verrez des analyseurs LALR(1) ("Lookahead LR(1)") utilisés. Ils fonctionnent également en essayant de résoudre les conflits dans un analyseur LR(0), mais les règles qu'ils utilisent pour résoudre les conflits sont beaucoup plus précises que celles utilisées dans SLR(1), et par conséquent un nombre beaucoup plus important de grammaires sont LALR(1) que SLR(1). Pour être un peu plus précis, les analyseurs SLR(1) essaient de résoudre les conflits en examinant la structure de la grammaire pour obtenir plus d'informations sur le moment où il faut décaler et réduire. Les analyseurs LALR(1) examinent à la fois la grammaire et l'analyseur LR(0) pour obtenir des informations encore plus spécifiques sur le moment où il faut décaler et réduire. Parce que LALR(1) peut regarder la structure de l'analyseur LR(0), il peut identifier plus précisément quand certains conflits sont faux. Les utilitaires Linux yacc y bison par défaut, produisent des analyseurs LALR(1).

Historiquement, les analyseurs syntaxiques LALR(1) étaient généralement construits par une méthode différente qui s'appuyait sur l'analyseur syntaxique LR(1), bien plus puissant, de sorte que vous verrez souvent LALR(1) décrit de cette façon. Pour comprendre cela, nous devons parler des analyseurs LR(1). Dans un analyseur LR(0), l'analyseur fonctionne en gardant une trace de l'endroit où il pourrait se trouver au milieu d'une production. Une fois qu'il a constaté qu'il a atteint la fin d'une production, il sait qu'il doit essayer de réduire. Cependant, l'analyseur syntaxique peut ne pas être capable de dire s'il se trouve à la fin d'une production et au milieu d'une autre, ce qui conduit à un conflit shift/reduce, ou à laquelle de deux productions différentes il a atteint la fin (un conflit reduce/reduce). Dans LR(0), cela conduit immédiatement à un conflit et l'analyseur syntaxique échoue. Dans SLR(1) ou LALR(1), l'analyseur syntaxique prend alors la décision de décaler ou de réduire en fonction du prochain token de lookahead.

Dans un analyseur LR(1), l'analyseur garde la trace d'informations supplémentaires au fur et à mesure de son fonctionnement. En plus de garder la trace de la production que l'analyseur croit être utilisée, il garde la trace des tokens possibles qui pourraient apparaître après que la production soit terminée. Parce que l'analyseur tient compte de ces informations à chaque étape, et pas seulement lorsqu'il doit prendre une décision, l'analyseur LR(1) est nettement plus puissant et précis que tous les analyseurs LR(0), SLR(1) ou LALR(1) dont nous avons parlé jusqu'à présent. LR(1) est une technique d'analyse syntaxique extrêmement puissante, et il est possible de montrer, à l'aide de quelques calculs mathématiques délicats, que tout langage pouvant être analysé de manière déterministe par LR(1) peut être analysé par LR(1). cualquier L'analyseur shift/reduce a une grammaire qui peut être analysée par un automate LR(1). (Notez que cela ne signifie pas que tous les grammaires qui peuvent être analysés de manière déterministe sont LR(1) ; cela dit seulement qu'un langage qui pourrait être analysé de manière déterministe a une certaine grammaire LR(1)). Cependant, cette puissance a un prix, et un analyseur syntaxique LR(1) généré peut nécessiter tellement d'informations pour fonctionner qu'il ne peut pas être utilisé en pratique. Un analyseur LR(1) pour un langage de programmation réel, par exemple, pourrait nécessiter des dizaines ou des centaines de mégaoctets d'informations supplémentaires pour fonctionner correctement. Pour cette raison, LR(1) n'est généralement pas utilisé dans la pratique, et des analyseurs plus faibles comme LALR(1) ou SLR(1) sont utilisés à la place.

Plus récemment, un nouvel algorithme d'analyse syntaxique appelé GLR(0) ("Generalized LR(0)") a gagné en popularité. Plutôt que d'essayer de résoudre les conflits qui apparaissent dans un analyseur LR(0), l'analyseur GLR(0) fonctionne en essayant toutes les options possibles en parallèle. En utilisant quelques astuces astucieuses, cela peut être fait pour fonctionner très efficacement pour de nombreuses grammaires. De plus, GLR(0) peut parser aucune grammaire sans contexte du tout D'autres analyseurs sont également capables de faire cela (par exemple, l'analyseur Earley ou un analyseur CYK), bien que GLR(0) tende à être plus rapide en pratique.

Si vous souhaitez en savoir plus, j'ai donné cet été un cours d'introduction aux compilateurs et j'ai passé un peu moins de deux semaines à parler des techniques d'analyse syntaxique. Si vous souhaitez obtenir une introduction plus rigoureuse à LR(0), SLR(1), et une foule d'autres techniques d'analyse syntaxique puissantes, vous pourriez apprécier mes diapositives de cours et mes devoirs sur l'analyse syntaxique. Tous les supports de cours sont disponibles ici sur mon site personnel .

J'espère que cela vous aidera !

Answer 2

Voici ce que j'ai appris. Habituellement, l'analyseur LR(0) peut présenter une ambiguïté, c'est-à-dire qu'une case de la table (que vous obtenez pour créer l'analyseur) peut avoir plusieurs valeurs (ou) pour mieux dire : l'analyseur conduit à deux états finaux avec la même entrée. L'analyseur SLR est donc créé pour lever cette ambiguïté. Pour le construire, il faut trouver toutes les productions qui mènent à des goto states, trouver le follow pour le symbole de production à gauche et n'inclure que les goto states qui sont présents dans le follow. Cela signifie que vous n'incluez pas une production qui n'est pas possible en utilisant la grammaire originale (parce que cet état n'est pas dans le follow set).

Answer 3

Dans la table d'analyse syntaxique pour LR(0), la règle de réduction pour la production est placée dans la ligne entière, à travers tous les terminaux, tandis que dans la table d'analyse syntaxique SLR, la règle de réduction pour la production est placée uniquement dans l'ensemble de suivi du non-terminal de gauche de la production réduite.

L'outil appelé parsing-EMU est très utile pour l'analyse syntaxique et peut générer les itemset first, follow, LR(0), LALR Evaluation, etc. Vous pouvez le trouver aquí .

Answer 4

En plus des réponses ci-dessus, la différence entre les analyseurs individuels de la classe des analyseurs 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 :

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).

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. Donc la grammaire ci-dessus n'est pas LR(0), mais c'est SLR(1). La table d'analyse suivante est générée par SLR :

L'animation suivante montre comment une expression d'entrée est analysée par la grammaire SLR(1) ci-dessus :

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

Définissons la grammaire comme suit :

# S --> A 
# A --> a A b | c
G = {}
NTs = ['S', 'A']
Ts = {'a', 'b', 'c'}
G['S'] = [['A']]
G['A'] = [['a', 'A', 'b'], ['c']]

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.