Grammaire hors contexte

Discutez d'informatique ici !
emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

grammaire hors contexte

par emmesse » 08 Oct 2018, 11:20

bonjour,

nous allons parler de grammaires hors contextes (grammaire LL) qui servent à concevoir un compilateur.
Je me suis aperçu que la grammaire ci-dessous est ambiguë
Code: Tout sélectionner
D  ->  d D'
D' ->  ; d D'
D' -> epsilone
S  -> i S'
S' -> ; i S'
S' -> epsilone
C  -> D ; S

en effet, les deux productions pour D' se trouvent, dans la table d'analyse (LL), à la même ligne (D') et la même colonne (';'). Je pense alors que cette grammaire est meilleure:
Code: Tout sélectionner
C -> d D
C -> S
C -> epsilone
D -> ; C
D -> epsilone

pour la DDS, je verrais ceci:
Code: Tout sélectionner
C -> d D        | C.val = D.s
                | D.h = d.code
C -> S          | C.val = S.code
C -> epsilone   | C.val = chaîne vide
D -> ; C        | D.h = D1.h || C.code
D -> epsilone   | D.s = D.h

cette grammaire et cette dds pour deux listes séparé avec le même séparateur est-elle correcte?
quelqu'un a une idée?
Modifié en dernier par emmesse le 29 Juil 2019, 00:19, modifié 1 fois.



emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

Re: grammaire hors contexte

par emmesse » 08 Oct 2018, 13:08

bonjour,

cette grammaire ne fait pas exactement ce que j'attends car elle se termine par un point-virgule, ce que je ne souhaite pas. Je l'ai donc modifiée:
Code: Tout sélectionner
C     -> d D
C     -> S
C     -> epsilone
D     -> ; Cobli
D     -> epsilone
Cobli -> d D
Cobli -> S

la dds est:
Code: Tout sélectionner
C      -> d D       |  C.val = D.s
                    |  D.h = d.code
C      -> S         |  C.val = S.code
C      -> epsilone  |  C.val = chaîne vide
D      -> ; Cobli   |  D.h=D1.h || Cobli.code
D      -> epsilone  |  D.s = D.h
Cobli  -> d D       |  Cobli.val = D.s
                    |  D.h = d.code
Cobli  -> S         |  Cobli.val = S.code


et voici le STDS:
Code: Tout sélectionner
C     -> d { D.h = d.code } D { C.val = D.s }
C     -> S { C.val = S.code }
C     -> epsilone { C.val=chaîne vide }
D     -> ; Cobli { D.h = D1.h || Cobli.code }
D     -> epsilone { D.s = D.h }
Cobli -> d { D.h = d. code } D { Cobli.val = D.s }
Cobli -> S { Cobli.val = S.code}


pensez-vous que ceci est correct?

emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

Re: grammaire hors contexte

par emmesse » 14 Fév 2019, 17:57

excusez-moi de déterrer cette discussion mais j'ai trouvé:
Code: Tout sélectionner
corps -> déclaration corpsprim | S
corpsprim -> point-virgule délaration corpsprim | S
S -> instruction RS | epsilone
RS -> point-virgule instruction RS | epsilone

epsilone est une production vide
cette grammaire met un point virgule entre déclaration et instruction et ne se termine pas par point-virgule, dérive une éventuelle séquence de déclarations séparé par des point-virgules, puis un point virgule, puis une séquence d'instruction, ou bien juste une séquence d'instructions, ou bien juste une séquence de déclaration, ou bien rien du tout
cool...

emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

Re: grammaire hors contexte

par emmesse » 28 Juil 2019, 18:36

la DDS précédente est fausse car S n'est pas précédé d'un point-virgule.
voici la bonne:
Code: Tout sélectionner
c-> d D         | c.s=D.s
                | D.h=d.s
c-> S           | c.s=S.s
D-> ; c         | D.s=D.h + c.s   (+ = concaténation)
D-> epsilone    | D.s=D.h

la stds correspondante:
Code: Tout sélectionner
c -> d {D.h=d.s} D {c.s=D.s}
c -> S {c.s=S.s}
D -> ; c {D.s=D.h + c.s}   (+ =concatenation)
D -> epsilone {D.s=D.h}

en sachant que d et S sont des terminaux. d.s et S.s sont donc connus d'avance et dans le reste de le grammaire (qui n'est pas présentée ici), S est annulable ( S -> epsilone )

emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

Re: grammaire hors contexte

par emmesse » 20 Aoû 2023, 23:26

Bonjour,

voici une autre grammaire qui devrait faire l'affaire:
Code: Tout sélectionner
C -> d ; C
C -> S
S -> i  Ri
Ri -> ; i Ri
Ri -> epsilon


c'est la fusion d'une liste de "d" séparés par ";" et une liste de "i" séparés par le même séparateur ";"

voici la STDS ( le symbole || est la concaténation de chaines)
Code: Tout sélectionner
C -> d ; { C1.h = C.h || d.s } C1 { C.s = C1.s }
C -> S  { C.s = C.h || S.s }
S -> i { Ri.h = i.s } Ri { S.s = Ri.s }
Ri -> ; i { Ri1.h = Ri.h || i.s } Ri1 { Ri.s = Ri1.s }
Ri -> epsilon { Ri.s = Ri.h }

emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

Re: grammaire hors contexte

par emmesse » 24 Aoû 2023, 04:01

Le problème avec cette STDS, c'est que S ne peut pas être vide. Le texte d'entrée contient forcément un ou plusieurs i.

Avec la grammaire ci-dessous, le texte d'entré est soit:
- une liste de d séparée par des sep,
- une liste de d séparés par sep, puis un sep, puis une liste de i séparés par des sep
- une liste de i séparés par des sep
- la liste vide:
Code: Tout sélectionner
C -> d  Cprim
  -> S
  -> epsilon
Cprim -> sep DI
      -> epsilon
DI -> d Cprim
   -> S
S -> i Sprim
Sprim -> sep i Sprim
      -> epsilon

le schéma de traduction dirigé par la syntaxe est:
Code: Tout sélectionner
C -> d { Cprim.h = d.s } Cprim { C.s = Cprim.s }
  -> S { C.s = S.s }
  -> epsilon { C.s = nil }
Cprim -> sep {DI.h = Cprim.h } DI { Cprim.s = DI.s }
      -> epsilon { Cprim.s = Cprim.h }
DI -> d { Cprim.h =DI.h ||  d.s } Cprim { DI.s = Cprim.s }
   -> S { DI.s = DI.h || S.s }
S -> i { Sprim.h = i.s } Sprim { S.s = Sprim.s }
Sprim -> sep i { Sprim1.h= Sprim.h || i.s } Sprim1 { Sprimi.s = Sprim1.s }
      -> epsilon { Sprim.s = Sprim.h }

emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

Re: grammaire hors contexte

par emmesse » 23 Sep 2023, 18:08

Je verrais plutôt cette gramaire et cette STDS
Code: Tout sélectionner
C0 -> C    (cette ligne sert à donner un  attribut hérité vide à C, sinon C est la racine et ne peux pas avoir d'attributs hérités)
C -> d Cprim
  -> S
  -> epsilon
Cprim -> sep C
      -> epsilon
S -> i Sprim
Sprim -> sep i Sprim
      -> epsilon

C.h || d.s signifie C.h concaténé avec d.s
Code: Tout sélectionner
C0 -> { C.h = nil } C { C0.s = C.s }
C -> d { Cprim.h = C.h || d.s } Cprim { C.s = Cprim.s }
  -> { S.h = C.h } S { C.s = S.s }
  -> epsilon { C.s = C.h }
Cprim -> sep { C.h = Cprim.h } C { Cprim.s = C.s }
      -> epsilon { Cprim.s = Cprim.h }
S -> i { Sprim.h = S.h || i.s } Sprim { S.s = Srpim.s }
Sprim -> sep i { Sprim1.h = Sprim.h || i.s } Sprim1 { Sprim.s = Sprim1.s }
      -> epsilon { Sprim.s = Sprim.h }
Modifié en dernier par emmesse le 01 Déc 2023, 03:13, modifié 1 fois.

emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

Re: grammaire hors contexte

par emmesse » 16 Nov 2023, 05:59

pour une liste éventuellement vide
Code: Tout sélectionner
C0 -> C
   -> epsilon
C -> d Cprim
  -> S
Cprim -> sep C
      -> epsilon
S -> i Sprim
Sprim -> sep i Sprim
      -> epsilon

le schéma de traduction dirigé par la synthaxe:

Code: Tout sélectionner
si C0 n'est pas l'axiome:
C0 -> { C.h = C0.h } C { C0.s = C.s }
   -> epsilon { C0.s = C0.h }

si C0 est l'axiome:
C0 -> { C.h=nil } C { C0.s = C.s }
   -> epsilon { C0 = nil }

C -> d { Cprim.h = C.h || d.s } Cprim { C.s = Cprim.s }
  -> {S.h=C.h} S {C.s= S.s }
Cprim -> sep { C.h = Cprim.h } C { Cprim.s = C.s }
      -> epsilon { Cprim.s =Cprim.h }
S -> i {Sprim.h = S.h || i.s } Sprim { S.s = Sprim.s}
Sprim -> sep i { Sprim.h = S.h || i.s } Sprim { S.s = Sprim.s}
      -> epsilon { Sprim.s = Sprim.h }
Modifié en dernier par emmesse le 12 Jan 2024, 02:37, modifié 1 fois.

emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

Re: grammaire hors contexte

par emmesse » 12 Jan 2024, 02:25

dans la stds précédente, les attributs de Sprim sont faux:
Code: Tout sélectionner
Sprim -> sep i { Sprim.h = S.h || i.s } Sprim { S.s = Sprim.s}
      -> epsilon { Sprim.s = Sprim.h }


voici ce qui est bon:
Code: Tout sélectionner
Sprim -> sep i {sprim1.h=Sprim.h || i.s} Sprim1 {Sprim.s=Sprim1.s}
      -> epsilon { Sprim.s=Sprim.h}

emmesse
Membre Naturel
Messages: 11
Enregistré le: 08 Oct 2018, 09:48

Re: grammaire hors contexte

par emmesse » 16 Jan 2024, 09:30

ne pas faire:
Code: Tout sélectionner
si C0 est l'axiome:
C0 -> { C.h=nil } C { C0.s = C.s }
   -> epsilon { C0 = nil }

mais plutôt:
Code: Tout sélectionner
si C0 est l'axiome:
C0 -> { C.h=nil } C { C0.s = C.s }
   -> epsilon { C0.s = nil }

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 6 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite