<- Syntaxe et sémantique   Lex et Flex ->

Théorie des langages : Analyse lexicale

Sommaire du document

L'analyse lexicale est la partie la plus facile à vérifier. Nous devons isoler les différents jetons, les symboles terminaux du code.

Nous utiliserons Lex[3] pour écrire notre spécification lexicale.

Définition du langage

Comme nous allons spécifier notre langage, nous devons d'abord définir ce qu'est un langage. Nous pouvons utiliser un certain nombre de convensions qui nous seront utiles par la suite[4] :

  • Nous utiliserons le symbole grec sigma majuscule (Σ) pour désigner l'alphabet, qui est un ensemble fini de caractères (par exemple ASCII [“American Standard Code for Information Interchange”[5]], UNICODE, EBCDIC [Extended Binary Coded Decimal Interchange Code], etc.).
  • Nous utiliserons les termes de texte, mot, et phrase pour désigner une suite de caractères. Ces termes sont identiques au début de notre analyse, mais prendront une signification particulière par la suite.
  • Le langage est un ensemble de phrases.
  • Nous utiliserons le symbole grec epsilon (ε) pour désigner une phrase vide.
  • Nous utiliserons le point comme opérateur de concaténation (comme en PHP)[8][9].

Propriétés du langage sous forme de monoïde

Comme nous avons défini le langage comme un ensemble, nous pouvons appliquer certaines propriétés algébriques sous la forme du monoïde[10] suivant :

NomPropriétéInformation
neutralitéX.ε = X = ε.Xε (une phrase vide) est neutre pour la concaténation.
associativitéX.(Y.Z); = (X.Y).ZL'ordre d'association est sans importance.

 

Ordres

  • X est un préfixe de Y si Y commence par X.
  • X est un suffixe de Y si Y finit par X.
  • X est une sous-chaîne de Y si X est obtennu par la suppression d'un suffixe et d'un préfixe de X.

 

Opérations et propriétés

NomPropriétéInformation
unionL1∪L2 = {p|p∈L1 ∨ p∈L2}L'union prend en compte des ensembles de chaînes.
concaténationL1.L2 = {x.y|x∈L1 ∧ x∈L2}La concaténation prend en compte des chaînes.
complémentC(L) = {x|x est une phrase sur Σ ∧ x∉L}
exponentielle ou puissanceLn = L.L.L. ... .LL'exponentielle est en fait une succession de concaténations[9].
exponentielle ou puissanceL0 = {$epsilon;}L'exposant 0 correspond au neutre, dans notre cas une phrase vide.
étoile de Kleene[11]L* = ∪Ln|n≥0De 0 à n fois. Par exemple {"a"}* = {ε,"a","aa","aaa",...}
“instance unique”[12]a = {"a"}Forme courte. Nous utilisons a, qui devrait normalement s'écrire {"a"}
langage vide∅ = { }Attention à ne pas confondre le langage vide (∅) avec un mot vide (ε)
mot videε = {ε}Neutre

 

Propriétés des langages

Les quelques propriétés suivantes ne sont pas exhaustives; quel que soit le nombre de règles que nous pouvons définir, nous en manquerons toujours...

NomPropriétéInformation
commutativitéL1 ∪ L2 = L2 ∪ L1
associativitéL1 ∪ (L2 ∪ L3) = (L1 ∪ L2) ∪ L3
associativitéL1 . (L2 . L3) = (L1 . L2) . L3
idempotenceL ∪ L = L
distributivitéL . (L1 ∪ L2) = L . L1 ∪ L . L2
distributivité(L1 ∪ L2) . L = L1 . L ∪ L2 . L 
neutralitéL ∪ ∅ = L
neutralitéL . ε = L = ε . L
langage vide absorbant∅ . L = ∅ = L . ∅
expansion du vide∅* = εcar expr* ⊃ expr0 ∧ expr0 = ε
expansion de l'étoileL* = ε ∪ L . L* ε ∪ L car l'étoile de Kleene correspond à zéro, une ou plusieurs fois.
redondance de l'étoile(L*)* = L*

 

<- Syntaxe et sémantique   Lex et Flex ->

Réseaux sociaux

|Plus d'options...

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

51 mots clés dont 42 définis manuellement (plus d'information...).

analyse Analyse lexicale analyse-lexicale ASCII associativité cardinalité commutativité complément concaténation distributivité EBCDIC epsilon etoile-de-kleene expansion exponentielle fermeture-de-kleene fermeture-iterative flex fundp Gaudry idempotence IHDCB332 jeton kleene kleene-star langage langage vide lex monoïde mot vide neutralité occurences ordre d'association Programmation propriétés algébriques Propriétés du langage préfixe puissance redondance Signaler une erreur singleton spécification Stéphane Gaudry suffixe symbole terminal symboles terminaux Théorie des langages UNICODE union étoile étoile de Kleene

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

Notes

  1. ↑ Gnu's Not Unix : correspond à « GNU n'est pas UNIX” en français

  2. ↑ GNU : “Gnu's Not Unix” (en français, « GNU n'est pas UNIX ») Groupement de logiciels libres. Il s'agit d'un acronyme récursif, car nous retrouvons l'acronyme dans sa propre définition.

  3. ↑ Lex : Nous emploierons le terme Lex pour désigner l'outil d'analyse lexicale, mais il peut s'agir de Flex, son équivalant GNU

  4. ↑ Langage : Nos différentes tentatives de définition du langage ne s'appliquent qu'aux langages séquentiels comme la parole (un mot avant l'autre) ou l'écriture (dans notre cas, de gauche à droite), mais pas aux langages graphiques tels que par exemple UML.

  5. ↑a,b American Standard Code for Information Interchange : correspond à « Code américain normalisé pour l'échange d'information” en français

  6. ↑ ASCII : “American Standard Code for Information Interchange” (en français, « Code américain normalisé pour l'échange d'information ») Mode de codage des caractères nécessaires pour écrire en anglais. Consulter la table ASCII.

  7. ↑ EBCDIC : Extended Binary Coded Decimal Interchange Code Mode de codage des caractères sur 8 bits, créé par IBM.

  8. ↑ Représentation de la concaténation : Par la suite, nous ne représenterons plus systématiquement l'opérateur de concaténation.

  9. ↑a,b Comportement de la concaténation : La concaténation se comporte exactement comme la multiplication.

  10. ↑ Langage : Les monoïdes sont des structures utilisées en théorie des langages.

  11. ↑ Kleene : Stephen Cole Kleene, mathématicien et logicien américain, inventeur des concepts d'expression rationnelle et de langage rationnel. L'étoile de Kleene (ou la fermeture de Kleene) est un opérateur unaire utilisé sur un ensemble de chaînes ou de symboles, utilisé dans les expressions rationnelles pour désigner la cardinalité 0 ou plus.

  12. ↑ instance unique : correspond à « singleton” en français

 

Références

  1. livre Langue du document: fr IHDCB332 - Théorie des langages : Syntaxe et sémantique : PY Schobbens, Syntaxe et sémantique (Janvier 2010)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Structure du document

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-10131
Document créé le 01/02/10 04:53, dernière modification le Vendredi 17 Juin 2011, 12:12
Source du document imprimé : http://www.gaudry.be/langages-analyse-lexicale.html Document affiché 2 fois ce mois de Juin.
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Navigation (masquer)
Apparence (afficher)
Stats (afficher)
15832 documents
452 astuces.
549 niouzes.
3099 definitions.
447 membres.
8115 messages.

Document genere en :
0,36 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Communiquer suppose aussi des silences, non pour se taire, mais pour laisser un espace à la rencontre des mots.

Jacques Salomé [Extrait de T'es toi quand tu parles]
 
l'infobrol
Nous sommes le Samedi 02 Juin 2012, 10:17, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)