Logo Search packages:      
Sourcecode: relational version File versions  Download package

parser.py

# -*- coding: utf-8 -*-
# coding=UTF-8
# Relational
# Copyright (C) 2008  Salvo "LtWorf" Tomaselli
# 
# Relation is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
# 
# author Salvo "LtWorf" Tomaselli <tiposchi@tiscali.it>


RELATION=0
UNARY=1
BINARY=2
b_operators=('*','-','ᑌ','ᑎ','ᐅᐊ','ᐅLEFTᐊ','ᐅRIGHTᐊ','ᐅFULLᐊ')
u_operators=('π','σ','ρ')

op_functions={'*':'product','-':'difference','ᑌ':'union','ᑎ':'intersection','ᐅᐊ':'join','ᐅLEFTᐊ':'outer_left','ᐅRIGHTᐊ':'outer_right','ᐅFULLᐊ':'outer','π':'projection','σ':'selection','ρ':'rename'}

00030 class node (object):
    '''This class is a node of a relational expression. Leaves are relations and internal nodes are operations.
    
    The kind property says if the node is a binary operator, unary operator or relation.
    Since relations are leaves, a relation node will have no attribute for children.
    
    If the node is a binary operator, it will have left and right properties.
    
    If the node is a unary operator, it will have a child, pointing to the child node and a prop containing
    the string with the props of the operation.
    
    This class is used to convert an expression into python code.'''
    kind=None
    
00044     def __init__(self,expression=None):
        '''Generates the tree from the tokenized expression
        If no expression is specified then it will create an empty node'''
        if expression==None or len(expression)==0:
            return
        
        #If the list contains only a list, it will consider the lower level list.
        #This will allow things like ((((((a))))) to work
        while len(expression)==1 and isinstance(expression[0],list): 
                expression=expression[0]
        
        #The list contains only 1 string. Means it is the name of a relation
        if len(expression)==1 and isinstance(expression[0],str): 
            self.kind=RELATION
            self.name=expression[0]
            return
            
        '''Expression from right to left, searching for binary operators
        this means that binary operators have lesser priority than
        unary operators.
        It find the operator with lesser priority, uses it as root of this
        (sub)tree using everything on its left as left parameter (so building
        a left subtree with the part of the list located on left) and doing 
        the same on right.
        Since it searches for strings, and expressions into parenthesis are
        within sub-lists, they won't be found here, ensuring that they will
        have highest priority.'''
        for i in range(len(expression)-1,-1,-1): 
            if expression[i] in b_operators: #Binary operator              
                self.kind=BINARY
                self.name=expression[i]
                self.left=node(expression[:i]) 
                self.right=node(expression[i+1:])
                return
        '''Searches for unary operators, parsing from right to left'''
        for i in range(len(expression)-1,-1,-1):
            if expression[i] in u_operators: #Unary operator
                self.kind=UNARY
                self.name=expression[i]
                self.prop=expression[1+i].strip()
                self.child=node(expression[2+i])
                
                return       
        pass
00088     def toPython(self):
        '''This method converts the expression into python code, which will require the
        relation module to be executed.'''
        if self.name in b_operators:
            return '%s.%s(%s)' % (self.left.toPython(),op_functions[self.name],self.right.toPython())
        elif self.name in u_operators:
            prop =self.prop
            
            #Converting parameters
            if self.name=='π':#Projection
                prop='\"%s\"' %  prop.replace(' ','').replace(',','\",\"')
            elif self.name=="ρ": #Rename
                prop='{\"%s\"}' % prop.replace(',','\",\"').replace('➡','\":\"').replace(' ','')
            else: #Selection
                prop='\"%s\"' %  prop
                        
            return '%s.%s(%s)' % (self.child.toPython(),op_functions[self.name],prop)
        else:
            return self.name
        pass
00108     def result_format(self,rels):
        '''This function returns a list containing the fields that the resulting relation will have.
        Since it needs to know real instances of relations, it requires a dictionary where keys are
        the names of the relations and the values are the relation objects.'''
        if rels==None:            
            return
        
        if self.kind==RELATION:
            return list(rels[self.name].header.attributes)
        elif self.kind==BINARY and self.name in ('-','ᑌ','ᑎ'):
            return self.left.result_format(rels)
        elif self.name=='π':
            l=[]
            for i in self.prop.split(','):
                l.append(i.strip())
            return l
        elif self.name=='*':
            return self.left.result_format(rels)+self.right.result_format(rels)
        elif self.name=='σ' :
            return self.child.result_format(rels)
        elif self.name=='ρ':
            _vars={}
            for i in self.prop.split(','):
                q=i.split('➡')
                _vars[q[0].strip()]=q[1].strip()
            
            _fields=self.child.result_format(rels)
            for i in range(len(_fields)):
                if _fields[i] in _vars:
                    _fields[i]=_vars[_fields[i]]
            return _fields
        elif self.name in ('ᐅᐊ','ᐅLEFTᐊ','ᐅRIGHTᐊ','ᐅFULLᐊ'):
            return list(set(self.left.result_format(rels)).union(set(self.right.result_format(rels))))
    def __eq__(self,other):
        if not (isinstance(other,node) and self.name==other.name and self.kind==other.kind):
            return False
        
        if self.kind==UNARY:
            if other.prop!=self.prop:
                return False
            return self.child==other.child
        if self.kind==BINARY:
            return self.left==other.left and self.right==other.right
        return True
    def __str__(self):
        if (self.kind==RELATION):
            return self.name
        elif (self.kind==UNARY):
            return self.name + " "+ self.prop+ " (" + self.child.__str__() +")"
        elif (self.kind==BINARY):
            if self.left.kind==RELATION:
                le=self.left.__str__()
            else:
                le="("+self.left.__str__()+")"
            if self.right.kind==RELATION:
                re=self.right.__str__()
            else:
                re="("+self.right.__str__()+")"
                
            return (le+ self.name +re)

def find_matching_parenthesis(expression,start=0):
    '''This function returns the position of the matching
    close parenthesis to the 1st open parenthesis found
    starting from start (0 by default)'''
    par_count=0 #Count of parenthesis
    for i in range(start,len(expression)):
        if expression[i]=='(':
            par_count+=1
        elif expression[i]==')':
            par_count-=1
            if par_count==0:
                return i #Closing parenthesis of the parameter

def tokenize(expression):
    '''This function converts an expression into a list where
    every token of the expression is an item of a list. Expressions into
    parenthesis will be converted into sublists.'''
    items=[] #List for the tokens
    
    '''This is a state machine. Initial status is determined by the starting of the
    expression. There are the following statuses:
    
    relation: this is the status if the expressions begins with something else than an
        operator or a parenthesis.
    binary operator: this is the status when parsing a binary operator, nothing much to say
    unary operator: this status is more complex, since it will be followed by a parameter AND a
        sub-expression.
    sub-expression: this status is entered when finding a '(' and will be exited when finding a ')'.
        means that the others open must be counted to determine which close is the right one.'''
    
    expression=expression.strip() #Removes initial and endind spaces
    state=0
    '''
    0 initial and useless
    1 previous stuff was a relation
    2 previous stuff was a sub-expression
    3 previous stuff was a unary operator
    4 previous stuff was a binary operator
    '''

    while len(expression)>0:
        if expression.startswith('('): #Parenthesis state
            state=2
            end=find_matching_parenthesis(expression)
            #Appends the tokenization of the content of the parenthesis
            items.append(tokenize(expression[1:end]))
            #Removes the entire parentesis and content from the expression
            expression=expression[end+1:].strip()
        
        elif expression.startswith("σ") or expression.startswith("π") or expression.startswith("ρ"): #Unary 2 bytes
            items.append(expression[0:2]) #Adding operator in the top of the list
            expression=expression[2:].strip() #Removing operator from the expression
            
            if expression.startswith('('): #Expression with parenthesis, so adding what's between open and close without tokenization
                par=expression.find('(',find_matching_parenthesis(expression)) 
            else: #Expression without parenthesis, so adding what's between start and parenthesis as whole  
                par=expression.find('(')
            
            items.append(expression[:par].strip()) #Inserting parameter of the operator
            expression=expression[par:].strip() #Removing parameter from the expression
        elif expression.startswith("*") or expression.startswith("-"): # Binary 1 byte
            items.append(expression[0])
            expression=expression[1:].strip() #1 char from the expression
            state=4
        elif expression.startswith("ᑎ") or expression.startswith("ᑌ"): #Binary short 3 bytes
            items.append(expression[0:3]) #Adding operator in the top of the list
            expression=expression[3:].strip() #Removing operator from the expression

            state=4
        elif expression.startswith("ᐅ"): #Binary long
            i=expression.find("ᐊ")
            items.append(expression[:i+3])
            expression=expression[i+3:].strip()
            
            state=4
        else: #Relation (hopefully)
            if state==1: #Previous was a relation, appending to the last token
                i=items.pop()
                items.append(i+expression[0])
                expression=expression[1:].strip() #1 char from the expression
            else:
                state=1
                items.append(expression[0])
                expression=expression[1:].strip() #1 char from the expression
    
    return items

def tree(expression):
    '''This function parses a relational algebra expression into a tree and returns
    the root node using the Node class defined in this module.'''
    return node(tokenize(expression))



def parse(expr):
    '''This function parses a relational algebra expression, converting it into python, 
    executable by eval function to get the result of the expression.
    It has 2 class of operators:
    without parameters
    *, -, ᑌ, ᑎ, ᐅᐊ, ᐅLEFTᐊ, ᐅRIGHTᐊ, ᐅFULLᐊ
    with parameters:
    σ, π, ρ
    
    Syntax for operators without parameters is:
    relation operator relation
    
    Syntax for operators with parameters is:
    operator parameters (relation)
    
    Since a*b is a relation itself, you can parse π a,b (a*b).
    And since π a,b (A) is a relation, you can parse π a,b (A) ᑌ B.
    
    You can use parenthesis to change priority: a ᐅᐊ (q ᑌ d).
    
    IMPORTANT: The encoding used by this module is UTF-8
    
    EXAMPLES
    σage > 25 and rank == weight(A)
    Q ᐅᐊ π a,b(A) ᐅᐊ B
    ρid➡i,name➡n(A) - π a,b(π a,b(A)) ᑎ σage > 25 or rank = weight(A)
    π a,b(π a,b(A))
    ρid➡i,name➡n(π a,b(A))
    A ᐅᐊ B
    '''
    return tree(expr).toPython()
    
if __name__=="__main__":
    while True:
        e=raw_input("Expression: ")
        print parse(e)

Generated by  Doxygen 1.6.0   Back to index