Grammaire non contextuelle déterministe

Dans les années 1960, des recherches théoriques en informatique sur les expressions régulières et les automates finis ont conduit à établir que les grammaires non contextuelles sont équivalentes aux automates à pile[1] - [2] - [3]. Les premiers langages de programmation étaient en cours de développement à l'époque (voir histoire des langages de programmation ) et l'écriture de compilateurs était difficile. L'utilisation de grammaires non contextuelles a permis d'automatiser la partie d'analyse du compilateur. Les grammaires non contextuelles déterministes étaient particulièrement utiles car elles pouvaient être analysées séquentiellement par un automate à pile déterministe, ce qui était une exigence en raison des contraintes de mémoire de l'ordinateur[4]. En 1965, Donald Knuth a conçu les analyseurs LR (k) et a prouvé qu'il existe une grammaire LR (k) pour chaque langage déterministe non contextuel[5]. Cet analyseur nécessitait encore beaucoup de mémoire. En 1969, Frank DeRemer a introduit les analyseurs LALR et simple LR, tous deux basés sur l'analyseur LR et ayant un besoin en mémoire ontsidérablement plus petit au prix d'une moindre puissance de reconnaissance du langage. L'analyseur LALR est l'alternative la plus efficace[6]. Ces deux analyseurs sont depuis largement utilisés dans les compilateurs de nombreux langages informatiques. Des recherches récentes ont identifié des méthodes par lesquelles des analyseurs LR canoniques peuvent être implémentés avec des exigences en tables considérablement réduites par rapport à l'algorithme de construction de tables de Knuth[7].

• Analyse déterministe
• Analyseur LL