Un analyseur syntaxique pour grammaires hors-contexte ascendant sélectif et général.
In Les techniques de l'informatique, Congrès AFCET 72, Brochure 1, Grenoble, France, Nov. 1972
(extrait de
l'introduction) :Construire un analyseur syntaxique, c'est passer d'un algorithme de génération du langage (grammaire hors contexte) à un algorithme de reconnaissance du langage. Pour des raisons d'efficacité, le modèle de reconnaissance (précédence d'opérateur, matricdes de transition, langage de production...) n'est pas équivalent au modèle de génération. Le passage du premier au second consiste à ne retenir qu'un certain type d'informations donné par la grammaire. Ce filtrage correspond à une perte d'informations. On définit alors la classe des grammaires pour lesquelles l'analyseur fonctionne correctement, c'est-à-dire la classe des grammaires qui ne contienne pas d'informations utiles éliminées à priori par le constructeur de l'analyseur. Suivant la qualité d'information perdue par différents constructeurs, les classes de grammaires correspondantes peuvent se hiérarchiser dans un arbre d'inclusion. On ne peut malheusement pas donner de critéres permettant d'écrire une grammaire entrant dans l'une ou l'autre des classes.
Notre approche respecte trois principes :
- l'analyseur doit être sélectif. Il est le résultat d'un algorithme dit 'constructeur' qui effectue un prétraitement de la grammaire pour réduire le nombre d'opérations é lémentaires de l'analyseur ;
- L'algorithme est général et multiple.
À ce stade, la donnée de la grammaire ou de l'analyseur est équivalente, (il existe un algorithme de passage de l'une à l'autre forme, les informations étant plus explicites dans l'analyseur) ; - l'analyseur est filtré : les informations non utiles pour l'analyse sont éliminées par un optimiseur.
(from the introduction):A bottom-up, general and selective analyseur for context-free grammars
Building a syntax analyzer consists in moving from a language generation algorithm (context-free grammar) to a language recognition algorithm. For efficiency reasons, the recognition model (operator precedence, transition matrix, production language, etc) is not equivalent to the generation model. The transition of the first to the second consists in retaining only a certain type of information given by the grammar. This filtering corresponds to a loss of information. We then define the class of grammars for which the analyzer operates properly, that is the class of grammars that do not contain information eliminated a priori by the analyzer constructor. According to the quality of the information lost by different constructors, the corresponding grammar classes can be organized in an inclusion tree hierarchy. Unfortunately, one cannot give criteria so as to write a grammar of one or another class.
Or approach follows three principles::
- The analyzer must be selective. It is the result of a so-called 'constructor' algorithm which performs a preprocessing of the grammar to reduce the number of elementary operations of the analyzer.
- The algorithm is general and multiple.
A this point, the grammar and the analyzer are equivalent (there is an algorithm to move from one another, the informations being more explicit in the analyzer). - The analyzer is filtered: the informations which are not useful for the analysis are eliminated by an optimizer.
\bibitem{Cousot-VMCAI03}
P{.} Cousot.
\newblock Un ana\-ly\-seur syn\-ta\-x\-ique pour gram\-mai\-res
hors-con\-tex\-te as\-cen\-dant s{\'e}\-lec\-tif et
g{\'e}\-n{\'e}\-ral.
\newblock In \emph{Les tech\-ni\-ques de l'in\-for\-ma\-ti\-que},
Con\-gr{\`e}s AF\-CET 72, Bro\-chu\-re 1, Gre\-no\-ble,
Fran\-ce, Nov.\ 1972.
@InProceedings{Cousot72-1,
author = {Cousot, P{.}},
title = {Un ana\-ly\-seur syn\-ta\-x\-ique pour gram\-mai\-res
hors-con\-tex\-te as\-cen\-dant s{\'e}\-lec\-tif et
g{\'e}\-n{\'e}\-ral},
pages = {391--405},
booktitle = {Les tech\-ni\-ques de l'in\-for\-ma\-ti\-que},
series = {Con\-gr{\`e}s AF\-CET 72, Bro\-chu\-re 1},
month = nov,
year = 1972,
address = {Gre\-no\-ble, Fran\-ce},
}