Left-Factoring une grammaire en LL (1)
-
16-10-2019 - |
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 -.
La solution
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.
- Ce serait les ensembles de terminaux qui peuvent venir en premier lieu dans dérivations d'une règle de / non-terminal alternatif.