Pourquoi séparer lexing et analyse?

15

Il est possible d'analyser un document en un seul passage depuis une machine d'état. Quel est l'avantage d'avoir deux passes, à savoir. avoir un lexer pour convertir du texte en jetons, et avoir un analyseur pour tester les règles de production sur ces jetons? Pourquoi ne pas avoir un seul passage qui applique directement les règles de production au texte?

compilers parsers Brent
la source
2
Connexes: programmers.stackexchange.com/questions/128888/…
Utilisateur
2
Cela a déjà été discuté sur CS, stackexchange, avec de nombreux commentaires très techniques dans une réponse à la puissance expressive de lexer + parser . Mais il peut y avoir de la place pour d'autres réponses.
babou
Je me demande si le parallélisme de type pipeline (bien que les étapes très déséquilibrées) pourrait être un avantage secondaire. Le comportement des instructions et du cache de données peut également être intéressant. La quantité (le cas échéant) qui réduirait le temps de compilation dépendrait du matériel spécifique.
Paul A. Clayton
Une raison assez évidente (du moins pour moi) est que vous pouvez ensuite utiliser l'outil scanner séparément. Dans la pratique, j'utilise fréquemment flex pour scanner les entrées, mais j'ai rarement besoin de toute la puissance de yacc.
jamesqf

Réponses:

13

Vous n'avez pas besoin de les séparer. Les gens les combinent en analyseurs sans scanner .

Le principal inconvénient des analyseurs sans scanner semble être que les grammaires résultantes sont plutôt compliquées - plus compliquées que la combinaison correspondante d'une expression régulière faisant lexing et d'une grammaire sans contexte faisant l'analyse sur le flux de jetons. En particulier, les grammaires pour l'analyse sans scanner tendent à l'ambiguïté. Il est plus facile de lever l'ambiguïté pour les grammaires travaillant sur un flux de jetons.

Un avantage pragmatique de l'utilisation d'une phase de lexing initiale dédiée est que vous ne couplez pas l'analyseur suivant avec des détails lexicaux. Ceci est utile lors du développement précoce du langage de programmation, lorsque les détails lexicaux et syntaxiques changent encore fréquemment.

Martin Berger
la source
1
TPPPT
@babou Oui c'est correct. Je ne connais aucun résultat formel de la forme d'expression régulière composée avec LL (k) sort de LL (k), ou similaire. De plus, le lexing ne se fait généralement pas avec des langages réguliers, mais avec quelque chose de plus puissant, à savoir des langages réguliers étendus avec des priorités de correspondance plus longue et de mots clés en premier. Je ne suis pas sûr de la classe de langue exacte et de ses propriétés de fermeture.
Martin Berger
2
Si votre anticipation implique la lecture d'un identifiant, la composition nécessitera une anticipation illimitée, car il n'y a (en principe) aucune limite sur la longueur des identifiants.
babou
@babou, je ne suis pas sûr. Si le mot clé le plus long comporte 17 caractères, toute chaîne plus longue doit être un identifiant ou lexicalement invalide.
Martin Berger
Mais votre identifiant, ou éventuellement une chaîne, un nombre ou un autre littéral, est une séquence de plus de 17 symboles individuels, qui peut se trouver devant le jeton dont vous avez réellement besoin. C'est un grand regard vers l'avenir, sans limite. Vous pouvez vous retrouver avec un langage non déterministe.
babou