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 となっていて、文法通りではない文字列であると判定されています。