Grammaires régulières et grammaires libres de contexte

Question

Je suis en train d'étudier pour mon les langages informatiques et il y a une idée que j'ai du mal à comprendre.

J'ai compris que grammaires régulières sont plus simples et ne peuvent pas contenir d'ambiguïté, mais ne peuvent pas effectuer un grand nombre de tâches requises pour les langages de programmation. J'ai également compris que grammaires sans contexte permettent l'ambiguïté, mais autorisent certaines choses nécessaires aux langages de programmation (comme les palindromes).

Ce qui me pose problème, c'est de comprendre comment je peux dériver tout ce qui précède en sachant que grammaire régulière non terminaux peut correspondre à un terminal ou à un nonterminal suivi d'un terminal, ou qu'un nonterminal sans contexte correspond à n'importe quelle combinaison de terminaux et de nonterminaux.

Quelqu'un peut-il m'aider à faire la synthèse de tout cela ?

Answer 1

La grammaire ordinaire est linéaire à droite ou à gauche, tandis que la grammaire libre de contexte est fondamentalement toute combinaison de terminaux et de non-terminaux. On voit donc que la grammaire régulière est un sous-ensemble de la grammaire sans contexte.

Ainsi, un palindrome, par exemple, est de la forme,

S->ABA
A->something
B->something

Vous pouvez clairement voir que les palindromes ne peuvent pas être exprimés dans la grammaire ordinaire puisqu'ils doivent être linéaires à droite ou à gauche et ne peuvent donc pas avoir de non-terminal des deux côtés.

Les grammaires régulières n'étant pas ambiguës, il n'existe qu'une seule règle de production pour un non-terminal donné, alors qu'il peut y en avoir plusieurs dans le cas d'une grammaire sans contexte.

Answer 2

Je pense que ce à quoi il faut penser, ce sont les différents lemmes de pompage. Un langage régulier peut être reconnu par un automate fini. Un langage sans contexte nécessite une pile, et un langage sensible au contexte nécessite deux piles (ce qui équivaut à dire qu'il nécessite une machine de Turing complète).

Ainsi, si nous pensons à la lemme de pompage pour les langages réguliers Ce qu'il dit, en substance, c'est que tout langage régulier peut être décomposé en trois parties, x , y y z où toutes les instances de la langue sont en xy*z (où * est une répétition de Kleene, c'est-à-dire 0 ou plusieurs copies de y .) Vous avez essentiellement un "non terminal" qui peut être développé.

Qu'en est-il des langages sans contexte ? Il existe un langage analogue, le lemme de pompage pour les langages sans contexte qui divise les chaînes de la langue en cinq parties, uvxyz et où toutes les instances de la langue sont en uv i xy i z pour i ≥ 0. On a alors deux des "non terminaux" qui peuvent être reproduits ou pompés, tant que vous avez le même nombre .

Answer 3

Grammaire régulière:- La grammaire contenant la production suivante est RG :

V->TV or VT
V->T

où V=variable et T=terminal

La GR peut être une grammaire linéaire gauche ou une grammaire linéaire droite, mais pas une grammaire linéaire moyenne.

Comme nous le savons, toutes les RG sont des grammaires linéaires, mais seules les grammaires linéaires gauche et droite sont des RG.

Une grammaire ordinaire peut être ambiguë.

S->aA|aB
A->a
B->a

Grammaire ambiguë pour une chaîne de caractères x, il existe plus d'un LMD ou plus d'un RMD ou plus d'un arbre de Parse ou un LMD et un RMD, mais les deux produisent un arbre de Parse différent.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

cette Grammaire est une Grammaire ambiguë car deux arbres d'analyse.

CFG:- Une grammaire est dite CFG si sa production est en forme :

   V->@   where @ belongs to (V+T)*

DCFL : - Comme nous le savons, toutes les DCFL sont des grammaires LL(1) et toutes les LL(1) sont des LR(1), de sorte qu'elles ne sont jamais ambiguës.

Nous savons également que tous les RL sont DCFL, de sorte que les RL ne sont jamais ambigus. Notez que RG peut être ambigu, mais pas RL.

CFL : CFl Peut être ambigu ou non.

Remarque : RL n'est jamais intrinsèquement ambiguë.

Answer 4

Expressions régulières

• Base de l'analyse lexicale
• Représenter des langages réguliers

Grammaires libres de contexte

• Base de l'analyse syntaxique
• Représenter les constructions linguistiques

Answer 5

Une grammaire est sans contexte si toutes les règles de production sont de la forme : A (c'est-à-dire que le côté gauche d'une règle ne peut être qu'une seule variable ; le côté droit n'est pas limité et peut être n'importe quelle séquence de terminaux et de variables). Nous pouvons définir une grammaire comme un 4-tuple où V est un ensemble fini (variables), _ est un ensemble fini (terminaux), S est la variable de départ, et R est un ensemble fini de règles, chacune d'entre elles étant une correspondance V
La grammaire régulière est linéaire à droite ou à gauche, alors que la grammaire sans contexte est fondamentalement toute combinaison de terminaux et de non-terminaux. on peut donc dire que la grammaire régulière est un sous-ensemble de la grammaire sans contexte. Compte tenu de ces propriétés, on peut dire que l'ensemble des langages sans contexte contient également l'ensemble des langages réguliers.