Grammaire sans contexte - Context-free grammar

Extrait simplifié de la grammaire formelle du langage de programmation C (à gauche), et dérivation d'un morceau de code C (à droite) à partir du symbole non terminal . Les symboles non terminaux et terminaux sont respectivement affichés en bleu et en rouge.${\ displaystyle \ langle {\ text {Stmt}} \ rangle}$

Dans la théorie du langage formel , une grammaire sans contexte ( CFG ) est une grammaire formelle dans laquelle chaque règle de production est de la forme

${\ displaystyle A \ \ à \ \ alpha}$

où est un seul symbole non terminal , et est une chaîne de terminaux et / ou non terminaux ( peut être vide). Une grammaire formelle est considérée comme «sans contexte» lorsque ses règles de production peuvent être appliquées quel que soit le contexte d'un non terminal. Quels que soient les symboles qui l'entourent, le seul non-terminal du côté gauche peut toujours être remplacé par le côté droit. C'est ce qui le distingue d'une grammaire contextuelle . ${\ displaystyle A}$ ${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$

Une grammaire formelle est essentiellement un ensemble de règles de production qui décrivent toutes les chaînes possibles dans un langage formel donné. Les règles de production sont de simples remplacements. Par exemple, la première règle de l'image,

${\ displaystyle \ langle {\ text {Stmt}} \ rangle \ to \ langle {\ text {Id}} \ rangle = \ langle {\ text {Expr}} \ rangle;}$

remplace par . Il peut y avoir plusieurs règles de remplacement pour un symbole non terminal donné. Le langage généré par une grammaire est l'ensemble de toutes les chaînes de symboles terminaux qui peuvent être dérivées, par des applications de règles répétées, d'un symbole non terminal particulier ("symbole de départ"). Les symboles non terminaux sont utilisés pendant le processus de dérivation, mais peuvent ne pas apparaître dans sa chaîne de résultat final. ${\ displaystyle \ langle {\ text {Stmt}} \ rangle}$${\ displaystyle \ langle {\ text {Id}} \ rangle = \ langle {\ text {Expr}} \ rangle;}$

Les langages générés par des grammaires sans contexte sont appelés langages sans contexte (CFL). Différentes grammaires sans contexte peuvent générer le même langage sans contexte. Il est important de distinguer les propriétés du langage (propriétés intrinsèques) des propriétés d'une grammaire particulière (propriétés extrinsèques). La question de l' égalité des langues (est-ce que deux grammaires données sans contexte génèrent le même langage?) Est indécidable .

Les grammaires sans contexte surgissent en linguistique où elles sont utilisées pour décrire la structure des phrases et des mots dans une langue naturelle , et elles ont en fait été inventées par le linguiste Noam Chomsky à cette fin. En revanche, en informatique , à mesure que l'utilisation de concepts définis de manière récursive augmentait, ils étaient de plus en plus utilisés. Dans une première application, les grammaires sont utilisées pour décrire la structure des langages de programmation . Dans une application plus récente, ils sont utilisés dans une partie essentielle du langage XML ( Extensible Markup Language ) appelé la définition de type de document .

En linguistique , certains auteurs utilisent le terme grammaire de structure de phrase pour désigner des grammaires sans contexte, où les grammaires de structure de phrase sont distinctes des grammaires de dépendance . En informatique , une notation populaire pour les grammaires sans contexte est la forme Backus – Naur , ou BNF .

Contexte

Depuis l'époque de Pāṇini , au moins, les linguistes ont décrit les grammaires des langues en fonction de leur structure en blocs, et décrit comment les phrases sont construites de manière récursive à partir de phrases plus petites, et éventuellement de mots ou d'éléments de mots individuels. Une propriété essentielle de ces structures de blocs est que les unités logiques ne se chevauchent jamais. Par exemple, la phrase:

John, dont la voiture bleue était dans le garage, se dirigea vers l'épicerie.

peut être logiquement entre parenthèses (avec les métasymboles logiques [] ) comme suit:

[ John [ , [ dont [ voiture bleue ]] [ était [ dans [ le garage ]]] , ]] [ marché [ à [ la [ épicerie ]]]] .

Une grammaire sans contexte fournit un mécanisme simple et mathématiquement précis pour décrire les méthodes par lesquelles des phrases dans un langage naturel sont construites à partir de blocs plus petits, capturant la «structure de bloc» des phrases de manière naturelle. Sa simplicité rend le formalisme propice à une étude mathématique rigoureuse. Les caractéristiques importantes de la syntaxe du langage naturel telles que l' accord et la référence ne font pas partie de la grammaire sans contexte, mais la structure récursive de base des phrases, la manière dont les clauses s'emboîtent dans d'autres clauses et la manière dont les listes d'adjectifs et d'adverbes sont avalé par les noms et les verbes, est décrit exactement.

Les grammaires sans contexte sont une forme particulière de systèmes Semi-Thue qui, dans leur forme générale, remontent aux travaux d' Axel Thue .

Le formalisme des grammaires sans contexte a été développé au milieu des années 1950 par Noam Chomsky , ainsi que leur classification en tant que type spécial de grammaire formelle (qu'il a appelé grammaires à structure de phrase ). Ce que Chomsky a appelé une grammaire de structure de phrase est également connu maintenant sous le nom de grammaire de circonscription, dans laquelle les grammaires de circonscription contrastent avec les grammaires de dépendance . Dans le cadre de grammaire générative de Chomsky , la syntaxe du langage naturel était décrite par des règles sans contexte associées à des règles de transformation.

La structure par blocs a été introduite dans les langages de programmation informatique par le projet Algol (1957–1960), qui, en conséquence, comportait également une grammaire sans contexte pour décrire la syntaxe Algol résultante. Cela est devenu une caractéristique standard des langages informatiques, et la notation des grammaires utilisées dans les descriptions concrètes des langages informatiques est devenue la forme Backus – Naur , après deux membres du comité de conception du langage Algol. L'aspect «structure de bloc» que capturent les grammaires sans contexte est si fondamental en grammaire que les termes syntaxe et grammaire sont souvent identifiés avec des règles de grammaire sans contexte, en particulier en informatique. Les contraintes formelles non capturées par la grammaire sont alors considérées comme faisant partie de la «sémantique» du langage.

Les grammaires sans contexte sont suffisamment simples pour permettre la construction d' algorithmes d'analyse efficaces qui, pour une chaîne donnée, déterminent si et comment elle peut être générée à partir de la grammaire. Un analyseur Earley est un exemple d'un tel algorithme, tandis que les analyseurs LR et LL largement utilisés sont des algorithmes plus simples qui ne traitent que des sous-ensembles plus restrictifs de grammaires sans contexte.

Définitions formelles

Une grammaire G sans contexte est définie par le 4- tuple , où ${\ displaystyle G = (V, \ Sigma, R, S)}$

1. V est un ensemble fini; chaque élément est appelé un caractère non terminal ou une variable . Chaque variable représente un type différent de phrase ou de clause dans la phrase. Les variables sont également parfois appelées catégories syntaxiques. Chaque variable définit une sous-langue de la langue définie par G .${\ displaystyle v \ in V}$
2. Σ est un ensemble fini de terminaux s, disjoints de V , qui constituent le contenu réel de la phrase. L'ensemble des terminaux est l'alphabet de la langue définie par la grammaire G .
3. R est une relation finie de V à , où l'astérisque représente l' opération d' étoile de Kleene . Les membres de R sont appelés les règles (de réécriture) ou de production de la grammaire. (également souvent symbolisé par un P )${\ displaystyle (V \ cup \ Sigma) ^ {*}}$
4. S est la variable de début (ou symbole de début), utilisée pour représenter la phrase entière (ou le programme). Il doit être un élément de V .

Notation des règles de production

Une règle de production dans R est formalisée mathématiquement comme une paire , où est un non terminal et est une chaîne de variables et / ou de terminaux; plutôt que d' utiliser la paire ordonnée notation, les règles de production sont généralement écrites à l' aide d' un opérateur de flèche avec comme côté gauche et β comme à droite: . ${\ displaystyle (\ alpha, \ beta) \ in R}$${\ displaystyle \ alpha \ dans V}$${\ displaystyle \ beta \ in (V \ cup \ Sigma) ^ {*}}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha \ rightarrow \ beta}$

Il est permis que β soit la chaîne vide , et dans ce cas, il est habituel de le désigner par ε. Le formulaire est appelé une ε -production. ${\ displaystyle \ alpha \ rightarrow \ varepsilon}$

Il est courant de lister tous les côtés droit pour le même côté gauche sur la même ligne, en utilisant | (le symbole du tuyau ) pour les séparer. Rules et peut donc être écrit comme . Dans ce cas, et est appelé la première et la deuxième alternative, respectivement. ${\ displaystyle \ alpha \ rightarrow \ beta _ {1}}$${\ displaystyle \ alpha \ rightarrow \ beta _ {2}}$${\ displaystyle \ alpha \ rightarrow \ beta _ {1} \ mid \ beta _ {2}}$${\ displaystyle \ beta _ {1}}$${\ displaystyle \ beta _ {2}}$

Application de la règle

Pour toutes les chaînes , nous disons que u donne directement v , écrit comme , si avec et tel que et . Ainsi, v est le résultat de l'application de la règle à u . ${\ displaystyle u, v \ in (V \ cup \ Sigma) ^ {*}}$${\ displaystyle u \ Rightarrow v \,}$${\ displaystyle \ existe (\ alpha, \ beta) \ in R}$${\ displaystyle \ alpha \ dans V}$${\ displaystyle u_ {1}, u_ {2} \ in (V \ cup \ Sigma) ^ {*}}$${\ displaystyle u \, = u_ {1} \ alpha u_ {2}}$${\ displaystyle v \, = u_ {1} \ beta u_ {2}}$${\ displaystyle (\ alpha, \ beta)}$

Application de règles répétitives

Pour toutes les chaînes, nous disons que u donne v ou v est dérivé de u s'il existe un entier positif k et des chaînes telles que . Cette relation est indiquée , ou dans certains manuels. Si , la relation tient. En d'autres termes, et sont la fermeture transitive réflexive (permettant à une chaîne de se céder) et la fermeture transitive (nécessitant au moins une étape) de , respectivement. ${\ displaystyle u, v \ in (V \ cup \ Sigma) ^ {*},}$ ${\ displaystyle u_ {1}, \ cdots, u_ {k} \ in (V \ cup \ Sigma) ^ {*}}$${\ displaystyle u = u_ {1} \ Rightarrow u_ {2} \ Rightarrow \ cdots \ Rightarrow u_ {k} = v}$${\ displaystyle u {\ stackrel {*} {\ Rightarrow}} v}$${\ displaystyle u \ Rightarrow \ Rightarrow v}$${\ displaystyle k \ geq 2}$${\ displaystyle u {\ stackrel {+} {\ Rightarrow}} v}$${\ displaystyle ({\ stackrel {*} {\ Rightarrow}})}$${\ displaystyle ({\ stackrel {+} {\ Rightarrow}})}$${\ displaystyle (\ Rightarrow)}$

Langage sans contexte

La langue d'une grammaire est l'ensemble ${\ displaystyle G = (V, \ Sigma, R, S)}$

${\ displaystyle L (G) = \ {w \ in \ Sigma ^ {*}: S {\ stackrel {*} {\ Rightarrow}} w \}}$

de toutes les chaînes de symboles terminaux dérivables du symbole de début.

Un langage L est dit être un langage sans contexte (CFL), s'il existe un CFG G , tel que . ${\ Displaystyle L \, = \, L (G)}$

Les automates pushdown non déterministes reconnaissent exactement les langages sans contexte.

Exemples

Mots concaténés avec leur revers

La grammaire , avec des productions ${\ displaystyle G = (\ {S \}, \ {a, b \}, P, S)}$

S → aSa ,

S → bSb ,

S → ε ,

est sans contexte. Ce n'est pas approprié car il comprend une ε-production. Une dérivation typique de cette grammaire est

S → aSa → aaSaa → aabSbaa → aabbaa .

Cela le montre clairement . Le langage est sans contexte, cependant, il peut être prouvé qu'il n'est pas régulier . ${\ displaystyle L (G) = \ {ww ^ {R}: w \ in \ {a, b \} ^ {*} \}}$

Si les productions

S → a ,

S → b ,

sont ajoutés, une grammaire sans contexte pour l'ensemble de tous les palindromes sur l'alphabet { a , b } est obtenue.

Des parenthèses bien formées

L'exemple canonique d'une grammaire sans contexte est la correspondance entre parenthèses, qui est représentative du cas général. Il existe deux symboles terminaux "(" et ")" et un symbole non terminal S. Les règles de production sont

S → SS ,

S → ( S ) ,

S → ()

La première règle permet au symbole S de se multiplier; la deuxième règle permet au symbole S d'être entouré de parenthèses correspondantes; et la troisième règle met fin à la récursivité.

Parenthèses imbriquées et crochets bien formés

Un deuxième exemple canonique est deux types différents de parenthèses imbriquées correspondantes, décrites par les productions:

S → SS

S → ()

S → ( S )

S → []

S → [ S ]

avec les symboles terminaux [] () et S.

La séquence suivante peut être dérivée dans cette grammaire:

([[[() () [] []]] ([])])

Paires assorties

Dans une grammaire sans contexte, nous pouvons associer des caractères comme nous le faisons avec des crochets . L'exemple le plus simple:

S → aSb

S → ab

Cette grammaire génère la langue , qui n'est pas régulière (selon le lemme de pompage pour les langues régulières ). ${\ displaystyle \ {a ^ {n} b ^ {n}: n \ geq 1 \}}$

Le caractère spécial ε représente la chaîne vide. En changeant la grammaire ci-dessus en

S → aSb

S → ε

nous obtenons à la place une grammaire générant la langue . Cela diffère uniquement en ce qu'il contient la chaîne vide, contrairement à la grammaire d'origine. ${\ displaystyle \ {a ^ {n} b ^ {n}: n \ geq 0 \}}$

Nombre distinct de a et b

Une grammaire sans contexte pour la langue composée de toutes les chaînes sur {a, b} contenant un nombre inégal de a et de b:

S → T | U

T → VaT | VaV | TaV

U → VbU | VbV | UbV

V → aVbV | bVaV | ε

Ici, le T non terminal peut générer toutes les chaînes avec le même nombre de a que b, le U non terminal génère toutes les chaînes avec plus de a que de b et le V non terminal génère toutes les chaînes avec moins de a que de b. Omettre la troisième alternative dans la règle pour U et V ne restreint pas la langue de la grammaire.

Deuxième bloc de b de taille double

Un autre exemple d'une langue non régulière est . Il est sans contexte car il peut être généré par la grammaire sans contexte suivante: ${\ displaystyle \ {{\ text {b}} ^ {n} {\ text {a}} ^ {m} {\ text {b}} ^ {2n}: n \ geq 0, m \ geq 0 \} }$

S → bSbb | UNE

A → aA | ε

Formules logiques du premier ordre

Les règles de formation des termes et formules de la logique formelle correspondent à la définition de la grammaire sans contexte, sauf que l'ensemble de symboles peut être infini et qu'il peut y avoir plus d'un symbole de début.

Exemples de langages qui ne sont pas sans contexte

Contrairement aux parenthèses imbriquées et crochets bien formées de la section précédente, il n'y a pas de grammaire sans contexte pour générer toutes les séquences de deux types différents de parenthèses, chacune équilibrée séparément sans tenir compte de l'autre , où les deux types n'ont pas besoin de s'imbriquer dans l'un un autre, par exemple:

[(])

ou

[[[[(((]]]])))) (([)) (([)) ([) (]) (]) (])

Le fait que ce langage ne soit pas sans contexte peut être prouvé en utilisant le lemme de pompage pour les langages sans contexte et une preuve par contradiction, en observant que tous les mots de la forme devraient appartenir à la langue. Cette langue appartient à la place à une classe plus générale et peut être décrite par une grammaire conjonctive , qui à son tour inclut également d'autres langues non sans contexte, telles que la langue de tous les mots de la forme . ${\ displaystyle {(} ^ {n} {[} ^ {n} {)} ^ {n} {]} ^ {n}}$${\ displaystyle {\ text {a}} ^ {n} {\ text {b}} ^ {n} {\ text {c}} ^ {n}}$

Grammaires régulières

Toutes les grammaires régulières sont sans contexte, mais toutes les grammaires sans contexte ne sont pas régulières. La grammaire sans contexte suivante, cependant, est également régulière.

S → a

S → aS

S → bS

Les terminaux sont ici un et b , alors que le seul est non - terminal S . Le langage décrit est toutes les chaînes non vides de s et s qui se terminent par . ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a}$

Cette grammaire est régulière : aucune règle n'a plus d'un non-terminal dans son côté droit, et chacun de ces non-terminaux est à la même extrémité du côté droit.

Toute grammaire régulière correspond directement à un automate fini non déterministe , nous savons donc qu'il s'agit d'un langage régulier .

En utilisant des symboles de tube, la grammaire ci-dessus peut être décrite plus brièvement comme suit:

S → a | aS | bS

Dérivations et arbres de syntaxe

Une dérivation d'une chaîne pour une grammaire est une séquence d'applications de règles de grammaire qui transforment le symbole de début en chaîne. Une dérivation prouve que la chaîne appartient au langage de la grammaire.

Une dérivation est entièrement déterminée en donnant, pour chaque étape:

• la règle appliquée à cette étape
• l'occurrence de son côté gauche auquel il est appliqué

Pour plus de clarté, la chaîne intermédiaire est également généralement donnée.

Par exemple, avec la grammaire:

1. S → S + S
2. S → 1
3. S → a

la corde

1 + 1 + a

peut être dérivée du symbole de départ S avec la dérivation suivante:

S

→ S + S (par règle 1. sur S )

→ S + S + S (par règle 1. sur le deuxième S )

→ 1 + S + S (par règle 2. sur le premier S )

→ 1 + 1 + S (par règle 2. sur le deuxième S )

→ 1 + 1 + a (par règle 3. sur le troisième S )

Souvent, une stratégie est suivie qui choisit de manière déterministe le prochain non terminal à réécrire:

• dans une dérivation la plus à gauche , c'est toujours le non-terminal le plus à gauche;
• dans une dérivation la plus à droite , c'est toujours le non-terminal le plus à droite.

Compte tenu d'une telle stratégie, une dérivation est complètement déterminée par la séquence de règles appliquées. Par exemple, une dérivation la plus à gauche de la même chaîne est

S

→ S + S (par la règle 1 sur le S le plus à gauche )

→ 1 + S (par la règle 2 sur le S le plus à gauche )

→ 1 + S + S (par la règle 1 sur le S le plus à gauche )

→ 1 + 1 + S (par la règle 2 sur le S le plus à gauche )

→ 1 + 1 + a (par la règle 3 sur le S le plus à gauche ),

qui peut être résumé comme

règle 1

règle 2

règle 1

règle 2

règle 3.

Une dérivation la plus à droite est:

S

→ S + S (par règle 1 sur le S le plus à droite )

→ S + S + S (par la règle 1 sur le S le plus à droite )

→ S + S + a (par la règle 3 sur le S le plus à droite )

→ S + 1 + a (par la règle 2 sur le S le plus à droite )

→ 1 + 1 + a (par règle 2 sur le S le plus à droite ),

qui peut être résumé comme

règle 1

règle 1

règle 3

règle 2

règle 2.

La distinction entre la dérivation la plus à gauche et la dérivation la plus à droite est importante car dans la plupart des analyseurs, la transformation de l'entrée est définie en donnant un morceau de code pour chaque règle de grammaire qui est exécutée chaque fois que la règle est appliquée. Par conséquent, il est important de savoir si l'analyseur détermine une dérivation la plus à gauche ou la plus à droite car cela détermine l'ordre dans lequel les morceaux de code seront exécutés. Voir pour un exemple d' analyseurs LL et d' analyseurs LR .

Une dérivation impose également dans un certain sens une structure hiérarchique à la chaîne dérivée. Par exemple, si la chaîne "1 + 1 + a" est dérivée selon la dérivation la plus à gauche décrite ci-dessus, la structure de la chaîne serait:

{{1} _S + {{1} _S + { a } _S } _S } _S

où {...} _S indique une sous - chaîne reconnue comme appartenant à S . Cette hiérarchie peut également être vue comme un arbre:

Cet arbre est appelé un arbre d'analyse ou «arbre de syntaxe concret» de la chaîne, par opposition à l' arbre de syntaxe abstraite . Dans ce cas, les dérivations présentées la plus à gauche et la plus à droite définissent le même arbre d'analyse; cependant, il existe une autre dérivation la plus à droite de la même chaîne

S

→ S + S (par règle 1 sur le S le plus à droite )

→ S + a (par la règle 3 sur le S le plus à droite )

→ S + S + a (par la règle 1 sur le S le plus à droite )

→ S + 1 + a (par la règle 2 sur le S le plus à droite )

→ 1 + 1 + a (par règle 2 sur le S le plus à droite ),

qui définit une chaîne avec une structure différente

{{{1} _S + { a } _S } _S + { a } _S } _S

et un arbre d'analyse différent:

Notez cependant que les deux arbres d'analyse peuvent être obtenus par les dérivations les plus à gauche et à droite. Par exemple, le dernier arbre peut être obtenu avec la dérivation la plus à gauche comme suit:

S

→ S + S (par la règle 1 sur le S le plus à gauche )

→ S + S + S (par la règle 1 sur le S le plus à gauche )

→ 1 + S + S (par la règle 2 sur le S le plus à gauche )

→ 1 + 1 + S (par la règle 2 sur le S le plus à gauche )

→ 1 + 1 + a (par la règle 3 sur le S le plus à gauche ),

Si une chaîne dans la langue de la grammaire a plus d'un arbre d'analyse, alors la grammaire est considérée comme une grammaire ambiguë . Ces grammaires sont généralement difficiles à analyser car l'analyseur ne peut pas toujours décider quelle règle de grammaire il doit appliquer. Habituellement, l'ambiguïté est une caractéristique de la grammaire, pas de la langue, et une grammaire sans ambiguïté peut être trouvée qui génère le même langage sans contexte. Cependant, il existe certaines langues qui ne peuvent être générées que par des grammaires ambiguës; ces langues sont appelées langues intrinsèquement ambiguës .

Exemple: expressions algébriques

Voici une grammaire sans contexte pour les expressions algébriques infixes syntaxiquement correctes dans les variables x, y et z:

1. S → x
2. S → y
3. S → z
4. S → S + S
5. S → S - S
6. S → S * S
7. S → S / S
8. S → ( S )

Cette grammaire peut, par exemple, générer la chaîne

( x + y ) * x - z * y / ( x + x )

comme suit:

S

→ S - S (par règle 5)

→ S * S - S (par la règle 6, appliquée au S le plus à gauche )

→ S * S - S / S (par la règle 7, appliquée au S le plus à droite )

→ ( S ) * S - S / S (par la règle 8, appliquée au S le plus à gauche )

→ ( S ) * S - S / ( S ) (par la règle 8, appliquée au S le plus à droite )

→ ( S + S ) * S - S / ( S ) (par la règle 4, appliquée au S le plus à gauche )

→ ( S + S ) * S - S * S / ( S ) (par la règle 6, appliquée au quatrième S )

→ ( S + S ) * S - S * S / ( S + S ) (par la règle 4, appliquée au S le plus à droite )

→ ( x + S ) * S - S * S / ( S + S ) (etc.)

→ ( x + y ) * S - S * S / ( S + S )

→ ( x + y ) * x - S * S / ( S + S )

→ ( x + y ) * x - z * S / ( S + S )

→ ( x + y ) * x - z * y / ( S + S )

→ ( x + y ) * x - z * y / ( x + S )

→ ( x + y ) * x - z * y / ( x + x )

Notez que de nombreux choix ont été faits en cours quant à la prochaine réécriture. Ces choix semblent assez arbitraires. En fait, ils le sont, dans le sens où la chaîne finalement générée est toujours la même. Par exemple, les deuxième et troisième réécritures

→ S * S - S (par la règle 6, appliquée au S le plus à gauche )

→ S * S - S / S (par la règle 7, appliquée au S le plus à droite )

pourrait être fait dans l'ordre inverse:

→ S - S / S (par la règle 7, appliquée au S le plus à droite )

→ S * S - S / S (par la règle 6, appliquée au S le plus à gauche )

De plus, de nombreux choix ont été faits sur la règle à appliquer à chaque S sélectionné . Changer les choix effectués et pas seulement l'ordre dans lequel ils ont été faits affecte généralement la chaîne de terminaison qui sort à la fin.

Regardons cela plus en détail. Considérez l' arbre d'analyse de cette dérivation:

En commençant par le haut, étape par étape, un S dans l'arborescence est développé, jusqu'à ce qu'il ne reste plus de S non développés (non terminaux). Choisir un ordre d'expansion différent produira une dérivation différente, mais le même arbre d'analyse. L'arbre d'analyse ne changera que si nous choisissons une règle différente à appliquer à une certaine position dans l'arborescence.

Mais un arbre d'analyse différent peut-il toujours produire la même chaîne de terminal, qui est ( x + y ) * x - z * y / ( x + x ) dans ce cas? Oui, pour cette grammaire particulière, c'est possible. Les grammaires avec cette propriété sont appelées ambiguës .

Par exemple, x + y * z peut être produit avec ces deux arbres d'analyse différents:

Cependant, la langue décrite par cette grammaire n'est pas intrinsèquement ambiguë: une grammaire alternative et non ambiguë peut être donnée pour la langue, par exemple:

T → x

T → y

T → z

S → S + T

S → S - T

S → S * T

S → S / T

T → ( S )

S → T ,

en choisissant à nouveau S comme symbole de départ. Cette grammaire alternative produira x + y * z avec un arbre d'analyse similaire à celui de gauche ci-dessus, c'est-à-dire en supposant implicitement l'association ( x + y ) * z , qui ne suit pas l' ordre standard des opérations . Des grammaires plus élaborées, sans ambiguïté et sans contexte peuvent être construites pour produire des arbres d'analyse qui obéissent à toutes les règles de priorité d'opérateur et d'associativité souhaitées .

Formes normales

Toute grammaire sans contexte sans ε-production a une grammaire équivalente dans la forme normale de Chomsky et une grammaire dans la forme normale de Greibach . «Equivalent» signifie ici que les deux grammaires génèrent la même langue.

La forme particulièrement simple de règles de production dans les grammaires de forme normale de Chomsky a des implications à la fois théoriques et pratiques. Par exemple, étant donné une grammaire sans contexte, on peut utiliser la forme normale de Chomsky pour construire un algorithme en temps polynomial qui décide si une chaîne donnée est dans le langage représenté par cette grammaire ou non ( l'algorithme CYK ).

Propriétés de fermeture

Les langages sans contexte sont fermés sous les différentes opérations, c'est-à-dire que si les langages K et L sont sans contexte, le résultat des opérations suivantes l'est aussi:

• union K ∪ L ; concaténation K ∘ L ; Étoile Kleene L ^*
• substitution (en particulier homomorphisme )
• homomorphisme inverse
• intersection avec une langue régulière

Ils ne sont pas fermés par intersection générale (donc ni par complémentation ) et par différence d'ensemble.

Problèmes décidables

Voici quelques problèmes résolus concernant les grammaires sans contexte.

Analyse

Le problème d'analyse, qui vérifie si un mot donné appartient au langage donné par une grammaire sans contexte, est décidable, en utilisant l'un des algorithmes d'analyse à usage général:

• Algorithme CYK (pour les grammaires sous forme normale de Chomsky )
• Earley parser
• Analyseur GLR
• Analyseur LL (uniquement pour la sous-classe appropriée des grammaires LL ( k ))

L'analyse sans contexte des grammaires de forme normale de Chomsky a été montrée par Leslie G. Valiant comme étant réductible à la multiplication de matrice booléenne , héritant ainsi de sa limite supérieure de complexité de O ( n ^2,3728639 ). Inversement, Lillian Lee a montré que la multiplication de matrice booléenne O ( n ^{3 − ε} ) est réductible à l' analyse syntaxique de CFG O ( n ^3−3ε ), établissant ainsi une sorte de borne inférieure pour cette dernière.

Accessibilité, productivité, nullité

Un symbole non terminal est appelé productif , ou générateur , s'il existe une dérivation pour une chaîne de symboles terminaux. est appelé accessible s'il existe une dérivation pour certaines chaînes de symboles non terminaux et terminaux à partir du symbole de début. est appelé inutile s'il est inaccessible ou improductif. est appelé nullable s'il y a une dérivation . Une règle est appelée une ε-production . Une dérivation est appelée un cycle . ${\ displaystyle X}$${\ displaystyle X {\ stackrel {*} {\ Rightarrow}} w}$${\ displaystyle w}$${\ displaystyle X}$${\ displaystyle S {\ stackrel {*} {\ Rightarrow}} \ alpha X \ beta}$${\ displaystyle \ alpha, \ beta}$${\ displaystyle X}$${\ displaystyle X}$${\ displaystyle X {\ stackrel {*} {\ Rightarrow}} \ varepsilon}$${\ displaystyle X \ rightarrow \ varepsilon}$${\ displaystyle X {\ stackrel {+} {\ Rightarrow}} X}$

Les algorithmes sont connus pour éliminer d'une grammaire donnée, sans changer sa langue générée,

• symboles improductifs,
• symboles inaccessibles,
• ε-productions, à une exception près, et
• cycles.

En particulier, une alternative contenant un symbole non terminal inutile peut être supprimée du côté droit d'une règle. De telles règles et alternatives sont dites inutiles .

Dans l'exemple de grammaire représenté, le D non terminal est inaccessible et E est improductif, tandis que C → C provoque un cycle. Par conséquent, en omettant les trois dernières règles ne change pas la langue générée par la grammaire, ni n'omettant les alternatives « | Cc | Ee » du côté droit de la règle de S .

Une grammaire sans contexte est dite correcte si elle ne comporte ni symboles inutiles, ni ε-productions, ni cycles. En combinant les algorithmes ci-dessus, toute grammaire sans contexte ne générant pas ε peut être transformée en une grammaire propre faiblement équivalente .

Contrôles de régularité et LL ( k )

Il est possible de décider si une grammaire donnée est une grammaire régulière , ainsi que si c'est une grammaire LL ( k ) pour un k ≥0 donné . Si k n'est pas donné, ce dernier problème est indécidable.

Étant donné un langage sans contexte , il n'est pas possible de décider s'il est régulier, ni s'il s'agit d'un langage LL ( k ) pour un k donné .

Vide et finitude

Il existe des algorithmes pour décider si une langue d'une langue sans contexte donnée est vide, ainsi que si elle est finie.

Problèmes indécidables

Certaines questions qui sont indécidables pour des classes plus larges de grammaires deviennent décidables pour des grammaires sans contexte; par exemple, le problème de la vacuité (si la grammaire génère des chaînes terminales du tout), est indécidable pour les grammaires contextuelles , mais décidable pour les grammaires sans contexte.

Cependant, de nombreux problèmes sont indécidables même pour les grammaires sans contexte. Des exemples sont:

Universalité

Étant donné un CFG, génère-t-il la langue de toutes les chaînes sur l'alphabet des symboles terminaux utilisés dans ses règles?

Une réduction de ce problème peut être démontrée à partir du problème indécidable bien connu de déterminer si une machine de Turing accepte une entrée particulière (le problème d'arrêt ). La réduction utilise le concept d'un historique de calcul , une chaîne décrivant un calcul complet d'une machine de Turing . Un CFG peut être construit qui génère toutes les chaînes qui n'acceptent pas les historiques de calcul pour une machine de Turing particulière sur une entrée particulière, et donc il n'acceptera toutes les chaînes que si la machine n'accepte pas cette entrée.

Égalité linguistique

Étant donné deux CFG, génèrent-ils le même langage?

L'indécidabilité de ce problème est une conséquence directe du précédent: il est même impossible de décider si un CFG est équivalent au CFG trivial définissant le langage de toutes les chaînes.

Inclusion de la langue

Étant donné deux CFG, le premier peut-il générer toutes les chaînes que le second peut générer?

Si ce problème était décidable, alors l'égalité de langage pourrait également être décidée: deux CFG G1 et G2 génèrent le même langage si L (G1) est un sous-ensemble de L (G2) et L (G2) est un sous-ensemble de L (G1).

Être à un niveau inférieur ou supérieur de la hiérarchie Chomsky

En utilisant le théorème de Greibach , on peut montrer que les deux problèmes suivants sont indécidables:

• Étant donné une grammaire contextuelle , décrit-elle un langage sans contexte?
• Étant donné une grammaire sans contexte, décrit-elle une langue régulière ?

Ambiguïté grammaticale

Étant donné un CFG, est-ce ambigu ?

L'indécidabilité de ce problème découle du fait que si un algorithme pour déterminer l'ambiguïté existait, le problème de correspondance post pourrait être résolu, ce qui est connu pour être indécidable.

Disjonction linguistique

Étant donné deux CFG, y a-t-il une chaîne dérivable des deux grammaires?

Si ce problème était décidable, le problème indécidable de la correspondance Post pourrait également être résolu: étant donné les chaînes sur un alphabet , laissez la grammaire se composer de la règle ${\ displaystyle \ alpha _ {1}, \ ldots, \ alpha _ {N}, \ beta _ {1}, \ ldots, \ beta _ {N}}$${\ displaystyle \ {a_ {1}, \ ldots, a_ {k} \}}$${\ displaystyle G_ {1}}$

${\ displaystyle S \ to \ alpha _ {1} S \ beta _ {1} ^ {rev} | \ cdots | \ alpha _ {N} S \ beta _ {N} ^ {rev} | b}$;

où désigne la chaîne inversée et n'apparaît pas parmi les ; et laissez la grammaire se composer de la règle ${\ displaystyle \ beta _ {i} ^ {rev}}$${\ displaystyle \ beta _ {i}}$${\ displaystyle b}$${\ displaystyle a_ {i}}$${\ displaystyle G_ {2}}$

${\ displaystyle T \ à a_ {1} Ta_ {1} | \ cdots | a_ {k} Ta_ {k} | b}$;

Ensuite, le problème Post donné par a une solution si et seulement si et partage une chaîne dérivable. ${\ displaystyle \ alpha _ {1}, \ ldots, \ alpha _ {N}, \ beta _ {1}, \ ldots, \ beta _ {N}}$${\ displaystyle L (G_ {1})}$${\ displaystyle L (G_ {2})}$

Extensions

Une manière évidente d'étendre le formalisme de grammaire sans contexte est de permettre aux non-terminaux d'avoir des arguments dont les valeurs sont transmises dans les règles. Cela permet d' exprimer de manière naturelle les caractéristiques du langage naturel telles que l' accord et la référence , et les analogues du langage de programmation tels que l'utilisation et la définition correctes des identificateurs. Par exemple, nous pouvons maintenant facilement exprimer que dans les phrases anglaises, le sujet et le verbe doivent être d'accord en nombre. Dans l'informatique, des exemples de cette approche comprennent grammaires affixes , grammaires d'attributs , grammaires indexés , et Van Wijngaarden grammaires à deux niveaux . Des extensions similaires existent en linguistique.

Une grammaire étendue sans contexte (ou grammaire de la partie droite régulière ) est une grammaire dans laquelle le côté droit des règles de production est autorisé à être une expression régulière sur les terminaux et les non terminaux de la grammaire. Les grammaires sans contexte étendues décrivent exactement les langages sans contexte.

Une autre extension consiste à permettre à des symboles terminaux supplémentaires d'apparaître sur le côté gauche des règles, limitant leur application. Cela produit le formalisme des grammaires contextuelles .

Sous-classes

Il existe un certain nombre de sous-classes importantes des grammaires sans contexte:

• Les grammaires LR ( k ) (également connues sous le nom de grammaires déterministes sans contexte ) permettent l' analyse (reconnaissance de chaînes) avec des automates de refoulement déterministes (PDA), mais elles ne peuvent décrire que des langages déterministes sans contexte .
• Les grammaires LR simples , Look-Ahead LR sont des sous-classes qui permettent une simplification supplémentaire de l'analyse. SLR et LALR sont reconnus en utilisant le même PDA que LR, mais avec des tableaux plus simples, dans la plupart des cas.
• Les grammaires LL ( k ) et LL ( * ) permettent l'analyse par construction directe d'une dérivation la plus à gauche comme décrit ci-dessus, et décrivent encore moins de langues.
• Les grammaires simples sont une sous-classe des grammaires LL (1) principalement intéressante pour sa propriété théorique selon laquelle l'égalité linguistique des grammaires simples est décidable, alors que l'inclusion de la langue ne l'est pas.
• Les grammaires entre crochets ont la propriété que les symboles terminaux sont divisés en paires de parenthèses gauche et droite qui correspondent toujours dans les règles.
• Les grammaires linéaires n'ont pas de règles avec plus d'un non terminal sur le côté droit.
• Les grammaires régulières sont une sous-classe des grammaires linéaires et décrivent les langages réguliers , c'est-à-dire qu'elles correspondent à des automates finis et des expressions régulières .

L'analyse LR étend l'analyse LL pour prendre en charge une plus large gamme de grammaires; à son tour, l' analyse LR généralisée étend l' analyse LR pour prendre en charge des grammaires arbitraires sans contexte. Sur les grammaires LL et les grammaires LR, il effectue essentiellement l'analyse LL et l'analyse LR, respectivement, tandis que sur les grammaires non déterministes , il est aussi efficace qu'on peut s'y attendre. Bien que l'analyse GLR ait été développée dans les années 1980, de nombreuses nouvelles définitions de langage et générateurs d'analyseurs continuent d'être basés sur l'analyse LL, LALR ou LR jusqu'à nos jours.

Applications linguistiques

Chomsky espérait initialement surmonter les limitations des grammaires sans contexte en ajoutant des règles de transformation .

Ces règles sont un autre dispositif standard de la linguistique traditionnelle; par exemple passivation en anglais. Une grande partie de la grammaire générative a été consacrée à trouver des moyens d'affiner les mécanismes descriptifs de la grammaire de la structure des phrases et des règles de transformation de telle sorte que exactement les types de choses peuvent être exprimés que le langage naturel permet réellement. Autoriser des transformations arbitraires ne répond pas à cet objectif: elles sont beaucoup trop puissantes, étant Turing complet à moins que des restrictions significatives ne soient ajoutées (par exemple, pas de transformations qui introduisent puis réécrivent des symboles sans contexte).

La position générale de Chomsky concernant la non-liberté de contexte du langage naturel a résisté depuis lors, bien que ses exemples spécifiques concernant l'inadéquation des grammaires sans contexte en termes de faible capacité générative aient été plus tard réfutés. Gerald Gazdar et Geoffrey Pullum ont fait valoir qu'en dépit de quelques constructions non sans contexte en langage naturel (comme les dépendances inter-séries en suisse allemand et la redondance en bambara ), la grande majorité des formes en langage naturel sont en effet sans contexte.

Voir également

• Analyse de la grammaire des expressions
• Grammaire sans contexte stochastique
• Algorithmes pour la génération de grammaire sans contexte
• Lemme de pompage pour les langages sans contexte

Les références

Remarques

Lectures complémentaires

• Hopcroft, John E .; Ullman, Jeffrey D. (1979), Introduction à la théorie des automates, aux langages et au calcul , Addison-Wesley. Chapitre 4: Grammaires sans contexte, pp. 77–106; Chapitre 6: Propriétés des langages sans contexte, pp. 125–137.
• Sipser, Michael (1997), Introduction à la théorie du calcul , PWS Publishing, ISBN 978-0-534-94728-6. Chapitre 2: Grammaires sans contexte, pp. 91–122; Section 4.1.2: Problèmes décidables concernant les langages sans contexte, pp. 156–159; Section 5.1.1: Réductions via les historiques de calcul: pp. 176–183.
• J. Berstel, L. Boasson (1990). Jan van Leeuwen (éd.). Langues sans contexte . Manuel d'informatique théorique. B . Elsevier. 59–102.

Liens externes

• Les programmeurs informatiques peuvent trouver la réponse d'échange de pile utile.
• Les programmeurs non informaticiens trouveront plus de matériel d'introduction académique pour être instructif.