Les expressions régulières

16

Si j'ai une grammaire de type 3, elle peut être représentée sur un automate déroulant (sans faire aucune opération sur la pile) afin que je puisse représenter des expressions régulières en utilisant des langages sans contexte. Mais puis-je savoir si une grammaire de type 3 est , L L ( 1 ) , S L R ( 1 ) , etc. sans construire de tables d'analyse?LR(1)LL(1)SLR(1)

Andrea Tucci
la source

Réponses:

15

Toutes les langues régulières ont des grammaires LL (1). Pour obtenir une telle grammaire, prenez n'importe quel DFA pour le langage régulier (peut-être en faisant la construction du sous-ensemble sur le NFA obtenu à partir de l'expression régulière), puis convertissez-le en une grammaire régulière récursive à droite. Cette grammaire est alors LL (1), car toute paire de productions pour le même non-terminal commence soit par des symboles différents, soit on produit ε et a $ comme jeton d'anticipation. Par conséquent, toutes les langues régulières sont également LR (1), car toute grammaire LL (1) est LR (1). De plus, en utilisant un résultat important de cet article , vous pouvez montrer que toute langue LR (1) a une grammaire SLR (1), ce qui signifie que toute langue régulière a une grammaire SLR (1).

Cependant, les langues régulières ne sont pas toutes LR (0). Les langages LR (0) ont des propriétés très spécifiques - en particulier, ils doivent être exempts de préfixe. Ainsi le langage régulier {a, aa} n'est pas LR (0), bien qu'il soit clairement régulier (regex a | (aa)). Cependant, les langues LR (0) ne sont pas correctement contenues dans les langues régulières; cette grammaire pour {0 n 21 n | n ≥ 1} est LR (0), mais la langue n'est pas régulière:

S -> E
E -> 0E1 | 2

J'espère que cela t'aides!

templatetypedef
la source
2
Le fait que les grammaires à droite et à droite acceptent exactement l'ensemble des langues régulières se fait généralement en classe (ou même dans les exercices), la réponse est donc beaucoup plus immédiate.
Raphael
2

La syntaxe d' expression régulière (ordinaire) (vous avez dit "représentation") est LR (0). Vous n'avez pas besoin d'anticipation pour analyser une chaîne représentant une expression régulière. Vous pouvez facilement décider cela en exécutant un générateur d'analyseur sur une grammaire pour les expressions régulières: -} Vous pouvez également facilement coder un analyseur de descente récursive simple (LL (0)) pour les expressions régulières; tout ce qui est LL (0) est LR (0).

Je ne sais pas si la syntaxe de soi-disant "regexps" plus compliquées comme Perl est comme ça; mais les regexps de Perl sont strictement plus puissants que les regexps, donc ce ne sont pas de vieilles regexps simples.

Pour déterminer si une grammaire possède une propriété, vous devez exécuter une sorte de prédicat. Pour déterminer s'il s'agit de (S) LR (k), vous devez exécuter un prédicat qui peut vérifier cette propriété. En effet, un tel prédicat doit en effet créer les tables d'analyse, en raison de la façon dont elles sont définies.

Ira Baxter
la source
Perl regular expressions fonctionne sur NFA
La question n'était pas de savoir comment fonctionnaient les expressions rationnelles de Perl. Il s'agissait de savoir si les expressions rationnelles (Perl?) Étaient analysables par certaines technologies. Je peux croire que les expressions rationnelles de Perl utilisent un NFA pour effectuer leur correspondance, ainsi que d'autres captures de données contextuelles, mais je ne vois pas la pertinence de la question.
3
-1 Les expressions régulières ne sont pas LR (0). Les langues LR (0) doivent être sans préfixe, mais l'expression régulière a|(aa)décrit une langue qui n'est pas sans préfixe. De plus, les langages LR (0) ne peuvent pas gérer les grammaires avec des productions epsilon, donc le langage régulier {epsilon, a} n'est pas LR (0). Cependant, les langues régulières sont LL (1) car vous pouvez les écrire comme des grammaires régulières, et donc elles sont toutes LR (1). Étant donné que toute langue LR (1) a une grammaire SLR (1), cela signifie que toutes les langues régulières sont SLR (1).
templatetypedef
1
En ce qui concerne LL (0), c'est l'inverse: les langues LL (0) sont un sous-ensemble approprié de langues régulières. Notez que LL (0) signifie que vous n'utilisez pas d'anticipation pour décider entre différentes dérivations - ce qui signifie essentiellement qu'il n'y a pas de décisions et que la langue se compose d'un seul mot. LR (0), en revanche, est une classe utile - encore une fois, vous n'utilisez pas l'anticipation pour décider (ici pour les réductions), mais il y a encore une certaine diversité en raison du fait que le décalage peut faire la distinction entre différentes productions.
1
@ IraBaxter - La syntaxe des expressions régulières n'est pas non plus LR (0) car les expressions régulières ne sont pas libres de préfixe. Ils ne sont pas non plus LL (0), car les langues LL (0) ne peuvent contenir qu'une seule chaîne (ou aucune chaîne).
templatetypedef