Create AST from logical expression

Question

I want to convert

((a v b) ^ c) v e -> c

into

[
    'implication'
    [
        'or',
        [
            'and',
            [
                'or',
                'a',
                'b'
            ],
            'c'
        ],
        'e'
    ],
    'c'
]

How is this possible?

I guess I should start by defining some operators (and operator type corresponds to the operator symbol)

var operators = {
  'v' : 'or',
  '^' : 'and',
  '->': 'implication'
};

and then traverse the string

// string
var infix = '((a v b) ^ c) v e -> c';

// remove spaces, so infix[i]!=" "
infix = infix.replace(/\s+/g, '');

// traverse through string
for (let i=0; i<infix.length; i++) {
  // get token
  var token = infix[i];

  // if token is an operator
  if (operators.indexOf(token) !== -1) {
    (...)
  }
  // if token is parenthesis
  else if (token === '(') {
    (...)
  }

  (...)
}

but I don't know how to get further than this.

I guess the tree structured array will be done using something like

expression = [operators[token], expression];

so the expression is preserved but on a nested level in the array.

Read up on the [Shunting-yard algorithm.](https://en.wikipedia.org/wiki/Shunting-yard_algorithm) — Mike Cluck, Sep 09 '16 at 17:03
But it gives me the result in postfix. How can I then convert it to the nested array — Jamgreen, Sep 09 '16 at 18:02
The point is that it will parse it based on precedence. It's trivial from there to put it into a nested array. Anytime you finish parsing a given operator and it's operands, you put them into an array. You do that recursively. — Mike Cluck, Sep 09 '16 at 19:20
Unless this is a school project intended to teach parsing theory (in which case I would have expected there to have been more guidance), your best bet would be to use jison. Just adapt a standard arithmetic parser with your logical operators. And don't ask the same question here repeatedly. — rici, Sep 09 '16 at 19:53

score 0 · Answer 1 · edited May 23 '17 at 10:33

0

See my SO answer on how to write a parser.

Using this, you can parse the expression, and spit out code as you parse the expression. You can generate postfix easily this way.

If you want to generate prefix code, then you have have a way to avoid doing output until at least the time you encounter the prefix operation. To do this, parse the expression and build a tree; then walk the tree in prefix order and spit out the result.

edited May 23 '17 at 10:33

Community

1
1

answered Sep 09 '16 at 18:31

Ira Baxter

93,541
22
172
341

I have already read your answer, but I am afraid I don't understand it. I don't understand the code snippets nor how it is possible to use it for simple propositional logic. I guess my BNF language is defined as `p ::= p | ~p | ^ | v | -> | <->`, but I don't know how to use it with your examples – Jamgreen Sep 09 '16 at 18:39
1

Your BNF isn't sane. For one thing, it doesn't show how operands relate to operators. Usually expression languages allow parentheses; yours does not and that seems suspicious. Go find an example of a small expression langauge, rewrite yours and come back with another definition. If you want help defining your BNF, start another SO question. – Ira Baxter Sep 09 '16 at 19:26

Create AST from logical expression

1 Answers1