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
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".