Grammaire hors contexte

[emmesse]

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?

[emmesse]

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]

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]

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]

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]

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]

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 }

[emmesse]

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 }

[emmesse]

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]

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 }