python lex-yacc で正規表現風の文法を解析

python lex-yacc で以下のような正規表現風の文法を受け付けられるパーザーを作成します。

abc
(abc|def)
a(b|c)(d|e)f

ただし、(...) の中に (...) は書けないものとします。

lex で使うシンボルは以下の通りです。

CHAR: [^|()] ※|、(、) 以外の文字。
LB:   (
RB:   )
PIPE: |

■test_lex.py

import sys
import ply.lex as lex

tokens = (
    'CHAR',
    'LB',
    'RB',
    'PIPE',
)

t_CHAR = r'[^|()]'
t_LB = r'[(]'
t_RB = r'[)]'
t_PIPE = r'[|]'

def t_error(t):
    sys.stderr.write('illegal char "%s"' % t.value[0])
    t.lexer.sip(t)

lexer = lex.lex()

yacc の文法は以下の通りです。

pttrn       : sub_pttrns
sub_pttrns  : sub_pttrn
            | sub_pttrns sub_pttrn
sub_pttrn   : chars
            | select
select      : LB chars RB
            | LB chars select_iter RB
select_iter : PIPE chars
            | PIPE chars select_iter
chars       : CHAR
            | chars CHAR

■test_yacc.py
以下で p[0] が上記の文法の左辺、p[1:] が右辺です。

import sys
import ply.yacc as yacc
from test_lex import tokens

def p_pttrn(p):
    '''pttrn : sub_pttrns'''
    p[0] = p[1]

def p_sub_pttrns(p):
    '''sub_pttrns : sub_pttrn
                  | sub_pttrns sub_pttrn'''
    if len(p) == 2:
        p[0] = p[1]
    else:
        p[0] = p[1]
        p[0].extend(p[2])

def p_sub_pttrn(p):
    '''sub_pttrn : chars
                 | select'''
    p[0] = p[1]

def p_select_pttrn(p):
    '''select : LB chars RB
              | LB chars select_iter RB'''
    if len(p) == 4:
        p[0] = [{'or': [p[2]]}]
    else:
        p[0] = [p[2]]
        p[0].extend(p[3])
        p[0] = [{'or': p[0]}]

def p_select_iter(p):
    '''select_iter : PIPE chars
                   | PIPE chars select_iter'''
    if len(p) == 3:
        p[0] = p[2]
    else:
        p[0] = [p[2]]
        p[0].extend(p[3])

def p_chars(p):
    '''chars : CHAR
             | chars CHAR'''
    if len(p) == 2:
        p[0] = [p[1]]
    else:
        p[0] = p[1]
        p[0].append(p[2])

上記の文法で以下の文字列を受け付けるか解析してみます。
最後の 'a(b|(c|d))' は (...) がネストしているため、
文法には合わない文字列です。

pttrns = [
    'abc',
    '(abc)',
    '(abc|def)',
    'abc(def|ghi)(jkl|mno)pqr',
    'a(b|(c|d))',
]

parser = yacc.yacc()
for pttrn in pttrns:
    print('====')
    print('pttrn: %s' % (pttrn))
    result = parser.parse(pttrn)
    print('parsed: %s' % (result))

■実行結果

====
pttrn: abc
parsed: ['a', 'b', 'c']
====
pttrn: (abc)
parsed: [{'or': [['a', 'b', 'c']]}]
====
pttrn: (abc|def)
parsed: [{'or': [['a', 'b', 'c'], 'd', 'e', 'f']}]
====
pttrn: abc(def|ghi)(jkl|mno)pqr
parsed: ['a', 'b', 'c', {'or': [['d', 'e', 'f'], 'g', 'h', 'i']}, {'or': [['j', 'k', 'l'], 'm', 'n', 'o']}, 'p', 'q', 'r']
====
pttrn: a(b|(c|d))
parsed: None

文法通りであれば文字列を解析した結果が返却されますが、
最後の文字列は解析結果が None となっていて、文法通りではない文字列であると判定されています。