nihil v0.3.0
nihil
Info
Author = Mepy Github : Language = Engilish, mainly Blog : Language = Simplified Chinese(简体中文)
Intro
WARNING : a TOY project current, do NOT use in production.
nihil
is a parser combinator library for Javascript(ES2015+).
nihil is null, nothingness, etc, while nihil
is useful and elegant
NPM.
nihil
is a lot inspired by bnb
But written in the style of FP(Functional Programming), mainly, I thought
details in ## Reference.
nihil
has zero dependencies and is about 5.2KB(exactly 5291 Bytes) raw Javascript.
As for minifying and zipping, I haven't tried it.
nihil
source code uses some features of ES2015(or ES6),
such as destructuring assignment, arrow function.
So you'd better use modern browser like Chrome, Firefox, etc.
nihil
library contains only, maybe you can consider, one object nihil
.
So it of course supports both Browser and NodeJS.
nihil
is elegant and easy to use, try it? -> Read ## Tutorial
Reference
nihil
is a lot inspired by bnb
At first, I used bnb
for another toy project
However, I met some troubles :
1. Creating a recursive parser is a little hard
2. Assign bnb.parser.parse to a variable will throw an error
Because bnb
implement parser with class
Assign instance.parse to a variable will lose this
pointer
I decide to implement my own one, and I read the source code of bnb
But nihil
is totally new written, I thought it should be NOT a derivative of bnb
The similarity between nihil
and bnb
might only be
bnb.match(RegExp)
<=> nihil(RegExp)
and chain method .and
, .or
, etc.
Tutorial
nihil(RegExp)
: Regular Expression Parser
You can use nihil(RegExp)
to create parsers:
nihil(/a+/) // a parser
.try
& .parse
: Parsing Raw String
With a parser, you can parse raw string with method .try
or .parse
:
const a = nihil(/a+/)
a.try("aaaa") // "aaaa"
a.try("bbbb") // throw { expected: '/a+/', location: 0 }
a.parse("aaaa") // { right: true, value: 'aaaa' }
a.parse("bbbb") // { right: false, error: { expected: '/a+/', location: 0 } }
The difference between them is that .try
would throw error while .parse
would return.
For convenience, we will use .try
in the following text.
.and
: Sequential Parser
You can use nihil.and(RegExp,...)
to create a sequential parser:
nihil.and(/a*/,/b*/,/c*/)
.try("bbbbcccc") // [ '', 'bbbb', 'cccc' ]
If exists a parser k
, you can use k.and(parser,...)
:
const k = nihil(/k+/)
const g = nihil(/g+/)
k.and(g,k)
.try("kkkggggkkkk") // [ 'kkk', 'gggg', 'kkkk' ]
But It would trouble you if the second parser is a simple parser generated by nihil
Well, you can simply enter RegExps in place of simple parsers:
k.and(/g+/,k)
.try("kkkggggkkkk") // [ 'kkk', 'gggg', 'kkkk' ]
.or
: Choose Parsers
If you want to parse "a" or "b", You can of course use RegExp /a|b/
But if you want to parse one complex language or another complex language,
You can also do it with a complex RegExp which might bring errors,
but using nihil.or
, you can implement the same function as /a|b/
with well-understanding code style:
const a_b = nihil.or(/a/,/b/)
a_b.try("a") // [ 'a' ]
a_b.try("b") // [ 'b' ]
.or
is similar to .and
, so you can also do like these:
const a = nihil(/a/)
const b = nihil(/b/)
const c = nihil(/c/)
a.or(b,c).try("c") // [ 'c' ]
a.or(b,/c/).try("c") // [ 'c' ]
ATTENTION : The order of parser makes difference, see ### Larger Precedes. The combined parser will try to parse using from left parser to right parser.
nihil.or(/a/,/a+/).parse("aaa") // { right: false, error: { expected: '<eof>', location: 1 } }
nihil.or(/a+/,/a/).parse("aaa") // { right: true, value: [ 'aaa' ] }
Well, maybe you are considering it is just another style to write RegExp
and doubting whether it is necessary to learn .or
method.
What if the complex language is not a RE language but a LL(1) language?
You can not implement it with RegExp!!!
Read the following tutorial, you can create a parser of LL(m) .
(m as big as you want and if your computer can compute it in time.)
.keep
: Select Parsers
.keep
method is used for selecting parsers according former value.
With this, you can implement a LL(m) parser.
For example, maybe improper, we implement a LL(1) parser
which accepts a string like 'aA', 'bB', ..., 'zZ'
const lowUp = nihil(/[a-z]/)
.keep($1=>nihil(RegExp($1.toUpperCase())))
.parse
lowUp("nN") // { right: true, value: [ 'n', 'N' ] }
lowUp("iJ") // { right: false, error: { expected: '/I/', location: 1 } }
ATTENTION : in .keep
method, you must give a function
which returns a parser but NOT a RegExp,
different from .and
and .or
.
As for LL(m), the format is like this, simply m = 2
const char4 = nihil.and(/./,/./,/./,/./)
// result of char4 is an array with a length of 4 > m = 2
const parser = char4.keep(([$1,$2,$3,$4])=>{
if($4=='a'){return nihil(/r/)}
else if($3=='b'){return nihil(/s/)}
else{return nihil(/t/)}
}).try
// parser accepts /...ar/, /..b[^a]s/ or /..[^b][^a]t/
parser("wxyar"), // [ 'w', 'x', 'y', 'a', 'r' ]
parser("wxbzs"), // [ 'w', 'x', 'b', 'z', 's' ]
parser("wxyzt"), // [ 'w', 'x', 'y', 'z', 't' ]
REASON : Why name this method after 'keep'?
Because this method KEEP the former value (e.g. result of char4
)
Can we choose not to keep it?
Of course, use .drop
instead of .keep
But it is little used in my view.
.map
: Transform Value
Until now, value of result of parsers are all strings.
Sometimes, we need to transform them, e.g. transform '3'
to 3
nihil(/0|[1-9][0-9]*/) // String of number, decimal
.map(Number) // from String to Number
.try("3") // 3
.map
could do other things, like verifying the value:
For example, we decide to reject 114514
const num = nihil(/0|[1-9][0-9]*/)
.map(Number)
.map($1=>{
if($1==114514)
return undefined
else
return $1
})
num.and(/\s+/,num)
.try("114514 3") // [ undefined, ' ', 3 ]
However, you might realize that the parser,
in fact, replace 114514 with undefined.
Can we DROP 114514, make the result [ ' ', 3 ]
?
Use .drop
.
.drop
: Intercept Value (Optional)
Except that .drop
drops the former parser's result,
it is nearly the same as .keep
What needs to be emphasized is
that fn
in .drop(fn)
MUST return a parser
NEITHER RegExp, NOR array of values in .map
nihil.box(value)
will return a parser
which does nothing but return value,
so called a box (a parser containing value).
You might feels it useful, right?
const num = nihil(/0|[1-9][0-9]*/)
.map(Number)
.drop($1=>{
if($1==114514)
return nihil
else
return nihil.box($1)
})
const foo = num.and(/\s+/,num).try
foo("114514 3") // [ ' ', 3]
foo("10492 3") // [ 10492, ' ', 3 ]
But wait, what is nihil
in return nihil
?
nihil
: NULL Parser
As is seen, nihil
acts as a parser, doing nothing.
Formly, nihil
, as its name, is a nihil (NULL parser, PSEUDO parser).
It can accept a RegExp and return a parser, which we have been using.
nihil
is a parser, so you can use its .and
, .or
.
But nihil
's .keep
, .drop
and .map
must accept a parser first,
because it doesn't return value when parsing. See API.
Until now, we have nearly been empowered to write LL(∞) parsers. But without knowing the flaw of parser combinator, i.e. the top down parser, The following methods would be hard to make by the above methods.
Higher Order Tutorial
For a quick-look, You can only read built-in method.
But reading completely is useful for understanding nihil
's feature.
.sep
: Seperator Between Parser
Recall the result of example in .drop
tutorial, [ ' ' , 3 ]
We might find that the ' ' is so ugly, we want to drop it!
Of course, we can use .map
to map the array [ ' ' , 3 ]
to [ 3 ]
.
But the annoying thing is we need to consider more situations :
const number = nihil(/0|[1-9][0-9]*/).map(Number)
const space = nihil(/\s*/) // accept 0~∞ space(s)
const left = " 3"
const right = "3 "
const leftright = " 3 "
using built-in .sep
nihil
implements a built-in method .sep
for parsers:
var parse = number.sep(space).try
parse(left) // 3
parse(right) // 3
parse(leftright) // 3
But it hides some interesting features, let's implement our .sep
.
using simple .and
// first method
var parse = nihil.and(space, number, space).parse
parse(left) // { right: false, error: { expected: '/\\s*/', location: 3 } }
parse(right) // { right: true, value: [ 3, ' ' ] }
parse(leftright) // { right: true, value: [ ' ', 3, ' ' ] } }
Obviously, sometimes it would err.
using simple .and
and partial .or(nihil)
// first method
var parse = nihil.and(space, number, space.or(nihil)).parse
parse(left) // { right: true, value: [ ' ', 3 ] }
parse(right) // { right: true, value: [ 3, ' ' ] }
parse(leftright) // { right: true, value: [ ' ', 3, ' ' ] } }
We have solved the problem it errs, but how to map three different cases to the same result 3
?
It is a bit difficult, especially differentiating the first and the second.
using .drop
ahead of combining parsers
When meeting \s*, we drop it.
var space_drop = space.drop(_=>nihil);
var parse = nihil.and(space_drop, number, space_drop.or(nihil))
.map($=>$[0])
.parse
parse(left) // { right: true, value: 3 }
parse(right) // { right: true, value: 3 }
parse(leftright) // { right: true, value: 3 }
Finally, we solve it.
feature
parser.drop(_=>nihil)
can drop the value of the parserparser.or(nihil)
can skip the parser if it couldn't match, similar to the symbol?
in the RegExp.
.loop
: Recursive Parser
If we want to parse " 3 4 5 "
,
we can use number.and(number, number)
with .sep
.
But if we don't know how many numbers occur?
const array4 = "3 4 6 4 "
const array2 = " 5 9"
using built-in .loop
Of course, there is a built-in .loop
:
var array = number.sep(space)
.loop()
array.try(array4) // [ 3, 4, 6, 4 ]
array.try(array2) // [ 5, 9 ]
but it also hides some interesting features, let's implement our .loop
.
loop = recursion
As programmers all know, loop is equal to recusion. So we can implement a recursive parser, the following is a BNF(Backus-Naur Form):
array ::= number array | nihil
But how can array
call itself?
straightly calling itself
var array = undefined // ensure array undefined
var array = number.sep(space)
.and(array)
.or(nihil)
// Thrown:
// TypeError: Cannot read property 'raw' of undefined
It failed, because array is undefined when we define array.
using wrapper and closure
In Javascript, closure is useful. In this way, an object can be captured by a function. We can use the object in the function when called. In other words, we wrap the object with a function.
We usually call this trick "late-bound" (especially in λ-calculus)
var array = undefined // ensure array undefined
var array = number.sep(space)
.and(_=>array(_))
.or(nihil)
array.try(array4) // [ 3, [ 4, [ 6, [ 4 ] ] ] ]
array.try(array2) // [ 5, [ 9 ] ]
ATTENTION : We defer the use time of array
!
It was called when the arrow function _=>array(_)
called.
Wait, is parser a function, now that called with argument _
?
Yes, a parser is a function, it accepts source
and return value
.
We use .try
or .parse
,
because source
is a wrapper of String
,
and we also need to wrap value
s into results or throw errors.
See nihil.parser
unfolding the result
Noticing that the result is a recursive array, we need to unfold it into a simple array.
const unfold = a=>(a.length == 1)?a:([a[0],...a[1]]) // a means array
var array = undefined // ensure array undefined
var array = number.sep(space)
.and(_=>array(_))
.map(unfold)
.or(nihil)
array.try(array4) // [ 3, 4, 6, 4 ]
array.try(array2) // [ 5, 9 ]
feature
parser
is indeed a function, we can call it with source_=>parser(_)
can defer the time of using parser.unfold
is needed for maping recursive array to simple array.
.wrap
: Wrapper Between Parser
Now, we could parse string such as "3 4 6 4 "
, " 5 9"
, etc.
We want to add "["
and "]"
on the left and right of array.
using built-in .wrap
array
.wrap(/\[/,/\]/)
.try("[3 4 6 4 ]") // [ 3, 4, 6, 4 ]
using .and
and .map
nihil
.and(/\[/,array,/\]/)
.map(([l,v,r])=>v)
.try("[3 4 6 4 ]") // [ 3, 4, 6, 4 ]
nihil
indeed uses such a method to offer a handy tool .wrap
.
feature
parser.wrap
is a useful tool.
Larger Precedes
Let's run 2 code segments with a slight difference:
var number = nihil(/0|[1-9][0-9]*/).map(Number).sep(/\s*/)
number.loop().or(number)
.parse("3 4") // { right: true, value: [ 3, 4 ] }
var number = nihil(/0|[1-9][0-9]*/).map(Number).sep(/\s*/)
number.or(number.loop())
.parse("3 4") // { right: false, error: { expected: '<eof>', location: 2 } }
The second one is incorrect.
The number
parsed the string first and succueeded,
so number.loop()
had no opportunity to parse the raw string.
However, number
could only parse one number,
so it expected \ after parsing "3 "
, but given "4"
,
finally it returned an error.
Notation :
- P, Q, R, ... are Parsers.
- P | Q means
P.or(Q)
- L(P) is the language described by P.
- p ∈ L(P) is a string of the language L(P).
p < q means p is a prefix substring of q.
Definition : P < Q iff L(P) < L(Q) iff ∀q ∈ L(Q), ∃p ∈ L(P), p < q
Theorem : P < Q ⇒ L(P | Q) = L(P)
Proof : Omitted.
Therefore, if P < Q, P.or(Q)
acts as P
.
feature
- when
.or
combining parsers, the larger should precedes.
Avoid Left Recursion
Recall the BNF in the loop recursion
array ::= number array | nihil
As a matter of fact, the following BNF is also correct.
array ::= array number | nihil
However, the corresponding Javascript code is incorrect:
var number = nihil(/0|[1-9][0-9]*/).map(Number).sep(/\s*/)
var array = nihil.and(_=>array(_),number).or(nihil)
array.try("3 4 ")
// Thrown:
// RangeError: Maximum call stack size exceeded
This is because array
always calling itself,
making the function calling stack overflow.
We call the first BNF "right recursion", the second "left recursion".
feature
- when
.and
creating recursive parsers, transform left recursion to right recursion.
Example : Tree Recursion
The recursive parser made in the .loop
is linked-list-like.
Now we implement a tree-like one.
var number = nihil(/0|[1-9][0-9]*/).map(Number)
var array = number.or(_=>array(_)).sep(/\s*/).loop().wrap(/\[/,/\]/)
array.try("[ 3 [5[9]] 6 [4 5 ] ]") // [ 3, [ 5, [ 9 ] ], 6, [ 4, 5 ] ]
Useful Tools
.lable
: Label Node
Sometimes we want to add a label to the parser result.
var decimal = nihil(/0|[1-9][0-9]*/).map(Number).label("decimal")
var hexadecimal = nihil(/0x(0|[0-9a-fA-F][1-9a-fA-F]*)/).map(Number).label("hexadecimal")
var number = decimal.or(hexadecimal)
number.try("33") // { label: 'decimal', value: 33 }
In fact, you can use .map
to implement it.
parser.label = label=>parser.map(value=>({label,value}))
.locate
: Located Parser
Sometimes we want to locate where parser works.
var a = nihil(/a+/)
var b = nihil(/b+/).locate()
a.or(b).loop()
.try("aaabbbbaa") // [ 'aaa', { beg: 3, value: 'bbbb', end: 7 }, 'aa' ]
Current Bugs
var a = nihil(/a+/).drop(_=>nihil)
var b = nihil(/b+/)
b.or(a).sep(/\s+/).loop().parse("aaabbbbaa")
// { right: false, error: { expected: '<eof>', location: 3 } }
The reason might be that .loop
uses nihil.nihil
to break the looping, while .drop
offers nihil
generating nihil.nihil
.
API
nihil
nihil(parser A)=>parser A nihil(source)=>nihil.nihil nihil(RegExp)=>parser(RE)
result format
{right:true, value : ... }
is the result when parsing succeeded.{right:false, error : ... }
is the result when parsing failed.nihil.nihil = { right:true, nihil:true }
is the result of the nihil parser.
nihil.parser
It is the helper function of nihil
If you are a new hand of Javascript but familiar with OOP(Object Oriented Programming),
you can consider it as class parser
As a matter of fact, its real member function are .try
and parse
for easily parse string and return proper result.
Because a parser is a function indeed, you can call it with argument source
,
see nihil.source
As for other functions, they are all for convenience of creating parsers
in the grammar of chain calling.
You can intuitively feels it in Tutorial.
Also, the source code of nihil.parser
promotes your understanding of the whole nihil
.
nihil.source
Label the raw string with an ima(a Japanese word, means "current") location.
const source = nihil.source("abc") // source = { raw: "abc", ima: 0 }
const ab = nihil(/ab/)
ab(source) // { right: true, value: "ab" }
// source = { raw: "abc", ima: 2 }
nihil.location
A parser returning the ima location of parsing source as value.
const source = nihil.source("abc") // source = { raw: "3", ima: 0 }
const ab = nihil(/ab/)
ab(source)
nihil.location(source) // {right: true, value: 2}
// source = { raw: "abc", ima: 2 }
nihil.and
input array of RegExp or parser, return a parser which parses source sequentially in the order of array
nihil.or
input array of RegExp or parser, return a parser which tries to parse source from array0 to arrayarray.length-1:=end. If arrayk succeeds, arrayk+1,...,end wouldn't be used to parse source.
nihil.keep
It helps implement the parser of LL(∞).
nihil.keep
accepts parser
and
selecting function fn
with value return by a parser
as argument
and a parser as return value, and returns a new parser.
var fn = value=>parser
var LLm = nihil.keep(parser)(fn)
nihil.drop
It is similar to nihil.keep
with difference
that it would DROP the values parsed out by parse
nihil.map
Used to map the value of parse
to the format you like
nihil.map(parse)(mapping)
nihil.sep
Used to deal with the seperator
on the left and the right of parser
.
nihil.sep(parser)(seperator)
nihil.loop
Used to looping parse string with parser
.
nihil.loop(parser)
nihil.label
Used to label the value of parser
.
nihil.label(parser)(label)
nihil.locate
Used to locate the value of parser
nihil.locate(parser)