Théorie des langages : Analyse lexicale

Inhaltsverzeichnis

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 Lex3 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 suite4 :

  • 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)89.

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ïde10 suivant :

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

Inhaltsverzeichnis Haut

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.

Inhaltsverzeichnis Haut

Opérations et propriétés

union | L1∪L2 = {p|p∈L1 ∨ p∈L2} | L'union prend en compte des ensembles de chaînes. |
concaténation | L1.L2 = {x.y|x∈L1 ∧ x∈L2} | La concaténation prend en compte des chaînes. |
complément | C(L) = {x|x est une phrase sur Σ ∧ x∉L} | |
exponentielle ou puissance | Ln = L.L.L. ... .L | L'exponentielle est en fait une succession de concaténations9. |
exponentielle ou puissance | L0 = {$epsilon;} | L'exposant 0 correspond au neutre, dans notre cas une phrase vide. |
étoile de Kleene11 | L* = ∪Ln|n≥0 | De 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 |

Inhaltsverzeichnis Haut

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...

commutativité | L1 ∪ L2 = L2 ∪ L1 | |
associativité | L1 ∪ (L2 ∪ L3) = (L1 ∪ L2) ∪ L3 | |
associativité | L1 . (L2 . L3) = (L1 . L2) . L3 | |
idempotence | L ∪ 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'étoile | L* = ε ∪ L . L* | ε ∪ L car l'étoile de Kleene correspond à zéro, une ou plusieurs fois. |
redondance de l'étoile | (L*)* = L* | |

Deutsche Übersetzung

Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.

Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.

Vielen Dank im Voraus.

Dokument erstellt 01/02/2010, zuletzt geändert 28/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de//langages-analyse-lexicale.html

Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.

Aufzeichnungen
  1. ↑ Gnu's Not Unix : entspricht « 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 : entspricht « 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 : entspricht « singleton » en français

Inhaltsverzeichnis Haut

Referenzen

  1. Buch Sprache des Dokuments:fr IHDCB332 - Théorie des langages : Syntaxe et sémantique : PY Schobbens, Syntaxe et sémantique (January 2010)

Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.

Inhaltsverzeichnis Haut