Exercices expressions régulières Théorie des langages-t...

Théorie des langages : Exercices expressions régulières

Télécharger PDF

Analyse de la grammaire LL(1) pour Scheme

1. Définition de la grammaire

L'axiome de la grammaire est PHRASE.

Les non-terminaux sont :

• PHRASE
• SUITE
• ATOME

Les terminaux sont :

• symbole (exemple : define, toto, il)
• nombre (exemple : 42, 3.14)
• (
• )
• .
• quote
• ' (abréviation de quote)

2. Règles de production

PHRASE ::= ATOME | (SUITE | quote PHRASE)
SUITE ::= PHRASE SUITE | PHRASE . PHRASE ) | PHRASE )
ATOME ::= symbole | nombre

3. Ensembles FIRST et FOLLOW

Ensemble FIRST

FIRST(PHRASE) = { symbole, nombre, ( }
FIRST(SUITE) = { symbole, nombre, ( }
FIRST(ATOME) = { symbole, nombre }

Ensemble FOLLOW

FOLLOW(PHRASE) = { ), $ }
FOLLOW(SUITE) = { ), $ }
FOLLOW(ATOME) = { ), ., $ }

4. Vérification de la grammaire LL(1)

Pour vérifier que la grammaire est de type LL(1), il faut s'assurer que pour chaque règle N → α, aucun terminal de FIRST(α) n'est dans FOLLOW(N), sauf si ε est dans FIRST(α).

La grammaire est bien LL(1) car les règles respectent cette condition.

5. Analyse de la phrase (define toto 'il pleut)

Voici les étapes de l'analyse :

1. Détecter ( et passer à SUITE.
2. Analyser PHRASE (début de SUITE) :
1. Détecter define comme ATOME.
2. Retour à SUITE.
3. Analyser PHRASE (suite de SUITE) :
1. Détecter toto comme ATOME.
2. Retour à SUITE.
4. Détecter ' comme quote et analyser PHRASE suivante :
1. Détecter il comme ATOME.
2. Retour à SUITE.
5. Détecter pleut comme ATOME.
6. Retour à SUITE et détecter ) pour terminer.

6. Pseudo-code de l'analyseur récursif descendant

parseP() (pour PHRASE) :
if (lookahead est un symbole ou un nombre) alors
parseA()
sinon si (lookahead == '(') alors
parseS()
sinon si (lookahead == 'quote') alors
consommer 'quote'
parseP()


parseS() (pour SUITE) :
consommer '('
parseP()
si (lookahead == ')') alors
consommer ')'
sinon si (lookahead == '.') alors
consommer '.'
parseP()
consommer ')'
sinon
parseS()


parseA() (pour ATOME) :
si (lookahead est un symbole) alors
consommer symbole
sinon si (lookahead est un nombre) alors
consommer nombre


FAQ

Qu'est-ce qu'une grammaire LL(1) ?

Une grammaire LL(1) est une grammaire qui peut être analysée par un analyseur récursif descendant en utilisant une seule fois le symbole de fin de chaîne et en regardant un seul symbole d'avance.

À quoi servent les ensembles FIRST et FOLLOW ?

Les ensembles FIRST et FOLLOW permettent de déterminer les symboles à analyser en priorité et de vérifier les conflits dans une grammaire LL(1). FIRST donne les premiers symboles possibles d'une règle, tandis que FOLLOW indique les symboles qui peuvent suivre un non-terminal.

Comment implémenter un analyseur récursif descendant ?

Un analyseur récursif descendant utilise des fonctions pour chaque non-terminal, qui appellent d'autres fonctions en fonction des règles de la grammaire. Chaque fonction vérifie le symbole courant et appelle les fonctions nécessaires pour analyser la suite.