Left-Factoring une grammaire en LL (1)

Question

J'ai un devoir où je dois convertir une grammaire en LL (1). Je l'ai déjà enlevé la récursion gauche, mais je vais avoir du mal à faire-affacturage gauche. Tous les exemples que j'ai trouvé sont simples, et ressembler à quelque chose comme ceci:

A -> aX | aY
devient:
A -> aZ
Z -> X | Y

Je comprends. Cependant, mes regards de grammaire plus comme ceci:

X -> aE | IXE | (X)E
E -> IE | BXE | ϵ
I -> ++ | --
B -> + | - | ϵ

Je ne sais pas comment appliquer l'exemple plus simple à cela. J'ai essayé pendant au moins deux heures et j'ai perdu la trace de toutes les choses que j'ai essayé. En général, mes tentatives ont regardé quelque chose comme ceci:

X  -> X' | IXE
X' -> aE | (X)E
E  -> IE | BIX'E | BX'E | ϵ

J'essaie ensuite de convertir les règles E en ceux ayant une seule production en commençant par + ou -:

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> IE | B'IX'E | IX'E | B'X'E | X'E | ϵ

Et puis ...

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> +P | -M | ϵ
P  -> +E | IX'E | +X'E | X'E
M  -> -E | IX'E | -X'E | X'E

Et ainsi de suite. Mais je finis toujours avec beaucoup de nonterminals supplémentaires, et quelques productions très longues / chaînes de productions, sans avoir réellement pris en compte à gauche il. Je ne sais pas comment aborder - je ne peux pas sembler éliminer certains ayant plusieurs productions nonterminal commençant par + et un -.

Answer 1

Jetons un coup d'oeil à votre grammaire:

$ \ qquad \ begin {align} X & \ Ae \ mid IXE \ mid (X) E \\ E & \ IE \ mid BXE \ mid \ varepsilon \\ I & \ to \ texte {++} \ mid \ texte {-} \\ B & \ to \ texte {+} \ mid \ texte {-} \ mid \ varepsilon \ End {align} $

Notez que $ X $ n'a pas besoin de gauche affacturage: toutes les règles ont disjoint PREMIER sets¹. Si vous voulez faire de cette évidence, vous pouvez déposer I $ $ et en ligne il:

$ \ qquad \ begin {align} X & \ Ae de la mi \ texte {++} XE \ mid \ texte {-} XE \ mid (X) E \\ E & \ to \ texte {++} E \ mid \ texte {-} E \ mid BXE \ mid \ varepsilon \\ B & \ to \ texte {+} \ mid \ texte {-} \ mid \ varepsilon \ End {align} $

De même, nous pouvons inline $ B $:

$ \ qquad \ begin {align} X & \ Ae de la mi \ texte {++} XE \ mid \ texte {-} XE \ mid (X) E \\ E & \ to \ texte {++} E \ mid \ texte {-} E \ mid \ texte {+} XE \ mid \ texte {-} XE \ mid XE \ mid \ varepsilon \ End {align} $

Maintenant, nous voyons que nous avons fait faire-affacturage à gauche $ E $: nous avons des conflits évidents, et nous obtenons des conflits supplémentaires via $ XE $. Donc, nous allons en ligne $ X $ une fois à $ XE $:

$ \ qquad \ begin {align} X & \ Ae de la mi \ texte {++} XE \ mid \ texte {-} XE \ mid (X) E \\ E & \ to \ texte {++} E \ mid \ texte {-} E \ mid \ texte {+} XE \ mid \ texte {-} XE \ mid Âèê \ mid \ texte {++} XEE \ mid \ texte {-} XEE \ mid (X) EE \ mid \ varepsilon \ End {align} $

Et maintenant, nous pouvons gauche facteur aussi facilement que dans votre exemple:

$ \ qquad \ begin {align} X & \ Ae de la mi \ texte {++} XE \ mid \ texte {-} XE \ mid (X) E \\ E & \ to \ texte {+} P \ mid \ texte {-} M \ mi Âèê \ mid (X) EE \ mid \ varepsilon \\ P & \ to \ texte {+} E \ mid XE \ mid \ texte {+} XEE \\ M & \ to \ text {-} E \ mid XE \ mid \ texte {-} XEE \ End {align} $

Maintenant, nous pouvons voir que nous ne va nulle part: par affacturage loin texte $ \ {de +} $ ou texte $ \ {-} $ des alternatives, nous creuser un autre $ X $, ce qui a encore une fois à la fois $ \ texte {+} $ et le texte $ \ {-}. $ dans sa première série

Alors, nous allons jeter un coup d'œil à votre langue. Via

$ \ qquad \ displaystyle X \ Rightarrow aE \ Rightarrow ^ * aI ^ n E \ Rightarrow aI ^ nBXE $

et

$ \ qquad \ displaystyle X \ Rightarrow aE \ Rightarrow ^ * aI ^ n E \ Rightarrow aI ^ NIE $

vous avez arbitrairement long préfixes de la forme $ + ^ + $ qui end différemment , sémantique sage: parser un LL (1) ne peut pas décider si une donnée (suivant) texte $ \ {+} $ appartient à une paire - ce qui voudrait dire le choix alternatif $ IE $ - ou vient seul -. ce qui voudrait dire le choix $ BXE $

Par conséquent, il ne ressemble pas à votre langue peut être exprimé par any LL (1) grammaire, essayant ainsi de convertir le vôtre en un seul est futile.

Il est encore pire: comme $ BXE \ Rightarrow BIXEE \ Rightarrow ^ * BI ^ n X E ^ n E $, vous ne pouvez pas décider de choisir $ BXE $ avec any fini look-ahead. Ce n'est pas une preuve formelle, mais elle suggère fortement que votre langue n'est pas même LL.

Si vous pensez à ce que vous faites - mélange notation polonaise avec les opérateurs unaire - il est peu surprenant que l'analyse devrait être difficile. En gros, il faut compter à partir de la gauche et de droite à même d'identifier un seul $ B $ - $ text \ {+} $ dans une longue chaîne de texte $ \ {+} $. Si je pense à plusieurs $ B $ - $ text \ {+} $ dans une chaîne, je ne suis même pas sûr que la langue (avec deux sémantiquement différentes mais égal syntaxiquement texte $ \ {+} $ ) peut être analysé de manière déterministe (sans retour en arrière) du tout.

---

1. Ce serait les ensembles de terminaux qui peuvent venir en premier lieu dans dérivations d'une règle de / non-terminal alternatif.