Skip to content

Instantly share code, notes, and snippets.

@geoffrasb

geoffrasb/Parser.js

Last active August 29, 2015 13:57
Show Gist options
  • Save geoffrasb/9454740 to your computer and use it in GitHub Desktop.
Save geoffrasb/9454740 to your computer and use it in GitHub Desktop.
Download ZIP
[JS] FP facilities and Parser Combinator
Raw
Parser.js
window.Parser = {
/* need to add mutual-recursive parser combinator
components:
reg
eof
ret
opt
seq
tryp
star
plus
oneOrNot = ques
rec
mkMutualParsersAt
*/
succ : function(d,r){
return { isSucc : true
, data : d
, rest : r }; }
, fail : function(m,r){
return { isSucc : false
, msg : m
, rest : r } }
, _toPsr : function(f){
f.isParser = true;
return f; }
, rec : function(f){
return (function(x){
return f( Parser._toPsr(function(y){ return (x(x))(y);}) );})
(function(x){
return f( Parser._toPsr(function(y){ return (x(x))(y);}) );})}
, _mutualY : function(f){
return (function(x){
return f( function(y1){ return Parser._toPsr(function(y2){ return ((x(x))(y1))(y2);})} );})
(function(x){
return f( function(y1){ return Parser._toPsr(function(y2){ return ((x(x))(y1))(y2);})} );}) }
, mkMutualParsersAt : function(env,table){
var namelst = [];
var flst = [];
for(var i in table){
namelst.push(i);
flst.push(table[i]); }
var R = Parser._mutualY(function(r){
var applst = {};
for(var i=0;i<namelst.length;i++){
applst[namelst[i]] = r(i);}
return function(s){
return flst[s](applst) } });
for(var i=0;i<namelst.length;i++){
env[namelst[i]] = R(i); } }
/* example:
mkMutualParsersAt(window,
{ 'p0': function(r){
return opt([ seq([ reg('0')
, r.p1])
, ret('at 0')]); }
, 'p1': function(r){
return opt([ seq([ reg('1')
, r.p0])
, p.ret('at 1')]); }
})
*/
, _opt : function(psr1,psr2){ //types of psr1,psr2 have been checked in opt
var res = function(src){
var psr1Result = psr1(src);
if(psr1Result.isSucc){
return psr1Result; }
else{
return psr2(src); } }
res.isParser = true;
return res; }
, opt : (function(){
var res = function(psrlst, errmsg){
if(psrlst.forEach==undefined){
console.log('ParserCombinator opt error: wrong type of the input, should be an array.');
return null; }
if(psrlst.length==0){
console.log('ParserCombinator opt error: opt cannot accept nothing.');
return null; }
for(var i in psrlst){
if(!psrlst[i].isParser){
console.log('ParserCombinator opt error: argument '+i+' is not a parser.');
return null; } }
if(psrlst.length==1){
return psrlst[0]; }
else{
var res = psrlst[psrlst.length-1];
for(var i=psrlst.length-2; i>=0 ; i--){
res = Parser._opt(psrlst[i], res); }
return res; } }
res.isParser = true;
return res; })()
/* example
p.Parser
p.opt([ p.reg('a')
, p.reg('b')
])
// a parser that parse /[ab]/
*/
, tryp : function(psr){
var res = function(src){
var pr = psr(src);
if(pr.isSucc){
pr.rest = src;}
return pr; }
res.isParser = true;
return res;}
/* tryp works like regular parsers, except that it won't consume source string. */
/*
, _seq : function(psr,seq_psr,errmsg){
var res = function(src){
var res = psr(src);
if(res.isSucc){
return seq_psr(res.data)(res.rest); }
else {
if(errmsg!=null) return Parser.fail(errmsg, src);
else return Parser.fail("fail of seq",src); } }
res.isParser = true;
return res; }
*/
, inh : function(f){ f.inheritingResults=true; return f; }
, seq : function(psrs, errmsg){
if(psrs.forEach==undefined){
console.log('ParserCombinator seq error: wrong type of the input, should be an array.');
return null;}
if(psrs.length==0){
console.log('ParserCombinator seq error: seq cannot accepts nothing.');
return null; }
for(var i in psrs){
if(!psrs[i].isParser && !psrs[i].inheritingResults && typeof(psrs[i])!='string'){
console.log('ParserCombinator seq error: input array['+i+'] is an inappropriate thing.');
console.log('It is:');
console.log(psrs[i].toString());
return null; } }
var respsr = function(src){
var reslst = {};
var restsrc = src;
var b;
var resultName = null;
for(var i in psrs){
if(psrs[i].isParser) {
b = psrs[i](restsrc); }
else if(psrs[i].inheritingResults) {
b = psrs[i](reslst);
if(b.isParser){
b = b(restsrc); }
else{
console.log('ParserCombinator seq error: illegal inheriting function (should return a parser).');
return null; }}
else if(typeof(psrs[i])=='string'){
resultName = psrs[i];
b = null;}
else{
console.log('ParserCombinator seq error: strange input.');
return null; }
if(b!=null && !b.isSucc){
//psrs[i] is a parser, and it failed
return Parser.fail(errmsg+">seq fail", src);}
else if(b!=null){
//sprs[i] is a parser, and it successed
if(resultName!=null){
reslst[resultName] = b.data;
resultName =null; }
restsrc = b.rest; } }
return b; }
respsr.isParser = true;
return respsr; }
/* seq example
p = Parser;
function max(a,b){
if(a>b) return a
return b; }
countParenthesisLevel = p.rec(function(r){
return p.opt([ p.seq([ p.reg(/\(/)
, "in", r
, p.reg(/\)/)
, "out", r
, p.inh(function(res){
return p.ret(max(res.in+1,res.out)); } )
])
, p.ret(0)
]) })
*/
, star : function(psr){
var acc=[];
var res = Parser.rec(function(r){
return function(src){
var pr = psr(src);
if(pr.isSucc){
acc.push(pr.data);
return r(pr.rest);}
else{
var fpr = acc;
acc = [];
return Parser.succ(fpr,pr.rest); } } })
res.isParser = true;
return res; }
, plus : function(psr,errmsg){
var res = function(src){
var pr = Parser.star(psr)(src);
if(pr.data.length==0){
return Parser.fail(errmsg+" >fail at Parser.plus",src); }
else{
return pr; }}
res.isParser = true;
return res; }
, oneOrNot : function(psr){
var res = function(src){
var res = psr(src);
if(res.isSucc) return Parser.succ([res.data],res.rest);
else return Parser.ret([])(res.rest); }
res.isParser = true;
return res; }
, ques : function(psr){ return Parser.oneOrNot(psr); }
, ret : function(a){
var res = function(src){
return Parser.succ(a,src); }
res.isParser = true;
return res; }
, eof : (function(){
var res = function(src,errmsg){
if(src=="") return Parser.succ(null,"");
else{
return Parser.fail(errmsg+" >failed matching eof",src); } }
res.isParser = true;
return res; })()
, reg : function(regex,errmsg){
var res = function(src){
if(src==null){ console.log('Parser.reg error: src is null.'); }
if(typeof(src)!='string'){ console.log('Parser.reg error: src is not a string.'); }
var m = src.match(regex);
if(src==""){
return Parser.fail(errmsg+' >src is eof',src); }
if(m!=null && m.index==0){
return Parser.succ(m[0],src.substr(m[0].length)); }
else {
return Parser.fail(errmsg+" >failed matching \'"+regex+"\'",src); } }
res.isParser = true;
return res; }
}
Raw
util.js
utilContainer = window;
utilContainer.Y = function(f){
return (function(x){ return f(function(y){ return (x(x))(y); }); })
(function(x){ return f(function(y){ return (x(x))(y); }); })}
utilContainer.assert = function(p,msg){
if(!p){
console.log('assert error: '+msg); } }
//===============================type===============================
window.onload = function(){
var p = Parser;
//-------------------------------type parsing----------------------------------
var typeParser = {}
p.mkMutualParsersAt(typeParser,
{ 'Type' : function(Type,AppType,TypeTok){
return p.seq([ p.reg(/\s*/)
, p.seq([ AppType
, p.star( p.seq([ p.reg(/\s*->/)
, AppType
]))
, p.inh(function(prl){
prl[1].unshift(prl[0]);
var len = prl[1].length;
if(len==1){
return p.ret(prl[1]); }
else{
var res = ['-To', prl[1][len-2] ,prl[1][len-1]];
for(var i=len-3;i>=0;i--){
res = ['-To', prl[1][i], res]; }
return p.ret(res); } })
])
])}
, 'AppType' : function(Type,AppType,TypeTok){
return p.seq([ p.reg(/\s*/)
, p.seq([ TypeTok
, p.star( p.seq([ p.plus(p.reg(/\s/))
, TypeTok
]))
, p.inh(function(prl){
prl[1].unshift(prl[0]);
return p.ret(prl[1]); })
])
], 'failed at AppType')}
, 'TypeTok' : function(Type,AppType,TypeTok){
return p.seq([ p.reg(/\s*/)
, p.opt([ p.seq([ p.tryp( p.reg(/^\([^\(]*,/))
, p.reg(/\(/)
, Type
, p.plus( p.seq([ p.reg(/\s*,/)
, Type
]))
, p.reg(/\s*\)/)
, p.inh(function(prl){
prl[3].unshift(prl[2]);
prl[3].unshift('-Tuple'+prl[3].length);
return p.ret(prl[3]);
})
])
, p.seq([ p.reg(/\(/)
, Type
, p.reg(/\s*\)/)
, p.inh(function(prl){
if(prl[1].length==1){
return p.ret(prl[1]);}
else{
return p.ret([prl[1]]);} })
])
, p.seq([ p.reg(/\[/)
, Type
, p.reg(/\]/)
, p.inh(function(prl){
return p.ret(['-List',prl[1]]); })
])
, p.reg(/[a-zA-Z_]\w*/)
])
])}
});
var NullType = function(){
return { isAType : true
, typearr : []
, toString: function(){ return typeToString(this); }
, freshVar: function(){
this.freshVarCounter += 1;
return "_a"+(this.freshVarCounter); }
, freshVarCounter : -1 } }
var isNullType = function(type){
return (type.typearr.length==0); }
var isTypevar = function(str){ return (str!=null && typeof(str)=='string' && (/^([a-z]|_)/).test(str)); }
var isTypeName = function(str){ return (str!=null && typeof(str)=='string' && (/^([A-Z]|-)/).test(str)); }
var isAType = function(d){ return (!(d==null) && d.isAType ); }
var mkType = function(ta){
var result = NullType();
if(isArr(ta)){ result.typearr = cpyArr(ta); }
else{ result.typearr = [ta]; }
return result; }
var recogTypevar = function(type){
var ta = type.typearr;
var result = {};
Y(function(f){
return function(typearr){
for(var i in typearr){
if(isTypevar(typearr[i])){
result[typearr[i]] = NullType(); }
else if(isArr(typearr[i])){
f(typearr[i]); } } } })(ta);
return result; }
var cpyArr = function(arr){
var narr = [];
for(var i in arr){
if(typeof(arr[i])=='string') {
narr.push(arr[i]); }
else if(isArr(arr[i])){
narr.push(cpyArr(arr[i])); } }
return narr; }
var copyType = function(type){
var res = mkType(cpyArr(type.typearr));
res.freshVarCounter = type.freshVarCounter;
return res; }
var typeToString = function(type){
//special cases: -List -To -TupleN
function show(a, single){
if(isArr(a)){
if(a[0]=='-List'){
return ['[',show(a[1],true),']'].join(''); }
else if((/^-Tuple/).test(a[0])){
var res = ['('];
for(var i=1;i<a.length;i++){
if(i>1) res.push(',');
res.push(show(a[i],true)); }
res.push(')');
return res.join(''); }
else if(a[0]=='-To'){
return [ show(a[1],true), ' -> ', show(a[2],true)].join(''); }
else{
var res = [];
if(!single) res.push('(');
for(var i=0;i<a.length;i++){
if(i>0) res.push(' ');
res.push(show(a[i]));}
if(!single) res.push(')');
return res.join(''); }
}
else{
return a.toString(); } }
return show(type.typearr); }
var parse = function(src){
var pr = typeParser.Type(src);
if(!pr.isSucc){
console.log('parse error');
return null; }
var flattenArr = function(arr){
var narr = cpyArr(arr);
function rec(a){
for(var i=0;i<a.length;i++){
if(isArr(a[i])){
if(a[i].length==1){
a[i] = a[i][0];
return rec(a); }
else{
rec(a[i]);}
} } }
rec(narr);
if(narr.length==1 && isArr(narr[0])) narr = narr[0];
return narr; }
return mkType(flattenArr(pr.data)); }
var isFullyInstantiatedType = function(type){
var table = recogTypevar(type);
for(var i in table){
return false; }
return true; }
var changeTypevar = function(type, varName, newName){
assert(isAType(type) && typeof(varName)=='string' && typeof(newName)=='string');
var ntype = copyType(type);
var recArr = function(ta){
for(var i in ta){
if(isArr(ta[i])){
recArr(ta[i]); }
else if(ta[i]==varName){
ta[i] = newName; } } }
recArr(ntype.typearr);
return ntype;}
var instantiateType = function(type,varName,totype){
if(!isAType(type)){
console.log('instantiateType error: the first input is not a type.');
return null; }
if(!isAType(totype)){
console.log('instantiateType error: the third input is not a type.');
return null; }
if(!isTypevar(varName)){
console.log('instantiateType error: the second input is illegal type variable name.');
return null; }
function replaceArr_x(arr,f,t){
for(var i in arr){
if(isArr(arr[i])){
replaceArr_x(arr[i],f,t); }
else if(f==arr[i]){
if(isArr(t)){
var ca = cpyArr(t);
if(ca.length==1){ arr[i] = ca[0]; }
else { arr[i] = cpyArr(t); } }
else{ arr[i] = t; } } } }
var ntype = copyType(type);
var tvmap = recogTypevar(type);
var ttvmap = recogTypevar(totype);
for(var i in ttvmap){
if(tvmap[i]!=undefined && tvmap[i]!=varName){
ntype = changeTypevar(ntype, i, ntype.freshVar()); } }
replaceArr_x(ntype.typearr, varName, totype.typearr);
return ntype;}
var areEqTypes = function(t1,t2){
if(!isAType(t1)){
console.log('typeEq error: first input is not a type.');
return null;}
if(!isAType(t2)){
console.log('typeEq error: second input is not a type.');
return null;}
if(t1.typearr.length != t2.typearr.length){
return false; }
function recArr(a1,a2){
for(var i in a1){
if(isArr(a1[i])){
if(!isArr(a2[i])) return false;
if(!recArr(a1[i],a2[i])) return false; }
else if(!isTypevar(a1[i]) && !isTypevar(a2[i])){
if(a1[i]!=a2[i]) return false; }
else if(isTypevar(a1[i]) && isTypevar(a2[i])){}
else return false; }
return true;
}
return recArr(t1.typearr, t2.typearr); }
var unifyTypes = function(t1,t2){
if(!isAType(t1)){
console.log('typeEq error: first input is not a type.');
return null;}
if(!isAType(t2)){
console.log('typeEq error: second input is not a type.');
return null;}
if(t1.typearr.length != t2.typearr.length){
return null; }
if(isNullType(t1)){
return copyType(t2);}
if(isNullType(t2)){
return copyType(t1);}
var nt1 = copyType(t1);
var nt2 = copyType(t2);
var t1InstTypes = null;
var t2InstTypes = null;
var instantiationHappened = false;
function initInstTypes(){
t1InstTypes = recogTypevar(nt1);
t2InstTypes = recogTypevar(nt2);
for(var i in t1InstTypes){
t1InstTypes[i] = { linkedTV : []
, type : t1InstTypes[i] } }
for(var i in t2InstTypes){
t2InstTypes[i] = { linkedTV : []
, type : t2InstTypes[i] } } }
function linkvars(v1,v2){
if(t1InstTypes[v1] == undefined) {
console.log('unification error at linkvars(of v1)');
return null; }
if(t2InstTypes[v2] == undefined) {
console.log('unification error at linkvars(of v2)');
return null; }
t1InstTypes[v1].linkedTV.push(v2);
t2InstTypes[v2].linkedTV.push(v1); }
function propagateInstantiation(side,v, t){
if(side==1){
if(t1InstTypes[v] == undefined) {
console.log('unification error at propagation: undefined tv(of v1)');
return null; }
if(!isNullType(t1InstTypes[v].type)){ }
else{
t1InstTypes[v].type = copyType(t);
for(var i in t1InstTypes[v].linkedTV){
propagateInstantiation(2, t1InstTypes[v].linkedTV[i], t); } } }
else if(side==2){
if(t2InstTypes[v] == undefined) {
console.log('unification error at propagation: undefined tv(of v2)');
return null; }
if(!isNullType(t2InstTypes[v].type)){ }
else{
t2InstTypes[v].type = copyType(t);
for(var i in t2InstTypes[v].linkedTV){
propagateInstantiation(1, t2InstTypes[v].linkedTV[i], t); } } }
else{
console.log('unification error at propagation: wrong side code(should be 1 or 2).')
return null; } }
function checkAndLink(a1,a2){
for(var i in a1){
if(isTypevar(a1[i]) && isTypevar(a2[i])){
if(isNullType(t1InstTypes[a1[i]].type) && isNullType(t2InstTypes[a2[i]].type)){
linkvars(a1[i], a2[i]); }
else if(isNullType(t1InstTypes[a1[i]].type)){
t1InstTypes[a1[i]].type = copyType(t2InstTypes[a2[i]].type); }
else if(isNullType(t2InstTypes[a2[i]].type)){
t2InstTypes[a2[i]].type = copyType(t1InstTypes[a1[i]].type); }
else{ } }
else if(isTypevar(a1[i])){
if(isNullType(t1InstTypes[a1[i]].type)){
propagateInstantiation(1, a1[i], mkType(a2[i]));
instantiationHappened = true; } }
else if(isTypevar(a2[i])){
if(isNullType(t2InstTypes[a2[i]].type)){
propagateInstantiation(2, a2[i], mkType(a1[i]));
instantiationHappened = true; } }
else{
//real typecheck
if(isArr(a1[i]) && isArr(a2[i])){
checkAndLink(a1[i], a2[i]); }
else if(typeof(a1[i])=='string' && typeof(a2[i])=='string' && a1[i]==a2[i]){ }
else {
return false; } } }
return true; }
do{
instantiationHappened = false;
initInstTypes();
if(!checkAndLink(nt1.typearr, nt2.typearr)){
return null; }
for(var i in t1InstTypes){
if(!isNullType(t1InstTypes[i].type)){
nt1 = instantiateType(nt1, i, t1InstTypes[i].type); } }
for(var i in t2InstTypes){
if(!isNullType(t2InstTypes[i].type)){
nt2 = instantiateType(nt2, i, t2InstTypes[i].type); } }
}while(instantiationHappened);
//assert
if(!areEqTypes(nt1, nt2)){
console.log('assert error of unification');
return null;}
return nt1; }
//------------------------------------------ADT facilities ---------------------------
utilContainer.ext = function(f){ f.isExtractor = true; return f; }
function mkConstructor(oftypeString, constructorString){ //return theConstructor, theConstructor.get(int) returns the getters
//console.log('mkConstructor('+(''+settype)+', '+(''+fieldNum)+', '+(''+fieldTypes)+')');
if(typeof(oftype)!='string'){
console.log('mkConstructor error: illegal parameter: oftype');
return null}
if(typeof(constructorString)!='string' || name.match(/^[A-Z]/)==null){
console.log('mkConstructor error: illegal parameter: name');
return null}
var oftype = parseType(oftypeString);
var constructor = parseType(constructorString);
if(oftype==null){
console.log('mkConstructor error: wrong oftype string was given.');
return null; }
if( constructor==null){
console.log('mkConstructor error: wrong constructor string was given.');
return null; }
// check typevar binding
for(var i in constructor.typevars){
if(oftype.typevars[i]==undefined){
console.log('mkConstructor error: type variable '+i+' of ('+constructor.toString()+') is not bounded in the type: '+oftype.toString()); } }
var res = function(f){
if(f.isExtractor)
return { _match : function(d){ return (d._type==oftype && d._const==name);}
, _pass : function(d){ return f.apply(this,d.data); } }
else{
if(arguments.length!=fieldNum){
console.log('Constructor error: of '+name+' : wrong number of parameters');
return null; }
var obj = { _type : ofType
, _const: ""
, data : [] }
// get constructor name
var pcs = parseType(constructorString);
// process on arguments, type construction and checking for Constructor
// arguments should be concrete types
for(var i=0;i<fieldNum;i++){
obj.data.push(arguments[i]); }
return obj; } }
res.getter = function(n){
if(n<0 || n>fieldNum){ console.log('error: No getter for field '+n); return null}
return function(d){
if(d._type != oftype){
console.log('getter error: expect: '+oftype+', but got: '+d._type+' .');
return null; }
else if(d._const != name){
console.log('getter error: expect: '+oftype+'-'+name+', but got: '+d._const+' .');
return null;
}else
return d[n]; } }
res.test = function(d){
return (d._type==oftype && d._const==name);}
return res; }
function ADT(env,type){
var constString;
for(var i=2;i<arguments.length;i++){
constString = arguments[i].split(' ');
if(constString==null){
console.log('ADT error: illegal Constructor name: '+arguments[i]);
return null; }
this[constString[0]] = mkConstructor(type+'-'+constString[0],
constString.length-1,
(function(){ constString.shift(); return constString})()); } }
function mat(arg){
var data = arg[0];
for(var i=1;i<arg.length;i++){
if(arg[i]._match(data)) {
return arg[i]._pass(data); } }
console.log("mis-match error");
}
/* using mat:
mat([ a
, Nil( ... )
, Cons( \x.... )
])
*/
//------------------------declarations----------------
/*
ADT(this, "Maybe a"
, "Nothing"
, "Just a")
var isNothing = Nothing.test;
var unJust = Just.getter(0);
ADT(this, "List"
, "Nil"
, "Cons a List");
var head = Cons.getter(0);
var tail = Cons.getter(1);
var foldl = function(f,i,l){
return mat([ l
, Nil([], function(){ return i; })
, Cons([], function(h,t){ return foldl(f,f(i,h),t); })
]); }
var map = function(f,l){
return mat([ l
, Nil([], function(){ return Nil([]); })
, Cons([],function(h,t){ return Cons([f(h), map(f,t)]); })
]);}
var reverse = function(l){
return foldl( function(t,h){ return Cons([h,t]);}
, Nil([])
, l); }
ADT(this, "Either"
, "Left a"
, "Right b" );
ADT(this, "Pair"
, "Pair a b");
var fst = Pair.getter(0);
var snd = Pair.getter(1);
*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment