Parse chaîne logique propositionnelle

Question

J'ai une formule logique propositionnelle

((a ou b) et d!) Ou e -> c

Comment est-il possible de parser cette chaîne, donc Je peux faire un arbre de vérité?

Je suppose que je devrais diviser ma chaîne par ->, and et or, mais il va gâcher les parenthèses. Comment puis-je protéger chaque parenthèse avant de diviser ma chaîne? Est-ce que je devrais peut-être diviser en utilisant l'expression régulière pour diviser par des expressions entre parenthèses avant de faire autre chose?

Pour la chaîne dans mon exemple, j'imagine que cela devrait faire un tableau imbriqué où ['or', a, b] est le niveau 'le plus profond' qui est stocké dans le 'niveau le plus profond suivant' ['and', ['or', a, b]]. Donc, je pense serait que cette chaîne doit être convertie en un tableau

[ 
    'implication' 
    [ 
     'or', 
     [ 
      'and', 
      [ 
       'or', 
       'a', 
       'b' 
      ] 
     ], 
     'e' 
    ], 
    'c' 
] 

où chaque tableau se compose de 3 éléments où le premier élément indique à l'opérateur et les deux éléments suivants indiquent que « les propositions », l'opérateur doit travailler .

Je ne suis pas sûr si c'est une structure intelligente, mais je suppose que ce serait un moyen possible d'analyser la chaîne. J'ai étudié l'algorithme de shunting-yard pour convertir de l'infixe à la notation postfixée ou à l'arbre de syntaxe abstraite (AST). Dois-je utiliser quelque chose comme ça pour le faire correctement?

Answer 1

Vous devez d'abord définir une grammaire BNF pour votre langage de calcul propositionnel. C'est plutôt facile. Vous pouvez ensuite l'utiliser pour définir un analyseur pour la langue.

Voir cette réponse SO comment écrire à la main parseurs descente récursive facilement: Is there an alternative for flex/bison that is usable on 8-bit embedded systems?

Cette réponse explique également comment vous pouvez évaluer l'expression que vous analysez, ou comment vous pouvez enregistrer la formule comme un « arbre "et l'évaluer plus tard avec des valeurs différentes pour les variables.