PC 10
Analyse Syntaxique

1. Syntaxe et grammaire
2. Analyse descendante
3. Analyse ascendante

Syntaxe

On considère des langages formels comme les langages de programmation. On distingue

• La syntaxe: comment on doit écrire.
• La sémantique: ce que ça veut dire.

On utilise pour spécifier la syntaxe des règles de grammaire qui ont la forme

Les expressions utilisent deux sortes de symboles:

1. Ceux du langage final: les symboles terminaux
2. Des symboles intermédiaires qui décrivent des catégories grammaticales

Définition formelle Une grammaire est donnée par:

1. Un alphabet A de symboles terminaux.
2. Un ensemble X de symboles non-terminaux.
3. Un ensemble fini de règles

   notées

Un mot sur l'alphabet A est une suite d'éléments de A.

On note l'ensemble des mots sur A.

Un langage formel est une partie de . Le langage défini par une grammaire (à partir de ) est l'ensemble

Exemple

Grammaire pour les expressions arithmétiques simples:

Le symbole E désigne la catégorie grammaticale des expressions arithmétiques. Nous considérons nombre comme un symbole abstrait (destiné à représenter les cha^ines de caractères qui sont des nombres).

Les symboles terminaux sont:

Langues naturelles On peut utiliser les mêmes grammaires pour décrire la syntaxe des langues naturelles. Ainsi on pourra utiliser les règles:

Ce sont les grammaires de Chomsky.

Arbre d'analyse

arbreana48mm78mm700Analyse de 3*(6+2)

Langage défini par une grammaire: ensemble des frontières d'arbres d'analyse (ce sont des mots sur l'alphabet terminal).

Ambiguité Grammaire ambigue: un même mot posséde plusieurs arbres d'analyse.

ambiguite123mm72mm700Deux analyses de 5*2+3

Exemples

1. La grammaire

   est ambigue.

2. La grammaire

   définit les expressions parenthésées. Elle n'est pas ambigue.

3. La grammaire

   définit les expressions additives en notation suffixe. Elle n'est pas ambigue.

Une grammaire non-ambigue pour les expressions

La grammaire E,T,F: on utilise trois catégories au lieu d'une:

1. Facteur: expression qu'on ne peut pas fragmenter.
2. Terme: produit ou quotient de facteurs.
3. Expression: somme ou différence de termes.

Choix réalisés:

1. Associativité de gauche à droite.
2. Priorité de * et / sur + et -

Analyse syntaxique Objectif: construction de l'arbre d'analyse d'un mot donné.

Deux méthodes:

• Analyse desendante (=descente recursive): on parcourt la donnée de gauche à droite en appelant des procédures pour chaque symbole de la grammaire.
• Analyse ascendante: on fait le même parcours mais en empilant les expressions identifiées au fur et à mesure.

2meth121mm43mm700Les deux méthodes

Analyse descendante des expressions arithmétiques

Les procédures Pascal suivantes effectuent la transformation en notation suffixe d'un expression arithmétique. On part de la grammaire:

On utilise un caractère d'anticipation ('lookahead') pour guider l'analyse. C'est une variable globale de type caractère.

On associe à chaque symbole non-terminal une procédure qui effectue des appels dans l'ordre indiqué par les règles:

procedure expression;
begin
 terme;
 if c='+' then begin
  read(c); expression
 end;
write('+')
end;

procedure terme;
begin
 facteur;
 if c='*' then begin
  read(c); terme
 end;
write('*')
end;

procedure facteur;
begin
 if c='(' then begin
  read(c); expression;
  if c=')' then read(c)
 else write(c)
end;

Le programme complet sera:

program analyse;

var
 c: char;
 
prodedure terme; forward;
procedure facteur; forward;
procedure expression;
 ...
procedure terme;
 ...
procedure facteur;
 ...
begin
 read(c);
 expression
end.

Premier et Suivant

Pour analyser l'algorithme descendant (algorithme LL) on introduit deux fonctions: Premier et Suivant.

premsuiv121mm104mm700

Calcul de Premier et Suivant

Pour calculer les fonctions Premier et Suivant, on construit un graphe pour chacune. Les sommets sont les symboles terminaux ou non. On a un chemin de X à a ssi Premier(X) (ou Suivant(X)). Premier

On a une flèche de X vers Y ssi il existe une règle avec (Y peut être terminal).

Suivant

Pour calculer Suivant, on aura une flèche de X à Y dans l'un des deux cas suivants:

1. Y=a et il existe une règle avec
2. il existe une règle avec (attention: on remonte les règles)

Exemples Pour la grammaire

exprem144mm72mm700

Table d'analyse LL

On peut utiliser Premier et Suivant pour construire une table d'analyse de la forme:

où la règle n est ou bien

avec ou bien

avec .

Exemple

Analyse ascendante

On utilise une pile pour ranger la partie de la donnée qui a déja été réduite.

Il y a deux sorte de mouvements:

1. Empiler de la donnée vers la pile.
2. Réduire un corps de règle en sommet de pile.

analascend81mm68mm700Schéma de fonctionnement

Analyseur LR On construit un analyseur LR utilisant:

1. des états donnant l'information sur le contenu de la pile.
2. des empilements ajoutant un état en sommet de pile notés ep .
3. des réductions par la règle n notées rn
4. des transitions donnant l'état après réduction.

Si la règle n est , on fait:

1. dépiler | w| symboles.
2. Si on a l'état u au sommet, empiler v.

Analyse SLR(1) C'est la stratégie la plus simple. Dans la situation:

on ne prend en compte une réduction par la règle que si Suivant(X).

Analyse ascendante des expressions arithmétiques

On prend la grammaire:

premsuivetf149mm33mm700Premier et Suivant

La table d'analyse

Calcul des états Les états sont des ensembles de règles marquées

correspondant à la situation: on a déja u en sommet de pile et on attend d'empiler v pour réduire uv en x.

Les transitions sont de deux sortes:

1. empilement: passer de à avec lecture de y.
2. réduction: passer de à sans lecture de symbole.

L'automate LR ETF120mm164mm700

Analyse LR(1) lr1100mm68mm700 On prend cette fois dans l'état la lettre attendue comme lookahead au moment de la réduction. Les états sont des ensembles de couples

avec les deux sortes de transitions:

1. empilement: sans changer de lookahead
2. réduction: on passe de à avec Premier(va)

Utilisation de grammaires ambigues On peut résoudre les conflits de l'analyse LR, même sur une grammaire ambigue en utilisant des règles de priorité. Ainsi, pour la grammaire:

on obtient une table d'analyse LR en résolvant les conflits par le choix de l'associativité de gauche à droite et la priorité de * sur +.

Automate LR

ambigu125mm98mm700

• About this document ...