Grammaire

[bijop]

Bonjour,

sur les conseils d'un membre du forum que je remercie, je me suis procuré le livre "Compilateurs - Principes, techniques et outils".
Le livre est très complet avec de nombreux exercices et je le conseille également. Malheureusement il ne comporte pas souvent les solutions.

Je vous en propose donc un ici que je n'arrive pas à résoudre (c'est en fait un des premiers ):

Soit la grammaire non contextuelle suivante :

Q1) Montrer comment la chaîne peut être produite par cette grammaire
Q2) Construire un arbre d'analyse pour cette chaîne
Q2) Quelle langage cette grammaire définit-elle ? Justifier.

Merci !
-----

[invite74a6a825]

Bonjour,

Aprés avoir lu wikipedia Grammaire non contextuelle

Je ne comprend pas ce que représente SS mais c'est normal puisque non contextuel

[invite74a6a825]

http://www.info.univ-angers.fr/~gh/hilapr/langage.htm

En mathématiques, la notion de langage formel se confond souvent avec celle de grammaire [formelle générative] : le langage est l'ensemble des mots qu'on peut construire à l'aide de régles de réécriture et de mots de départ nommés axiomes, la réécriture pouvant être séquentielle, parallèle... Ainsi la grammaire



Axiome : S
Règles : 1. S -> ()
Règles : 2. S -> SS
3. S -> (S)


définit les expressions correctement parenthésées, alors que la grammaire



Axiome : S
Règles : 1. x -> A ou B ou C ou...
Règles : 2. S -> x S x
3. S -> ^ (le caractère "vide")

définit le langages des mots-miroir ou "palindromes" comme ICI, LAVAL...