Langages réguliers

Les équations syntaxiques définies par l’EBNF génèrent des langages dits context free. L’expression context free est due à Chomsky et provient du fait que la substitution du symbole à gauche du signe \(=\) par une séquence dérivée de l’expression à droite du signe \(=\) est toujours autorisée, quel que soit le contexte dans lequel le symbole est intégré dans la phrase.

Il s’est avéré que cette restriction à la liberté de contexte (au sens de Chomsky) est tout à fait acceptable, et même souhaitable, pour les langages de programmation.

Intéressons-nous maintenant à une classe de langages plus restreinte que celle des langages context free : les langages réguliers qui jouent un rôle important dans le domaine des langages de programmation.

Définition 1

Un langage régulier est un langage sans contexte dont la syntaxe ne contient pas de récursion, sauf pour la spécification de la répétition.

Étant donné que, dans le langage EBNF, la répétition est spécifiée directement et sans recours à la récursivité, la définition suivante peut aussi être donnée :

Définition 2

Un langage est régulier si sa syntaxe peut être exprimée par une seule expression EBNF non récursive.

L’exigence selon laquelle une seule équation suffit implique également que seuls les symboles terminaux apparaissent dans l’expression. Une telle expression est appelée expression régulière.

Voici deux brefs exemples de langages réguliers : Le premier définit les identificateurs tels qu’ils sont couramment utilisés dans la plupart des langages, et le second définit les entiers en notation décimale.

identifier = letter {letter | digit}.
integer = digit {digit}.
letter = "A" | "B" | ... | "Z".
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".

Pour plus de commodité, nous utilisons les symboles non terminaux letter et digit. Ils peuvent facilement être éliminés par substitution, ce qui permet d’obtenir une expression régulière pour identifier et integer.

Considérons maintenant la grammaire suivante :

\[\begin{gather*} S = \mathsf{«a»} S \mathsf{«c»} \, | \, \mathsf{«b»} \\ \end{gather*}\]

Cette grammaire définit un langage context free mais pas un langage régulier.

La raison de notre intérêt pour les langues régulières réside dans le fait que les programmes de reconnaissance des phrases régulières sont particulièrement simples et efficaces. Par reconnaissance, nous entendons la détermination de la structure de la phrase, et donc naturellement la détermination du fait que la phrase est bien formée, et donc qu’elle appartient au langage. La reconnaissance de la phrase est appelée analyse syntaxique.

Pour la reconnaissance de phrases régulières, un automate fini, également appelé machine d’états¹, est nécessaire et suffisant. À chaque étape, l’automate lit le symbole suivant et change d’état. L’état résultant est uniquement déterminé par l’état précédent et le symbole lu. Si l’état résultant est unique, la machine à états est déterministe, sinon elle est non déterministe.

Pour illustrer les automates finis, considérons le langage suivant:

\[\begin{gather*} S = \{ \mathsf{«a»} | \mathsf{«b»} \} \mathsf{«a» } \mathsf{«b» } \mathsf{«b» }\\ \end{gather*}\]

L’automate représenté dans la figure ci-dessous reconnaît ce langage, mais il n’est pas déterministe.

Machine d’état non déterministe

Pourquoi cette machine n’est-elle pas déterministe ?

Parce que, à partir de l’état initial, la lecture du symbole a peut conduire à deux états différents :

On peut rester dans l’état initial (0), ou
On peut passer à l’état 1.

Machine d’état déterministe

Reconnaissance de langages

Le programme qui analyse le langage peut être dérivé directement de sa définition en EBNF. Pour chaque construction EBNF \(K\), il existe une règle de traduction qui produit un fragment de programme \(Pr(K)\). Les règles de traduction de EBNF en texte de programme sont présentées ci-dessous. Dans ce tableau, sym désigne une variable globale représentant le dernier symbole. Ce symbole est lu dans le code source par un appel à la fonction next. La fonction error met fin à l’exécution du programme en signalant que la séquence de symboles lue jusqu’à présent n’appartient pas au langage.

\(K\)	\(Pr(K)\) (Python)
`"x"`	if sym == “x”: next() else: error()
`(exp)`	Pr(exp)
`[exp]`	if sym in first(exp): Pr(exp)
`{exp}`	while sym in first(exp): Pr(exp)
`fac_0 fac_1 ... fac_n`	Pr(fac_0) Pr(fac_1) … Pr(fac_n)
`term_0 \| term_1 \| ... \| term_n`	if sym in first(term_0): Pr(term_0) elif sym in first(term_1): Pr(term_1) … elif sym in first(term_n): Pr(term_n) else: error()

L’ensemble first(K) contient tous les symboles (terminaux) par lesquels une phrase dérivée de la construction K peut commencer. C’est l’ensemble des symboles de début de K.

Pour les deux exemples d’identifiants et d’entiers, ce sont :

first(identifier) = letters = {"A", "B", ... , "Z"}
first(integer) = digits = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}

L’application de ces règles de traduction simples pour générer un parser à partir d’une syntaxe donnée est cependant soumise à la condition que la syntaxe soit déterministe. Cette condition préalable peut être formulée plus concrètement avec ces 3 règles :

Règle 1

Lors d’une alternative de termes (\(K\) = term_0 | term_1 ), les termes ne doivent pas avoir de symboles de départ communs

Règle 2

Lors d’une séquence de facteurs (\(K\) = fac_0 fac_1), si le premier facteur contient la séquence vide, les facteurs ne doivent pas avoir de symboles de départ communs

Règle 3

Lors d’une répétition de facteurs (\(K\) = [exp] ou {exp}), les ensembles de symboles de départ de exp et de symboles pouvant suivre \(K\) doivent être disjoints

Ces conditions sont satisfaites de manière triviale dans les exemples des identificateurs et des entiers, et nous obtenons donc le programme Python suivant pour les reconnaître :

#
# Lexical analysis of identifiers and numbers.
#

import string

letters = set(string.ascii_lowercase)
digits = set(string.digits)

# Global variables
ch = None
text = None
pos = 0


def init(t: str) -> None:
    global pos, text
    pos = 0
    text = t
    next_char()


def error(msg: str) -> None:
    raise Exception(msg)


def next_char() -> None:
    global ch, pos
    if text is not None and pos < len(text):
        ch = text[pos]
        pos += 1
    else:
        ch = None


def ident() -> None:
    ident = ""
    if ch in letters:
        ident += ch
        next_char()
    else:
        error(f"letter expected, got {ch}")
    while ch in letters | digits:
        if ch in letters:
            ident += ch
            next_char()
        elif ch in digits:
            ident += ch
            next_char()
        else:
            error(f"letter or digit expected, got {ch}")
    print(f"Identifier: {ident}")


def number() -> None:
    number = ""
    if ch in digits:
        number += ch
        next_char()
    else:
        error(f"digit expected, got {ch}")
    while ch in digits:
        number += ch
        next_char()
    print(f"Number: {number}")


def main() -> None:
    init("ab123 123abc")
    ident()
    next_char()
    number()


if __name__ == "__main__":
    main()

Souvent, le programme obtenu par l’application des règles de traduction peut être simplifié en éliminant des conditions qui sont manifestement établies par des conditions précédentes.

Dans l’exemple ci-dessus, les tests aux lignes 44 et 47 sont inutiles, car on entre dans la boucle while uniquement si le caractère est une lettre ou un chiffre. On peut donc réécrire la fonction indent comme suit :

def ident():
    ident = ""
    if ch in letters:
        ident += ch
        next_char()
    else:
        error(f"letter expected, got {ch}")
    while ch in letters | digits:
        ident += ch
        next_char()

    print(f"Identifier: {ident}")

En Python, les conditions sym in letters et sym in digits peuvent aussi être formulées comme ceci :

"a" <= sym <= "z" et "0" <= sym <= "9".

L’importance des langages réguliers par rapport aux langages de programmation tient au fait que ces derniers sont généralement définis en deux étapes :

Tout d’abord, leur syntaxe est définie en termes de vocabulaire de symboles abstraits.
Ensuite, ces symboles abstraits sont définis en termes de séquences de symboles terminaux concrets, tels que les caractères ASCII.

Cette deuxième définition a généralement une syntaxe régulière.

La séparation en deux étapes présente l’avantage que la définition des symboles abstraits, et donc du langage, est indépendante de toute représentation concrète en termes de jeux de caractères particuliers utilisés par un équipement particulier.

Cette séparation a également des conséquences sur la structure d’un compilateur. Le processus d’analyse syntaxique repose sur une procédure permettant d’obtenir le symbole suivant. Cette procédure est à son tour basée sur la définition des symboles en termes de séquences d’un ou plusieurs caractères.

Cette dernière procédure est appelée scanner, et l’analyse syntaxique à ce deuxième niveau, analyse lexicale. La définition des symboles en termes de caractères est généralement donnée en termes de langage régulier, et par conséquent, le scanner est généralement une machine à états.

Le tableau ci-dessous résume les différences entre les deux niveaux:

Processus	Élément d’entrée	Algorithme	Syntaxe
Analyse lexicale	Caractères	Scanner (Machine d’états)	Langage régulier
Analyse syntaxique	Symboles	Parser	Langage context free

À titre d’exemple, voici un scanner pour un parser d’EBNF. Ses symboles terminaux et leur définition en termes de caractères sont les suivants:

symbol     = {blank}(identifier|string|"("|")"|"["|"]"|"{"|"}"|"|"|"="|".").
identifier = letter {letter | digit}.
string     = """ {character} """.

Nous en déduisons une classe Scanner et une méthode next_symbol qui, à chaque appel, assigne à l’attribut sym une valeur numérique représentant le prochain symbole lu. Si le symbole est un identificateur ou une chaîne de caractères, la séquence de caractères réelle est affectée à l’attribut value. Il convient de noter qu’en règle générale, un scanner prend également en compte les règles relatives aux espaces et aux fins de lignes. La plupart du temps, ces règles stipulent que les espaces (blank) et les fins de ligne séparent les symboles consécutifs, mais qu’ils n’ont pas d’autre signification.

import io
import typing
from dataclasses import dataclass
from enum import Enum
from typing import ClassVar, Union


class Token(Enum):
    IDENT = 1
    LITERAL = 2
    LPAREN = 3
    LBRAK = 4
    LBRACE = 5
    BAR = 6
    EQL = 7
    RPAREN = 8
    RBRAK = 9
    RBRACE = 10
    PERIOD = 11
    OTHER = 12


@dataclass
class Scanner:
    src: typing.TextIO
    sym: Union[Token, None] = None
    ch: str = ""
    value: str = ""

    token_map: ClassVar = {
        "=": Token.EQL,
        "(": Token.LPAREN,
        ")": Token.RPAREN,
        "[": Token.LBRAK,
        "]": Token.RBRAK,
        "{": Token.LBRACE,
        "}": Token.RBRACE,
        "|": Token.BAR,
        ".": Token.PERIOD,
    }

    def __post_init__(self) -> None:
        self.next_char()

    def skip_space(self) -> None:
        while self.ch.isspace():
            self.next_char()

    def eof(self) -> bool:
        return self.ch == ""

    def error(self, msg: str) -> None:
        print(f"Error: {msg} at position {self.src.tell()}")

    def next_char(self) -> str:
        self.ch = self.src.read(1)
        return self.ch

    def next_symbol(self) -> Token:
        self.skip_space()
        if self.ch.isalpha():
            self.sym = Token.IDENT
            self.value = self.ch
            while (ch := self.next_char()).isalpha():
                self.value += ch
        elif self.ch == '"':
            self.sym = Token.LITERAL
            self.value = ""
            while not self.eof() and (ch := self.next_char()) != '"':
                self.value += ch
            if self.eof():
                self.error("Unterminated literal")
            self.next_char()
        elif self.ch in self.token_map:
            self.sym = self.token_map[self.ch]
            self.value = self.ch
            self.next_char()
        else:
            self.sym = Token.OTHER
            self.value = self.ch
            self.next_char()
        return self.sym


def main() -> None:
    src = """
    ident = letter { letter | digit }.
    number = digit { digit }.
    digit = "0" | "1" | "2" | "3".
    """
    scanner = Scanner(io.StringIO(src))
    while True:
        sym = scanner.next_symbol()
        if scanner.eof():
            break
        print(f"{sym:20s}{scanner.value}")


if __name__ == "__main__":
    main()

Ce programme produit la sortie suivante

Token.IDENT         ident
Token.EQL           =
Token.IDENT         letter
Token.LBRACE        {
Token.IDENT         letter
Token.BAR           |
Token.IDENT         digit
Token.RBRACE        }
Token.PERIOD        .
Token.IDENT         number
Token.EQL           =
Token.IDENT         digit
Token.LBRACE        {
Token.IDENT         digit
Token.RBRACE        }
Token.PERIOD        .
Token.IDENT         digit
Token.EQL           =
Token.LITERAL       0
Token.BAR           |
Token.LITERAL       1
Token.BAR           |
Token.LITERAL       2
Token.BAR           |
Token.LITERAL       3
Token.PERIOD        .
Token.IDENT         ident
Token.EQL           =
Token.IDENT         letter
Token.LBRACE        {
Token.IDENT         letter
Token.BAR           |
Token.IDENT         digit
Token.RBRACE        }
Token.PERIOD        .
Token.IDENT         number
Token.EQL           =
Token.IDENT         digit
Token.LBRACE        {
Token.IDENT         digit
Token.RBRACE        }
Token.PERIOD        .
Token.IDENT         digit
Token.EQL           =
Token.LITERAL       0
Token.BAR           |
Token.LITERAL       1
Token.BAR           |
Token.LITERAL       2
Token.BAR           |
Token.LITERAL       3
Token.PERIOD        .

En anglais finite-state automaton ou finite state machine ou FSM ↩