javascriptparsinggrammarabstract-syntax-treepegjs

PEGJS: How to add NOT (!) logical operator to grammar that parses AND (&&) OR (||) logic statements


I'm very new to writing grammars (first time ever to be exact) and I'd like to create a grammar that can return an AST for basic logic statements. So far I have a grammar that can handle AND, OR logic (I simply modified the basic calculator example from the official pegjs site). Here is what the grammar currently does:

The statement

item1 && item2

Returns the AST

{
   "type": "AND",
   "left": "item1",
   "right": "item2"
}

The statement:

(item1 || item2) && item3

Returns the AST

{
   "type": "AND",
   "left": {
      "type": "OR",
      "left": "item1",
      "right": "item2"
   },
   "right": "item3"
}

Here is the grammar that I have so far. It can be pasted directly into the online pegjs parser (http://pegjs.majda.cz/online).

start
  = logical_or

logical_or
  = left:logical_and ws+ "||" ws+ right:logical_or { return {type: "OR", left:left, right:right} }
  / logical_and

logical_and
  = left:primary ws+ "&&" ws+ right:logical_and { return {type: "AND", left:left, right:right} }
  / primary

primary
  = token
  / "(" logical_or:logical_or ")" { return logical_or; }

token 
  = token:[a-zA-Z0-9_]+ { return token.join(""); }

ws 
  = [ \t]

What I'd like to do is add support for the NOT operator (!). So for example I'd like to be able to parse the following statements:

item1 && !item2
!(item1 && item2 && item3)

My first question is how do you typically represent the NOT operator in an AST? It seems like the not operator can be applied to an entire left or right branch of the AST but unlike OR and AND will not have both a left and right branch.

The second question is how do you support a NOT operator in a PEGJS grammar?

Thank you very much for your time!

Edit: Fixed the AST representation


Solution

  • You just need to introduce a layer between "AND" and "primary":

    logical_and
      = left:factor ws+ "&&" ws+ right:logical_and { return {type: "AND", left:left, right:right} }
      / factor
    
    factor
      = "!" ws* operand:factor { return {type: "NOT", operand: operand } }
      / primary
    

    Since ! is a unary operator, "left" and "right" don't really make sense; I used "operand".