Created
December 6, 2011 23:24
-
-
Save marchdown/1440558 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python | |
# -*- coding: utf-8 -*- | |
import sys#, re, 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) | |
# def __init__(self, s, T, R): | |
# self.m, self.s, self.p, self.T, self.R, a = "#", s+"#", 0, T, R, [] | |
def perenesi(self): | |
self.m += (self.s[self.p]) | |
self.p += 1 | |
if self.m[-1] in '+*': | |
self.i += 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: | |
i = self.i | |
# print '!свертка m:[',self.m,']\t', tail, '->', self.R[tail], '\ti:', i | |
self.m = head + self.R[tail] | |
if tail == '1': | |
self.a[i] = 1 # инициализировать новую ячейку. Это начало числа. | |
# перед ним могли быть другие числа, отделенные + или * | |
# следовательно, нужно увеличить индекс при переносе + или * | |
# на стек, и уменишить при свертке + или *. | |
if tail == 'N1': | |
self.a[i] *= 2 | |
self.a[i] += 1 | |
if tail == 'N0': | |
self.a[i] *= 2 | |
if tail == 'E+T': | |
self.i -=1 | |
i -= 1 | |
self.a[i] = self.a[i]+self.a[i+1] | |
if tail == 'T*F': | |
self.i -=1 | |
i -= 1 | |
self.a[i] = self.a[i]*self.a[i+1] | |
return True # произошла замена | |
return False # не нашлось замены | |
def REPORT(self): | |
# print 'm: [', self.m, (len(self.s) - len(self.m))*' ', ']\t p:', self.p, '\ta:', self.a | |
pass | |
def reduce(self, expression): | |
if self.validate(expression): | |
print 'выражение', expression, 'имеет значение', self.a[0] | |
return self.a[0] | |
else: | |
return False | |
lab4 = Validator4('101+11*(1001+101)',T4, R4) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment