Utilisation du premier analyseur de descente récursif

J'écris un analyseur de descente récursif pour C en C++. Je ne sais pas comment choisir la production droite dans le cas suivant:Utilisation du premier analyseur de descente récursif

statement: labeled-statement | compound-statement | expression-statement | selection-statement | iteration-statement | jump-statement

je lis au sujet de la « première » -set qui compare le jeton-test avant/char avec des bornes possibles qui vient en premier dans les productions. Actuellement, je suis bloqué à l'aide d'un premier ensemble dans un analyseur de descente récursif, parce que je n'ai qu'une fonction et rien d'autre, aucun objet pour chaque règle ou toute autre chose avec laquelle je peux identifier une règle/production.

Source

2011-09-15 dcast

Quelque chose de mieux avec votre clé de changement de vitesse? –

Non, sry. La prochaine fois que je vais l'utiliser :) – dcast

Merci! Il garde juste l'endroit en ordre, et c'est une petite politesse à ceux qui vont vous aider. –

Votre grammaire est valide pour parseurs descente récursive car il est ambigu sur le côté gauche:

labeled-statement commence par un identifiant
compound-statement commence par un { (ce qui est bien)
expression-statement commence par un identifiant ou un numéro (ou ()

Peut s'arrêter ici , vous avez un conflit entre une instruction étiquetée et une expression. Vous devez transformer votre grammaire pour éliminer les ambiguïtés du côté gauche (à travers des nœuds grammaticaux temporaires pour contenir les parties communes, alors quand vous branchez, vous pouvez déterminer la branche à utiliser en utilisant seulement le look-ahead).

Source

2011-09-15 16:01:57 Blindy

mhh sonne bien, mais qu'en est-il d'essayer un la production après l'autre et en excluant celles-ci, ce qui ne correspond pas à son "premier" -set (pour une performance accrue). Si une production échoue, je peux revenir à la dernière production ou au dernier état valide? btw: après avoir éliminé les ambiguïtés du côté gauche, je ne sais toujours pas quelle production choisir, car je n'ai toujours pas de premier jeu à comparer avec le lookahead. Y a-t-il aussi de bonnes solutions? – dcast

Un compilateur backtracking ne fonctionnera jamais en raison de ses performances incroyablement faibles, même pour les petits fichiers d'entrée. En supposant que vous ayez réellement éliminé les ambiguïtés du côté gauche, la construction du premier ensemble est facile (si fastidieuse): il suffit de descendre les productions pour chaque branche et de construire un ensemble des premières lettres possibles. Par exemple, le premier ensemble de 'statement' est' identifier' (à partir des expressions et des labels), '{' (à partir de la déclaration composée), 'number' (expressions),' goto', 'for',' if' etc. Dans votre fonction récursive, il vous suffit de vérifier l'anticipation par rapport au premier ensemble de chaque branche. – Blindy

Dans le cas où ce n'est pas évident, avoir * tout * chevauchement entre les branches d'une seule production signifie que votre grammaire est ambiguë. Les productions epsilon n'ont pas non plus leur place dans la grammaire de l'analyseur de descente récursive, il faut s'en débarrasser si vous en avez. – Blindy

Utilisation du premier analyseur de descente récursif

Répondre

Questions connexes