Qu'obtiendriez-vous si vous ajoutez des paramètres à des grammaires sans contexte?

13

Je pensais aux grammaires pour les langues sensibles à l'indentation et il semble que les grammaires CF feraient l'affaire si elles étaient combinées avec des paramètres. À titre d'exemple, considérons ce fragment pour la grammaire Python simplifiée au format de type ANTLR:

// on top-level the statements have empty indent
program  
    : statement('')+
    ;

// let's consider only one compound statement and one simple statement for now
statement(indent) 
    : ifStatement(indent)
    | passStatement(indent)
    ;

passStatement(indent)
    : indent 'pass' NEWLINE
    ;

// statements under if must have current indent plus 4 spaces
ifStatement(indent)
    : indent 'if' expression ':' NEWLINE (statement(indent '    ')+)
    ;

Ma question: ce genre de grammaires (CFG avec paramètres) a-t-il un nom?

Il semble qu'il ne serait pas difficile d'écrire un analyseur de descente récursif pour cette grammaire (les paramètres devraient être essentiellement des analyseurs). Quelles pourraient être les difficultés de cette approche?

L'ajout de paramètres élève-t-il la classe de langue prise en charge au-dessus du contexte?

Aivar
la source
1
Si l'ensemble des valeurs que les paramètres peuvent prendre est fini, alors il est trivialement sans contexte (vous pouvez ensuite parcourir toutes les valeurs et tout écrire).
ratchet freak
1
Il convient de noter que votre proposition concerne des langues sensibles à l'indentation avec une indentation fixe. Python (et d'autres langages de ce type) ne sont pas limités de cette manière; ils acceptent l'indentation souhaitée par l'utilisateur. Cela n'affecte pas la parseabilité (sauf pour la gestion des caractères de tabulation) mais il serait difficile de l'exprimer avec votre proposition, du moins si je comprends bien.
rici
@HendrikJan, les grammaires d'attributs sont un moyen d'annoter la grammaire avec une action sémantique, elles ne contrôlent pas l'analyse.
AProgrammer
1
Si l'objectif est de gérer l'indentation, cela convient mieux au tokenizer qu'à l'analyseur. Demandez au tokenizer d'émettre des jetons virtuels INDENT et UNINDENT lorsque le niveau d'indentation change. Ensuite, il n'est pas nécessaire d'augmenter la grammaire du langage avec des informations sur l'indentation.
John Kugelman

Réponses:

14

Les grammaires d'affixe ( grammaires paramétriques sans contexte) ont été étudiées en détail par l'éminent informaticien néerlandais Cornelis HA Koster , à commencer par son article de 1962 "Basic English, a generative grammar for a part of English", co-écrit avec LGLT Meertens. En 1970, il a produit un formalisme du concept; un aperçu utile est disponible dans son article de 1971 "Affix Grammars for Programming Languages", dont j'ai trouvé une version sur Citeseer .

Dans cet article, Koster compare son formalisme (et un autre similaire) avec les grammaires à deux niveaux de Van Wijngaarden , et les trouve très similaires.

La bibliographie annotée inestimable de Dick Grune sur les techniques d'analyse comprend un grand nombre d'autres références utiles pour les grammaires d'affixe et d'autres formalismes non chomskyiens. (Voir la section 18.2.6 de la bibliographie, bien qu'il existe des articles utiles dans d'autres sections.) Grune couvre brièvement les grammaires d'affixe au §15.3.2 de la deuxième édition de Parsing Techniques: A Practical Guide (et encore plus brièvement dans la première édition , disponible en ligne) mentionnant le fait qu'il est facile d'adapter des techniques d'analyse descendante (et autres).

unenbncn

Koster, qui était également rédacteur en chef du rapport Algol 68, était le développeur original du langage de description du compilateur (CDL) , basé sur ses idées sur les grammaires d'affixe. Cette boîte à outils et ses dérivés ultérieurs ont été utilisés dans la production pendant de nombreuses années. Cette page , que j'ai trouvée avec une recherche Google et dont je ne peux garantir la permanence, contient des liens vers le manuel et le site de téléchargement de CDL3.

rici
la source
Je pense que les langages CDL ressemblent plus à des grammaires d'attributs : les valeurs des attributs peuvent être calculées par des fonctions définies en externe. Je réserverais la grammaire d'affixe de nom aux cas où les relations entre les valeurs des affixes (attributs) sont définies dans le formalisme, comme dans les grammaires d'affixe étendues .
reinierpost
@reinierpost: Vous avez bien sûr droit à votre propre terminologie; le privilège n'est pas limité aux œufs anthropomorphes. Cependant, le manuel CDL lui-même affirme que "CDL3 est un langage d'implémentation basé sur des grammaires d'affixe", ce qui, je pense, devrait être pris en compte. (Manuel disponible sur ftp.cs.kun.nl/pub/cdl3/cdl3-manual-1.2.7.pdf ). C'est ce que j'ai affirmé dans ma réponse: que CDL était basé sur le travail de Koster sur les grammaires d'affixe. Comme le souligne Grune, la différence entre les grammaires d'affixe et d'attribut est faible; sa distinction est de savoir si les affixes sont utilisés pour décider de la validité syntaxique.
rici
(La citation est tirée de la première page du manuel.)
rici
Je sais ... et tu as raison. Mon commentaire n'était pas censé vous contredire.
reinierpost
6

Prenez le lemme de pompage pour les CFG :

Prenez la grammaire

S -> A("")
A(p) -> p 
      | p '\n' A(p"*") '\n' p 

Cela décrit un triangle étoilé:

*
**
***
**
*

uvwXy{uvnwXny|n>0}vX

Cela signifie que le triangle étoilé n'est pas un langage sans contexte.

Ou un exemple plus simple:

S-> B("")
B(p)-> p 'a' p 'a' p
     | B(p 'b')

{bnunebnunebn|n0}

monstre à cliquet
la source
3

Je n'ai jamais vu ce formalisme présenté (même dans quelque chose comme les techniques d'analyse de Grune ). grammaire de structure de phase sans restriction (c'est-à-dire plus puissante que sensible au contexte, vous pouvez écrire une grammaire VW qui donne tous les programmes d'arrêt).

AProgrammer
la source
Koster et son groupe ont étudié deux types de grammaires d'affixe, à ma connaissance: 1) des formes restreintes de grammaires Van Wijngaarden, destinées à permettre une reconnaissance plus facile; 2) les langages CDL, langages pratiques de description du compilateur sans manipulation explicite de valeur d'affixe mais avec la possibilité de définir des règles dans le langage cible (par exemple l'assembleur), ce qui les rend Turing complets.
reinierpost