lab34.py

 logging
from functools import partial

if __name__ == '__main__':
  print '''
Программа работает из интерактивной сесии (REPL'а):
>>> from lab34 import *

есть два разборщика, lab3 и lab4. 
пользоваться так:

>>> lab3('a+a*(a*a)')
True
>>> lab3('a+a*(a*a))')
False
>>> lab4('101+(11001*10101)')
530
'''






#### parse_rules
# Сигнатура: string -> dict of arrays of strings.
# Зачем? Чтобы не забивать все правила подстановки вручную.
# ex.: 
# '''
# x->y | yy
# y->z''' -> {'z':'y', 'y':'x', 'yy':'x'}
#
def parse_rules(textual_rules):
  lines = textual_rules.split('\n')[1:-1]
  split_lines = [l.split('->') for l in lines]
  rules_dict = {}
  for l in split_lines:
    for rhs in l[1].split(' | '):
      rules_dict[rhs] = l[0]
  return rules_dict

Rules_3_raw = """
E->E+T | T
T->T*F | F
F->(E) | a
"""

Rules_4_raw = """
E->E+T | T
T->T*F | F
F->(E) | N
N->N1 | N0 | 1
"""

#### split_row_into_cells_by_column_headers:
#Вспомогательная функция для разбора таблицы предшествования
def split_row_into_cells(column_headers, row):
  r = row+' '
  cells = []
  for i in range(len(column_headers)):
    cells.append(r[i*3:i*3+3])
  named_cells = dict(zip(column_headers, cells))
  return named_cells
#### parse_precedence_table
# Сигнатура: string -> dict of dicts
# Зачем? Чтобы не перенабирать всю огромную таблицу вручную.
# example: 
# '''
# * | 0  1
# __|_____
# 0 | 0  0   
# 1 | 0  1'''  ->  {0:{0:0, 1:0}, 1:{0:0, 1:1}}
def parse_precedence_table(textual_table):
  # первый столбец — оглавление, следущие два — декорации
  # аналогично со строками
  # ячейки имеют по три клетки в ширину, одну в высоту; последняя ячейка — 2x1
  lines = textual_table.split('\n')
  column_headers = lines[1][4:].split('  ')
  row_headers = [row[0] for row in lines[3:]]
  # rows are arrays of cells
  rows = [line[3:] for line in lines[3:]]
  outer_dictionary = dict(zip(row_headers, map(partial(split_row_into_cells, column_headers), rows)))
  return outer_dictionary
  #return column_headers, row_headers, rows
#### a quick test of partial application:
  
Precedence_Table_3_raw = '''
  | E  T  F  a  (  )  +  *  #
__|__________________________
E |                =  =      
T |                >  >  =  >
F |                >  >  >  >
a |                >  >  >  >
) |                >  >  >  >
( |<=  <  <  <  <            
+ |    <= <  <  <            
* |       =  <  <            
# | <  <  <  <  <            '''

Precedence_Table_4_raw = '''
  | E  T  F  N  0  1  (  )  +  *  #
__|________________________________ 
E |                      =  =      
T |                      >  >  =  >
F |                      >  >  >  >
N |             <= <=    >  >  >  >
0 |             >  >     >  >  >  >
1 |             >  >     >  >  >  >
) |                      >  >  >  >
( |<=  <  <  <     <  <            
+ |    <= <  <     <  <            
* |       =  <     <  <            
# | <  <  <  <     <  <            '''

T3, R3 = parse_precedence_table(Precedence_Table_3_raw), parse_rules(Rules_3_raw)
T4, R4 = parse_precedence_table(Precedence_Table_4_raw), parse_rules(Rules_4_raw)

#### lab2
# Contract: Expression -> boolean


#### lab3
# Contract: lab3: Expression -> boolean
# Purpose: Обработать строку алгоритмом переноса и свертки используя готовую ТП.
# Examples: lab3(a+a) -> True
#           lab3(a+(a*a)) -> True
#           lab3(a) -> True
#           lab3((a)) -> True
#           lab3(E) -> False
#           lab3(aaa) -> False
#           lab3(a+F) -> False
#           lab3(FT+E) -> False

class Validator3:
  def __init__(self, s, T, R):
    self.m, self.s, self.p, self.T, self.R, self.a = "#", s+"#", 0, T, R, [0]*(len(s)+1)
  def __call__(self, expr):
    
    return self.validate(expr)

  def prover(self):
    if self.m == "#E" and self.p == (len(self.s) - 1):
#      print 'проверка прошла'
      self.FINISH()
      return True
    else:
      print 'некорректное выражение'
      self.REPORT()
      return False
  
  def perenesi(self):
    self.m += (self.s[self.p])
    self.p += 1
  
  def sverni(self):
             #список длин правых сторон правил по убыванию:
    for i in sorted(list(set(map(len,self.R.keys()))))[::-1]: 
      head, tail = self.m[:-i], self.m[-i:]
      if tail in self.R:
        self.m = head + self.R[tail]
        return True # произошла замена
    return False # не нашлось замены

  def step(self):
    if '<' in self.lookup():
      self.perenesi()
    elif '=' in self.lookup():
      self.perenesi()
    if '>' in self.lookup():
      if not self.sverni():
        return False
      

    elif self.lookup() == '   ':
      return self.prover()
    self.REPORT()
    return self.step()

  def lookup(self):
    return self.T[self.m[-1]][self.s[self.p]]
  def REPORT(self):
  #    print 'm: [', self.m, (len(self.s) - len(self.m))*' ', ']\t p:', self.p, self.lookup(), '|'
    pass
 
  def GREET(self):
    #print 'проверяю выражение', self.s
    pass
 
  def FINISH(self):
    print 'выражение', self.s[:-1], 'корректно.'

  def validate(self, expression):
    self.i = 0
    self.m, self.s, self.p, self.a = "#", expression+"#", 0, [0]*(1+len(expression))
    self.GREET()
    for c in list(set(self.s)):
      if not c in self.T.keys():
        print 'выражение содержит недопустимый символ', c
        return False
    if 'E' in self.s or 'F' in self.s or 'T' in self.s:
      print 'выражение содержит нетерминалы'
      return False
    return self.step()

lab3 = Validator3('a+a*(a+a)', T3, R3)

#### lab4
# Сигнатура: lab4: string -> int
# Назначение: Получить число в результате переноса и свертки выражения по ТП
# ex.: lab4(101+11) -> 1000
# Example: lab4(101+11*(1001+101)) -> 1110000

class Validator4(Validator3):
  def __call__(self, expr):
    return self.reduce(expr)