règles d'analyse - comment les faire jouer ensemble agréable

Question

Je fais un parseur, où je privilégie la flexibilité sur la vitesse, et je veux que ce soit facile d'écrire pour grammaires, par exemple aucune règle de contournement délicate (règles de faux pour résoudre les conflits etc, comme vous devez le faire dans yacc / bison, etc.)

Il y a un code Lexer à la main avec un ensemble fixe de jetons (par exemple PLUS, DECIMAL, STRING_LIT, NOM, etc.) en ce moment, il existe trois types de règles:

• TokenRule: correspond à un jeton particulier
• SequenceRule: correspond à une liste ordonnée de règles
• GroupRule: correspond à une règle à partir d'une liste

Par exemple, disons que nous avons le TokenRule 'varAccess', qui correspond à nom de jeton (environ / [A-Za-z] [A-Za-z0-9 _] * /) et le SequenceRule 'cession', qui correspond à [expression, TokenRule (PLUS), expression].

L'expression est un GroupRule correspondant soit « cession » ou « varAccess » (la ruleset réelle que je teste avec est un peu plus complet, mais qui fera pour l'exemple)

Mais maintenant, disons que je veux analyser

var1 = var2

Et disons que la Parser commence par la règle d'expression (l'ordre dans lequel elles sont définies ne devrait pas question - les priorités seront résolus plus tard). Et disons que l'expression de GroupRule va d'abord essayer « cession ». Alors, puisque « expression » est la première règle à apparié dans « cession », il va essayer d'analyser une expression à nouveau, et ainsi de suite jusqu'à ce que la pile est remplie et l'ordinateur - comme prévu - donne simplement dans une segfault scintillante.

Alors, ce que je faisais est - SequenceRules s'ajouter comme « leafs » à leur première règle, et deviennent des règles non-ROOT. règles de base sont les règles que l'analyseur premier essai. Lorsque l'un de ceux qui est appliqué et les matches, il essaie de subapply chacun de ses feuilles, un par un, jusqu'à ce qu'un matches. Ensuite, il tente les feuilles de la feuille de correspondance, et ainsi de suite, jusqu'à ce qu'il ne correspond plus.

Alors qu'il peut analyser des expressions comme

var1 = var2 = var3 = var4

Juste à droite =) Maintenant, les choses intéressantes. Ce code:

var1 = (var2 + var3)

N'analyser. Ce qui se passe est, var1 se parsé (varAccess), attribuer est sous-appliqué, il recherche une expression, tente « parenthèse », commence, cherche une expression après la « ( », trouve var2 et selfs puis sur le « + »parce qu'elle attendait un ')'.

Pourquoi ne pas correspondre à la 'var2 + var3'? (Et oui, il y a une SequenceRule « add », avant de vous demander). Parce que « ajouter » n'est pas une règle de racine (pour éviter une récursion infinie avec l'analyse syntaxique-expresssion-début avec l'expression-etc.) Et que leafs ne sont pas testés dans SequenceRules il serait autrement analyser des choses comme

reader readLine() println()

reader (readLine() println())

(par exemple. '1 = 3' est l'expression attendu par ajout, la feuille de varAccess a)

alors que nous aimerions qu'il soit laissé associatif, par exemple l'analyse syntaxique comme

(reader readLine()) println()

De toute façon, maintenant nous avons ce problème que nous devrions être en mesure d'analyser l'expression telle que « 1 + 2 » au sein SequenceRules. Que faire? Ajouter un cas particulier que lorsque SequenceRules commencent par un TokenRule, puis les GroupRules qu'il contient sont testés pour leafs? Ne serait-ce même pas de sens en dehors de cet exemple particulier? Ou faut-il être en mesure de préciser dans chaque élément d'une SequenceRule si elle doit être testé pour leafs ou non? Dites-moi ce que vous pensez (autre que jeter tout le système - qui va probablement arriver dans quelques mois de toute façon)

P.S: S'il vous plaît, s'il vous plaît assez, ne répondez pas à quelque chose comme « aller lire ce livre 400pages ou que vous ne méritent même pas notre temps » Si vous ressentez le besoin - juste pour vous éviter et aller bash sur reddit. D'accord? Merci à l'avance.

Answer 1

LL (k) parseurs (haut en bas récursif, que ce soit automatisé ou écrit à la main) exigent refactoring de votre grammaire pour éviter gauche récursion, et nécessitent souvent des spécifications particulières de préanalyse (par exemple ANTLR) pour être en mesure de gérer préanalyse k-token . Depuis grammaires sont complexes, vous obtenez à découvrir k par l'expérimentation, ce qui est exactement la chose que vous voulez éviter.

YACC / LALR (1) grammaires aviod le problème de récursivité à gauche, ce qui est un grand pas en avant. Les mauvaises nouvelles sont qu'il n'y a pas de programmation langauges réel (autres que de Wirth d'origine PASCAL) qui sont LALR (1). Par conséquent, vous obtenez de pirater votre grammaire pour changer de LR (k) à LALR (1), vous forçant à nouveau à subir les expériences qui exposent les cas étranges, et le piratage de la logique de réduction de la grammaire pour essayer de gérer K-lookaheads lorsque l'analyseur générateurs (YACC, BISON, ... vous nommez) produisent parseurs 1-lookahead.

GLR parseurs ( http://en.wikipedia.org/wiki/GLR_parser ) vous permettent d'éviter presque toutes ces absurdités. Si vous pouvez écrire un contexte analyseur libre, dans des circonstances les plus pratiques, un analyseur GLR analysera sans effort supplémentaire. C'est un énorme soulagement lorsque vous essayez d'écrire grammaires arbitraires. Et un très bon analyseur RGL produire directement un arbre.

BISON a été amélioré pour faire l'analyse syntaxique GLR, en quelque sorte. Il vous reste à écrire une logique complexe pour produire votre AST désiré, et vous avez à vous soucier de la façon de gérer l'échec et le nettoyage parseurs / suppression de leurs correspondants (échec) arbres. DMS Software Reengineering Tookit fournit des parseurs standards GLR pour toute grammaire sans contexte, et construit automatiquement sans aucun effort RSHS supplémentaire de votre part; arbres ambigus sont construits automatiquement et peuvent être nettoyés par analyis sémantique post-analyse syntaxique. Nous avons utilisé ce faire définir de 30 grammaires de langue, y compris C, y compris C ++ (qui est largement pensé pour être difficile à analyser [et il est presque impossible d'analyser avec YACC] mais est simple avec de vrais GLR); voir C +++ analyseur d'extrémité avant et le constructeur AST sur la base de DMS.

Bottom line: si vous voulez écrire des règles de grammaire d'une manière simple et obtenir un analyseur pour les traiter, utiliser la technologie d'analyse syntaxique GLR. Bison presque fonctionne. DMs vraiment fonctionne.

Answer 2

Ma technique préférée est de l'analyse syntaxique pour créer analyseur récursif-descente (RD) à partir d'une spécification de grammaire PEG. Ils sont généralement très rapide, simple et flexible. Un grand avantage est que vous n'avez pas à vous soucier de passes de tokenisation séparés, et se soucier de presser la grammaire dans une certaine forme de LALR est inexistante. Certaines bibliothèques PEG sont répertoriées [ici] [1].

Désolé, je sais que cela tombe dans jeter le système, mais vous êtes à peine hors de la porte avec votre problème et passer à un analyseur PEG RD, serait tout simplement éliminer vos maux de tête maintenant.