Grammaire paramétrée et sémantique
Dans les grammaires paramétrées (ou attribuées), certains attributs sont associés à des éléments individuels de la grammaire, c’est-à-dire aux symboles non-terminaux. Le processus de traduction consiste à associer une sortie (éventuellement vide) à chaque analyse de structure syntaxique. Chaque règle de production est accompagnée de règles supplémentaires qui définissent :
- les relations entre les valeurs d’attributs des symboles reconnus,
- les valeurs d’attributs du symbole non-terminal résultant
- la sortie produite.
Les sections suivants illustrent ces concepts à travers trois applications concrètes d’attributs et des règles d’attributs
Règles de type
A titre d’exemple, considérerons un langage comportant plusieurs types de données.
Au lieu de spécifier des règles syntaxiques distinctes pour les expressions de chaque type, nous définissons les expressions une seule fois et nous associons le type de données T comme attribut à chaque construction concernée.
Par exemple, une expression de type T est dénotée comme exp(T), c’est-à-dire comme exp avec la valeur d’attribut T.
Les règles relatives à la compatibilité des types sont alors considérées comme des ajouts aux équations syntaxiques individuelles.
Par exemple, les exigences selon lesquelles les deux opérandes de l’addition et de la soustraction doivent être du même type et que le type du résultat est le même que celui des opérandes sont spécifiées par ces règles d’attributs supplémentaires :
Syntaxe Règle Condition
------------------------------------------------------------
exp(T0) = term(T1) | T0 := T1
exp(T1) "+" term(T2) | T0 := T1 T1 = T2
exp(T1) "-" term(T2). T0 := T1 T1 = T2
Si les opérandes des types INT et FLOAT doivent être admis dans les expressions mixtes, les règles sont plus souples, mais aussi plus compliquées.
La règle devient :
T0 := if (T1 = INT) & (T2 = INT) then INT else FLOAT
et la condition deviennent :
(T1 = INT or T1 = FLOAT) & (T2 = INT or T2 = FLOAT)
Les règles relatives à la compatibilité des types sont statiques, c’est-à-dire qu’elles peuvent être vérifiées sans exécution du programme. Par conséquent, leur intégration dans la syntaxe sous la forme de règles d’attributs est tout à fait appropriée.
Cependant, nous notons que les grammaires paramétrée prennent une nouvelle dimension si les valeurs d’attributs possibles (ici, les types) et leur nombre ne sont pas connus à l’avance.
Si une équation syntaxique contient une répétition, il convient, au regard des règles d’attributs, de l’exprimer à l’aide de la récursivité :
exp(T0) = term(T1) {"+" term(T2)}
devient
exp(T0) = term(T1) |
exp(T1) "+" term(T2).
Dans le cas d’une option, il est préférable d’exprimer les deux cas séparément :
exp(T0) = ["-"] term(T1).
devient
exp(T0) = term(T1) |
"-" term(T1).
Les règles de type associées à une production entrent en vigueur chaque fois qu’une construction correspondant à la production est reconnue.
Cette association est simple à mettre en œuvre dans le cas d’un analyseur syntaxique récursif :
Les instructions qui implémentent les règles d’attributs sont intercalées dans les instructions du parser et les attributs apparaissent en tant que paramètres des fonctions du parser correspondant aux constructions syntaxiques (symboles non terminaux).
La fonction de reconnaissance des expressions arithmétiques sert de premier exemple pour démontrer ce processusd’extension :
def expression() -> None:
term()
while sym == "+" or sym == "-":
getSym()
term()
est étendu pour mettre en œuvre ses règles d’attributs (types) :
def expression() -> Type:
typ1: Type = term()
while sym == "+" or sym == "-":
getSym()
typ2: Type = term()
typ1 = ResType(typ1, typ2)
return typ1
où ResType est une fonction qui calcule le type du résultat de l’opération en fonction des types des opérandes.
Règles d’évaluation
Dans notre deuxième exemple, nous considérons un langage composé d’expressions dont les facteurs sont uniquement des nombres.
Il n’y a qu’un pas à franchir pour étendre le parser à un programme qui ne se contente pas de reconnaître les expressions, mais qui les évalue également.
Pour ce faire, nous associons à chaque construction sa valeur par le biais d’un attribut appelé val.
Par analogie avec les règles de compatibilité de type de notre exemple précédent, nous traitons les règles d’évaluation lors de l’analyse syntaxique.
Nous avons ainsi implicitement introduit la notion de sémantique :
Syntaxe Règle d'attribut (sémantique)
-------------------------------------------------------------------------
exp(v0) = term(v1) | v0 := v1
exp(v1) "+" term(v2) | v0 := v1 + v2
exp(v1) "-" term(v2). v0 := v1 - v2
term(v0) = factor(v1) | v0 := v1
term(v1) "*" factor(v2) | v0 := v1 * v2
term(v1) "/" factor(v2). v0 := v1 / v2
factor(v0) = number(v1) | v0 := v1
"(" exp(v1) ")". v0 := v1
Ici, l’attribut est la valeur numérique calculée à partir de la construction reconnue. L’extension nécessaire de la procédure d’analyse syntaxique donne la fonction suivante pour les expressions arithmétiques :
def expression() -> Value:
val1: Value = term()
while sym == "+" or sym == "-":
op = sym
getSym()
val2: Value = term()
if op == "+":
val1 = val1 + val2
else:
val1 = val1 - val2
return val1
Règles de traduction
Un troisième exemple d’application des grammaires paramétée présente la structure de base d’un compilateur. Les règles supplémentaires associées à une production ne régissent pas les attributs des symboles, mais spécifient la sortie (code) produite lorsque la production est appliquée dans le processus d’analyse syntaxique. La génération de sortie peut être considérée comme un effet secondaire de l’analyse syntaxique. Généralement, la sortie est une séquence d’instructions.
Dans cet exemple, les instructions sont remplacées par des symboles abstraits, et leur sortie est spécifiée par la fonction put :
Syntax Règle de traduction (semantique)
--------------------------------------------------------------
exp = term | -
exp "+" term | put("+")
exp "-" term. put("-")
term = factor | -
term "*" factor | put("*")
term "/" factor. put("/")
factor = number | put(number)
"(" exp ")". -
Comme on peut facilement le vérifier, la séquence des symboles de sortie correspond à l’expression analysée en notation postfix. Le parser est donc été étendu pour en faire un traducteur.
| Notation infix | Notation postfix |
|---|---|
| 2 + 3 | 2 3 + |
| 2 * 3 + 4 | 2 3 * 4 + |
| 2 + 3 * 4 | 2 3 4 * + |
| (5 - 4) * (3 + 2) | 5 4 - 3 2 + * |
La procédure d’analyse et de traduction des expressions est la suivante :
def expression():
term()
while sym == "+" or sym == "-":
op = sym
getSym()
term()
put(op)
Lors de l’utilisation d’un analyseur piloté par des tables, les tables exprimant la syntaxe peuvent facilement être étendues pour représenter également les règles d’attributs. Si les règles d’évaluation et de traduction sont également contenues dans des tableaux associés, on est tenté de parler d’une définition formelle du langage.
L’analyseur syntaxique générique, piloté par des tables, se transforme en un compilateur générique, piloté par des tables. Un tel système peut être illustré par le schéma suivant :
En fin de compte, l’idée de base de toute langue est qu’elle doit servir de moyen de communication. Cela signifie que les partenaires doivent utiliser et comprendre la même langue. Promouvoir la facilité avec laquelle un langage peut être modifié et étendu peut donc s’avérer contre-productif. Néanmoins, il est devenu habituel de construire des compilateurs utilisant des analyseurs syntaxiques pilotés par des tables, et de dériver automatiquement ces tables de la syntaxe à l’aide d’outils. La sémantique est exprimée par des procédures dont les appels sont également intégrés automatiquement dans le parser. Les compilateurs deviennent ainsi non seulement plus volumineux et moins efficaces, mais aussi beaucoup moins transparents. Cette dernière propriété reste l’une de nos principales préoccupations, et c’est pourquoi nous ne poursuivrons pas plus loin dans cette voie.