на память: использование 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)