Annuler
connectez vous
logique en post-bac
- Description de mathématique formelle-termes et relations
- Théorèmes
- Théories logiques
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann LogiqueTopics traitant de logique [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Grammaire propre & LL(1)
Posté par Khiti
Bonjour à tous,
J'ai différent exercices concernant la grammaire propre et les grammaires LL(1).
Exercice1:
Soit le langage L={e,(0),((0)),(((0))),((((0)))),.....)
1) Donner la grammaire qui reconnaît un tel langage.
G= { E=> (E) | (0) , E'=> E | e)
C'est correct ?
Exercice2:
Soient les règles de grammaire suivantes: {Expr=>nbre|Expr'+'Expr|Expr'-'Expr}
1) Déterminer les ensembles Vn, Vt, P Axiome
Vn={Expr}
Vt={nbre,+,-}
P={Expr=>nbre|Expr'+'Expr|Expr'-'Expr}
Axiome={Expr}
2) Est-elle LL(1) ? Transformer la grammaire en LL(1).
Elle n'est pas LL(1) car elle est récursive à gauche.
Pour la transformer en LL(1), je ne sais pas faire ...
Exercice3
Soient les règles suivantes de grammaire: {E->TE'|nbre, E'->+TE'|e, T->(E)T', T'->(E)T'|e}
1) Déterminer les ensembles Vn, Vt, P, S
Vn={E,T,E',T'}
Vt={nbre,+,e,(,)}
P= {E->TE'|nbre, E'->+TE'|e, T->(E)T', T'->(E)T'|e}
S={E}
C'est correct ?
2) Render la grammaire propre
E-> T+TE' | T | nbre
E'-> +TE' | +T
T-> (E)(E)T' | (E)
T'-> (E)T' | (E)
Merci d'avance pour votre aide.
Mes souvenirs sont un peu lointains ...
Dans l'ensemble les réponses me paraissent cohérentes.
Pour rendre LL(1) je pense que c'est du genre:
Expr => nbre | nbre SExpr
SExpr => '+' Expr | '-' Expr
Merci pour ton intérêt.
Que représente SExpr ?
Et dans l'exercice3:
Le + fait-il partie de Vt ? (car on a + et non '+')
Et concernant la grammaire propre, la ligne: E'-> +TE' | +T est-elle cohérente ? (on a le droit d'écrire +T ?)
Et la ligne T-> (E)(E)T' | (E) peut-elle être simplifiée par T-> (E)T' | (E) ?
Merci !
Citation :
Que représente SExpr ?
Que représente SExpr ?
Un nouveau non terminal (élément de Vn). Pour rendre une grammaire LL(1), on introduit un nouveau NT de façon à éliminer la récursivité à gauche.
Citation :
Le + fait-il partie de Vt ? (car on a + et non '+')
Le + fait-il partie de Vt ? (car on a + et non '+')
Je pense que oui, on oublie souvent les apostrophes dans l'énoncé des règles comportant des opérateurs usuels.
Citation :
concernant la grammaire propre, la ligne: E'-> +TE' | +T est-elle cohérente ?
Là effectivement ça ne me paraît pas correct, un E' ne peut pas se réécrire en un +T suivi de rien, au minimum on a +Te .Rappelle moi la définition d'une grammaire "propre" . Exercice 3 2) me paraît à revoir.concernant la grammaire propre, la ligne: E'-> +TE' | +T est-elle cohérente ?
Ok merci.
Une grammaire est dite propre si elle ne contient pas des règles de production du type: A=>e
Donc comment faire pour l'exercice 3 ?
Je reviens à l'exercice 1. J'aurais plutôt écrit:
L => e | E
E => (0) | (E)
L'axiome est L (il représente le langage). Ta grammaire n'est pas fausse à condition de dire que l'axiome est E', ce qui n'est pas très habituel comme notation, mais l'ordre des règles n'est pas logique, on écrit en principe (sauf si on t'a indiqué une autre convention explicitement) d'abord les réécritures terminales, puis les réécritures faisant intervenir les non terminaux.
Je regarde la suite.
Citation :
Une grammaire est dite propre si elle ne contient pas des règles de production du type: A=>e
Une grammaire est dite propre si elle ne contient pas des règles de production du type: A=>e
e représentant VIDE encore noté
si j'en crois une définition que je viens de lire.
Définition : Une grammaire est dite propre si elle ne contient aucune production A->
Comment rendre une grammaire propre ? En rajoutant une production dans laquelle le A est remplacé par
, ceci pour chaque A apparaîssant en partie droite d'une production, et pour chaque A d'un A ->
Exemple :
S -> a Tb|aU
T -> bTaTA|
U -> a U | b
devient
S -> a Tb|ab|aU
T -> bTaTA|baTA|bTaA|baA
U -> a U | b
exemple qui doit pouvoir t'aider.
J'ai bien compris ton exemple sur la grammaire propre. Mais comment faire lorsqu'il y a des + ? (il faut les laisser tel quel ? (comme je l'ai fais))
Merci.
Vu l'heure tardive, je n'étais plus là 
Citation :
comment faire lorsqu'il y a des + ? il faut les laisser tel quel ?
comment faire lorsqu'il y a des + ? il faut les laisser tel quel ?
Oui, bien sûr, + est un élément du langage, il reste tel quel (on est dans un cadre formel, il n'y a pas de calcul de type arithmétique avec réductions ou simplifications).
Je reviens à
Exercice 2 2) Pour éliminer la récursivité à gauche on doit transformer les règles du type
A => A
|
en
A =>
A'
A' =>
A'|
Je me limite pour ne pas trop en écrire à
Expr => Expr + Expr| nbre
Je prends A = Expr, A' = SExpr,
= + Expr, = nbre, on obtient donc
Expr => nbre SExpr
SExpr => + Expr SExpr|
En rendant propre cette grammaire
Expr => nbre | nbre SExpr
SExpr => + Expr SExpr|+ Expr
Pour intégrer le symbole -
Expr => nbre | nbre SExpr
SExpr => + Expr SExpr | + Expr | - Expr SExpr | - Expr
doit convenir. La grammaire intuitive simplifiée que j'avais donnée au départ est sans doute bonne aussi. A vérifier.
Exercice 3 2) Désolé de t'avoir peut-être induit en erreur, c'était correct, je n'avais pas compris la notation e, que j'ai l'habitude de voir notée
ou VIDE. Par contre (et conformément aux règles données sur le site cité), j'aurais écrit plus simple:
E-> TE' | T | nbre
E'-> +TE' | +T
T-> (E)T' | (E)
T'-> (E)T' | (E)
Si je peux me permettre de te recommander un ouvrage de personnes avec qui j'ai travaillé:
P.-C. Scholl, M.-C. Fauvet, F. Lagnier, F. Maraninchi, Cours d'Informatique - Langages et Programmation, Manuels Informatiques Masson
Cordialement.