kison


https://yiminghe.me/kison

https://github.com/yiminghe/kison

A LALR(1)/LL(1)/LL(K) parser generator for javascript/typescript

examples

https://yiminghe.me/kison/examples/

- xtemplate: an extensible template engine


- json: es5 compliant javascript implementation of JSON parser


- excel formula engine: excel formula engine


- regular expression engine: support async stream match


- vba engine: written in typescript/javascript


run command

``
npx kison@latest -g xx-grammar.js
`

grammar and lexer definition

$3

cal-grammar.js: support operator precedence

` javascript
module.exports = {
productions: [
{
symbol: 'exp',
rhs: ['primaryExpression'],
},

{
symbol: 'exp',
rhs: ['exp', '^', 'exp'],
action() {
return {
v: Math.pow(this.$1.v, this.$3.v),
l: this.$1,
r: this.$3,
op: '^',
};
},
},
{
symbol: 'exp',
rhs: ['exp', '-', 'exp'],
action() {
return { v: this.$1.v - this.$3.v, l: this.$1, r: this.$3, op: '-' };
},
},
{
symbol: 'exp',
rhs: ['exp', '*', 'exp'],
action() {
return { v: this.$1.v this.$3.v, l: this.$1, r: this.$3, op: '' };
},
},
{
symbol: 'exp',
rhs: ['exp', '/', 'exp'],
action() {
return { v: this.$1.v / this.$3.v, l: this.$1, r: this.$3, op: '/' };
},
},
{
symbol: 'exp',
precedence: 'UMINUS',
rhs: ['-', 'exp'],
action() {
return { v: -this.$2.v, op: 'UMINUS' };
},
},
{
symbol: 'exp',
rhs: ['exp', '+', 'exp'],
action() {
return { v: this.$1.v + this.$3.v, l: this.$1, r: this.$3, op: '+' };
},
},
{
symbol: 'primaryExpression',
rhs: ['(', 'exp', ')'],
action() {
return this.$2;
},
},
{
symbol: 'primaryExpression',
rhs: ['NUMBER'],
action() {
return { v: Number(this.$1) };
},
},
],

operators: [
['left', '+', '-'],
['left', '*', '/'],
['right', '^'],
['right', 'UMINUS'],
],

lexer: {
rules: [
{
regexp: /^\s+/,
token: '$HIDDEN',
},
{
regexp: /^[0-9]+(\.[0-9]+)?\b/,
token: 'NUMBER'
}
]
}
};
`


$3

cal-grammar.js:

- LL(1) and LL(K) support:
- direct left recursive
- operator precedence
- repeat notation(*/+)
- optional notation(?)
- group notation('('/')')
- alternative natation('|')
- LL(K) extra support:
- lazy repeat notation(*?/+?)
- lazy optional notation(??).

` javascript
const startGroup = '(';
const endGroup = ')';
const alternative = '|';

module.exports = () => ({
productions: [
{
symbol: 'program',
rhs: ['statements'],
},
{
symbol: 'statements',
rhs: [startGroup, 'exp', 'NEW_LINE', endGroup + '*'],
},
{
symbol: 'exp',
rhs: [
'exp', '+', 'exp',
alternative,
'exp', '-', 'exp',
alternative,
'exp', '*', 'exp',
alternative,
'exp', '/', 'exp',
alternative,
'exp', '^', 'exp',
],
label: 'binary-exp',
},
{
symbol: 'exp',
rhs: ['-', 'exp'],
precedence: 'UMINUS',
},
{
symbol: 'exp',
rhs: ['NUMBER'],
},
{
symbol: 'exp',
rhs: ['(', 'exp', ')'],
},
],

operators: [
['left', '+', '-'],
['left', '*', '/'],
['right', '^'],
['right', 'UMINUS'],
],

lexer: {
rules: [
{
regexp: /^\n/,
token: 'NEW_LINE',
},
{
regexp: /^\s+/,
token: '$HIDDEN',
},
{
regexp: /^[0-9]+(\.[0-9]+)?\b/,
token: 'NUMBER',
},
],
},
});
`

command options

- --es: generate es module
- -g: grammar file
- -m: ll or lalr or llk (llk is powerful than ll but less performant!)
- --babel: use babel to transform code. need install @babel/core@7.x and @babel/preset-env manually
- --declaration: generate d.ts type file for LL parser

$3

`
npx kison@latest -g cal-grammar.js
`

$3

ll parser generator

`
npx kison@latest -m ll -g cal-grammar.js
`

changelog

$3

- support incremental parser

$3

- support '-m llk' support LL(K)

$3

- support --declaration` to generate d.ts type for LL

$3

* LL & LALR
* add $HIDDEN token type
* use js config file
* add excel formula demo
* support filter for lexer config
* support operator precedence

* LL
* support LL parser
* support direct left recursive elimination and extract common prefix for LL
* support parser tree auto return even if partly error

$3

* optimize error debug info

Fork me on GitHub