Boullier, Pierre
Rapport de recherche de l'INRIA -
Rocquencourt ,
Equipe : CHLOE
54 pages - Août 1994 - Document en anglais
Titre français : Grammaires dynamiques et analyse sémantique
Abstract : We define a dynamic grammar as a device which may generate an unbounded set of context-free grammars, each grammar is produced, while parsing a source text, by the recognition of some construct. It is shown that dynamic grammars have the formal power of Turing machines. For a given source text, a dynamic grammar, when non ambiguous, may be seen as a sequence of usual context-free grammars specialized by this source text: an initial grammar is modified, little by little, while the program is parsed and is used to continue the parsing process. An experimental system which implements a non ambiguous \sl dynamic parser is sketched and applications of this system for the resolution of some semantic analysis problems are shown. Some of these examples are non-trivial (overloading resolution, derived types, polymorphism, \ldots) and indicate that this method may partly compete with other well-known techniques used in type-checking.
Résumé : Nous dèinissons une grammaire dynamique comme un dispositif qui peut engendrer un nombre non borné de grammaires indépendantes du contexte, chacune de ces grammaires étant produite, au cours de l'analyse d'un texte source, par la reconnaissance de constructions particulières. On montre que les grammaires dynamiques ont la puissance formelle des machines de Turing. Pour un texte source donné, une grammaire dynamique, lorsqu'elle est non ambiguù, peut être vue comme une séquence de grammaires usuelles, spécialisées par l'analyse de ce texte : grammaire initiale est modifiée au fur et à mesure de l'analyse du programme et est utilisée pour en poursuivre l'analyse. Un système expérimental, qui implante un \sl analyseur dynamique non ambigu est esquissé et des applications de ce système à la résolution de quelques problèm- es d'analyse sémantique sont proposés. Certains de ces exemples sont non triviaux (résolution de surcharge, types dérivés, polymorphisme, \ldots) et indiquent que cette méthode peut partiellement concurrencer les techniques bien connues utilisées en contrôle de type.
Key-Words : PARSING / INCREMENTAL / EXTENSIBLE / LR / UNBOUNDED LOOK-AHEAD / CONTEXT-FREE /
CONTEXT-SENSITIVE / AMBIGUITY / TYPE-CHECKING
Mots-clés : ANALYSE / INCRÉMENTAL / EXTENSIBLE / LR / PRÉ-VISION NON BORNÉE / INDÉPENDANT
DU CONTEXTE / DÉPENDANT DU CONTEXTE / AMBIGUïTES / CONTRÔLE DE TYPE
