Introduction aux grammaires hors-contexte par un exemple: la définition du langage des expressions régulières

Essayons de définir le langage des expressions régulières (comme un langage régulier)

Nous écrivons AL = {a, b, c} pour l'alphabet des langages qui seront définis par les expressions régul

Maintenant nous définissons le langage de toutes les expressions régulières qui définissent un language sur l'alphabet AL. Ce langage d'expressions régulières est un méta-langage. Appellons-le RE. L'alphabet de RE est {a, b, c, epsi, con, or, star, open, close} ou {a, b, c, є, ., |, *, (, )} or {a, b, c, "є", ".", "|", "*", "(", ")"}

Équations de langages resursive - définition du langage RE:

• RE = C | RE "|" C -- union - Note: on distingue | de "|" , le dernier étant une unité lexicale du langage RE
• C = B | C "." B -- concatenation
• B = Sim | B "*" -- expression de base, possiblement avec un étoile
• Sim = a | b | c | "є" -- expression simple

Comme discuté auparavent, on peut trouver une solution à ce système d'équations: notez que LG = L1 |  LG .L2 a la solution LG = L1 . L2 * ; nous obtenons C = B ( "." B )* -- RE = C ( "|" C )* ---- donc RE = ( ( B ( "." B )* ) ( "|" ( B ( "." B )* ) )* ) où B = Sim ("*" )*

Mais il faut aussi accommoder les parenthèses: B = Sim | B "*" | "(" RE ")"

Le diagramme ci-dessous est un automate d'états finis (étendu avec recursivité) qui accepte les parenthèses dans la branch en bas. Avec cette branche "(" RE ")", l'automate devient un automate recursif. Il peut être utilisé pour vérifier si une séquence de symboles est une expression régulière valable. Mais, aucun automate d'états fini (sans recursion) existe qui pourrait faire ce travail. Pourquoi pas ?

Exercice: Resoudre le système d'équation recursif ci-haut par iteration

Note: Chaque séquence qui appartient à RE, C, B ou Sim peut aussi être représentée par un arbre où les noeuds feuilles sont des symboles de l'alphabet et le noeuds internes et la racine correspondent aux (RE, C, B et Sim) qui représentent des ensembles de chaînes. Des exemples seront donnés en classe.

Définir une grammaire hors-contexte pour les expressions régulières

Nous pouvons ré-écrire les equations recursives dans la forme d'une grammaire comme suit:

We can write the recursive equations above in the form of a context-free grammar as follows:

Notes:

• "a"  ,  "b"  ,  "c"  sont appellés des terminaux de la grammaire. Ils représentent les symboles de l'alphabet des langages décrits par les expressions régulières.
• RE, C, S et Sim sont appellés des non-terminaux (ils représentent des ensembles de chaînes formées de terminaux)
• Chaque ligne de la grammaire à droite est appellée une règle (de production). Elle contient à gauche du symbole --> un non-terminal, et à droite une séquence de terminaux et non-terminaux.
• --> et    |   sont des méta-symboles, c'est-à-dire, ils font partie du méta-langage qui est utilisé pour définir la grammaire des expressions régulières. Une méta-language bien connu pour la définition de grammaires est le BNF (Backus-Naur Form; Backus et Naur ont introduit cette notation pour définir la grammaire d'Algol en 1960). BNF utilise ": = =" pour "-->" et au lieu d'utiliser "|" , il utilise la forme montrée ci-haut à droite. Chaque règle se termine par un point ".".
• Les terminaux et non-terminaux sont aussi appellés les symboles de la grammaire. Un symbole est non-terminal, s'il apparait sur la côté à gauche d'une règle.
• Differentes conventions peuvent être utilisées pour distinguer entre symboles terminaux et non-terminaux, tel que les conventions suivantes:
  • non-terminaux sont souvent écrits dans la forme <name of the non-terminal>.
  • les terminaux sont souvent écrits en guillemets, par exemple "end" ou ")".
  • Les méta-symboles sont normalement bien connus; si on veut définir un non-terminal qui écrit de la même manière, on doit trouver une façon d'éviter de l'ambiguitié; par exemple, on peut écrire <op> --> "+"  |  "|".
• Un des non-terminaux est le symbole de départ (starting symbol) de la grammaire. C'est normalement le symbole à gauche de la première règle.
• Le sens (sémantique) d'une grammaire est la langage qu'elle définit, c'est-à-dire, l'ensemble de séquences de symboles terminaux qui peuvent être dérivées du symbole de départ en utilisant les règles de la grammaire. On dit que deux grammaires sont équivalentes si elles génèrent le même langage.

Arbres syntaxiques

The syntax tree of a sequence of terminal symbols explains why the sequence is part of the language according to the syntax rules of the context-free grammar. Consider the following example (a):