Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Grammaire L-attribuée
Résumé
Une grammaire L-attribuée est un type spécial de grammaire attribuée qui permet aux attributs d'être évalués dans une traversée de droite à gauche de l'arbre syntaxique. Cela permet à l'évaluation des attributs d'être facilement incorporée dans une analyse descendante.
De nombreux langages de programmation sont L-attribués. Un type spécial de compilateur, les compilateurs étroits, sont fondés sur certaines formes de grammaires L-attribuées.
Dans les productions d'une grammaire L-attribuée, les attributs d'un symbole syntaxique peuvent dépendre de ceux des symboles qui les précèdent dans la production syntaxique (que ce soit en membre gauche ou droit)
A → A1 A2...An
L'attribut de A2 dépend de ceux de A1 et A.
L'attribut de An dépend de ceux de An-1... A1 et A.
Une grammaire est dite L-attribuée si, dans toute règle A → X1 X2 ... Xn, le calcul dans l'action associée d'un attribut Xi.b ne dépend que des attributs des variables X1 X2 ... Xi-1 et des attributs hérités de A.
Un attribut est soit :
hérité : il participe au calcul de la valeur d’attributs des nœuds fils. C'est-à-dire du nœud vers les fils.
synthétisé : participe au calcul de la valeur d’attributs du nœud père.
parcours(nœud n) {
pour chaque fils m de n {
calculer les attributs hérités de m ;
parcours(m) ; }
calculer les attributs synthétisés de n ; }
le parcours d'un arbre syntaxique dans une grammaire L-attribuée se fait en depth-first-search.
thumb|alt=Flot possible|center|upright=1.5|Flot possible
Dans le graphe de dépendances d’attributs d'une grammaire L-attribuée, les nœuds sont visités en profondeur : visiter le nœud courant, ensuite les fils de gauche à droite en profondeur.
Conséquences :
dans une production A → A1 A2 ... An, le calcul d'un attribut d’un symbole αi à Ai associé ne doit pas nécessiter celui d'un symbole se trouvant à sa droite, que ce soit dans la production courante ou dans toutes les dérivations possibles.
Une évaluation ascendante construit l'arbre syntaxique de bas en haut. Une grammaire L-attribuée requiert le parcours de l'arbre de haut en bas.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.