Problème de création de la grammaire LL (1)

Question

J'apprends comment les analyseurs fonctionnent en créant un simple analyseur de descente récursif. Cependant, j'ai un problème pour définir ma grammaire comme LL (1). Je veux être en mesure d'analyser les deux énoncés suivants:

a = 1 
a + 1 

Pour ce faire, je l'ai créé les règles de grammaire suivantes:

statement: assignent | expression 
assignment: NAME EQUALS expression 
expression: term [(PLUS|MINUS) term] 
term:  NAME | NUMBER 

Cependant, cela conduit à l'ambiguïté lors de l'utilisation d'un LL (1) parser que lorsqu'un jeton NAME est rencontré dans la règle statement, il ne sait pas s'il s'agit d'un assignment ou d'un expression sans anticipation.

La grammaire de Python est LL (1), donc je sais que c'est possible mais je ne sais pas comment faire. J'ai regardé les règles de grammaire de Python trouvées ici (https://docs.python.org/3/reference/grammar.html) mais je ne suis toujours pas sûr de la façon dont elles implémentent cela.

Toute aide serait grandement apprécié :)

Answer 1

Traitez = comme un opérateur de priorité très faible. Cependant (sauf si vous voulez un langage comme C où = est vraiment un opérateur avec une préséance très faible), vous devez l'exclure des expressions internes (par exemple parenthétiques).

Si vous aviez seulement la multiplication et l'addition, vous pouvez utiliser:

expression: factor ['+' factor] 
factor:  term ['*' term] 
term:  ID | NUMBER | '(' expression ')' 

C'est un guide pour la priorité des opérateurs: a une priorité plus élevée parce que les arguments + peuvent inclure s mais pas vice versa. Donc, nous pourrions simplement ajouter la cession:

statement: expression ['=' expression] 

Malheureusement, cela permettrait, par exemple:

(a + 1) = b 

ce qui est indésirable. Il doit donc être éliminé, mais il est possible de l'éliminer lorsque la production est acceptée (par une vérification de la forme du premier expression), plutôt que dans la grammaire elle-même. Si je comprends bien, c'est ce que fait l'analyseur Python; voir le long commentaire sur test et mots-clés.

Si vous utilisiez un analyseur LR (1) à la place, vous n'auriez pas ce problème.