Here is a JS parser for a simple language we use at work. For now it can only parse arithmetic expressions. I would like to make sure I am on the right track before starting with the other constructs, as I've never done that before.
One point in particular: I don't really like my withPar hack to reject expressions like '1)', is there a better solution without making the grammar obscure?
const REG_STR = /".*?"/;
const REG_VAR = /\{.+?\}/;
const REG_NUM = /\d+/;
const REG_FCT = /[A-Za-z_]\w*/;
const REG_SPACE = /\s+/;
const keyWords = ['si', 'alors', 'ssi', 'sinon', 'et', 'ou', 'in'];
let tokDef = [
{ id: 'TOK_STR', pattern: REG_STR, withVal: true, transfoVal: val => val.slice(1, -1) },
{ id: 'TOK_VAR', pattern: REG_VAR, withVal: true, transfoVal: val => val.slice(1, -1) },
{ id: 'TOK_NUM', pattern: REG_NUM, withVal: true, transfoVal: val => Number(val) },
{ id: 'TOK_FCT', pattern: REG_FCT, withVal: true, checkVal: val => !keyWords.includes(val) },
{ id: 'TOK_SPACE', pattern: REG_SPACE, ignore: true },
{ id: 'TOK_ELSE', pattern: 'sinon' },
{ id: 'TOK_IF', pattern: 'si' },
{ id: 'TOK_THEN', pattern: 'alors' },
{ id: 'TOK_ELSEIF', pattern: 'ssi' },
{ id: 'TOK_AND', pattern: 'et' },
{ id: 'TOK_OR', pattern: 'ou' },
{ id: 'TOK_EQ', pattern: '=' },
{ id: 'TOK_NEQ', pattern: '#' },
{ id: 'TOK_LE', pattern: '<=' },
{ id: 'TOK_LT', pattern: '<' },
{ id: 'TOK_GE', pattern: '>=' },
{ id: 'TOK_GT', pattern: '>' },
{ id: 'TOK_INCR', pattern: '++' },
{ id: 'TOK_ADD', pattern: '+' },
{ id: 'TOK_DECR', pattern: '--' },
{ id: 'TOK_SUB', pattern: '-' },
{ id: 'TOK_MUL', pattern: '*' },
{ id: 'TOK_DIV', pattern: '/' },
{ id: 'TOK_PAR_OPEN', pattern: '(' },
{ id: 'TOK_PAR_CLOSE', pattern: ')' },
{ id: 'TOK_TERN_1', pattern: '?' },
{ id: 'TOK_TERN_2', pattern: ':' },
{ id: 'TOK_IN', pattern: 'in' },
{ id: 'TOK_COMMA', pattern: ',' }
];
tokDef.forEach(elt => this[elt.id] = elt.id);
let tokenize = str => {
let res = [];
let pos = 0;
let match = tok => {
let matched = false;
let sub = str.substring(pos);
let oldPos = pos;
let val;
if (tok.pattern instanceof RegExp) {
let m = sub.match(tok.pattern);
if (m !== null && m.index === 0) {
val = m[0];
pos += m[0].length;
matched = true;
}
}
else if (sub.startsWith(tok.pattern)) {
val = tok.pattern;
pos += tok.pattern.length;
matched = true;
}
if (matched && !tok.ignore) {
if (tok.withVal) {
tok.transfoVal && (val = tok.transfoVal(val));
tok.checkVal && (matched = tok.checkVal(val));
matched ? res.push({ tok: tok.id, val }) : (pos = oldPos);
}
else {
res.push({ tok: tok.id });
}
}
return matched;
}
while (pos < str.length) {
for (let i = 0; i < tokDef.length; i++) {
if (match(tokDef[i])) break;
}
}
return res;
}
let parse = str => {
let list = tokenize(str);
let pos = -1;
let peek = () => list[pos + 1] || { tok: null };
let next = () => list[++pos] || { tok: null };
let fail = () => {
throw 'parse error at ' + pos;
};
// Expr -> Term ({+,-} Term)*
let parseExpr = withPar => {
let term = parseTerm();
while (true) {
let op = peek().tok === TOK_ADD ? 'add' : (peek().tok === TOK_SUB ? 'sub' : null);
if (op) {
next();
let term2 = parseTerm();
term = { op: op, left: term, right: term2 };
}
else if (peek().tok === TOK_PAR_CLOSE) {
return withPar ? term : fail();
}
else if (peek().tok === null) {
return term;
}
else fail();
}
};
// Term -> Fact ({+,-} Fact)*
let parseTerm = () => {
let fact = parseFact();
while (true) {
let op = peek().tok === TOK_MUL ? 'mul' : (peek().tok === TOK_DIV ? 'div' : null);
if (op) {
next();
let fact2 = parseFact();
fact = { op: op, left: fact, right: fact2 };
}
else {
return fact;
}
}
};
// Fact -> num | -num | (Expr)
let parseFact = () => {
if (peek().tok === TOK_NUM) {
return next().val;
}
else if (peek().tok === TOK_SUB) {
next();
if (peek().tok === TOK_NUM)
return -next().val;
else fail();
}
else if (peek().tok === TOK_PAR_OPEN) {
next();
let expr = parseExpr(true);
if (peek().tok === TOK_PAR_CLOSE) {
next();
return expr;
}
else {
fail();
}
}
else {
fail();
}
}
return parseExpr();
}
I test it using the reply from Ray Toal to this thread: https://stackoverflow.com/a/6881218/3262284 With a slight modification to have some unary minus:
from random import random, randint, choice
class Expression:
pass
class Number(Expression):
def __init__(self, num):
self.num = num
def __str__(self):
return str(self.num)
class BinaryExpression(Expression):
def __init__(self, left, op, right):
self.left = left
self.op = op
self.right = right
def __str__(self):
return str(self.left) + " " + self.op + " " + str(self.right)
class ParenthesizedExpression(Expression):
def __init__(self, exp):
self.exp = exp
def __str__(self):
return "(" + str(self.exp) + ")"
def randomExpression(prob, nonNeg):
p = random()
if p > prob:
return Number(randint((1 if nonNeg else -100), 100))
elif randint(0, 1) == 0:
return ParenthesizedExpression(randomExpression(prob / 1.2, False))
else:
left = randomExpression(prob / 1.2, False)
op = choice(["+", "-", "*", "/"])
right = randomExpression(prob / 1.2, True)
return BinaryExpression(left, op, right)
for i in range(10):
print(randomExpression(1, False))
Examples with generated expressions:
parse('(-51 * 21 / 41 - (82 + 58 - (5 - 19) / 74) * -71 * 37 - (-11) / -25 / 50) + (14)')
Gives:
{
"op":"add",
"left":{
"op":"sub",
"left":{
"op":"sub",
"left":{
"op":"div",
"left":{
"op":"mul",
"left":-51,
"right":21
},
"right":41
},
"right":{
"op":"mul",
"left":{
"op":"mul",
"left":{
"op":"sub",
"left":{
"op":"add",
"left":82,
"right":58
},
"right":{
"op":"div",
"left":{
"op":"sub",
"left":5,
"right":19
},
"right":74
}
},
"right":-71
},
"right":37
}
},
"right":{
"op":"div",
"left":{
"op":"div",
"left":-11,
"right":-25
},
"right":50
}
},
"right":14
}
And
parse('(((-72 * 52) * (44) / 5 / 15 * 48) * ((85)) - (-37 * ((30))) * 69 - 56)')
Gives:
{
"op":"sub",
"left":{
"op":"sub",
"left":{
"op":"mul",
"left":{
"op":"mul",
"left":{
"op":"div",
"left":{
"op":"div",
"left":{
"op":"mul",
"left":{
"op":"mul",
"left":-72,
"right":52
},
"right":44
},
"right":5
},
"right":15
},
"right":48
},
"right":85
},
"right":{
"op":"mul",
"left":{
"op":"mul",
"left":-37,
"right":30
},
"right":69
}
},
"right":56
}
