parsing binary expressions in javascript

Parsing binary expressions can be achieved through constructing an Abstract Syntax Tree (AST) using recursive descent parsing.

Here's an example implementation:


index.tsx
function parseExpression(tokens) {
  let current = 0;
  
  function walk() {
    let token = tokens[current];
    
    // handle number literals
    if (token.type === 'number') {
      current++;
      return { type: 'NumberLiteral', value: token.value }
    }
    
    // handle binary expressions
    if (token.type === 'paren' && token.value === '(') {
      token = tokens[++current];
      
      let node = {
        type: 'BinaryExpression',
        operator: token.value,
        left: null,
        right: null
      }
      
      token = tokens[++current];
      node.left = walk();
      
      token = tokens[++current];
      node.right = walk();
      
      token = tokens[++current];
      
      return node;
    }
    
    throw new TypeError('Unknown token type: ' + token.type);
  }
  
  let ast = {
    type: 'Program',
    body: []
  };
  
  while (current < tokens.length) {
    ast.body.push(walk());
  }
  
  return ast;
}
950 chars
49 lines

This function expects an array of tokens as an argument and returns an abstract syntax tree representing the expression. The method leverages recursion through the walk() function to create nodes and handle binary operations.

To use this parser, one would first tokenize an input expression (using a tokenizer or elsewhere), and then pass the token array to the parseExpression() function:


index.tsx
const tokens = [
  { type: 'paren', value: '(' },
  { type: 'number', value: '5' },
  { type: 'operator', value: '+' },
  { type: 'number', value: '2' },
  { type: 'paren', value: ')' }
];

const ast = parseExpression(tokens);

console.log(ast);
/*
  output:
  {
    type: 'Program',
    body: [{
      type: 'BinaryExpression',
      operator: '+',
      left: { type: 'NumberLiteral', value: '5' },
      right: { type: 'NumberLiteral', value: '2' },
    }]
  }
*/
467 chars
24 lines

similar javascript code snippets

create a function that takes in 3 arguments in javascript

find the sum of all values in a map in javascript

add two numbers in javascript

state in javascript

créate a funnxtu in javascript

steam autg in javascript

asdas in javascript

find the sum of a list of numbers in javascript

find the sum of all elements in an array in javascript

define a function that takes a list of numbers as an argument and returns the sum of the numbers in the list. in javascript

related categories

recursive-descent-parsing