cours-2-4

Jean-Pierre Jacquot

Description

Grammaires 1Utiliser la machine tortue– En Caml ?Possible, mais :Oblige à savoir « trop » de chosesOblige à s'occuper de détails indépendants du vrai problèmeOblige à connaître Caml !– En un autre langage ?Oui, mais :Lequel ?DEF carre(l) PARREPETE 4 FOIS SEQ A l; T 90 QESFED DEUG 2 2000Grammaires 2Trouver Saussure à son pied• Problème :Si nous souhaitons définir un nouveau langage pour les graphiques tortue, nous devons répondre à quelques questions :A quelles phrases pouvons-nous associer un sens ?• REPETE 2 FOIS carre(10)• RECULE 37Quels sont les mots qui ont un sens ?• DEF• carreComment doit-on arranger les mots ?• on mots arranger doit comment les ?Qu’est-ce qu’un mot ?• euhhhhhhDEUG 2 2000Page 1Grammaires 3Langage : définition• Langage =Système de signes servant à transmettre des significationsLorsqu’il y a transmission de sentiments ou de significations à plusieurs niveaux, il est préférable de parler de langue• Langage formel =Système dans lequel il existe des règles rigides qui permettent dedonner un sens univoque aux phrasesdéfinir des procédures de transformation et de manipulation de phrasesDEUG 2 2000Grammaires 4Phrase : définition• Mot =Unité élémentaire (c’est-à-dire non décomposable) composée de caractères• Phrase =Concaténation (c’est-à-dire, mise bout à bout) de motsLa théorie ne différencie pas entre mots (au sens usuel), symboles, ponctuation, etc.Les mots peuvent eux-mêmes avoir une structure, ...

Sujets

• informatique

Informations

• Publié par: Zoen
• Nombre de lectures: 128
• Langue: Français

Extrait

Page 1

DEUG 2

2000

1

Grammaires

Utiliser la machine tortue

– En Caml ?

Possible, mais :

Oblige à savoir « trop » de choses

Oblige à s'occuper de détails indépendants du vrai problème

Oblige à connaître Caml !

– En un autre langage ?

Oui, mais :

Lequel ?

DEF carre(l) PAR

REPETE 4 FOIS

SEQ A l; T 90 QES

FED

DEUG 2

2000

2

Grammaires

Trouver Saussure à son pied

• Problème :

Si nous souhaitons définir un nouveau langage pour les

graphiques tortue, nous devons répondre à quelques

questions :

A quelles phrases pouvons-nous associer un sens ?

• REPETE 2 FOIS carre(10)

• RECULE 37

Quels sont les mots qui ont un sens ?

• DEF

• carre

Comment doit-on arranger les mots ?

• on mots arranger doit comment les ?

Qu’est-ce qu’un mot ?

• euhhhhhh

Page 2

DEUG 2

2000

3

Grammaires

Langage : définition

• Langage =

Système de signes servant à transmettre des significations

Lorsqu’il y a transmission de sentiments ou de significations à

plusieurs niveaux, il est préférable de parler de

langue

• Langage formel =

Système dans lequel il existe des règles rigides qui

permettent de

donner un sens univoque aux phrases

définir des procédures de transformation et de

manipulation de phrases

DEUG 2

2000

4

Grammaires

Phrase : définition

• Mot =

Unité élémentaire (c’est-à-dire non décomposable)

composée de caractères

• Phrase =

Concaténation (c’est-à-dire, mise bout à bout) de mots

La théorie ne différencie pas entre mots (au sens usuel),

symboles, ponctuation, etc.

Les mots peuvent eux-mêmes avoir une structure, mais celle-ci

correspond à un autre langage (ex. écriture des nombres)

Mathématiquement, les phrases sont des structures

appartenant aux monoïdes

Page 3

DEUG 2

2000

5

Grammaires

Rôle des langages

• En mathématiques

– parler de propriétés

• toute fonction dérivable est-elle continue ?

• (

2200

f, dérivable(f)

⇒

continue(f) )

– exprimer des relations

• (U + V) ‘ = U’ + V’

• En informatique

– donner des ordres à une machine

• let q = 123;;

• SEQ A 100; T 90; C bleu QES

– exprimer des algorithmes

• function x -> x+1;;

DEUG 2

2000

6

Grammaires

Cas de

-Logo

– Doit être capable de décrire un graphique

• des figures simples

• des figures construites par assemblage

• des figures calculées (Von Koch)

– Agit sur une machine tortue

• la signification sera le tracé de graphique

– Doit être traitable par une machine

• Un utilisateur doit pouvoir écrireen

μ

-Logo (c’est-à-dire, écrire des

textes)

• Un programme doit pouvoir déterminer si un texte est en

μ

-Logo ou

non

• Un programme doit pouvoir transformer le texte en la suite d’appel

des fonctions de la machine tortue

Page 4

DEUG 2

2000

7

Grammaires

Définir un langage

• Un langage : trois constituants

–

vocabulaire =

ensemble des mots qui peuvent apparaître dans les

phrases

–

syntaxe =

ensemble des règles permettant d’assembler les mots

pour former des phrases

–

sémantique =

ensemble des règles permettant de déterminer le sens

d’une phrase

Pour les langages formels, les 3 constituants sont définis de

façon arbitraire

DEUG 2

2000

8

Grammaires

Grammaire : définition

• Grammaire =

1) mécanisme de réécriture (ou de production) qui permet

d’engendrer systématiquement les phrases d’un langage

2) ensemble des règles de réécriture qui définissent un

langage particulier

– définition due à N. Chomsky

– définition constructive :

» un langage est défini comme les objets (phrases) que

l’on peut construire

– les grammaires des langues sont plutôt descriptives : elles

recensent les règles de cohérence interne des phrases et

définissent une langue comme l’ensemble des phrases

cohérentes

Page 5

DEUG 2

2000

9

Grammaires

Exemple des propositions

AX ::= PROP

PROP ::=

APROP ou APROP |

APROP et APROP |

non APROP |

APROP

APROP ::=

p |

q |

r |

( PROP )

» les phrases suivantes sont-elles des propositions ?

• p

ou q et r

• (non (((p)))) ou r

DEUG 2

2000

10

Grammaires

Mécanisme de génération

• Terminal =

élément du vocabulaire du langage, n'apparaît qu’à droite

du symbole ::=

• Non Terminal =

élément du méta-vocabulaire qui sera réécrit, apparaît à

gauche du symbole ::=

• Productions =

ensemble des façons de réécrire un non terminal,

exprimées comme une liste d’alternatives (symbole |)

• Axiome =

non terminal qui n'apparaît jamais à droite du symbole ::=

Page 6

DEUG 2

2000

11

Grammaires

Algorithme de génération

– On représente une phrase par une liste de mots

– la liste initiale contient uniquement l’axiome

– tant que la liste contient des non terminaux

» sélectionner un non terminal

» le remplacer par une de ses productions

– le procès s’arrête lorsque la liste ne contient plus que des

terminaux, l’écriture de cette liste produit une phrase

Le procès s’arrête-t-il toujours ? Non, certains langages ont des

phrases infinies !

L’ordre de choix des non terminaux est-il important ? Non, pour

les langages que nous considérons

DEUG 2

2000

12

Grammaires

Camlisons

– Soit le module “grammaire” qui propose les définitions suivantes

type grammaire

type production = string list

est_terminal: grammaire -> string -> bool

productions: grammaire -> string -> production list

une_production: grammaire -> string -> production

– fonction de création d’une phrase à partir d’une production

let phrase = function prod ->

list_it (function g -> function d -> g^” “^d) prod “ “ ;;

– fonction technique de réécriture

let reecrit = function gram ->

function mot ->

if

est_terminal gram mot

then [mot]

else une_production gram mot;;

Page 7

DEUG 2

2000

13

Grammaires

Génération

let Chomsky =

function gram ->

function axiome ->

let rec Noam =

function prod ->

if (for_all (est_terminal gram) prod)

then prod

else Noam (List.flatten

(List.map (reecrit gram) prod))

in Noam [axiome];;

List.flatten: 'a list list -> 'a list = <fun>

List.flatten [a; b; ... ; k] == a @ b @...@ k

DEUG 2

2000

14

Grammaires

Intérêt des grammaires

• Objets mathématiques

– Propriétés démontrables

» classes de langages

• régulier, non contextuel, contextuel, etc.

» techniques de traitement

• automates, générateurs de reconnaisseurs, etc.

– Classes d’équivalences de langages

• langages égaux = langages engendrables par la même grammaire

• grammaires équivalentes = qui engendrent les mêmes langages

– Transformations

• pour adapter la définition d’un langage à des outils

Page 8

DEUG 2

2000

15

Grammaires

Intérêt des grammaires

• Moyen de description

– Manuel de référence des langages de programmation

– Description des langages de données de certaines

applications

• Précision

• Concision

• Non ambiguïté

• Outil de modélisation

– Objets complexes

– Représentation textuelle de valeurs complexes