Analyse de descente récursive - à partir de LL (1)

Question

L'expression & suivante simple de la calculatrice & "; la grammaire (BNF) peut être facilement analysée avec l’analyseur trivial à descente récursive, qui est prédictif LL (1):

<expr>      :=  <term> + <term>
            |   <term> - <term>
            |   <term>
<term>      :=  <factor> * <factor>
                <factor> / <factor>
                <factor>
<factor>    :=  <number>
            |   <id>
            |   ( <expr> )
<number>    :=  \d+
<id>        :=  [a-zA-Z_]\w+

Parce qu'il suffit toujours de voir le prochain jeton pour connaître la règle à choisir. Cependant, supposons que j'ajoute la règle suivante:

<command>   :=  <expr>
            |   <id> = <expr>

Pour interagir avec la calculatrice sur la ligne de commande, avec des variables telles que:

calc> 5+5
=> 10
calc> x = 8
calc> 6 * x + 1
=> 49

Est-il vrai que je ne peux pas utiliser un simple analyseur prédictif LL (1) pour analyser les règles <command>? J'ai essayé d'écrire l'analyseur pour cela, mais il semble que j'ai besoin de connaître davantage de jetons. La solution est-elle d'utiliser le retour en arrière, ou puis-je simplement mettre en œuvre LL (2) et regarder toujours deux jetons vers l'avant?

Comment les générateurs d’analyseur RD gèrent-ils ce problème (ANTLR, par exemple)?

Answer 1

Le problème avec

<command>   :=  <expr>
            |   <id> = <expr>

est que lorsque vous &, vous voyez & "; <id> vous ne pouvez pas dire s'il s'agit du début d'une affectation (deuxième règle) ou s'il s'agit d'un " <factor> " ;. Vous saurez seulement quand vous lirez le prochain jeton.

AFAIK ANTLR est LL (*) (et est également capable de générer des analyseurs syntaxiques de rat-pack si je ne me trompe pas), donc il gérera probablement ce programme en considérant deux jetons à la fois.

Si vous pouvez jouer avec la grammaire, je vous suggèrerais soit d'ajouter un mot clé pour l'affectation (par exemple, let x = 8):

<command>   :=  <expr>
            |   "let" <id> "=" <expr>

ou utilisez le = pour indiquer l'évaluation:

<command>   :=  "=" <expr>
            |   <id> "=" <expr>

Answer 2

Je pense qu'il existe deux manières de résoudre ce problème avec un analyseur récursif de descente: soit en utilisant (davantage) d'anticipation, soit en effectuant un retour en arrière.

Lookahead

command() {
    if (currentToken() == id && lookaheadToken() == '=') {
        return assignment();
    } else {
        return expr();
    }
}

Retour en arrière

command() {
    savedLocation = scanLocation();
    if (accept( id )) {
         identifier = acceptedTokenValue();
         if (!accept( '=' )) {
             setScanLocation( savedLocation );
             return expr();
         }
         return new assignment( identifier, expr() );
    } else {
         return expr();
    }
}

Answer 3

Le problème est que la grammaire:

<command>   :=  <expr>
            |   <id> = <expr>

n'est pas une procédure mutuellement récursive. Pour un analyseur décent récursif, vous devrez déterminer un équivalent non récursif.

rdentato post montre comment résoudre ce problème, en supposant que vous puissiez jouer avec la grammaire. Ce powerpoint énonce le problème un peu plus en détail et montre comment le corriger: http://www.google.com/url?sa=t & amp; source = web & amp; ct = res & amp; cd = 7 & amp; url = http% 3A % 2F% 2Fxml.cs.nccu.edu.edu.html sig2 = nlYKQVfakmqy_57137XzrQ

Answer 4

ANTLR 3 utilise un & "; LL (*) " analyseur contrairement à un analyseur LL (k), il regardera donc en avant jusqu’à ce qu’il atteigne la fin de l’entrée si nécessaire, sans effectuer un retour arrière, en utilisant un automate fini (DFA) déterministe spécialement optimisé.