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.
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.
Langage algébriqueEn théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui est engendré par une grammaire algébrique. De manière équivalente, un langage algébrique est un langage reconnu par un automate à pile. Les langages algébriques forment les langages de dans la hiérarchie de Chomsky. Ils ont des applications importantes dans la description des langages de programmation et en linguistique. Ils interviennent également dans la description des langages XML.
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.
Syntactic StructuresSyntactic Structures is an important work in linguistics by American linguist Noam Chomsky, originally published in 1957. A short monograph of about a hundred pages, it is recognized as one of the most significant and influential linguistic studies of the 20th century. It contains the now-famous sentence "Colorless green ideas sleep furiously", which Chomsky offered as an example of a grammatically correct sentence that has no discernible meaning, thus arguing for the independence of syntax (the study of sentence structures) from semantics (the study of meaning).
Étoile de KleeneL'étoile de Kleene, parfois appelée fermeture de Kleene ou encore fermeture itérative, est, en théorie des langages, un opérateur unaire utilisé pour décrire les langages formels. Le nom étoile vient de la notation employée, un astérisque, et Kleene de Stephen Cole Kleene qui l'a introduite. L'étoile de Kleene est l'un des trois opérateurs de base utilisés pour définir une expression rationnelle, avec la concaténation et l'union ensembliste.
Equivalence (formal languages)In formal language theory, weak equivalence of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same. In compiler theory the notion is distinguished from strong (or structural) equivalence, which additionally means that the two parse trees are reasonably similar in that the same semantic interpretation can be assigned to both. Vijay-Shanker and Weir (1994) demonstrates that Linear Indexed Grammars, Combinatory Categorial Grammars, Tree-adjoining Grammars, and Head Grammars are weakly equivalent formalisms, in that they all define the same string languages.
Linguistique théoriqueLa linguistique théorique est la branche de la linguistique qui s'occupe de modéliser la connaissance linguistique. Cette approche implique la recherche et l'explication des universaux linguistiques, qui sont des propriétés que toutes les langues ont en commun. Les champs d'étude généralement considérés comme le noyau de la linguistique théorique sont la syntaxe, la phonologie, la morphologie et la sémantique. La phonologie est souvent confondue avec la phonétique, qui comme la psycholinguistique et la sociolinguistique, sont rarement considérées comme faisant partie de la linguistique théorique.
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.
