Conception du compilateur - Expressions régulières

L'analyseur lexical doit scanner et identifier uniquement un ensemble fini de chaîne / jeton / lexème valide appartenant à la langue en cours. Il recherche le modèle défini par les règles de langue.

Les expressions régulières ont la capacité d'exprimer des langages finis en définissant un modèle pour des chaînes finies de symboles. La grammaire définie par les expressions régulières est appeléeregular grammar. Le langage défini par la grammaire régulière est appeléregular language.

L'expression régulière est une notation importante pour spécifier des modèles. Chaque modèle correspond à un ensemble de chaînes, de sorte que les expressions régulières servent de noms pour un ensemble de chaînes. Les jetons de langage de programmation peuvent être décrits par des langages normaux. La spécification d'expressions régulières est un exemple de définition récursive. Les langues ordinaires sont faciles à comprendre et ont une mise en œuvre efficace.

Il existe un certain nombre de lois algébriques auxquelles obéissent les expressions régulières, qui peuvent être utilisées pour manipuler des expressions régulières sous des formes équivalentes.

Opérations

Les différentes opérations sur les langues sont:

  • L'union de deux langues L et M s'écrit

    LUM = {s | s est en L ou s est en M}

  • La concaténation de deux langues L et M s'écrit

    LM = {st | s est dans L et t est dans M}

  • La fermeture Kleene d'une langue L s'écrit

    L * = Zéro occurrence ou plus de la langue L.

Notations

Si r et s sont des expressions régulières désignant les langages L (r) et L (s), alors

  • Union : (r) | (s) est une expression régulière désignant L (r) UL (s)

  • Concatenation : (r) (s) est une expression régulière désignant L (r) L (s)

  • Kleene closure : (r) * est une expression régulière désignant (L (r)) *

  • (r) est une expression régulière désignant L (r)

Préséance et associativité

  • *, concaténation (.) et | (signe de tuyau) sont laissés associatifs
  • * a la priorité la plus élevée
  • La concaténation (.) A la deuxième priorité la plus élevée.
  • | (signe de tuyau) a la priorité la plus basse de tous.

Représenter des jetons valides d'un langage dans une expression régulière

Si x est une expression régulière, alors:

  • x * signifie zéro occurrence ou plus de x.

    c'est-à-dire qu'il peut générer {e, x, xx, xxx, xxxx,…}

  • x + signifie une ou plusieurs occurrences de x.

    c'est-à-dire qu'il peut générer {x, xx, xxx, xxxx…} ou xx *

  • X? signifie au plus une occurrence de x

    c'est-à-dire qu'il peut générer {x} ou {e}.

    • [az] est tous les alphabets minuscules de la langue anglaise.

    [AZ] est tous les alphabets majuscules de la langue anglaise.

    [0-9] est tous les chiffres naturels utilisés en mathématiques.

Représenter l'occurrence de symboles à l'aide d'expressions régulières

lettre = [a - z] ou [A - Z]

chiffre = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ou [0-9]

signe = [+ | -]

Représenter des jetons de langage à l'aide d'expressions régulières

Décimal = (signe) ? (chiffre) +

Identifiant = (lettre) (lettre | chiffre) *

Le seul problème qui reste avec l'analyseur lexical est de savoir comment vérifier la validité d'une expression régulière utilisée pour spécifier les modèles de mots-clés d'une langue. Une solution bien acceptée consiste à utiliser des automates finis pour la vérification.