cours-2-5

Jean-Pierre Jacquot

Description

Analyse syntaxique 1Qu'est-ce qui dit ?Langage : moyen de communicationconstructeurémetteur analyseurphrase récepteurde phrase de phraseémetteur : engendre la phrase selon la grammairerécepteur : doit reconnaître la phrase« La phrase appartient-elle au langage ? »tout système informatique interactif est un récepteur !Le problème de la reconnaissance est centralDEUG 2 2000Analyse syntaxique 2Analyse syntaxique : définitionAnalyse syntaxique =procédure permettant de décider si une phrase appartient à un langage.Dans la pratique, un analyseur syntaxique donne également la structure de la phraseconstructeurémetteur analyseurphrase récepteurde phrase de phraseGrammaire dulangageDEUG 2 2000Page 1Analyse syntaxique 3ExempleAXIOME ::= EXPREXPR ::= TERM + TERM | T ERM * TERMTERM ::= NOMBRE | ( EXPR )NOMBRE ::= CHIFFRE | CHIFFRE NOMBRECHIFFRE ::= 1 | 0Les phrases suivantes sont-elles des expressions ?"101" "1+10+11" "((((1+1))))*(0+0)"Peut-on écrire une fonction qui teste si les phrases appartiennent au langage ?DEUG 2 2000Analyse syntaxique 4Principe de baseUne chaîne est une phrase d'un langage si on peut trouver une application des règles qui l'engendre.Idée : interpréter une règle de grammaire comme une fonctiongénération : une règle-fonction insère des mots dans la phrasereconnaissance : une règle-fonction efface les mots !AXIOME ("1 + 1") =>EXPR ("1 + 1") =>(TERM; /+; TERM) ("1 + 1") =>(NOMBRE; /+; TERM) ("1 + 1") =>(/1; /+; ...

Sujets

• informatique
• système informatique

Informations

• Publié par: Chaet
• Nombre de lectures: 36
• Langue: Français

Extrait

EXPR ("1 + 1") =>(TERM; /+; TERM) ("1 + 1") =>(NOMBRE; /+; TERM) ("1 + 1") =>(/1; /+; ..." />

Page 1

DEUG 2

2000

1

Analyse syntaxique

Qu'est-ce qui dit ?

Langage : moyen de communication

émetteur : engendre la phrase selon la grammaire

récepteur : doit reconnaître la phrase

« La phrase appartient-elle au langage ? »

tout système informatique interactif est un récepteur !

Le problème de la reconnaissance est central

émetteur

constructeur

de phrase

récepteur

analyseur

de phrase

phrase

DEUG 2

2000

2

Analyse syntaxique

Analyse syntaxique : définition

Analyse syntaxique =

procédure permettant de décider si une phrase appartient à

un langage.

Dans la pratique, un analyseur syntaxique donne également la

structure de la phrase

émetteur

constructeur

de phrase

récepteur

analyseur

de phrase

phrase

Grammaire du

langage

Page 2

DEUG 2

2000

3

Analyse syntaxique

Exemple

AXIOME

::= EXPR

EXPR

::= TERM + TERM

| T ERM * TERM

TERM

::= NOMBRE | ( EXPR )

NOMBRE

::= CHIFFRE | CHIFFRE NOMBRE

CHIFFRE

::= 1 |

0

Les phrases suivantes sont-elles des expressions ?

"101"

"1+10+11"

"((((1+1))))*(0+0)"

Peut-on écrire une fonction qui teste si les phrases

appartiennent au langage ?

DEUG 2

2000

4

Analyse syntaxique

Principe de base

Une chaîne est une phrase d'un langage si on peut trouver

une application des règles qui l'engendre.

Idée : interpréter une règle de grammaire comme une

fonction

génération : une règle-fonction

insère

des mots dans la phrase

reconnaissance : une règle-fonction

efface

les mots !

AXIOME ("1 + 1") =>

EXPR ("1 + 1") =>

(TERM; /+; TERM) ("1 + 1") =>

(NOMBRE; /+; TERM) ("1 + 1") =>

(/1; /+; TERM) ("1 + 1") =>

(/+ ;TERM) ("+ 1") =>

(TERM) ("1") => etc.

Page 3

DEUG 2

2000

5

Analyse syntaxique

Problèmes pratiques

– Dans quel

ordre effacer?

– Comment choisir la production à utiliser lorsqu'une règle en a

plusieurs ?

– Comment passer d'une grammaire à un analyseur ?

Il y a plusieurs réponses possibles qui dépendent du type de la

grammaire et de la stratégie de programmation.

Dans ce cours, nous utiliserons la stratégie dite

analyse descendante prédictive (LL(1))

» effacement de gauche à droite

» grammaire permettant de décider de la production

» utilisation du mécanisme de flot en Caml

DEUG 2

2000

6

Analyse syntaxique

Choix de la production

Facteurs gauches d’un non-terminal =

ensemble des symboles apparaissant le plus à gauche

dans toutes les phrases engendrables à partir du

non-terminal

par extension, les facteurs gauches d’une production sont les

facteurs gauches de son premier élément, le facteur gauche

d’un terminal t1 est le singleton {t1}

Condition nécessaire : Un langage défini par une grammaire G

pourra être reconnu par un analyseur descendant prédictif si

pour toute règle de G de la forme R::= P1 | P2 | ... | Pn

les facteurs gauches de P1, ..., Pn sont

tous

différents.

La condition peut être vérifiée assez simplement

Page 4

DEUG 2

2000

7

Analyse syntaxique

Transformation de grammaire

Que faire si la grammaire ne vérifie pas la condition ?

la transformer !

– un « truc » simple : ajouter des terminaux

mais le langage est lui aussi modifié

– plus élégant, mais plus difficile : factoriser les règles et

introduire de nouveaux non-terminaux

EXPR ::= TERM + TERM | TERM * TERM

EXPR ::= TERM SUITE_EXPR

SUITE_EXPR ::= + TERM | * TERM

départ commun

facteurs gauches différents

DEUG 2

2000

8

Analyse syntaxique

Transformation de grammaire

Le problème des listes se traite de façon similaire

NOMBRE ::= CHIFFRE | CHIFFRE NOMBRE

NOMBRE ::= CHIFFRE SUITE_NOMBRE

SUITE_NOMBRE ::=

CHIFFRE SUITE_NOMBRE |

Λ

Pour des grammaires complexes, les transformations peuvent

être difficiles à faire.

symbole conventionnel

pour la chaîne vide

Page 5

DEUG 2

2000

9

Analyse syntaxique

Streams

Stream (flot) =

type de données Caml représentant une suite de valeurs

qui jouit de deux propriétés :

les valeurs sont produites à la demande

les valeurs sont consommées

Bien adapté à l’analyse syntaxique : il suffit que la phrase soit

un flot de mots et que les procédures consomment les mots

comme ils sont produits

Objets très particuliers : modèle d'exécution spécifique

fonction

Caml

arguments

résultat

flot

partie

consommée

chaque application

de la fonction

consomme la tête

du flot

DEUG 2

2000

10

Analyse syntaxique

Utilisation des streams

mécanisme de filtrage destructif

let f = parser

[< patron1 de stream >] -> valeur1

| [< patron2 de stream >] -> valeur2

| [< >]

-> valeur pour vide;;

patron de stream : suite de valeurs

» une valeur simple Caml :

int, float, char, string

, ...

‘ 12, ‘ 14.5, ‘ 'a', ‘ “bonjour”,

...

» un constructeurs (

type t = C1 of string | C2 of t1*t2

) :

‘C2 (g, d), ‘C1 s

(g, d, s ont des variables liées aux valeurs)

» une fonction qui travaille sur le stream

resf=(f arguments)

Attention à la syntaxe, dans un patron de stream, le nom resf est

lié au résultat de l’exécution de f !

Page 6

DEUG 2

2000

11

Analyse syntaxique

Exemple

fonction qui calcule la somme des nombres entiers présent dans

un stream

let rec som_stream =

function val_som ->

parser

[< 'i ; resf=(som_stream (i+val_som)) >] -> resf

| [< >] -> val_som;;

som_stream 0

[<'1; '2; '3; '4; '5; '6 >]

;;

- : int = 21

valeur de flot

DEUG 2

2000

12

Analyse syntaxique

Construction systématique d'un

analyseur

1 - s'assurer que la grammaire a la bonne forme (prédictive)

2- chaque non-terminal devient un nom de fonction

3- chaque règle devient le corps d'une fonction qui travaille sur

un flot

4- chaque production devient un patron de flot

la grammaire se retrouve directement dans le programme Caml

Page 7

DEUG 2

2000

13

Analyse syntaxique

Mon premier analyseur

let rec ax = parser [< res=(expr) >] -> res

and expr = parser

[< rest=(term); res =(expr_suite) >] -> res

and expr_suite = parser

[< ''*'; res =(term) >] -> res

| [< ''+'; res =(term) >] -> res

and term = parser

[< ''('; res=(expr); '')' >] -> res

| [< res =(nombre) >] -> res

and nombre = parser

[< resc=(chiffre); resns =(nombre_suite) >] -> resns

and nombre_suite = parser

[< resc=(chiffre); resn =(nombre_suite) >] -> resn

| [< >] -> true

and chiffre = parser

[< ''1' >] -> true

| [< ''0' >] -> true;;

DEUG 2

2000

14

Analyse syntaxique

Résultat d'un analyseur

plutôt que "true" ou "false", il est préférable d'avoir un terme qui

reprend la structure de la phrase !

AX IOME

::= EXPR

EXPR

::= TERM + TERM

| T ERM * TERM

T ERM

::= NOMBRE | ( EXPR )

NOMBRE ::= CHIFFRE | CHIFFRE NOMBRE

CHIFFRE ::= 1 |

0

type expr =

Plus of expr*expr

| Fois of expr*expr

| Nombre of string

| ArbreVide ;;

Page 8

DEUG 2

2000

15

Analyse syntaxique

Analyseur plus réaliste

let rec ax = parser [< res =(expr) >] -> res

and expr = parser

[< rest=(term); res =(expr_suite) >] -> (assemble_expr rest res)

and expr_suite = parser

[< ''*'; res =(term) >] -> Fois (ArbreVide, res)

| [< ''+'; res =(term) >] -> Plus (ArbreVide, res)

and term = parser

[< ''('; res=(expr); '')' >] -> res

| [< res =(nombre) >] -> res

and nombre = parser

[< resc=(chiffre); resns =(nombre_suite) >] -> Nombre (resc^resns)

and nombre_suite = parser

[< resc=(chiffre); resn= (nombre_suite) >] -> resc^resn

| [< >] -> ""

and chiffre = parser

[< ''1' >] -> "1"

| [< ''0' >] -> "0";;

let assemble_expr =

function ag ->

function

Plus(_, ad) -> Plus(ag,ad)

| Fois(_,ad)

-> Fois(ag, ad);;

DEUG 2

2000

16

Analyse syntaxique

Architecture d’un analyseur

Ensemble de procédures

sur les streams

une procédure par

règle

Page 9

DEUG 2

2000

17

Analyse syntaxique

texte

découpage

en mots

structure

phrase

Ensemble de procédures

sur les streams

une procédure par

règle

DEUG 2

2000

18

Analyse syntaxique

Analyse lexicale : définition

• Lexème (token) =

terme technique désignant un mot, terminal ou terminal

générique, utilisable par l’analyseur syntaxique

• Analyse lexicale =

transformation d’un flot de caractères en un flot de lexèmes

Généralement, les lexèmes ont eux-mêmes une structure. Ils

forment un “sous-langage”

Les techniques utilisées pour l’analyse lexicale sont identiques à

celles utilisées pour l’analyse syntaxique. Caml offre un type

token et un outil de construction automatique (make_lexer)