Quels modèles de calcul peuvent être exprimés par des grammaires?

18

Il s'agit d'une reformulation des programmes de grammaires Are? précédent demandé par Vag et avec de nombreuses suggestions des commentateurs.

De quelle manière une grammaire peut-elle être considérée comme spécifiant un modèle de calcul? Si, par exemple, nous prenons une grammaire simple sans contexte telle que

G ::= '1' -> '0' '+' '1'
      '1' -> '1' '+' '0'
      '2' -> '2' '+' '0'
      '2' -> '1' '+' '1'
      '2' -> '0' '+' '2'
      '3' -> '3' '+' '0'
      '3' -> '2' '+' '1'
      '3' -> '1' '+' '2'
      '3' -> '1' '+' '2'

En supposant que l'analyseur ne fait pas de distinction entre les terminaux et non terminaux symboles comme je l' ai démontré ici, alors il est possible d'effectuer des opérations arithmétiques simples pour les nombres jusqu'à 3.

Par exemple, prenez la chaîne

"2 + 0 + 1"

L'exécution d'un analyseur LR (1) sur cette chaîne devrait nous donner l' arbre de syntaxe concret suivant où le résultat du calcul est stocké à la racine de l'arbre:

           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0' 

Ainsi, si nous considérons une grammaire comme un programme et un générateur d'analyseur comme un compilateur , pourrions-nous voir le langage de spécification de la grammaire comme un langage de programmation ?

De plus, pourrions-nous construire des programmes complets de Turing en spécifiant des grammaires similaires à la façon dont vous pourriez construire des programmes complets de Turing avec des automates celullaires ou le calcul lambda ?

En d'autres termes, on sait que dans le sens de la reconnaissance d' un langage, les langages réguliers correspondent à des automates à états finis , les langages sans contexte correspondent à des automates à pousser vers le bas et les langages contextuels correspondent à des automates bornés linéaires . Cependant, si nous considérons les grammaires comme des dispositifs de calcul (c'est-à-dire des programmes au sens de l'exemple ci-dessus), comment classer la force de calcul de chaque classe de grammaires dans la hiérarchie de Chomsky?

Aussi, que diriez-vous des sous-classes de grammaires moins connues telles que

EDIT: Soit dit en passant, c'est une réponse à ma propre question, mais je n'ai pas mentionné que je n'ai donné aucun symbole de départ pour l'exemple de grammaire et fait signe de la main à la nécessité de faire la distinction entre les terminaux et les non terminaux. Techniquement ou traditionnellement, je pense que la grammaire devrait probablement être écrite sous une forme plus compliquée comme celle-ci (où S est le symbole de départ et le $ représente le terminal de fin de flux):

G ::= S -> R0 '$'
      S -> R1 '$'
      S -> R2 '$'
      R0 -> '0'
      R0 -> R0 '+' '0'
      R1 -> '1'
      R1 -> R0 '+' '1'
      R1 -> '1' '+' R0
      R1 -> R0 '+' '1' '+' R0
      R2 -> '2'
      R2 -> R0 '+' '2'
      R2 -> '2' '+' R0
      R2 -> R0 '+' '2' '+' R0
      R2 -> R1 '+' '1'
      R2 -> R1 '+' '1' '+' R0

... pas que ça change vraiment quelque chose, mais j'ai pensé que je devais le mentionner.

EDIT: Une autre chose qui m'est venue à l'esprit lorsque j'ai lu la réponse de gasche est que chaque branche de l'arbre dans mon exemple représente un sous-calcul. Si vous regardez chaque règle de production comme une fonction où le LHS représente le résultat et le RHS représente ses arguments, la structure de la grammaire détermine la façon dont les fonctions sont composées.

En d'autres termes, le contexte de l'analyseur avec son mécanisme d'anticipation aide à déterminer non seulement les fonctions à appliquer (un peu comme le polymorphisme paramétrique), mais comment elles doivent être composées ensemble pour former de nouvelles fonctions.

Au moins, je suppose que vous pourriez le voir de cette façon pour les CFG sans ambiguïté, pour les autres grammaires, la gymnastique mentale est un peu trop pour moi en ce moment.

Rehno Lindeque
la source
3
Vous avez oublié de mentionner l'automate Visiblement Pushdown (mots imbriqués), un appareil si charmant et si prometteur! C'est important car cela semble être une amélioration minimale par rapport aux expressions régulières pour pouvoir analyser des programmes écrits dans des langages de programmation populaires. ( cis.upenn.edu/~alur/nw.html )
Vag
1
Merci, c'est très intéressant, je n'ai pas cherché! Il y en a quelques autres que j'ai également ignorés comme sans contexte déterministe, adjacents à des arbres, indexés et ainsi de suite, je pensais juste que cela pourrait être un peu trop pour une question ... Mais peut-être que je les ajouterai
Rehno Lindeque
1
@imz Je veux dire les grammaires telles qu'elles sont formellement définies dans la hiérarchie chomsky (c'est-à-dire comme des ensembles de productions). Puisque je revendique exactement ce que vous dites: que les grammaires sont des programmes, cela signifie simplement la classe de programmes représentable par les grammaires (c'est la question).
Rehno Lindeque
1
@imz Pour être honnête, je ne suis vraiment pas familier avec les grammaires indexées, je ne les ai ajoutées qu'après coup.
Rehno Lindeque
1
Je commence à penser que cela aurait pu être une bonne idée de poster cette question sur le forum LtU au lieu de regarder les discussions sympas: P. Btw @imz, il serait peut-être préférable de lire la question comme "quelles classes de grammaires correspondent à quelles classes de programmes au sens" fonctionnel "décrit par Jukka dans la réponse de Marc Hamman". Je devrais peut-être clarifier cela ...
Rehno Lindeque

Réponses:

10

Il existe une correspondance biunivoque entre les grammaires Chomsky Type-0 et les machines de Turing.

Ceci est exploité dans le langage de programmation Thue qui vous permet d'écrire des programmes complets de Turing spécifiés par une chaîne initiale et un ensemble de règles de réécriture de chaîne (une grammaire semi-Thue , qui équivaut à une grammaire de type 0).

MISE À JOUR:

Outre les langages ésotériques "Turing tar-pit" comme Thue, divers langages à usage général qui permettent au programmeur d'étendre leur propre syntaxe peuvent être utilisés pour effectuer un calcul complet de Turing pendant l'étape d'analyse-compilation.

Les langages de la famille Lisp , en particulier Common Lisp , sont probablement les exemples les plus évidents, mais aussi, de manière générale, les langages avec vérification de type statique qui n'ont pas toujours besoin d'être interrompus, comme le C ++ avec des modèles , Scala et Qi .

Antonio Valerio Miceli-Barone
la source
Mais la question porte sur des choses qui fonctionnent dans l'autre sens: il faut arriver au résultat non pas en réécrivant une séquence initiale de symboles selon les règles, mais le "résultat" du calcul défini par une grammaire dans cette question est une initiale symbole qui peut produire la séquence "d'entrée" selon les règles de la grammaire.
imz - Ivan Zakharyaschev
2
concunet(quote(jen),out)TM(jen)=out
Je conviens que la correspondance entre les grammaires Type0 et les MT est une réponse valable à la question (surtout si elle se limite au calcul des fonctions oui / non). La suggestion supplémentaire de modéliser une MT arbitraire avec une grammaire en introduisant une convention sur la façon de représenter les paires d'entrée-sortie me semble ne pas correspondre à l'intérêt voulu de la question d'origine: (à suivre)
imz - Ivan Zakharyaschev
Je le comprends comme une question pour exploiter exactement les cadres de grammaire existants et les analyseurs correspondants pour effectuer des calculs, c'est-à-dire que la forme autorisée de la traduction entre une fonction f et une grammaire ne peut être que: une entrée que j'ai analysée comme S signifie f ( I) = S.
imz - Ivan Zakharyaschev
1
Superficiellement, le langage de programmation Thue ne semble pas tomber dans ce type d'utilisation d'un framework de grammaire: bien qu'il ait des règles de réécriture comme une grammaire, le calcul d'un résultat à partir d'une entrée va dans le sens des règles, pas dans le sens inverse. direction, comme Rehno veut. (Mais peut-être ne s'agit-il que de changer le sens des flèches dans les productions: traduire une grammaire "calcul en tant qu'analyseur" au sens de ce Q en Thue ne pourrait être que changer les directions des règles, alors le programme Thue arrivera aux symboles de départ comme les résultats en effet, n'est-ce pas? ..)
imz - Ivan Zakharyaschev
6

Ma réponse n'est pas destinée à être formelle, précise et absolument pertinente. Je pense que la réponse de Marc Hamman est solide, mais votre question m'a fait penser à un sujet connexe.

Les grammaires peuvent être considérées comme des cas particuliers de systèmes déductifs: l'entrée est un jugement, et l'arbre d'analyse est une dérivation du jugement, ou la preuve que le jugement est valide selon les règles (grammaticales).

En ce sens, votre question pourrait être liée à l'approche d'une partie de la communauté de programmation logique / recherche de preuves (je pense à Dale Miller par exemple), qui est que la recherche de preuves a un contenu informatique, par opposition à la plus classique point de vue théorie des types / preuves où le calcul est la normalisation des preuves .

Remarque: en relisant ma réponse, je pense que l'idée que "la construction d'un arbre d'analyse est une recherche de preuves" est un peu farfelue ici. La recherche de preuve va plutôt dans l'autre sens: on part d'un jugement donné, assez complexe et, par l'utilisation répétée de règles d'inférence travaillant sur la structure de la preuve, on peut espérer atteindre des axiomes plus simples qui n'ont pas besoin d'être prouvés davantage. Il serait donc plus naturel de voir, en termes de grammaire, des jugements complexes comme des non-terminaux, des atomes comme des terminaux, et la recherche de preuves comme un problème de génération de mots, ou un test de non-vide.

gasche
la source
Remarques très intéressantes cependant. Mon cerveau est un peu trop fatigué pour donner une bonne réponse en ce moment, mais dans mon exemple, les branches de l'arbre représentent essentiellement des sous-calculs qui sont composés ensemble selon les règles d'analyse ...
Rehno Lindeque
6

De plus, pourrions-nous construire des programmes complets de Turing en spécifiant des grammaires…?

Je ne sais pas si j'ai bien compris votre question, mais si vous cherchez un langage de programmation basé sur une sorte de système de réécriture de chaînes, vous seriez probablement intéressé par Refal , qui est basé sur le formalisme de l' algorithme de Markov (un Turing- formalisme comlete qui est aussi un système de réécriture de chaînes de type grammatical).

Artem Pelenitsyn
la source
1
J'ai compris la question de la manière suivante: Rehno s'intéresse au processus d'analyse bootom-up (défini par une grammaire) à considérer comme un calcul du résultat. Le calcul doit construire le résultat à partir des parties allant dans le sens opposé aux règles de production de la grammaire. Les règles de réécriture de Refal (IIUC, de la même manière que le langage de programmation Thue mentionné ci-dessus) iraient dans l'autre sens (de l'entrée au résultat).
imz - Ivan Zakharyaschev
Maintenant que j'y pense cependant, les grammaires contextuelles ont plus d'un symbole sur le LHS des règles de production. Je pense donc qu'il n'y a pas de réelle différence pratique. Un analyseur pour un langage contextuel serait un système de réécriture de chaînes, peu importe comment vous le voyez, non?
Rehno Lindeque
@imz merci pour la clarification sur la question de Rehno. @Rehno «Un analyseur pour un langage contextuel serait un système de réécriture de chaînes, peu importe comment vous le regardez, n'est-ce pas?» - cela a probablement du sens, oui.
Artem Pelenitsyn
Mais les règles de réécriture de Refal sont-elles traitées de manière non déterministe? (Ou autrement: Refal effectuera-t-il un retour en arrière dans la recherche d'un chemin de réécriture fonctionnel?) Si nous voulons modéliser cette approche de "l'analyse en tant que calcul" avec des règles de réécriture dans le sens inverse, nous avons besoin de règles non déterministes; envisager une grammaire comme S -> A a; S -> B b; A -> 0; B -> 0. Si nous programmons cela en inversant les règles, nous devrons choisir différentes règles pour le traitement 0au moment de l'exécution afin d'évaluer "0a" ou "0b" à S.
imz - Ivan Zakharyaschev
6

(Juste quelques considérations triviales. Cela pourrait être un commentaire, mais trop long.)

En fait, ce que vous décrivez ressemble en fait à la vision très naturelle de ce qu'est une langue (dans la compréhension humaine du "langage", de son but) et de la manière dont une grammaire définit une langue.

Un langage comprend (une infinité de) formes syntaxiques correctes qui sont interprétées pour donner les valeurs sémantiques .

Si l'interprétation est calculable, les formes syntaxiques d'un langage peuvent être considérées comme des programmes qui calculent les valeurs sémantiques.

Si nous supposons qu'un langage est implémenté comme un dispositif fini, nous pouvons appeler cette représentation finie d'un langage une "grammaire". Selon cette compréhension, une grammaire se soucie de la syntaxe, mais aussi de la sémantique, c'est-à-dire comment calculer la valeur sémantique d'une expression entière à partir des valeurs de ses parties (les parties atomiques et leurs valeurs sont stockées dans un "lexique") .

Certaines théories du langage naturel ont une telle forme (la forme qui est cohérente avec les considérations ci-dessus; elle a déjà été mentionnée dans la réponse de @ gasche ici): un système déductif qui recherche une dérivation de l'entrée (couplé avec le calcul de la sémantique valeur, ou construction du terme de preuve; cf. correspondance Curry-Horward). Donc, si nous regardons des systèmes comme ça et les considérons comme des grammaires, votre question est triviale : ces systèmes sont exactement conçus pour effectuer des calculs de la manière que vous décrivez.

Fgje F(je)=SjeSg

(En fait, les vrais compilateurs pour les langages de programmation ressemblent plus à un système à la fois syntaxique et sémantique: ils transforment la forme syntaxique d'un programme en un exécutable, qui est la signification sémantique du programme, et non pas simplement en un symbole de départ de la grammaire.)

imz - Ivan Zakharyaschev
la source
4

Juste pour ajouter:

Un programme de logique pure a une lecture déclarative et une lecture procédurale. Ce rapport discute l'idée que ceux-ci peuvent être complétés par une lecture grammaticale, où les clauses sont considérées comme des règles de réécriture d'une grammaire. L'objectif est de montrer que ce point de vue facilite le transfert d'expertise de la programmation logique vers d'autres recherches sur les langages de programmation et vice versa. Quelques exemples d'un tel transfert sont discutés. D'autre part, la vue grammaticale présentée justifie certaines extensions ad hoc à la programmation logique pure et facilite le développement de fondements théoriques pour de telles extensions.

Une vue grammaticale de la programmation logique par Pierre Deransart et Jan Maluszynski.

Vag
la source
Apparemment, Prolog est né de grammaires d'attributs, c'est donc cette vue qui a commencé la programmation logique.
reinierpost
1

Qu'en est-il de quelque chose comme les nombres Peano:

S    -> int
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int

il reconnaîtra n'importe quelle chaîne (nombre) de ce formulaire:

0   // zero
#0  // one
##0 // two

et il doit renvoyer une structure imbriquée, la profondeur étant le nombre.

Mais ça commence à se compliquer quand on veut implémenter juste dire addition:

S    -> int
int  -> sum
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int
sum  -> int "+" int

Il est parfaitement logique en ce qu'il ne reconnaîtra que des fourmis bien formées comme ceci:

#####0 + ####0

Mais cette grammaire introduit une division dans l'arbre d'analyse chaque fois qu'il y a une somme, donc au lieu d'avoir un bel arbre à une branche, qui correspond directement à un nombre, nous avons la structure de l'expression, à quelques calculs de l'efficacité valeur. Donc, aucun calcul n'est fait, seulement la reconnaissance. Le problème n'est peut-être pas la grammaire mais l'analyseur. On peut plutôt utiliser autre chose, idk ... Un autre point qui me vient à l'esprit est l'adéquation du formalisme grammatical pour exprimer le calcul. Lorsque vous regardez l'axiome d'un Peano (en notation de type Haskell):

1) Nat = Zero
2) Nat = Succ Nat
3) Sum ( Succ X ) ( Y ) = Succ ( X + Y )
4) Sum Zero X = X

La troisième règle énonce explicitement une transformation. Quelqu'un pourrait-il imaginer porter la même quantité de sens dans une règle de grammaire sans contexte. Et si oui, comment!?

dader
la source