Analyse syntaxique Plan du cours Analyse syntaxique d'une ...

Description

Analyse syntaxique Plan du cours Analyse syntaxique d'une ...

Sujets

• cours

Informations

• Publié par: olexazuq
• Nombre de lectures: 220
• Langue: Français

Extrait

Analyse syntaxique par descente récursive Analyse syntaxique ascendante Gestion des erreurs

Analyse syntaxique

Martin Odersky

7, 14 et 15 novembre 2005 version 1.3

Analyse syntaxique

Analyse syntaxique par descente récursive Analyse syntaxique ascendante Gestion des erreurs

Martin Odersky

Analyse syntaxique d’une grammaire noncontextuelle Exemple : Analyseur syntaxique EBNF Grammaires LL(1)

Analyse syntaxique d’une grammaire noncontextuelle

Les grammaires régulièresne peuvent pas exprimer l’imbrication. Les grammaires noncontextuellesne peuvent pas être reconnues par des machines à états finis.

Que se passetil si l’on essaie quand même ?

Exemple na¨ıf : Reconnaˆıtre une grammaire noncontextuelle La grammaireA = "a" A "c" | "b".est reconnue par : if(char == "a") { next; if(char == A) nextelseerror; if(char == "c") nextelseerror; }else if(char == "b") next elseerror;

Lenonterminala été traité comme unterminal, ce qui est faux !

Analyse syntaxique

Martin Odersky

1 de 42

3 de 42

Analyse syntaxique par descente récursive Analyse syntaxique ascendante Gestion des erreurs

Plan du cours

1

2

3

Analyse syntaxique par descente récursive Analyse syntaxique d’une grammaire noncontextuelle Exemple : Analyseur syntaxique EBNF Grammaires LL(1)

Analyse syntaxique ascendante Principes de fonctionnement Analyses LR(x) Pragmatisme

Gestion des erreurs Reprise de l’analyse après erreur Dans l’analyse par descente récursive Dans l’analyse ascendante

Analyse syntaxique

Analyse syntaxique par descente récursive Analyse syntaxique ascendante Gestion des erreurs

Martin Odersky

Analyse syntaxique d’une grammaire noncontextuelle Exemple : Analyseur syntaxique EBNF Grammaires LL(1)

Pour dériver un analyseur syntaxique d’une grammaire noncontextuelle écrite dans le style EBNF : Introduire une fonctiondefA: Unitpour chaque nonterminalA. Celleci reconnâıt les sousphrases dérivées deA, ou émet une erreur si aucunAn’a été trouvé. Traduire toutes les expressions régulières des membres d roits d’une production comme précédemment, sauf . . . un nonterminalBse traduit maintenant par un appel à la fonctionB. La récursivité dans la grammaire se traduit naturellement par la récursivité dans l’analyseur syntaxique.

Cette technique pour écrire des analyseurs syntaxiques es t appelée analyse syntaxique par descente récursive(en anglaisrecursive descent parsing) ou analyse prédictive.

Analyse syntaxique

Martin Odersky

2 de 42

4 de 42