Parsing logical expression using PLY
<p>I am trying to parse logical expression containing 'implies' 'and' 'or' and 'negation' with parentheses such as <code>(Q(a)=&gt;R(b))</code> using PLY where Q(a) and R(b) are predicates and always start with block letters and variables 'a' and 'b' will be single small letter characters.</p>

<p>Each operator and its operands will be surrounded by parenthesis. Some other examples of logical expression i am trying to parse are <code>((D(q,w) &amp; E(r,s)) =&gt; F(t)), (((G(a)=&gt;H(b))=&gt;I(c))=&gt;J(d)), (~(~(~P(a))))</code>.</p>

<p>Below is the code i have written</p>

<pre><code>import ply.lex as lex
import ply.yacc as yacc

tokens = [
    'LPAREN',
    'RPAREN',
    'PREDICATE',
    'AND',
    'OR',
    'IMPLIES',
    'NEGATION'
]

t_PREDICATE = r'[A-Z][a-z]*\(([A-Za-z,]+)\)'
t_LPAREN = r'\('
t_RPAREN = r'\)'
t_AND = r'\&amp;'
t_OR = r'\|'
t_IMPLIES = r'\=&gt;'
t_NEGATION = r'\~'

t_ignore = r' '

def t_error(t):
    print("Illegeal characters")
    t.lexer.skip(1)

lexer = lex.lex()


def p_expression_negation(p):
    '''
    expression : LPAREN NEGATION PREDICATE RPAREN

    '''
    p[0] = (p[2], p[3])
    print(p[0])

def p_expression_single(p):
    '''
    expression : PREDICATE
    '''
    p[0] = p[1]
    print(p[0])

def p_expression(p):
    '''
    expression : LPAREN term IMPLIES term RPAREN
               | LPAREN term AND term RPAREN
               | LPAREN term OR term RPAREN
    '''

    p[0] = (p[3], p[2], p[4])
    print(p[0])

def p_term_negation(p):
    '''
    term : LPAREN NEGATION PREDICATE RPAREN

    '''
    p[0] = (p[2], p[3])
    return p[0]


def p_term_single(p):
    '''
    term : PREDICATE
    '''
    p[0] = (p[1])
    return p[0]

def p_term_multiple(p):
    '''
    term : LPAREN PREDICATE IMPLIES PREDICATE RPAREN
         | LPAREN PREDICATE AND PREDICATE RPAREN
         | LPAREN PREDICATE OR PREDICATE RPAREN

    '''
    p[0] = (p[3], p[2], p[4])
    return p[0]


def p_error(p):
    print("Syntax error in input!")

parser = yacc.yacc()

while True:
    try:
        s = input('Enter the input')
    except EOFError:
        break
    parser.parse(s, lexer=lexer)
</code></pre>

<p>But this program fails for logic expression such as <code>(((G(a)=&gt;H(b))=&gt;I(c))=&gt;J(d)), (~(~(~P(a))))</code> since  these expressions start with more than 2 '(', i am not able to modify my code to accommodate such cases where opening parentheses at beginning of expression can range from 1 to n.</p>

<p>I think i should use recursion but that as well is failing for me.</p>

<p>This is my first program with PLY so not able to write a proper Grammar rule for yacc, it would be of great help if someone could help me with this</p>