2e:null 2f:["$","title",null,{"children":"Moo and Nearley (2.20.1) | Anatoli Babenia | Observable"}] 34:T714,md`# [Nearley](https://github.com/kach/nearley) nearley is a simple, fast and powerful parsing toolkit. It consists of: 1. [A powerful, modular DSL for describing languages](https://nearley.js.org/docs/grammar) 2. [An efficient, lightweight Earley parser](https://nearley.js.org/docs/parser) 3. [Loads of tools, editor plug-ins, and other goodies!](https://nearley.js.org/docs/tooling) nearley is a **streaming** parser with support for catching **errors** gracefully and providing _all_ parsings for **ambiguous** grammars. It is compatible with a variety of **lexers** (we recommend [moo](http://github.com/tjvr/moo)). It comes with tools for creating **tests**, **railroad diagrams** and **fuzzers** from your grammars, and has support for a variety of editors and platforms. It works in both node and the browser. Unlike most other parser generators, nearley can handle *any* grammar you can define in BNF (and more!). In particular, while most existing JS parsers such as PEGjs and Jison choke on certain grammars (e.g. [left recursive ones](http://en.wikipedia.org/wiki/Left_recursion)), nearley handles them easily and efficiently by using the [Earley parsing algorithm](https://en.wikipedia.org/wiki/Earley_parser). nearley is used by a wide variety of projects: - [artificial intelligence](https://github.com/ChalmersGU-AI-course/shrdlite-course-project) and - [computational linguistics](https://wiki.eecs.yorku.ca/course_archive/2014-15/W/6339/useful_handouts) classes at universities; - [file format parsers](https://github.com/raymond-h/node-dmi); - [data-driven markup languages](https://github.com/idyll-lang/idyll-compiler); - [compilers for real-world programming languages](https://github.com/sizigi/lp5562); - and nearley itself! The nearley compiler is bootstrapped. `35:T949,viewof calcGrammar = { let s = html``; s.value = ` # This is a nice little grammar to familiarize yourself # with the nearley syntax. # It parses valid calculator input, obeying OOO and stuff. # ln (3 + 2*(8/e - sin(pi/5))) # is valid input. # This is (hopefully) pretty self-evident. # \`main\` is the nonterminal that nearley tries to parse, so # we define it first. # The _'s are defined as whitespace below. This is a mini- # -idiom. main -> _ AS _ {% function(d) {return d[1]; } %} # PEMDAS! # We define each level of precedence as a nonterminal. # Parentheses P -> "(" _ AS _ ")" {% function(d) {return d[2]; } %} | N {% id %} # Exponents E -> P _ "^" _ E {% function(d) {return Math.pow(d[0], d[4]); } %} | P {% id %} # Multiplication and division MD -> MD _ "*" _ E {% function(d) {return d[0]*d[4]; } %} | MD _ "/" _ E {% function(d) {return d[0]/d[4]; } %} | E {% id %} # Addition and subtraction AS -> AS _ "+" _ MD {% function(d) {return d[0]+d[4]; } %} | AS _ "-" _ MD {% function(d) {return d[0]-d[4]; } %} | MD {% id %} # A number or a function of a number N -> float {% id %} | "sin" _ P {% function(d) {return Math.sin(d[2]); } %} | "cos" _ P {% function(d) {return Math.cos(d[2]); } %} | "tan" _ P {% function(d) {return Math.tan(d[2]); } %} | "asin" _ P {% function(d) {return Math.asin(d[2]); } %} | "acos" _ P {% function(d) {return Math.acos(d[2]); } %} | "atan" _ P {% function(d) {return Math.atan(d[2]); } %} | "pi" {% function(d) {return Math.PI; } %} | "e" {% function(d) {return Math.E; } %} | "sqrt" _ P {% function(d) {return Math.sqrt(d[2]); } %} | "ln" _ P {% function(d) {return Math.log(d[2]); } %} # I use \`float\` to basically mean a number with a decimal point in it float -> int "." int {% function(d) {return parseFloat(d[0] + d[1] + d[2])} %} | int {% function(d) {return parseInt(d[0])} %} int -> [0-9]:+ {% function(d) {return d[0].join(""); } %} # Whitespace. The important thing here is that the postprocessor # is a null-returning function. This is a memory efficiency trick. _ -> [\s]:* {% function(d) {return null; } %} ` return s; }36:T48a,λ = { var parse = function(src, lv) { var body = '', idx, m, i, d, l; while (m = src.match(/^([\s\S]*?)(λ)\(/)) { body += m[1]; src = src.substr(m[0].length-1); for (i = d = 1, l = src.length; i < l; ++i) { if (src.charAt(i) === '(') d++; else if (src.charAt(i) === ')') d--; if (!d) break; }; if (i === l) throw new SyntaxError('() mismatch'); var t = src.substr(1,i-1); body += tr(t, lv+1); src = src.substr(i+1); } return body + src; }; function tr(src, lv) { if (!lv) lv = 0; var parts = src.match(/^([^:]*):([\s\S]+)/), head = parts[1], body = parse(parts[2], lv); var fun = '(function _' + (lv) + '('+head+'){return '+body+'})'; return fun; } function lambda(src, nomemo, lv) { if (!nomemo && src in lambda.memo) return lambda.memo[src]; let fun = eval(tr(src, lv)) ; if (!nomemo) lambda.memo[src] = fun; return fun; }; lambda.memo = {}; lambda.t = tr; return lambda; } 37:[] 32:{"id":"55a946315a3c0e46","slug":"moo-and-nearley","title":"Moo and Nearley (2.20.1)","thumbnail":"926e6ecb1bc43cf034372432ada64b1514f4862dbe9c3c4eb715eae53d38e9bb","access_level":"public","create_time":"$D2021-08-26T19:02:39.522Z","update_time":"$D2021-09-03T10:10:15.743Z","view_time":null,"first_public_time":"$D2021-08-29T15:19:45.412Z","has_unpublished_edits":null,"fork":{"id":"cc82c1931efdb135","slug":"moo-and-nearley","title":"Moo and Nearley","owner":{"id":"6b99b74a49d4f877","login":"kindy","name":"Kindy Lin"}},"stars":3,"starred":false,"owner":{"type":"team","id":"051440672874d568","login":"abitrolly","name":"Anatoli Babenia","avatar_url":"https://avatars-next.observableusercontent.com/2f343abb5b012a4f26ec5ddf4f3b27e3a604c9e61f196dc6634e49da57892fa1","tier":"starter_2024"},"version":262,"publish_version":262,"role":null,"authored":false,"authors":[{"type":"individual","id":"d88a810c493f2e55","login":"abitrolly","name":"Anatoli Babenia","avatar_url":"https://avatars-next.observableusercontent.com/2f343abb5b012a4f26ec5ddf4f3b27e3a604c9e61f196dc6634e49da57892fa1","tier":null}],"members":[{"type":"individual","id":"d88a810c493f2e55","login":"abitrolly","name":"Anatoli Babenia","avatar_url":"https://avatars-next.observableusercontent.com/2f343abb5b012a4f26ec5ddf4f3b27e3a604c9e61f196dc6634e49da57892fa1","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Moo and Nearley (2.20.1)","cells":[{"id":102,"value":"md`# Moo and Nearley (2.20.1)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"md`

\n![](https://github.com/no-context/moo/raw/master/cow.png)\n

\n# [Moo!](https://github.com/no-context/moo)\n\nMoo is a highly-optimised tokenizer/lexer generator. Use it to tokenize your strings, before parsing 'em with a parser like [nearley](https://github.com/hardmath123/nearley) or whatever else you're into.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"moo = require('moo')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"lexer = moo.compile({\n WS: /[ \\t]+/,\n comment: /\\/\\/.*?$/,\n number: /0|[1-9][0-9]*/,\n string: { match: /\"(?:\\\\[\"\\\\\\n]|[^\\n\"\\\\])*\"/, lineBreaks: true },\n lparen: '(',\n rparen: ')',\n keyword: ['while', 'if', 'else', 'moo', 'cows', 'say'],\n NL: { match: /\\n/, lineBreaks: true },\n })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"md`## Source Text:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"viewof text = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"md`## Tokens:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"tokens = ['', ...rawTokens.map(x => ` ${x.type}: ${x.value}`), ''].join('\\n')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"rawTokens = {\n lexer.reset(text);\n return Array.from(lexer);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"md`## Calc demo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"calcParser = {\n let parser = ne.compile(calcGrammar);\n parser.initstate = parser.save();\n return parser;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"viewof calcExp = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"calcResult = calc(calcExp)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"calc = {\n return (exp) => {\n calcParser.restore(calcParser.initstate);\n calcParser.feed(exp);\n return md`

${exp}\\n  -> ${calcParser.results[0]}

`;\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"md`## Nearley toolkit`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"ne = {\n let neGrammar = await require('https://bundle.run/nearley@2.20.1/lib/nearley-language-bootstrapped.js');\n let generate = await require('https://bundle.run/nearley@2.20.1/lib/generate.js');\n let Compile = await require('https://bundle.run/nearley@2.20.1/lib/compile.js');\n let nearley = await require('https://bundle.run/nearley@2.20.1');\n\n var x = nearley.Grammar.fromCompiled(neGrammar);\n \n return {\n Grammar: nearley.Grammar,\n Parser: nearley.Parser,\n generate,\n compile(grammar, opts = {}) {\n var parser = new nearley.Parser(x);\n parser.feed(grammar);\n let ast = parser.results[0];\n let code = generate(Compile(ast, opts), opts.export || 'grammar');\n let mod = {exports: {}};\n (new Function('module', code))(mod);\n let compiledGrammar = {ast, grammar: mod.exports};\n return new nearley.Parser(nearley.Grammar.fromCompiled(compiledGrammar.grammar));\n },\n };\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"{\n let div = md`# [js-lambda](https://github.com/dankogai/js-lambda)\n\nDSL for, but not limited to, the lambda calculus.\n`\ndiv.style.paddingTop = '2em';\n\nreturn div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":166,"value":"temp1 = λ.t(`x:λ(x:x+1)`)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W37","stdlib":"1","titling":"auto"}} 33:"$32:body"