Python pyparsing: grammar implementation for parsing AND logical expression

I am trying to analyze and evaluate the expressions given to me as data from a file, form:

var[3] = 0 and var[2] = 1 var[0] = 1 and var[2] = 0 and var[3] = 1 ... 

(in fact, I also allow "multi-bit access" (ie var[X:Y] ), but not ignore it yet ...)
Where var is an integer and [] is a bit. For example, for var = 0x9 first expression above should be evaluated as False , and the second should be evaluated to True with 0x9 = b1001 .
and and = are the only binary operators that I allow, and for the = operator, the left operand is always var[X] , and the right operand is always a number.
I tried to look pyparsing bit and found that this could be achieved using Python pyparsing , but I ran into some difficulties trying to implement it.
Here is what I have tried so far, based roughly on this example (which is one of many examples here ):

 #!/usr/bin/env python from pyparsing import Word, alphas, nums, infixNotation, opAssoc class BoolAnd(): def __init__(self, pattern): self.args = pattern[0][0::2] def __bool__(self): return all(bool(a) for a in self.args) __nonzero__ = __bool__ class BoolEqual(): def __init__(self, pattern): self.bit_offset = int(pattern[0][1]) self.value = int(pattern[0][-1]) def __bool__(self): return True if (0xf >> self.bit_offset) & 0x1 == self.value else False # for now, let assume var == 0xf __nonzero__ = __bool__ variable_name = 'var' bit_access = variable_name + '[' + Word(nums) + ']' multibit_access = variable_name + '[' + Word(nums) + ':' + Word(nums) + ']' value = Word(nums) operand = bit_access | multibit_access | value expression = infixNotation(operand, [ ('=', 2, opAssoc.LEFT, BoolEqual), ('AND', 2, opAssoc.LEFT, BoolAnd), ]) p = expression.parseString('var[3] = 1 AND var[1] = 0', True) print 'SUCCESS' if bool(p) else 'FAIL' 

I have three problems that I need help with.

  • For multi-bit access to the form var[X:Y] = Z , how can I ensure that this is done:
    a. X > Y
    b. Z < 2^{X - Y + 1}
    I assume that this cannot be implemented by the grammar itself (for example, for single-bit access of the form var[X] = Y , I can ensure that the grammar is respected, that Y will be either 0 or 1 , and this will result in expression.parseString() will fail if Y != 0/1 ).
  • Most importantly: why does he always print SUCCESS ? What am I doing wrong?
    To enter var[3] = 1 AND var[1] = 0 it must be printed FAIL (in my example, you can see that I am hard-coded var as 0xf , so var[3] = 1 is True , but var[1] = 0 is False ).
  • Which leads me to my third problem: var not a member of the BoolEqual class and is not global ... is there a way to somehow send it to the BoolEqual __init__ function?
+5
source share
2 answers

Before moving on to solving the problem, I suggest some minor changes to your grammar, especially the inclusion of result names. Adding these names will make your resulting code cleaner and more reliable. I also use some expressions that were added in recent versions of pyparsing, in the pyparsing_common namespace pyparsing_common :

 from pyparsing import pyparsing_common variable_name = pyparsing_common.identifier.copy() integer = pyparsing_common.integer.copy() bit_access = variable_name('name') + '[' + integer('bit') + ']' multibit_access = variable_name('name') + '[' + integer('start_bit') + ':' + integer('end_bit') + ']' 

Part 1a: Executing Valid Values ​​in "var [X: Y]"

This type of work is best used using actions and parsing conditions. Parse actions are time parser callbacks that you can attach to pyparsing expressions to modify, improve, filter results, or raise an exception if the validation rule fails. They are attached using the method:

 expr.addParseAction(parse_action_fn) 

And parse_action_fn can have any of the following signatures:

 def parse_action_fn(parse_string, parse_location, matched_tokens): def parse_action_fn(parse_location, matched_tokens): def parse_action_fn(matched_tokens): def parse_action_fn(): 

(For more, see https://pythonhosted.org/pyparsing/pyparsing.ParserElement-class.html#addParseActio)n )

Analysis actions can return None, return new tokens, modify specified tokens, or throw an exception.

If all parsing actions are performed, some condition based on input tokens is evaluated, you can write it as a simple function that returns True or False, and pyparsing will throw an exception if False is returned. In your case, your first validation rule can be implemented as:

 def validate_multibit(tokens): return tokens.end_bit > tokens.start_bit multibit_access.addCondition(validate_multibit, message="start bit must be less than end bit", fatal=True) 

Or even as a function of a Python lambda function:

 multibit_access.addCondition(lambda t: t.end_bit > t.start_bit, message="start bit must be less than end bit", fatal=True) 

Now you can try the following:

 multibit_access.parseString("var[3:0]") 

And you will get this exception:

 pyparsing.ParseFatalException: start bit must be less than end bit (at char 0), (line:1, col:1) 

Part 1b: Providing Valid Values ​​in "var [X: Y] = Z"

The second rule of verification concerns not only var bit ranges, but also the value with which it is compared. To do this, you need to perform parsing, which will be tied to the full BoolEqual. We could put this in the BoolEqual __init__ method, but if possible, I prefer to separate independent functions separately. And since we will add our validation by joining the infixNotation level, and infixNotation accepts only parsing actions, we will need to write our second validation rule as a parsing action that throws an exception. (We will also use a new feature that was recently released in pyparsing 2.2.0, adding a few parsing actions at the infixNotation level.)

Here is the confirmation we want to complete:

  • if a single bit expression, the value must be 0 or 1
  • if the multibyte expression is var [X: Y], the value must be <2 ** (YX + 1)

      def validate_equality_args (tokens):
         tokens = tokens [0]
         z = tokens [-1]
         if 'bit' in tokens:
             if z not in (0,1):
                 raise ParseFatalException ("invalid equality value - must be 0 or 1")
         else:
             x = tokens.start_bit
             y = tokens.end_bit
             if not z <2 ** (y - x + 1):
                 raise ParseFatalException ("invalid equality value") 

And we attach this parsing action to infixNotation using:

 expression = infixNotation(operand, [ ('=', 2, opAssoc.LEFT, (validate_equality_args, BoolEqual)), ('AND', 2, opAssoc.LEFT, BoolAnd), ]) 

Part 3: Support for other var names and values ​​than 0xf

To deal with vars of different names, you can add level dictation to BoolEqual:

 class BoolEqual(): var_names = {} 

and set this in advance:

 BoolEqual.var_names['var'] = 0xf 

And then implement your __bool__ method as soon as:

return (self.var_names[self.var_name] >> self.bit_offset) & 0x1 == self.value

(This will need to be expanded to support multi-line, but the general idea is the same.)

+3
source

How to convert a variable to a list of 1 and 0 and use eval to evaluate Boolean expressions (with a slight modification, changing = to ==):

 def parse(lines, v): var = map(int,list(bin(v)[2:])) result = [] for l in lines: l = l.replace('=','==') result.append(eval(l)) return result inp = \ """ var[3] = 0 and var[2] = 1 var[0] = 1 and var[2] = 0 and var[3] = 1 """ lines = inp.split('\n')[1:-1] v = 0x09 print parse(lines, v) 

Output:

 [False, True] 

Note that you should only use eval if you trust this input.

0
source

Source: https://habr.com/ru/post/1266063/


All Articles