L'évaluation de votre travail dans ce module est faite sur une synthèse d'articles de recherche. Cet exercice consiste en une présentation individuelle d'un article choisi parmi les articles proposés dans cette page. C'est un exercice assez difficile.
Le contenu technique des articles vous paraîtra probablement incompréhensible au premier abord. Ne vous affolez pas : la première lecture d'un article prend facilement une demi journée, et ne vous permet pas de comprendre tous les points techniques de l'article. En revanche, essayez lors de cette première lecture de comprendre les motivations et la démarche des auteurs. Relisez l'introduction et la conclusion plusieurs fois au besoin, mais vous devez bien comprendre pourquoi l'auteur s'intéresse au problème et comment il l'aborde.
Même au moment de votre présentation, les preuves des points théoriques avancés vous paraîtront peut-être encore obscures ; ça n'est pas un problème. Nous souhaitons cependant que vous ayez acquis une bonne compréhension des points techniques développés dans l'article. Aussi, il est recommandé de concevoir un nouvel exemple (non présent dans l'article) et de lui appliquer les formules et algorithmes développés par les auteurs. C'est le meilleur moyen de vous approprier les explications qui vous ont parues difficiles au premier abord.
Enfin, il est nécessaire d'être capable de situer l'article dans l'ensemble des travaux du domaine. Pour cela, vous allez considérer un autre article (cité par votre article étudié, le citant, ou simplement proche), et chercher les liens entre les deux. La recherche bibliographique est un travail important. Vous trouverez des pistes sur des sites tels que Google Scholar ou CiteSeer pour trouver des références citant l'article étudié. Faire le tri peut être difficile, aussi vous pouvez nous demander conseil sur le choix de cet autre article. Il n'est pas nécessaire de faire une étude approfondie de cet autre article, il faut simplement saisir comment les résultats scientifiques se propagent et se réutilisent. Positionner l'article dans le contexte général de la recherche en analyse syntaxique vous permet aussi d'user un peu de votre esprit critique. Les auteurs ont naturellement tendance à présenter leurs résultats sous un jour très favorable, mais leurs non-dits (et leurs erreurs !) nous intéressent aussi.
En bref, l'exercice consiste en
La lecture d'articles de recherche est un exercice nouveau pour la majorité, si ce n'est la totalité, d'entre vous. En préparation de la quatrième séance de cours, nous vous recommandons de lire l'article original d'Earley sur sa méthode d'analyse générale :
A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.
Certains des articles proposés ont une version électronique qui a été copiée sur le serveur pour vous en faciliter l'accès. Cet accès se fait uniquement sur mot de passe individuel pour respecter les droits des éditeurs qui ont publié les articles (la copie est permise dans le cadre du cours, mais la redistribution aveugle sur Internet ne l'est pas). Les autres articles ne sont disponibles que sous forme papier, et nous vous fournirons les copies nécessaires. Cela vaut aussi pour les articles que vous lirez pour comparaison.
Ne basez pas votre choix sur le nombre de pages des articles, celui-ci peut-être trompeur. Utilisez plutôt vos affinités avec les problèmes abordés.
Un article très pédagogue, bien illustré.
An algorithm is described which accepts an arbitrary context-free grammar and constructs a bounded-context parser for it whenever such a parser exists.
In the first part of the paper the definition of a context-free grammar and the working of a bounded-context parser are recalled. The notion of reduction class for a context-free grammar is then introduced and its connection with the structure of a bounded-context parser is indicated. Next, pushdown automata which generate the different reduction classes of a context-free grammar are defined. Finally, the algorithm is described; it essentially carries out an exhaustive study of all possible runs of the pushdown automata generating the reduction classes.
In the second part, the utility of the algorithm is discussed in the light of the experience gained from its use in compiler design. The algorithm is claimed to be particularly useful in the simultaneous design of a language and a compiler for it.
L'article de Backhouse éclaire l'article original de Knuth par une nouvelle formulation de la grammaire caractéristique, susceptible d'améliorer votre compréhension de LR. L'article est un peu long, mais on ne vous reprochera pas de ne pas traiter la fin sur l'élimination des unit productions.
The methods of improving LR(k) parsers proposed by DeRemer and Korenjak are shown to be based on a single concept—that of modifying the contextual information on which parsing decisions are made. This concept is then used to derive a straightforward algorithm for eliminating unit productions from an LR parser.
L'article original de DeRemer sur SLR est une lecture facile.
A class of context-free grammars, called the "Simple LR(k)" or SLR(k) grammars is defined. This class has been shown to include weak precedence and simple precedence grammars as proper subsets. How to construct parsers for the SLR(k) grammars is also shown. These parser-construction techniques are extendible to cover all of the LR(k) grammars of Knuth; they have been implemented and by direct comparison proved to be superior to precedence techniques, not only in the range of grammars covered, but also in the speed of parser construction and in the size and speed of the resulting parsers.
A practical method is presented for extending the lookahead of LR parsers, by the addition of "reduce-arcs." Applied to an LR(0) parser, this gives a machine which is close in size to the corresponding LALR(1) machine, but is capable of making use of unbounded lookahead. The class of grammars parsable by this method is a subset of the LR-regular grammars which is shown to be properly included in the LALR(k) grammars, if limited to k symbols of lookahead, but also includes non-LR grammars if no such limit is imposed. Application is foreseen to error recovery in LALR(1) parsers, as well as the handling of occasional non-LALR(1) situations in normal parsing.
Si vous avez eu des difficultés avec le cours d'analyse non canonique, cet article donne une bonne introduction au problème. Les annexes avec les preuves de certains points ne sont pas particulièrement intéressantes (les points concernés non plus, ce qui est sans doute lié), et peuvent être totalement ignorées.
Two noncanonical extensions of the simple LR(1) (SLR(1)) method are presented, which reduce not only handles but also other phrases of sentential forms. A class of context-free grammars called leftmost SLR(1) (LSLR(1)) is defined by using lookahead symbols which appear in leftmost derivations. This class includes the SLR(1), reflected SMSP, and total precedence grammars as proper subclasses. The class of LSLR(1) languages properly includes the deterministic context-free languages, their reflections, and total precedence languages. By requiring that phrases which have been scanned be reduced as early as possible, a larger class of context-free grammars called noncanonical SLR(1) (NSLR(1)) is defined. The NSLR(1) languages can be recognized deterministically in linear time using a two-stack pushdown automaton. An NSLR(1) parser generator has been implemented. Empirical results show that efficient NSLR(1) parsers can be constructed for some non-LR grammars which generate nondeterministic languages. Applications of the NSLR(1) method to improve the parsing and translation of programming languages are discussed.
Un article sur l'utilisation de prédicats syntaxiques ou sémantiques pour résoudre les conflits lors de l'analyse descendante.
Most existing language translation problems can be solved with existing LALR(1) or LL(k) language tools; e.g. YACC [Joh78] or ANTLR [PDC92]. However, there are language contructs that defy almost all parsing strategy commonly in use. Some of these constructs cannot be parsed without semantics, such as symbol table information, and some cannot be properly recognized without first examining the entire construct, that is we need "infinite lookahead".
In this paper, we introduce a new LL(k) parser strategy, pred-LL(k), that uses semantic or syntactic predicates to recognize language constructs when normal deterministic LL(k) parsing breaks down. Semantic predicates indicate the semantic validity of applying a production; syntactic predicates are grammar fragments that describe a syntactic context that must be satisfied before application of an associated production is authorized. Throughout, we discuss the implementation of predicates in ANTLR, the parser generator of The Purdue Compiler-Construction Tool Set.
Un article assez lisible présentant un algorithme d'analyse linéaire pour un formalisme syntactique recognitif (pas pour des grammaires algébriques, qui sont génératives).
Packrat parsing is a novel technique for implementing parsers in a lazy functional programming language. A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees linear parse time. Any language defined by an LL(k) or LR(k) grammar can be recognized by a packrat parser, in addition to many languages that conventional linear-time algorithms do not support. This additional power simplifies the handling of common syntactic idioms such as the widespread but troublesome longest-match rule, enables the use of sophisticated disambiguation strategies such as syntactic and semantic predicates, provides better grammar composition properties, and allows lexical analysis to be integrated seamlessly into parsing. Yet despite its power, packrat parsing shares the same simplicity and elegance as recursive descent parsing; in fact converting a backtracking recursive descent parser into a linear-time packrat parser often involves only a fairly straightforward structural change. This paper describes packrat parsing informally with emphasis on its use in practical applications, and explores its advantages and disadvantages with respect to the more conventional alternatives.
Une optimisation de GLR.
We prove a property of generalized LR (GLR) parsing if the grammar is without right and hidden left recursions, then the number of consecutive reductions between the shifts of two adjacent symbols cannot be greater than a constant. Further, we show that this property can be used for constructing an optimized version of our GLR parser. Compared with a standard GLR parser, our optimized parser reads one symbol on every transition and performs significantly fewer stack operations. Our timings show that, especially for highly ambiguous grammars, our parser is significantly faster than a standard GLR parser.
Encore une revisite de l'algorithme d'Earley.
Earley's parsing algorithmis a general algorithm, able to handle any context-free grammar. As with most parsing algorithms, however, the presence of grammar rules having empty right-hand sides complicates matters. By analyzing why Earley's algorithm struggles with these grammar rules, we have devised a simple solution to the problem. Our empty-rule solution leads to a new type of finite automaton expressly suited for use in Earley parsers and to a new statement of Earley's algorithm. We show that this new form of Earley parser is much more time efficient in practice than the original.
Ces articles sur les aspects linguistiques de la syntaxe sont intéressants dans le cadre du cours. Cependant, il risque d'être difficile de suivre exactement la démarche prévue, puisque proposer un exemple linguistique est l'objet même de la recherche dans le domaine. Sur ces articles, vous pouvez donc vous contenter de l'exercice de synthèse à proprement parler et de la mise en contexte.
L'article original définissant (entre autres) les grammaires algébriques comme support de la formalisation de l'anglais.
We investigate several conceptions of linguistic structure to determine whether or not they can provide simple and "revealing" grammars that generate all of the sentences of English and only these. We find that no finite-state Markov process that produces symbols with transition from state to state can serve as an English grammar. Furthermore, the particular subclass of such processes that produce n-order statistical approximations to English do not come closer, with increasing n, to matching the output of an English grammar. We formalize the notions of "phrase structure" and show that this gives us a method for describing language which is essentially more powerful, though still representable as a rather elementary type of finite-state process. Nevertheless, it is successful only when limited to a small subset of simple sentences. We study the formal properties of a set of grammatical transformations that carry sentences with derived phrase structure into new sentences with derived phrase structure, showing that transformational grammars are processes of the same elementary type as phrase-structure grammars; that the grammar of English is materially simplified if phrase structure description is limited to a kernel of simple sentences from which all other sentences are constructed by repeated transformations; and that this view of linguistic structure gives a certain insight into the use and understanding of language.
Après avoir longtemps considéré les langues naturelles comme non algébriques sur des bases faussées, les linguistes ont enfin pu lire dans cet article une preuve recevable.
Pour finir, vous êtes bien sûr libres de proposer une autre référence.