|
|
Friday, June 13th, 2014
|
12:54a - на память: использование lex и yacc на примере PLY
ply - это простой и довольно удобный lex и yacc для питона на питоне.
используем, если нужно что-то распарсить;
здесь мы решаем задачу парсинга многочленов вроде z^4+1.5z-z^2+5.
сначала лексер. токены будут:
"число с плавающей точкой"
"плюс"
"минус"
"степень" - выражение вида z или z^n, n-параметр токена (для "z просто" n=1)
import ply.lex as lex
tokens = (
'DOUBLE',
'PLUS',
'MINUS',
'POW'
)
def t_DOUBLE(t):
r'\d+(\.\d*)?'
t.value = float(t.value)
return t
t_PLUS = r'\+'
t_MINUS = r'-'
def t_POW(t):
r'z(\^\d+)?'
t.value = int(t.value[2:]) if len(t.value) > 1 else 1
return t
t_ignore = ' '
def t_error(t):
print('Illegal character "%s" in string' % t.value[0])
t.lexer.skip(1)
lexer = lex.lex()
здесь t.value на входе лежит заматченный регулярным выражением
кусок строки, на выходе - параметр токена.
теперь парсер. таблица правил для парсера (беру сгенерированную
по определению парсера debug-распечатку ply-yacc):
Rule 1 expr -> term
Rule 2 expr -> expr PLUS term
Rule 3 expr -> expr MINUS term
Rule 4 term -> DOUBLE
Rule 5 term -> POW
Rule 6 term -> DOUBLE POW
Rule 7 term -> MINUS term
парсер берёт значения из токенов (и уже свёрнутых нетерминалов), и синтезирует
значение для левой стороны правила. у нас в term будет лежать пара (степень, коэффициент)
(терм - это выражение вида 1.5z^3, соответственное значение (3, 1.5)),
в expr - словарь, отображающий степени в коэффициенты (для простоты используется
defaultdict(float), который по запросу сразу инициализирует несуществующее поле нулём).
выглядит это так:
import ply.yacc as yacc
from collections import defaultdict
from polylex import tokens
def p_expr_term(p):
'expr : term'
p[0] = defaultdict(float)
p[0][p[1][0]] = p[1][1]
def p_expr_plus(p):
'expr : expr PLUS term'
p[0] = p[1]
p[0][p[3][0]] = p[0][p[3][0]] + p[3][1]
def p_expr_minus(p):
'expr : expr MINUS term'
p[0] = p[1]
p[0][p[3][0]] = p[0][p[3][0]] - p[3][1]
def p_term_double(p):
'term : DOUBLE'
p[0] = (0, p[1])
def p_term_pow(p):
'term : POW'
p[0] = (p[1], 1.)
def p_term_double_pow(p):
'term : DOUBLE POW'
p[0] = (p[2], p[1])
def p_term_minus(p):
'term : MINUS term'
p[0] = (p[2][0], -p[2][1])
def p_error(p):
print('Syntax error in input')
parser = yacc.yacc()
индексы после p - это номер буквы в правиле, например, в
'term : MINUS term'
p[0] - это синтезируемое значение term слева,
p[1] - минус, а
p[2] - уже свёрнутое значение term справа.
что мы видим: берём term (справа) - это пара (степень, коэффициент) -
меняем знак у коэффициента и обратно склеиваем пару.
вызывается это хозяйство (например) так:
while True:
try:
s = input('polynomial>')
except EOFError:
break
if not s: continue
result = parser.parse(s)
print(result)
(comment on this)
|
5:22a - решил почитать ДиНД
всё-таки Манин гораздо круче Арнольда в смысле чтения. Арнольд - это как бы остроумие в его высшем проявлении, а Манин - это ЛСД, Atom Heart Mother и всякая крышесносная хуйня. да здравствует Манин
(7 comments |comment on this)
|
|
|
|