boolean prop matching

Question

I have certain logical proposition and I want to check their validity with Regex in C#.

Each capital letter is a predicate. Formulas for predicate logic are built with predicates and connectives like ¬, ⇒, ⇔, ⋀ and ⋁. However user input should be in ASCII string notation, namely:

Logical notation       ASCII               
¬A                     ~(A)                 Negation

A ⇒ B                 >(A,B)               Implication

A ⇔ B                 =(A,B)               Bi-Implication

A ⋀ B                  &(A,B)               AND

A ⋁ B                  |(A,B)               OR

Furthermore True and False are represented with 0 and 1, like so : &(0,1)

Let's say I have following ASCII input

string input1 = "&(&(=(A,B),>(&(A,B),~(C))),>(A,~(&(A,B))))"; // valid
string input2 = "1"     // valid
string input3 = "=(~(A),>(>(B,C),~(A)))" // valid
string input4 = "(~(A))" // invalid because no connective in the beginning
string input5 = ">(A,B"  // invalid because no closing parenthesis

So, the ascii string should be either

1. Single Predicate - A-Z or 0-1
2. string starting with connective and containing two propositions separated by comma, those propositions could be either a single predicate or a connective with two propositions...

I came up with this:

Regex checkExpression = new Regex(
                   @"([&|>=]\(([A-Z0-1]{1}|\(.*\)),([A-Z0-1]{1}|\(.*\))\))
                                          |([~]\(([A-Z0-1]{1}|\(.*\))\))");

However, I am not very familiar with building Regular expressions, any help is appreciated.

Answer 1

As Richard has stated you should be using ASTs to manage the validation and actually you can also use this to start building your own language on C#. I have done this many times in the past for various projects and have used a pretty decent tool called "Irony.Net" irony where you design your grammar in code directly.

Irony is a development kit for implementing languages on .NET platform. Unlike most existing yacc/lex-style solutions Irony does not employ any scanner or parser code generation from grammar specifications written in a specialized meta-language. In Irony the target language grammar is coded directly in c# using operator overloading to express grammar constructs. Irony's scanner and parser modules use the grammar encoded as c# class to control the parsing process. Irony.Net CodePlex

With this have come up with a pretty basic grammar that seems to handle your cases below. However there is an odd case in your examples (or require further explanation)

1. 1 is valid but is 0 valid?
2. As above what about any of the predicates A-Z (upper case)?

Example grammar

[Language("Logical Proposition", "1.0", "")]
public class LogicalPropositionGrammar : Grammar
{
    public LogicalPropositionGrammar()
    {
        //syntax terminals
        var lpar = ToTerm("(");
        var rpar = ToTerm(")");
        var comma = ToTerm(",");
        var trueTerm = ToTerm("1") | "true";
        var falseTerm = ToTerm("0") | "false";

        //nonterms
        var predicate = new NonTerminal("Predicate");
        var connective = new NonTerminal("Connective");
        var pexp = new NonTerminal("PredExpression");
        var formula = new NonTerminal("Formula");
        var literal = new NonTerminal("Literal");
        var singleTerm = new NonTerminal("SingleTerm");
        var multiTerm = new NonTerminal("MultiTerm");

        //formulat non terms
        var negation = new NonTerminal("Negation");
        var implication = new NonTerminal("Implication");
        var biImplication = new NonTerminal("Bi-Implication");
        var andTerm = new NonTerminal("And");
        var orTerm = new NonTerminal("Or");

        literal.Rule = trueTerm | falseTerm;
        singleTerm.Rule = lpar + pexp + rpar; //single term is (pexp)
        multiTerm.Rule = lpar + pexp + comma + pexp + rpar; //mult term = (pexp, pexp)

        //formula rules
        negation.Rule = ToTerm("~") + singleTerm;
        implication.Rule = ToTerm(">") + multiTerm;
        biImplication.Rule = ToTerm("=") + multiTerm;
        andTerm.Rule = ToTerm("&") + multiTerm;
        orTerm.Rule = ToTerm("|") + multiTerm;

        //predicate terms
        predicate.Rule = ToTerm("A") | "B" | "C" | "D" | "E" | "F" | "G" |
                            "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" |
                            "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" |
                            "X" | "Y" | "Z" | literal;

        //predicate rule
        pexp.Rule = predicate | negation | implication | biImplication | andTerm | orTerm;

        //a base formulat
        formula.Rule = MakeStarRule(formula, pexp);

        RegisterOperators(10, "&", "~", ">", "=", "|");
        MarkPunctuation(",", "(", ")");
        MarkTransient(pexp, singleTerm);

        Root = formula;
    }
}