Pour qu'un langage soit programmable, est-il obligatoire qu'il soit basé sur une grammaire sans contexte

23

Pratiquement, pour un langage qui peut éventuellement être compilé / transformé en instructions au niveau du système, est-il nécessaire que ce soit une grammaire sans contexte?

ex: tous les langages de programmation / script sont-ils des grammaires sans contexte? Java est basé sur des CFG, mais est-il vrai que tous les langages de programmation sont basés sur des CFG?

Cela ne semble pas obligatoire, mais il y a des lacunes dans ma compréhension.

Un contexte pour la question: je regardais la spécification du langage Java, qui fournit également les règles de grammaire . Cela m'a fait réfléchir à cette question.

pl.programming-languages context-free sandeepkunkunuru
la source
1
En général, je pense que c'est juste que vous voulez que le problème de compilation soit calculable, et analyser les CFG est agréable et facile. Bien que j'aie entendu certaines affirmations selon lesquelles, par exemple, la reconnaissance de programmes perl valides est en fait un problème non calculable.
Janne H.Korhonen
2
en fait, tout ce dont vous avez vraiment besoin est une syntaxe décidable par Turing (ce que sont tous les CFG). Vous aussi pouvez faire un langage de programmation qui dont la syntaxe est non-turing décidable, mais quand vous faites une faute de frappe le compilateur peut jamais cesser alors qu'il est en train de décider si elle est est une syntaxe valide. ce n'est pas vraiment utile
monstre à cliquet
@ratchet, supposez-vous que la syntaxe doit être récursivement énumérable?
David Harris
4
@JanneKorhonen: Plus précisément, Perl ne peut pas être analysé statiquement , c'est-à-dire qu'il ne peut pas être analysé sans être également exécuté; étant donné que ladite exécution pourrait ne pas se terminer, l'analyse statique de Perl impliquerait de résoudre le problème d'arrêt.
Jon Purdy
@janne Je veux dire, le post-traitement qui peut entraîner des problèmes qui peuvent être calculables ou non, est-il généralement le cas que la grammaire finale par rapport à laquelle le programme est validé est hors contexte. Pour être plus précis, après le prétraitement, pour identifier une règle qui correspond à une séquence de jetons, devons-nous examiner les autres jetons entourant la séquence. Je ne sais pas si j'ai du sens, désolé pour ça. Je suis un peu confus en fait.
sandeepkunkunuru

Réponses:

20

Deux fois non.

Premièrement, la plupart des HPL ne sont pas sans contexte. Bien qu'ils aient généralement une syntaxe basée sur un CFG, ils ont également ce que les gens appellent la sémantique statique (qui est également souvent incluse dans le terme syntaxe). Cela peut inclure des noms et des types qui doivent rechercher un programme correct. Par exemple,

class A {
  String a = "a";
  int b = a + d;
}

est un programme Java syntaxiquement correct mais ne se compilera pas car il dn'est pas défini et an'a pas de type approprié.

Deuxièmement, vous pouvez analyser des langages qui ne sont pas sans contexte (comme le prouve évidemment l'existence de compilateurs). C'est seulement que les CFG peuvent être analysés efficacement, tandis que les CSG ne le peuvent pas, en général. Cependant, vous pouvez ajouter certaines fonctionnalités non contextuelles tout en restant efficace.

Les compilateurs s'exécutent souvent par phases: d'abord la tokenisation (régulière), puis l'analyse sans contexte, puis l'analyse des noms et des types (contextuelle, parfois même plus difficile). Vous pouvez observer ce comportement par le type de messages d'erreur que vous obtenez.

Raphael
la source
3
N'oubliez pas que public class Program { public static void main(String[] args) { ... } }... Java ne vous laissera pas partir aussi facilement. :-)
Roy Tinker
Techniquement, class A { ... }c'est tout à fait suffisant pour javaccompiler des choses que vous ne pouvez pas réellement exécuter (faute de point d'entrée). Mais oui.
Raphael
20

L'analyse de perl n'est pas décidable.

http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0

http://www.perlmonks.org/?node_id=663393

Niall Murphy
la source
6
Je pense que cela devrait être la punchline d'une blague Perl :)
Suresh Venkat
5
Suresh: J'ai déjà fait cette blague, même si elle ne s'est pas avérée être une très bonne blague, dans l'article "Sur les langages de programmation non flexibles" dans SIGBOVIK 2011 ( sigbovik.org/2011/proceedings.pdf - page 79- 82).
Rob Simmons
1
Remarque: l'interprète Perl n'est pas encore non déterministe, si cela peut réconforter quelqu'un :)
Roy Tinker
15

Je ne crois pas que la grammaire de Python soit sans contexte. L'exigence que les lignes dans le même bloc de code aient la même quantité d'indentation n'est pas le genre de chose que les grammaires sans contexte gèrent bien.

Plus précisément, il semble y avoir un homomorphisme du langage des blocs Python de la forme

si condition:
     ligne 1
     ligne 2
     ligne3
autre:
     ligne4

à la langue non contextuelle où le premier bloc de zéros vient de l'ensemble des espaces au début de la ligne 1, le deuxième bloc vient l'ensemble des espaces au début de la ligne 2, le troisième bloc provient de l'ensemble des espaces au début de la ligne 3, et les lignes restantes avec le reste, etc. sont là pour forcer la ligne 1, la ligne 2 et la ligne 3 à appartenir au même bloc.0n10n10n

David Eppstein
la source
4
Strictement, vous avez raison, mais dans le contexte des langages de programmation, nous essayons de rendre sans contexte le langage résultant après une étape de prétraitement appelée tokenisation . Je pense que l'indentation est vérifiée avant cela.
Diego de Estrada
7
Oui, le lexer Python (tokenizer) a une pile de profondeurs d'indentation; le flux de jetons a un symbole INDENT au début de chaque bloc et un symbole DEDENT à la fin qui peuvent être analysés sans contexte (INDENT et DEDENT agissent comme les accolades en C). C a le problème "ne peut pas dire si la déclaration ou l'expression" est foo * bar;une déclaration de foocomme un pointeur vers barou une multiplication de foofois bar?
Max
8
Ok, bien sûr, mais alors vous cachez juste la même complexité dans le lexer, plutôt que d'en faire un transducteur à états finis comme ils le sont souvent.
David Eppstein
1
@DavidEppstein: Pour être juste, cette complexité n'est en aucun cas grande.
Jon Purdy
1
Outre la gestion de INDENT / DEDENT dans le lexer, Python a une grammaire LL (1) très simple.
rmmh
13

Bodo Manthey et Martin Böhme montrent que chaque compilateur C ++ est nécessairement Turing complet, c'est-à-dire qu'il peut calculer n'importe quelle fonction récursive partielle au moment de la compilation . C'est donc bien pire que simplement sensible au contexte.

http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf

Markus Bläser
la source
Oui, mais le compilateur n'est jamais seulement des grammaires sans contexte. Vous devriez discuter de la grammaire elle-même, pas du compilateur.
Jeff Burdges
@Jeff: "Compiler le temps" dans ma réponse signifie "vérifier si un code source C + donné est correct". Par une légère modification de la construction de l'article, il s'ensuit que vous pouvez réduire chaque langage décidable à l'ensemble de tous les programmes C ++ corrects.
Markus Bläser
7

Je pense que la déclaration avant utilisation des variables et le polymorphisme de fonction des langages POO sont d'autres exemples de spécifications de langages de programmation qui ne peuvent pas être gérées par des grammaires sans contexte:

int myfun(int a) { ... }
int myfun(int a, int b) { ... }
int myfun(int a, int b, int c, ...) { ... }
...
int I_m_I_cfg = myfun(1,2);
...

J'ai fait une petite recherche sur Google et j'ai trouvé cet article: " Une grammaire booléenne pour un langage booléen simple " par A.Okhotin (2004); selon lui, le vrai problème est de trouver un langage de programmation complètement décrit par une grammaire formelle:

Un langage de programmation procédural jouet est défini, et une grammaire booléenne pour l'ensemble des programmes bien formés dans ce langage est construite. Il s'agit apparemment de la première spécification d'un langage de programmation entièrement par une grammaire formelle.

La section Introduction de l'article est courte mais très claire.

Marzio De Biasi
la source
6

Je pense que la grammaire de C n'est techniquement pas contextuelle dans la mesure où les analyseurs utilisent toujours des techniques non contextuelles pour prendre en charge l'appareil de Duff .

Les langages basés sur l'indentation ne sont pas naturellement non plus contextuels, comme l'a dit David, mais ils deviennent indépendants du contexte par rapport à un jeton d'indentation paramétré.

Haskell vous permet de modifier la priorité des opérateurs avec infix et infixl. Le module pragma strict de Perl est implémenté en utilisant les paramètres lexicaux $ ^ H et% ^ H, ce qui le rend non contextuel, probablement d'autres paramètres également.

Il existe des langages de développement de macro comme TeX dans lesquels l'analyse afaik n'a pas de sens sans exécution.

Il existe probablement même deux grammaires sans contexte dont l'intersection n'est pas sans contexte mais décrit toujours une machine de Turing.

Java et l'assembleur sont probablement tous deux naturellement hors contexte.

Jeff Burdges
la source
2
L'ambiguïté du (a)-brendu C n'est-elle pas contextuelle? ( apourrait être une variable ou un typedef - certaines autres langues ne permettent pas de
transposer des
Je m'excuse pour le commentaire très retardé, mais l'appareil de Duff n'implique aucune déviation syntaxique. Les bretelles s'équilibrent correctement. La fonction C est le plus souvent ignorée dans les discussions pour savoir si C est sans contexte est le préprocesseur. Je suis sceptique qu'il existe une interprétation, même informelle, de «sans contexte» qui permet de l'utiliser pour décrire un langage avec un macro processeur, même un comportement correct. Et le préprocesseur C est tout sauf sage.
rici
4

Non, et de nombreuses langues pratiques ne sont pas sans contexte. Par exemple, la grammaire C ++ ne l'est pas, car dans certains contextes, la résolution de la grammaire dépend de la saisie d'informations qui ne sont pas hors contexte.

antti.huima
la source
4

Permettez-moi d'abord de faire une distinction entre la syntaxe d'un langage de programmation et le langage lui-même.

La syntaxe de nombreuses langues est (au moins basée sur) une grammaire sans contexte (CFG) car elles sont bien étudiées et il existe des algorithmes qui peuvent analyser efficacement un CFG et le cas de bord qui ne peut pas être résolu par le CFG peut être géré spécialement

Cependant, de nombreux langages ne sont en fait pas sans contexte (lorsque des symboles de déclaration avant utilisation sont utilisés, par exemple en java, C (++), D).

Fait amusant: D a une évaluation de la fonction de compilation complète de Turing et une extension de modèle rendant le langage lui-même non décidable par Turing. Cependant, le créateur du langage s'est donné beaucoup de mal pour faire de la syntaxe un CFG.

monstre à cliquet
la source
L'analyse de nom et de type effectue généralement des tâches intrinsèquement non contextuelles.
Raphael
La méta-programmation des modèles en C ++ est Turing terminée.
Jeff Burdges
3

En ce qui concerne les «grammaires sans contexte de tous les langages de programmation / scripting? partie est concernée, la réponse est un non.

Re: la question principale de "pour un langage qui peut éventuellement être compilé / transformé en instructions de niveau système", je ne sais pas pourquoi il doit nécessairement être un CFG. Cependant, il pourrait y avoir de meilleures explications à venir.

Kris
la source
1
Kris, pouvez-vous donner quelques exemples de langages de programmation basés sur une grammaire non contextuelle. Je veux dire, un post-traitement qui peut entraîner des problèmes qui peuvent ou non être calculables, la grammaire finale par rapport à laquelle le programme est validé.
sandeepkunkunuru
3

Un langage de programmation doit être basé sur une sorte de formalisme grammatical, dont les CFG sont un exemple. Alors que les CFG sont les plus courants (et sont la chose habituelle enseignée dans les cours de compilateur dans les universités), il existe d'autres formalismes tels que les grammaires d'expression syntaxique, que vous pouvez lire ici (pdf) ou sur Wikipedia pour une lecture plus petite.

evilcandybag
la source