Langages hors contexte et automates à pile

Les grammaires hors contexte génèrent des langages à structure imbriquée et récursive, et les automates à pile reconnaissent précisément ces langages en augmentant un contrôle fini d'une pile illimitée.

Definition

Un langage hors contexte est généré par une grammaire dont les règles réécrivent un unique symbole non terminal indépendamment du contexte, et il est reconnu par un automate à pile, un automate fini équipé d'une pile qui fournit une mémoire de type dernier entré, premier sorti (LIFO) de profondeur illimitée.

Scope

Ce sujet couvre les grammaires hors contexte et les dérivations, les arbres de dérivation et l'ambiguïté, l'équivalence des grammaires hors contexte avec les automates à pile, les formes normales telles que la forme normale de Chomsky, le lemme de pompage pour les langages hors contexte, ainsi que les propriétés de clôture et de décision qui distinguent cette classe des langages réguliers.

Core questions

• Quels types de motifs imbriqués ou récursifs nécessitent une pile plutôt qu'une mémoire finie ?
• Pourquoi les grammaires hors contexte et les automates à pile sont-ils équivalents en termes de puissance ?
• Quand une grammaire est-elle ambiguë, et pourquoi l'ambiguïté est-elle importante pour l'analyse syntaxique ?
• Quels problèmes de décision pour les langages hors contexte sont solubles, et lesquels ne le sont pas ?

Key theories

Équivalence grammaire-automate

Un langage est hors contexte si et seulement s'il est accepté par un automate à pile, de sorte que la perspective de la grammaire générative et celle de la machine à pile décrivent la même classe de langages.

Forme normale de Chomsky

Toute grammaire hors contexte peut être réécrite de manière à ce que chaque règle produise soit deux non-terminaux, soit un seul terminal, une forme normale qui sous-tend les algorithmes d'analyse syntaxique et les preuves inductives concernant cette classe.

Lemme de pompage pour les langages hors contexte

Toute chaîne suffisamment longue dans un langage hors contexte peut être divisée de manière à ce que deux de ses parties puissent être « pompées » ensemble, une propriété qui ne s'applique pas aux langages nécessitant plus qu'une mémoire de pile et qui prouve ainsi qu'ils ne sont pas hors contexte.

Clinical relevance

Les grammaires hors contexte spécifient la syntaxe de presque tous les langages de programmation et de nombreux formats de données, et les algorithmes d'analyse syntaxique de type automate à pile transforment ces grammaires en analyseurs syntaxiques au cœur des compilateurs et des interpréteurs, faisant de ce sujet le fondement théorique du traitement des langages de programmation.

History

Chomsky a introduit les grammaires hors contexte à la fin des années 1950 dans le cadre de sa hiérarchie, et elles ont été utilisées indépendamment par Backus et Naur pour définir la syntaxe du langage de programmation ALGOL. L'équivalence avec les automates à pile et la théorie structurelle de cette classe ont été élaborées tout au long des années 1960.

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

Pourquoi l'analyse syntaxique d'un langage de programmation nécessite-t-elle une pile ?

Les programmes contiennent des constructions imbriquées telles que des parenthèses, des blocs et des appels de fonction dont la profondeur d'imbrication est illimitée. Une pile enregistre chaque construction non terminée et la dépile lorsqu'elle est fermée, ce qui correspond précisément à la discipline de mémoire qu'un automate à pile fournit et qu'un automate fini ne possède pas.

Que signifie pour une grammaire d'être ambiguë ?

Une grammaire est ambiguë lorsqu'une chaîne donnée possède plus d'un arbre de dérivation, ce qui signifie qu'elle peut être dérivée avec des structures véritablement différentes. L'ambiguïté est indésirable pour les langages de programmation car elle rend le sens du code peu clair ; les concepteurs de langages recherchent donc des grammaires non ambiguës ou ajoutent des règles de désambiguïsation.