Quelles bonnes notations existent pour les langages déterministes sans contexte et visiblement pushdown?

10

Les langues déterministes sans contexte (DCFL) et les langues visiblement pushdown (VPL) sont deux ensembles de langues formelles entre les langues sans contexte (CFL) et les langues régulières (REG). Existe-t-il une notation lisible qui peut être exprimée en ASCII simple comme Backus-Naur-Form pour CFL et des expressions régulières pour REG?

Jakob
la source
1
Il pourrait être utile de clarifier le sens de «bon» dans le titre de la question. Quel est le problème avec l'utilisation de BNF pour décrire un DCFL?
Tsuyoshi Ito du
1
Par bon je veux dire qu'il devrait être facile à lire et à écrire pour les êtres humains, donc il devrait être basé sur ASCII. BNF est génial - les expressions régulières sont un sous-ensemble compact de BNF. Mais quel sous-ensemble de BNF définit DCFL et qui définit VPL?
Jakob

Réponses:

5

Concernant les DCFL, je ne vois pas de meilleure notation que la fonction de transition de l'automate déterministe pushdown, c'est-à-dire écrire explicitement des règles de forme avec q ,q,z,uneq,γ états q dans Q , z un symbole de pile, γ une séquence de symboles de pile, et aq,qQzγuneun symbole d'entrée ou la chaîne vide. La notation elle-même n'applique pas le déterminisme, mais elle est facilement vérifiée. En utilisant une notation de grammaire sans contexte (comme BNF), vous allez rencontrer des problèmes car les DCFL sont une sous-classe appropriée de CFL, et comme indiqué par DaniCL, vous ne pouvez pas décider en général, étant donné un CFG, si son langage est déterministe.

En ce qui concerne les VPL, un style entre parenthèses / pour les CFG serait suffisant, avec des règles de forme UNEuneαb est un non terminal, a un symbole d'appel, b un symbole de retour et α uneséquence deUNEunebα expression régulière sur un mélange symboles internes et non terminaux. Étant donné que tout VPL est également un (D) CFL, vous pouvez également réutiliser la notation ci-dessus pour les automates de refoulement et vérifier que les opérations de pile correspondent aux appels et aux retours, ou noter la relation de transition d'un automate de mots imbriqué (qui serait moins redondant) .

Edit: à bien y penser, une notation pour les schémas XML, comme la syntaxe compacte de RelaxNG --- qui est une notation ASCII ---, pourrait facilement être utilisée pour les VPL. Vous auriez juste besoin de faire respecter certaines conventions de nommage pour les balises, par exemple une balise d'ouverture « <ab> » pour un symbole appel d' correspondant une balise de fermeture « </ ab> » pour un symbole de retour b .uneb

Sylvain
la source
Merci! En ce qui concerne les DCFL, je pense que c'est une bonne direction. Une syntaxe concrète aurait quelques abréviations pratiques pour les sous-ensembles qui sont analysés par des expressions régulières. En ce qui concerne les VPL, je ne suis pas encore sûr, car un VLP est autorisé à avoir des symboles d'appel et de retour pendants contrairement aux modèles d'arbre comme XML. Vous pouvez mieux le comparer avec une sous-séquence arbitraire d'événements SAX provenant d'une arborescence XML arbitraire. Je doute que RelaxNG puisse décrire cela.
Jakob
La remarque Utiliser ... est déterministe. est hors de propos - cela ne dit pas s'il existe une sous-classe du CFG qui décrit très clairement tous les DCFL et rien d'autre. Telles que les grammaires LR (k).
reinierpost
@reinerpost: vrai, mais (pour ma défense) je ne considérerais pas que les grammaires LR (1) fournissent une notation syntaxique , car il faut vérifier la condition LR (1).
Sylvain
3

Afin de trouver une représentation canonique, considérez ce qui suit: la classe de DCFL est équivalente à la classe de langages générés par les grammaires LR (k), qui est encore une fois équivalente à LR (1). Cela signifie que vous pouvez trouver une grammaire LR (1) pour chaque DCFL. Bien sûr, une grammaire LR (1) est toujours une grammaire sans contexte, mais avec une propriété spéciale: à partir des grammaires LR (1), nous pouvons facilement construire des tables d'analyse pour guider un analyseur déterministe (avec lookahead de 1 symbole, d'où LR (1)). Ces tables d'analyse seraient une autre représentation, quoique un peu moins lisible.

Soit dit en passant, sachez qu'il est indécidable qu'un langage sans contexte donné soit déterministe (Théorème de Greibach).

Je dois admettre que je n'ai jamais entendu parler de VPL.

DaniCL
la source
Eh bien, les représentations canoniques sont rarement faciles à lire, mais merci pour les instructions. Si le théorème de Greibach déclare qu'il y a des langues dans CFL qui ne peuvent pas être décidées pour être dans DCFL - comment spécifiez-vous ces langues? Si vous avez une grammaire, vous pouvez l'exprimer sous forme Backus Naur (BNF), donc le théorème de Greibach semble impliquer qu'il n'y a pas de sous-ensemble de BNF qui exprime exactement DCFL? Les langues visiblement déroulantes sont également appelées «mots imbriqués». Cette classe de langages est relativement nouvelle mais pertinente pour l'analyse des arbres ordonnés et des structures similaires.
Jakob
À propos du problème d'indécidabilité: un langage est un CFL s'il existe une grammaire sans contexte (CFG) le générant. Si on vous donne un CFG, vous pouvez décider si cette grammaire est LR (k), donc déterministe. (La même chose s'applique aux automates pushdown - il est facile de vérifier si un PDA donné est déterministe ou non.) Cependant, supposons que vous ayez un CFG qui n'est pas LR (k) - cela ne signifie pas que la langue n'est pas un DCFL ; vous pourriez ne pas être en mesure de trouver une grammaire LR (k) pour cela.
DaniCL
"vous pouvez décider si cette grammaire est LR (k)" pour k fixe.
Sylvain
@Jakob: Le théorème de Greibach ne dit pas cela, et même si c'était le cas, cela signifierait seulement que les CFG arbitraires ne sont pas un formalisme de notation approprié pour les DCFG, tout comme ils ne sont pas un bon formalisme de notation pour les langages réguliers (que ce soit un CFG décrit qu'un langage régulier est également indécidable). Il n'y a rien de mal cependant à choisir une sous-classe des CFG (par exemple les grammaires régulières pour les langues normales).
reinierpost
Il y a une tradition de formulation bâclée dans les manuels scolaires ici: ils ont tendance à faire des déclarations comme "il est indécidable si une LCF est régulière / déterministe" quand ce qu'ils veulent vraiment dire par là "il est indécidable si un CFG décrit une régularité / déterminisme Langue".
reinierpost