Analyse LL

Résumé

En informatique, l'analyse LL est une analyse syntaxique descendante pour certaines grammaires non contextuelles, dites grammaires LL. Elle analyse un mot d'entrée de gauche à droite (Left to right en anglais) et en construit une dérivation à gauche (Leftmost derivation en anglais). L'arbre syntaxique est construit depuis la racine puis en descendant dans l'arbre. L'analyse LL réalise une seule passe sur le mot d'entrée. Une analyse LL est appelée analyse LL(k) lorsqu'elle utilise une fenêtre de k lexèmes pour décider comment construire l'arbre syntaxique du mot d'entrée. Architecture d'un analyseur LL Ce qui suit décrit une analyse descendante à dérivation à gauche fondée sur une table d'analyse. La notion de dérivation à gauche signifie que lors du processus d'application des règles c'est le non-terminal le plus à gauche qui est choisi et réécrit. Cet aspect se traduit par l'utilisation d'une pile dans l'algorithme de l'analyseur. Cas général pour une analyse LL(

Source officielle

https://fr.wikipedia.org/wiki/Analyse_LL

À 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.

Publications associées (3)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (11)

Concepts associés

Chargement

Cours associés (5)

Cours associés

Chargement

Séances de cours associées (15)

Séances de cours associées

Chargement

Neural Tangent Kernel: Convergence and Generalization in Neural Networks (Invited Paper)

Franck Raymond Gabriel, Clément Hongler

The Neural Tangent Kernel is a new way to understand the gradient descent in deep neural networks, connecting them with kernel methods. In this talk, I'll introduce this formalism and give a number of results on the Neural Tangent Kernel and explain how they give us insight into the dynamics of neural networks during training and into their generalization features.

ASSOC COMPUTING MACHINERY2021

Chargement

Traversal Query Language For Scala.Meta

Eric Beguet, Eugene Burmako

With the rise of metaprogramming in Scala, manipulating ASTs has become a daily job. Yet the standard API provides only low-level mechanisms to transform or to collect information on those data structures. Moreover, those mechanisms often force the programmer to manipulate state in order to retrieve information on these ASTs. In this report, we try to solve those problems by introducing TQL, a high-level combinator Scala library to transform and query data structures in a purely functional way. Parser combinators allow to combine several small parsers to build a bigger one in an expressive way. In this report, we argue that we can apply the same concept to data structure manipulation and construct complicated traversers on top of smaller ones. Yet combinators may feel unnatural or too complicated for certain usage. We therefore built a library on top of TQL to manipulate data structures as a collection. We then put TQL in practice to scala.meta ASTs, and describe the challenges we face when traversing a real-word data structure, especially performance-wise.

2015

Chargement

MLsub extends traditional Hindley-Milner type inference with subtyping while preserving compact principal types, an exciting new development. However, its specification in terms of biunification is difficult to understand, relying on the new concepts of bisubstitution and polar types, and making use of advanced notions from abstract algebra. In this paper, we show that these are in fact not essential to understanding the mechanisms at play in MLsub. We propose an alternative algorithm called Simple-sub, which can be implemented efficiently in under 500 lines of code (including parsing, simplification, and pretty-printing), looks more familiar, and is easier to understand. We present an experimental evaluation of Simple-sub against MLsub on a million randomly-generated well-scoped expressions, showing that the two systems agree. The mutable automaton-based implementation of MLsub is quite far from its algebraic specification, leaving a lot of space for errors; in fact, our evaluation uncovered several bugs in it. We sketch more straightforward soundness and completeness arguments for Simple-sub, based on a syntactic specification of the type system. This paper is meant to be light in formalism, rich in insights, and easy to consume for prospective designers of new type systems and programming languages. In particular, no abstract algebra is inflicted on readers.

2020

Chargement