Combinateur d'analyseursEn programmation informatique, un combinateur d'analyseurs est une fonction d'ordre supérieur qui accepte plusieurs analyseurs en entrée et renvoie un nouvel analyseur en sortie. Dans ce contexte, un analyseur est une fonction acceptant des chaînes en entrée et renvoyant une structure en sortie, généralement un arbre d'analyse ou un ensemble d'indices représentant les emplacements dans la chaîne où l'analyse s'est arrêtée avec succès.
Analyse syntaxiqueL' consiste à mettre en évidence la structure d'un texte, généralement une phrase écrite dans une langue naturelle, mais on utilise également cette terminologie pour l'analyse d'un programme informatique. L' (parser, en anglais) est le programme informatique qui réalise cette tâche. Cette opération suppose une formalisation du texte, qui est vue le plus souvent comme un élément d'un langage formel, défini par un ensemble de règles de syntaxe formant une grammaire formelle.
Recursive descent parserIn computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes. A predictive parser is a recursive descent parser that does not require backtracking.
Comparison of parser generatorsThis is a list of notable lexer generators and parser generators for various language classes. Regular languages are a category of languages (sometimes termed Chomsky Type 3) which can be matched by a state machine (more specifically, by a deterministic finite automaton or a nondeterministic finite automaton) constructed from a regular expression.
Analyseur LRComme tout analyseur grammatical (ou analyseur syntaxique), un analyseur LR vise à vérifier si une chaîne de caractères (typiquement contenue dans un fichier) possède bien la structure d'une grammaire spécifiée à l'avance. Cette vérification s'accompagne généralement d'actions. Une action typique est la génération d'une autre chaîne de caractères ou encore d'un arbre d'analyse. Ainsi l'analyse grammaticale est généralement utilisée pour la compilation (transformation d'un code source en code machine).
Analyse lexicaleEn informatique, l’analyse lexicale, lexing, segmentation ou tokenization est la conversion d’une chaîne de caractères (un texte) en une liste de symboles (tokens en anglais). Elle fait partie de la première phase de la chaîne de compilation. Ces symboles sont ensuite consommés lors de l'analyse syntaxique. Un programme réalisant une analyse lexicale est appelé un analyseur lexical, tokenizer ou lexer. Un analyseur lexical est généralement combiné à un analyseur syntaxique pour analyser la syntaxe d'un texte.
Analyse EarleyEn théorie des langages, l'algorithme d'Earley est un algorithme d'analyse syntaxique pour les grammaires non contextuelles décrit pour la première fois par Jay Earley. À l'instar des algorithmes CYK et GLR, l'algorithme d'Earley calcule toutes les analyses possibles d'une phrase (et pas seulement une de ces analyses). Il repose sur de la programmation dynamique. On peut construire un analyseur Earley pour toute grammaire non contextuelle. Il s'exécute en temps cubique (O (n3), où n est la longueur de la chaîne d'entrée).
Arbre de la syntaxe abstraiteEn informatique, un arbre de la syntaxe abstraite ou ASA (abstract syntax tree, ou AST, en anglais) est un arbre dont les nœuds internes sont marqués par des opérateurs et dont les feuilles (ou nœuds externes) représentent les opérandes de ces opérateurs. Autrement dit, généralement, une feuille est une variable ou une constante. Un arbre de la syntaxe abstraite est utilisé par un analyseur syntaxique comme un intermédiaire entre un arbre d'analyse et une structure de données.
Arbre syntaxiqueUn arbre syntaxique est un arbre permettant de représenter la syntaxe d'un objet. En linguistique, l'arbre syntaxique représente la structure syntaxique d'une phrase. Le nombre de catégories morphosyntaxiques correspondent à des classes distributionnelles, c'est-à-dire à la place qu'elles occupent dans la phrase, sur l'axe syntagmatique. En fonction de son voisinage, chaque élément peut commuter avec un autre élément de même catégorie.
Shift-reduce parserA shift-reduce parser is a class of efficient, table-driven bottom-up parsing methods for computer languages and other notations formally defined by a grammar. The parsing methods most commonly used for parsing programming languages, LR parsing and its variations, are shift-reduce methods. The precedence parsers used before the invention of LR parsing are also shift-reduce methods. All shift-reduce parsers have similar outward effects, in the incremental order in which they build a parse tree or call specific output actions.
Top-down parsingTop-down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. LL parsers are a type of parser that uses a top-down parsing strategy. Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis.
Grammaire formelleUne grammaire formelle est un formalisme permettant de définir une syntaxe et donc un langage formel, c'est-à-dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation logique, compilation (analyse syntaxique), en théorie de la calculabilité et dans le traitement des langues naturelles (tout particulièrement en ce qui concerne leur morphologie et leur syntaxe).
GrammaireLa grammaire est l'étude objective et systématique des éléments (phonème, morphème et mot) et des mécanismes et processus de formation, de construction et d'expression constitutifs d'une langue naturelle, écrite ou parlée, en particulier par l'étude de la morphologie et de la syntaxe et à l'exclusion de la phonologie, de la lexicologie, de la sémantique et de la stylistique. Par extension, on nomme aussi grammaire un manuel ou un ensemble de documents décrivant des règles grammaticales.
Grammaire générative et transformationnelleLa grammaire générative et transformationnelle est une théorie syntaxique s’inscrivant dans le courant de la linguistique générative. Majoritairement présente en Amérique du Nord, elle s’est développée depuis 1957 sous l’impulsion de Noam Chomsky. Cette théorie tente de caractériser la connaissance de la langue qui permet l'acte effectif du locuteur-auditeur. La grammaire générative est basée sur la distinction entre compétence et performance (connaissance que le locuteur-auditeur a de sa langue contre l’emploi effectif de la langue dans des situations concrètes).
Parsing expression grammarIn computer science, a parsing expression grammar (PEG) is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s. Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG.
ANTLRANTLR, sigle de ANother Tool for Language Recognition, est un framework libre de construction de compilateurs utilisant une analyse LL(*), créé par Terence Parr à l'Université de San Francisco. ANTLR prend en entrée une grammaire définissant un langage et produit le code reconnaissant ce langage. La dernière version d'ANTLR permet de générer du code pour les langages Java, C#, Python2, Python3, JavaScript, C++, Go, Swift et PHP. Dans sa dernière version, ANTLR peut supporter des grammaires utilisant de la récursivité gauche directe, mais pas indirecte.
Syntax (programming languages)In computer science, the syntax of a computer language is the rules that define the combinations of symbols that are considered to be correctly structured statements or expressions in that language. This applies both to programming languages, where the document represents source code, and to markup languages, where the document represents data. The syntax of a language defines its surface form. Text-based computer languages are based on sequences of characters, while visual programming languages are based on the spatial layout and connections between symbols (which may be textual or graphical).
Lex (logiciel)vignette|Éric Schmidt, programmeur de Lex.. Lex est un outil de génération d'analyseurs lexicaux en langage C. Du point de vue de la classification des langages, Lex est capable de traiter des langages de type 3 (réguliers). Il a été originellement écrit par Mike Lesk et Eric Schmidt (devenu PDG, puis président exécutif du conseil d'administration de Google) et fut décrit en 1975. Il est fréquemment utilisé en association avec Yacc, générateur d'analyseur syntaxique. Flex est la version GNU de Lex.
Indentation comme syntaxeUn langage de programmation utilise l'indentation comme syntaxe si une zone de code indentée délimite un bloc. Un bloc est une entité programmatique qui délimite une portée. Peter J. Landin a inventé le concept de l'indentation comme syntaxe et créé le terme anglais off-side rule qui le désigne en 1966. Il constitue une alternative au . L'exemple qui suit est un exemple de bloc en Python (noter les deux points obligatoires - Ils sont des marqueurs syntaxiques qui facilitent la lecture) : def fib(n): if n
Grammaire ambigüeEn informatique théorique et en théorie des langages, une grammaire ambiguë ou ambigüe est une grammaire algébrique qui admet un mot avec deux dérivations gauches distinctes ou — de manière équivalente — deux arbres de dérivation distincts. L'ambiguïté ou l'inambiguïté est une propriété des grammaires, et non des langages. De nombreux langages admettent à la fois des grammaires ambiguës et inambigües, alors que d'autres ne possèdent que des grammaires ambiguës.
