DjangoBB LoFi version

Начало » Python для новичков » парсер Страуструпа

1 2

baslie

Сен. 25, 2012 18:46:30

Осваиваю программирование. Переписываю код Страуструпа и никак не могу понять в чем ошибка. На вход подаю 3 - 2 - 1 ( = (3 - 2) - 1 = 1 - 1 = 0), а получаю 1, т.е. вычисляется только (3 - 2), а -1 опускается.

class Buffer(object):
    def __init__(self, expr):
        self.expr = expr
        self.buffer = []
    def get(self):
        if len(self.expr) != 0:
            self.buffer = self.expr.pop(0)
        return self.buffer
    def putback(self, val):
        self.expr.insert(0, val)
def expression(buf):
    left = term(buf)
    t = buf.get()
    if t == '+':
        left += term(buf)
    elif t == '-':
        left -= term(buf)
    else:
        buf.putback(t)
    return left
def term(buf):
    left = primary(buf)
    t = buf.get()
    if t == '*':
        left *= primary(buf)
    elif t == '/':
        left /= float(primary(buf))
    else:
        buf.putback(t)
    return left
def primary(buf):
    t = buf.get()
    if t.isdigit():
        return int(t)
    elif t == '(':
        d = expression(buf)
        t = buf.get()
        if t != ')':
            print("')' expected")
    else:
        buf.putback(t)
buf = Buffer(['3','-','2','-','1'])
print expression(buf)

py.user.next

Сен. 26, 2012 02:05:58

    Expression:
        Term
        Expression + Term
        Expression - Term
    Term:
        Primary
        Term * Primary
        Term / Primary
        Term % Primary
    Primary:
        Number
        ( Expression )
        - Primary
        + Primary
    Number:
        floating-point-literal

убрал Name

тебе нужно заглядывать, есть ли там операция, и только после этого принимать решение, что читать, Expression или Term, Term или Primary

а сейчас у тебя там написано Term + Term, а не Expression + Term

add
хотя посмотрел у Страуструпа, он их просто считывает
Expression - Term, а Term - Primary в любом случае

py.user.next

Сен. 26, 2012 08:35:52

#!/usr/bin/env python
 
#    Expression:
#        Term
#        Expression + Term
#        Expression - Term
#    Term:
#        Primary
#        Term * Primary
#        Term / Primary
#        Term % Primary
#    Primary:
#        Number
#        ( Expression )
#        - Primary
#        + Primary
#    Number:
#        floating-point-literal
 
class Buffer(object):
    def __init__(self, expr):
        self.expr = expr
        self.buffer = []
    def get(self):
        if len(self.expr) != 0:
            self.buffer = self.expr.pop(0)
        return self.buffer
    def putback(self, val):
        self.expr.insert(0, val)
 
def expression(buf):
    left = term(buf)
    t = buf.get()
    while True:
        if t == '+':
            left += term(buf)
            t = buf.get()
        elif t == '-':
            left -= term(buf)
            t = buf.get()
        else:
            buf.putback(t)
            return left
 
def term(buf):
    left = primary(buf)
    t = buf.get()
    while True:
        if t == '*':
            left *= primary(buf)
            t = buf.get()
        elif t == '/':
            d = float(primary(buf))
            if (d == 0.0):
                raise ValueError('divide by zero')
            left /= d
            t = buf.get()
        else:
            buf.putback(t)
            return left
 
def primary(buf):
    t = buf.get()
    if t.isdigit():
        return int(t)
    elif t == '(':
        d = expression(buf)
        t = buf.get()
        if t != ')':
            raise ValueError("')' expected")
        return d
    else:
        raise ValueError('primary expected')
 
buf = Buffer(['3','*', '(', '1','+','3', '/', '2', ')'])
print expression(buf)

[guest@localhost rasp]$ ./s2.py
7.5
[guest@localhost rasp]$

в принципе, записал напрямую с его исходника

baslie

Сен. 26, 2012 16:46:59

py.user.next, спасибо большущее! Жаль, конечно, что сам до этого не додумался. Я не до конца понимал, как происходит обработка лексем в цикле, поэтому из цикла возвращал совсем другое.

baslie

Сен. 26, 2012 18:17:57

Немного переписал, работает как надо теперь.

#! /usr/bin/env python
 
#    Expression:
#        Term
#        Expression + Term
#        Expression - Term
#    Term:
#        Primary
#        Term * Primary
#        Term / Primary
#        Term % Primary
#    Primary:
#        Number
#        ( Expression )
#        - Primary
#        + Primary
#    Number:
#        floating-point-literal
 
class Buffer(object):
    def __init__(self, expr):
        self.expr = expr
        self.buffer = []
        self.isset = False
    def get(self):
        if self.isset:
            self.isset = False
        else:
            if len(self.expr) != 0:
                self.buffer = self.expr.pop(0)
        return self.buffer
    def putback(self, val):
        self.isset = True
        self.buffer = val
 
def expression(buf):
    left = term(buf)
    t = buf.get()
    while True:
        if t == '+':
            left += term(buf)
            t = buf.get()
        elif t == '-':
            left -= term(buf)
            t = buf.get()
        else:
            buf.putback(t)
            return left
 
def term(buf):
    left = primary(buf)
    t = buf.get()
    while True:
        if t == '*':
            left *= primary(buf)
            t = buf.get()
        elif t == '/':
            d = primary(buf)
            if d == 0.:
                raise ValueError('divide by zero')
            left /= d
            t = buf.get()
        elif t == '%':
            d = primary(buf)
            if d == 0.:
                raise ValueError('divide by zero')
            left %= d
            t = buf.get()
        else:
            buf.putback(t)
            return left
 
def primary(buf):
    t = buf.get()
    if isInt(t):
        return int(t)
    elif isFloat(t):
        return float(t)
    elif t == '-':
        return - primary(buf)
    elif t == '+':
        return primary(buf)
    elif t == '(':
        d = expression(buf)
        t = buf.get()
        if t != ')':
            raise ValueError("')' expected")
        return d
    else:
        raise ValueError('primary expected')
 
def isdigit(ch):
    for i in ch:
        if not i.isdigit() and i != '.':
            return False
    return True
 
def isFloat(string):
    try:
        float(string)
        return True
    except ValueError:
        return False
 
def isInt(string):
    try:
        int(string)
        return True
    except ValueError:
        return False
 
def parser(expr):
    expr = ''.join(expr.split())
    output = []
    num = ''
    for ch in expr:
        if ch.isdigit() or ch == '.':
            num += ch
        elif ch in ['(', ')', '+', '-', '*', '/', '%']:
            if num:
                output.append(num)
                num = ''
            output.append(ch)
        else:
            raise ValueError("Bad character '" + ch + "'")
    if num:
        output.append(num)
    return output
 
def calc(expr):
    return expression(Buffer(parser(expr)))
 
if __name__ == "__main__":
    exprs = ['(3+2+1+9/2-98*5+7%2)-2+4/2+(((321)-43)-1)/2.',
             '-2-1',
             '(+2-1)/100.0',
             '100.3-2/4.5']
    for e in exprs:
        print "eval()\t" + str(eval(e)) + "\ncalc():\t" + str(calc(e)) + "\n"

Но все-таки как лучше считывать лексемы? Есть другие варианты, кроме list?

py.user.next

Сен. 27, 2012 03:26:44

baslie

elif ch in ['(', ')', '+', '-', '*', '/', '%']:

elif ch in '()+-*/%':

baslie

def isdigit(ch):
    for i in ch:
        if not i.isdigit() and i != '.':
            return False
    return True

что это за функция ?
она две точки воспримет
(parser() тоже одни точки посчитает числом)

baslie

print "eval()\t" + str(eval(e)) + "\ncalc():\t" + str(calc(e)) + "\n"

>>> print "eval():\t{0}\ncalc():\t{1}\n".format(eval(e), calc(e))
eval(): 3
calc(): 3
>>>

baslie
Но все-таки как лучше считывать лексемы? Есть другие варианты, кроме list?

этот список - промежуточное звено, его удобно заполнять из любого источника
есть collections.deque
у Страуструпа используется специальная лексема для возврата, потому что в поток нельзя вернуть её
у тебя же можно вернуть в поток лексему, причём не одну, так как у тебя поток лексем, а не поток символов
(зря ты сделал отдельную переменную для возвращаемой лексемы; то, что было вначале, было лучше)

class Buffer(object):
    def __init__(self, expr):
        self.expr = expr
    def get(self):
        if self.expr:
            return self.expr.pop(0)
    def putback(self, val):
        self.expr.insert(0, val)

class Buffer(list):
    def get(self):
        if self:
            return self.pop(0)
    def putback(self, val):
        self.insert(0, val)
        
class Buffer(list):
    def __init__(self, expr):
        list.__init__(self, expr)
    def get(self):
        if self:
            return self.pop(0)
    def putback(self, val):
        self.insert(0, val)

ещё пара вариантов: один - простой, другой - с возможностью каких-нибудь изменений

>>> class Buffer(list):
...     def __init__(self, expr):
...         list.__init__(self, expr * 2)
...     def get(self):
...         if self:
...             return self.pop(0)
...     def putback(self, val):
...         self.insert(0, val)
... 
>>> buf = Buffer(['10', '+', '20', '*', '30'])
>>> buf
['10', '+', '20', '*', '30', '10', '+', '20', '*', '30']
>>> buf.get()
'10'
>>> buf.get()
'+'
>>> buf
['20', '*', '30', '10', '+', '20', '*', '30']
>>> buf.putback('+')
>>> buf
['+', '20', '*', '30', '10', '+', '20', '*', '30']
>>>

пример изменений

baslie

Сен. 27, 2012 11:49:32

Клево, не знал что так можно

class Buffer(list):
    def get(self):
        if self:
            return self.pop(0)
    def putback(self, val):
        self.insert(0, val)

Тогда вопрос по парсеру (переписал - точки теперь правильно ловит). Можно как-то упростить такую “логику”?

def isint(string):
    try:
        int(string)
        return True
    except ValueError:
        return False
 
def isfloat(string):
    try:
        float(string)
        return True
    except ValueError:
        return False
 
def isnumber(output, num):
    if num:
        if isint(num) or isfloat(num):
            output.append(num)
            num = ''
        else:
            raise ValueError("Bad number '{0}'".format(num))
    return output, num
 
def parser(expr):
    expr = ''.join(expr.split())
    output = []
    num = ''
    for ch in expr:
        if ch in '.0123456789':
            num += ch
        elif ch in '()+-*/%':
            output, num = isnumber(output, num)
            output.append(ch)
        else:
            raise ValueError("Bad character '{0}'".format(ch))
    output, num = isnumber(output, num)
    return output

Не нравится, что в конце снова проверяем num. С whileом будет коряво смотреться мне кажется.

py.user.next

Сен. 27, 2012 14:03:37

def parser(expr):
    expr = ''.join(expr.split())
    output = []
    num = ''
    for ch in expr:
        if ch in '.0123456789':
            if ch == '.' and '.' in num:
                raise ValueError(1)
            num += ch
        elif ch in '()+-*/%':
            if num:
                output.append(num)
                num = ''
            output.append(ch)
        else:
            raise ValueError("Bad character '{0}'".format(ch))
    if num:
        output.append(num)
    return output

add
вариант, не воспринимающий точку как число

def parser(expr):
    expr = ''.join(expr.split())
    output = []
    num = ''
    for ch in expr:
        if ch in '.0123456789':
            if ch == '.' and '.' in num:
                raise ValueError(1)
            num += ch
        elif ch in '()+-*/%':
            if num:
                if num == '.':
                    raise ValueError(2)
                output.append(num)
                num = ''
            output.append(ch)
        else:
            raise ValueError("Bad character '{0}'".format(ch))
    if num:
        if num == '.':
            raise ValueError(2)
        output.append(num)
    return output

add
конечный автомат

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
# разделяет арифметическое выражение на лексемы
 
def f(s):
    res = []
     
    state = 'normal'
     
    i = 0
    slen = len(s)
    while i < slen:
        c = s[i]
        if state == 'normal':
            num = ''
            was_period = False
            if c in '.0123456789':
                state = 'number'
            elif c in '()+-*/%':
                state = 'op'
            else:
                state = 'error'
            i -= 1
        elif state == 'number':
            if c in '0123456789':
                num += c
            elif c == '.':
                if not was_period:
                    was_period = True
                    num += c
                else:    
                    state = 'error'
                    i -= 1
            if c not in '.0123456789' or i + 1 == slen:
                if num != '.':
                    res.append(num)
                    state = 'normal'
                    if i + 1 < slen:
                        i -= 1
                else:
                    state = 'error'
                    i -= 1
        elif state == 'op':
            if c in '()+-*/%':
                res.append(c)
            else:
                state = 'normal'
                i -= 1
        elif state == 'error':
            raise ValueError('wrong character "{0}" '
                             'at index {1}'.format(c, i))
        i += 1
    return res
 
if __name__ == '__main__':
    print f('123.+1.')
    print f('(3+2+1+9/2-98*5+7%2)-2+4/2+(((321)-43)-1)/2.')

[guest@localhost py]$ ./expr.py
['123.', '+', '1.']
['(', '3', '+', '2', '+', '1', '+', '9', '/', '2', '-', '98', '*', '5', '+', '7', '%', '2', ')', '-', '2', '+', '4', '/', '2', '+', '(', '(', '(', '321', ')', '-', '43', ')', '-', '1', ')', '/', '2.']
[guest@localhost py]$

baslie

Сен. 28, 2012 19:10:23

py.user.next, пардон за глупый вопрос ~~гуглить лень~~: это примерно так же регулярки работают? на конечных автоматах?

odnochlen

Сен. 28, 2012 19:39:24

Именно так и работают. Хотя в зависимости от регулярки они компилируются в детерминированный КА, недетерменированный КА и даже машину Тьюринга.

Ну и c in ‘0123456789’ стоило бы заменить на c in set('0123456789'). Там уже на двух элементах разница будет в 2 раза.