Comment supprimer une ambiguïté dans la grammaire suivante?

Question

Comment faire pour supprimer l'ambiguïté dans la grammaire suivante?

E -> E * F | F + E | F 

F -> F - F | id 

Answer 1

D'abord, nous devons trouver l'ambiguïté. Considérons les règles pour E sans F; changez F en f et considérez-le comme un symbole terminal. Ensuite, la grammaire

E -> E * f 
E -> f + E 
E -> f 

est ambiguë. Considérons f + f * f:

E      E 
    |      | 
    +-------+--+   +-+-+ 
    |  | |   | | | 
    E  * f   f + E 
    +-+-+      | 
    | | |      +-+-+ 
    f + E      E * f 
     |      | 
     f      f 

Nous pouvons résoudre cette ambiguïté en forçant * ou + à avoir préséance. Généralement, * a la priorité dans l'ordre des opérations, mais c'est totalement arbitraire.

E -> f + E | A 
A -> A * f | f 

Maintenant, la chaîne f + f * f a juste une analyse syntaxique:

E 
    | 
    +-+-+ 
    | | | 
    f + E 
     | 
     A 
     | 
     +-+-+ 
     A * f 
     | 
     f 

Maintenant, considérons notre grammaire originale qui utilise F au lieu de f:

E -> F + E | A 
A -> A * F | F 
F -> F - F | id 

Est-ce ambigu? C'est. Considérons la chaîne id - id - id.

E     E 
|     | 
A     A 
|     | 
F     F 
|     | 
+-----+----+----+ +----+----+----+ 
     | | |   | | | 
     F - F   F - F 
     |   |   |   | 
    +-+-+  id  id  +-+-+ 
    F - F       F - F 
    | |       | | 
    id id      id id 

L'ambiguïté ici est que - peut être à gauche associative ou à droite. Nous pouvons choisir la même convention que pour +:

E -> F + E | A 
A -> A * F | F 
F -> id - F | id 

Maintenant, nous avons une seule analyse syntaxique:

E 
| 
A 
| 
F 
| 
+----+----+----+ 
    | | | 
    id - F 
       | 
      +--+-+ 
      | | | 
      id - F 
       | 
       id 

Maintenant, est cette grammaire ambiguë? Ce n'est pas. S y aura # (+) + s, et nous avons toujours besoin d'utiliser exactement la production E -> F + E fois # (+) fois puis la production E -> A une fois.

s y aura # (*) * s, et nous devons toujours utiliser la production A -> A * F exactement # (*) fois et ensuite la production E -> F une fois.

s y aura # (-) -s, et nous devons toujours utiliser la production F -> id - F exactement # (-) fois et la production F -> id une fois. Ce qui a exactement # (+) + s, # (*) * s et # (-) -s peut être pris pour acquis (les nombres peuvent être zéro s'ils ne sont pas présents dans s). Que E -> A, A -> F et F -> id doivent être utilisés exactement une fois peut être montré comme suit:

Si E -> A n'est jamais utilisé, toute chaîne dérivée aura toujours E, un non terminal , dedans, et donc ne sera pas une chaîne dans la langue (rien n'est généré sans prendre E -> A au moins une fois). De plus, chaque chaîne qui peut être générée avant d'utiliser E -> A contient au maximum un E (vous commencez avec un E, et la seule autre production en garde un E), donc il n'est jamais possible d'utiliser E -> A plus que une fois que. Donc E -> A est utilisé exactement une fois pour toutes les chaînes dérivées. La démonstration fonctionne de la même manière pour A -> F et F -> id.Que E -> F + E, A -> A * F et F -> id - F sont utilisés exactement # (+), # (*) et # (-) fois, respectivement, est apparent à partir de l ' fait que ce sont les seules productions qui introduisent leurs symboles respectifs et chacune introduit une instance.

Si l'on considère les sous-grammaires de nos grammaires résultants, nous pouvons prouver qu'ils sont sans ambiguïté comme suit:

F -> id - F | id 

C'est une grammaire sans ambiguïté pour (id -)*id. La seule dérivation de (id -)^kid est d'utiliser F -> id - F k fois, puis d'utiliser F -> id exactement une fois. Nous avons déjà vu que F est sans ambiguïté pour le langage qu'il reconnaît. Par le même argument, c'est une grammaire non ambiguë pour le langage F(* F)*. La dérivation de F(* F)^k nécessitera l'utilisation de A -> A * F exactement k fois, puis l'utilisation de A -> F. Parce que la langue est produite à partir de F sans ambiguïté et parce que la langue A sépare sans ambiguïté les instances de F en utilisant *, un symbole non généré par F, la grammaire

A -> A * F | F 
F -> id - F | id 

Est également sans ambiguïté. Pour compléter l'argument, appliquer la même logique à la grammaire générant (F +) * A à partir du symbole de départ E.