Qu'entend-on vraiment par sans contexte dans le terme de grammaire sans contexte?

J'étudie les compilateurs depuis un certain temps et je cherche ce que l'on entend par «contexte» en grammaire et ce que cela signifie pour la grammaire d'être «sans contexte», mais sans résultat.

Alors, quelqu'un peut-il m'aider?

terminology context-free formal-grammars Shady Atef
la source

Que voulez-vous dire par «vraiment»? Quelles explications avez-vous lues et que ne comprenez-vous pas? IIRC, chaque manuel à mi-chemin décent sur la question expliquera ce qu'ils signifient.

Raphael

Voici un exemple relatable. Considérez le mot «lire». C'est un seul mot qui a deux significations complètement différentes. L'un est le présent "lire", l'autre est le passé "je lis". Si vous avez vu le mot "lire" dans un morceau de texte, vous ne pouvez pas lever l'ambiguïté des deux significations qu'il représente, sans regarder le contexte. Ainsi, l'anglais est sensible au contexte, car vous ne pouvez pas analyser chaque jeton (mot) sans le considérer dans son contexte. Une grammaire contextuelle est une grammaire dans laquelle la signification de chaque jeton est déductible sans ambiguïté du seul jeton qui la représente.

Alexander - Rétablir Monica le

Réponses:

Le contexte peut être expliqué en ce qui concerne les règles de production autorisées pour différentes grammaires dans la hiérarchie Chomsky.

Si vous envisagez des grammaires sans contexte, leurs règles de production ont la forme suivante:

A \to α

$A \rightarrow \alpha$

Ainsi, vous pouvez observer que la partie gauche de ce type de règles est composée d'un seul symbole non terminal; ainsi, la substitution du symbole non terminal a lieu sans considérer son "contexte", c'est-à-dire les autres symboles qui l'entourent.

En revanche, si vous considérez les règles de production de grammaires contextuelles, elles ont la forme suivante:

β A γ \to β α γ

$\beta A \gamma \rightarrow \beta \alpha \gamma$

où est un non-terminal et , , sont des séquences de non-terminaux et de terminaux. $A$ $\alpha$ $\beta$ $\gamma$

Dans ce cas, le "contexte" (c'est-à-dire et ) du symbole non terminal à substituer influence l'effet de la substitution et il fait partie de la règle elle-même. $\beta$ $\gamma$

Vous pouvez trouver plus de détails dans cette réponse sur les mathématiques et dans cette réponse sur le génie logiciel.

PieCot
la source

Merci pour la réponse. Mais ce qui est étrange pour moi, c'est qu'une question similaire a été posée sur les mathématiques SE.

Shady Atef

Notez que et n'ont pas besoin de faire partie du résultat de la production. Ils auraient également pu être remplacés par une autre séquence comme on peut le voir dans la réponse de @David Richerby.

β

$\beta$

γ

$\gamma$

Frozn

@Frozn AFAIK celui donné ici est la définition standard selon la hiérarchie Chmosky. Bien sûr, il existe des grammaires plus puissantes que contextuelles qui permettent tout type de production, mais les grammaires contextuelles standard ne le permettent pas.

Bakuriu

@Frozn: Bakariu a raison, nous parlons ici de grammaires définies selon la hiérarchie de Chomsky, qui sont basées sur des conditions de plus en plus restrictives sur les règles de production. En particulier, les grammaires hors contexte sont des grammaires de type 2, tandis que les grammaires contextuelles sont de type 1. Cependant, les grammaires de type 0 ont des règles de production qui ne sont limitées par aucune restriction et sont donc appelées systèmes de réécriture sans restriction. Ici , vous trouverez une brève description de la hiérarchie avec quelques exemples Chomsky.

PieCot

@Bakuriu et PieCot Eh bien merci pour cela, je connaissais la hiérarchie Chomsky. Parfois, lorsque quelqu'un a introduit des grammaires monotones comme sensibles au contexte et avec le type 0 et le type 1 de la hiérarchie Chomsky, cela a abouti à la règle générale tant que.

β A γ \to δ

$\beta A\gamma \rightarrow \delta$

| β A γ | \leq | δ |

$|\beta A\gamma| \leq |\delta|$

Frozn

"Contexte" est un texte environnant. Les grammaires sans contexte sont sans contexte dans le sens où les règles ressemblent à , plutôt qu'à . Le côté gauche d'une règle est toujours un symbole non terminal unique. Autrement dit, les règles pour développer un symbole non terminal ne dépendent pas du texte qui apparaît autour de ce symbole (son contexte), mais dépendent uniquement du symbole lui-même. Par exemple, dans la grammaire d'un langage de programmation, le terme s'étend au même type d'expression que vous écriviez une affectation (par exemple, ), en passant des arguments à une fonction (par exemple ) ou en renvoyant une valeur à partir d'une fonction (par exemple, ). $A\to\text{things}$ $\text{stuff}\,A\,\text{more-stuff}\to\text{things}$ $\mathrm{Expr}$ x:=y+zf(y+z)return y+z

David Richerby
la source

De manière générale, même les langues normales peuvent avoir des dépendances de contexte, ce qui signifie que vous pouvez déterminer - dans une certaine mesure - de quelle manière les symboles peuvent apparaître à proximité d'autres symboles dans une chaîne qui appartient à cette langue.

Ce qui est spécifique aux grammaires sans contexte, c'est que lorsqu'il existe plusieurs façons de remplacer un symbole non terminal, en appliquant différentes règles avec le même non terminal sur le côté droit, le choix de la règle à appliquer ne dépend jamais de ce se passe autour de ce symbole pendant le processus de dérivation.

Vous pouvez les considérer comme des langues de dérivation sans contexte, des langues sans contexte pour faire court.

André Souza Lemos
la source