Show HN: Chevrotain – Fault-Tolerant JavaScript Parsing DSL(github.com)
github.com
Show HN: Chevrotain – Fault-Tolerant JavaScript Parsing DSL
https://github.com/SAP/chevrotain
17 comments
I am familiar with PEG.js, which is basically the same thing, but exists for 6 years now. Does Chevrotain have any other advantages, than being about 2 times faster?
Hello.
I am the author behind Chevrotain.
I would say the two major functional advantages (as already mentioned in this thread) are Error Recovery and Performance.
Error Recovery online playable demo can be found here: http://sap.github.io/chevrotain/playground/?example=tutorial...
Performance in the jsperf benchmark is affected by the javascript engine used. On latest chrome (V8) and thus node.js which is the most common runtime, Chevrotain is ±3 times faster in the provided jsperf benchmark. http://jsperf.com/json-parsers-comparison/21
Shahar.
I am the author behind Chevrotain.
I would say the two major functional advantages (as already mentioned in this thread) are Error Recovery and Performance.
Error Recovery online playable demo can be found here: http://sap.github.io/chevrotain/playground/?example=tutorial...
Performance in the jsperf benchmark is affected by the javascript engine used. On latest chrome (V8) and thus node.js which is the most common runtime, Chevrotain is ±3 times faster in the provided jsperf benchmark. http://jsperf.com/json-parsers-comparison/21
Shahar.
What "Error recovery" means in your software? You usually want the parser to accept the input when it corresponds the grammar and refuse input, when it does not.
I think that user should modify his grammar in order to accept errors (e.g. missing colon in your example). If you do it for him, then you must specify, what you mean by tolerable and intolerable errors. I think your specification may get very large and confusing.
EDIT: I just found out what you mean by "error recovery". However I still think, that user should specify accepted errors inside a grammar, so he has bigger control over it. Your "error recovery" can never be prepared to all kinds of rerrors, that user may want to recover from.
BTW. PEG.js can generate a parser "object", which is directly usable in the same JS "process". I have never seen any parser code while working with PEG.js.
BTW2. generating the parser code can also be very useful, when you don't want to distribute your grammar alongside with your app.
I think that user should modify his grammar in order to accept errors (e.g. missing colon in your example). If you do it for him, then you must specify, what you mean by tolerable and intolerable errors. I think your specification may get very large and confusing.
EDIT: I just found out what you mean by "error recovery". However I still think, that user should specify accepted errors inside a grammar, so he has bigger control over it. Your "error recovery" can never be prepared to all kinds of rerrors, that user may want to recover from.
BTW. PEG.js can generate a parser "object", which is directly usable in the same JS "process". I have never seen any parser code while working with PEG.js.
BTW2. generating the parser code can also be very useful, when you don't want to distribute your grammar alongside with your app.
The use case of only handling valid input is a very common one, Particularly during compiler construction.
But what about the use case of building an Editor (IDE) ? In this context it would highly beneficial to be able to handle invalid inputs as the user would still expect outline/navigation/formatting/.../ to work even when there are syntax errors.
Error Recovery algorithms are heuristics, they can never solve all the possible kinds of errors. Automatic error recovery is also not mutually exclusive with expanding the grammar to support some "tolerable" errors, Both can be used to improve the "robustness" of the grammar when fault tolerance is needed.
Also note that expanding the grammar will work best for simple common errors (missing semicolon), but what about when you need to re-sync an unknown number of tokens and unwind the parser call stack?
Also note these "heuristics" are not "mine", they are based on heuristics used in Antlr 3. Which is itself based on Academic studies in this topic: Specifically:
Josef Grosch. Efficient and comfortable error recovery in recursive descent parsers. Structured Programming, 11(3):129–140, 1990.
Rodney W. Topor. A note on error recovery in recursive descent parsers. SIGPLAN Not., 17(2):37–40, 1982.
Niklaus Wirth. Algorithms + Data Structures = Programs. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1978.
But what about the use case of building an Editor (IDE) ? In this context it would highly beneficial to be able to handle invalid inputs as the user would still expect outline/navigation/formatting/.../ to work even when there are syntax errors.
Error Recovery algorithms are heuristics, they can never solve all the possible kinds of errors. Automatic error recovery is also not mutually exclusive with expanding the grammar to support some "tolerable" errors, Both can be used to improve the "robustness" of the grammar when fault tolerance is needed.
Also note that expanding the grammar will work best for simple common errors (missing semicolon), but what about when you need to re-sync an unknown number of tokens and unwind the parser call stack?
Also note these "heuristics" are not "mine", they are based on heuristics used in Antlr 3. Which is itself based on Academic studies in this topic: Specifically:
Josef Grosch. Efficient and comfortable error recovery in recursive descent parsers. Structured Programming, 11(3):129–140, 1990.
Rodney W. Topor. A note on error recovery in recursive descent parsers. SIGPLAN Not., 17(2):37–40, 1982.
Niklaus Wirth. Algorithms + Data Structures = Programs. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1978.
Having the parser recover from errors is very useful if you want to build a text editing environment for your language, for example. It would allow you to highlight errors to the user, and to provide context-sensitive help, even beyond the position of the first error of the user's input.
Answer to BTW:
But what about debugging and stepping through the grammar
execution? I assume that in the
case you are describing EVAL is performed on text generated "in memory". If you want to debug your code snippets (grammar actions) or just the grammar flow itself you still can't escape the generated code, even if you can escape generating an actual file.
Answer to BTW2: Could you describe such a use case? what would be the motivation for it?
Answer to BTW2: Could you describe such a use case? what would be the motivation for it?
This looks extremely neat --- I'm about to need to dive into Javascript parsing; I was planning on PEG.js, but I'm thinking about using Chevrotain instead. The error recovery and handling look exactly what I'm looking for.
The demo is really slick, too. I'm thoroughly impressed by the automatic highlighting of syntactic errors in the source via CodeMirror; that is precisely what I'm going to end up doing. How much of that is built in to the parser as opposed to part of the demo? That is, do I need to care about handling and reporting errors when writing my parser?
Is there anything novel about the parsing algorithm itself?
The demo is really slick, too. I'm thoroughly impressed by the automatic highlighting of syntactic errors in the source via CodeMirror; that is precisely what I'm going to end up doing. How much of that is built in to the parser as opposed to part of the demo? That is, do I need to care about handling and reporting errors when writing my parser?
Is there anything novel about the parsing algorithm itself?
There is nothing special about the parsing algorithm.
It is currently a naive LL(1) (single token lookahead) Parser.
I may try to upgrade it to LL(*) in the future.
However that does not mean Chevrotain it limited to LL(1) grammars. You can explicitly implement the lookahead function in any point the grammar.
So if you are trying to parse a well designed grammar like Python who explicitly declare that being LL(1) is a blessing not a curse. https://www.python.org/dev/peps/pep-3099/#core-language You won't have any issues.
If you are trying to parse a language that is nearly always LL(1) You also won't have many issues as you can define your own custom lookahead. Example: https://github.com/SAP/chevrotain/blob/master/examples/custo...
If you are trying to parse a language that is nearly always NOT LL(1) You may want to use a different tool to parse it(at this point in time).
However that does not mean Chevrotain it limited to LL(1) grammars. You can explicitly implement the lookahead function in any point the grammar.
So if you are trying to parse a well designed grammar like Python who explicitly declare that being LL(1) is a blessing not a curse. https://www.python.org/dev/peps/pep-3099/#core-language You won't have any issues.
If you are trying to parse a language that is nearly always LL(1) You also won't have many issues as you can define your own custom lookahead. Example: https://github.com/SAP/chevrotain/blob/master/examples/custo...
If you are trying to parse a language that is nearly always NOT LL(1) You may want to use a different tool to parse it(at this point in time).
Thanks for the feedback.
The Lexer and Parser both expose a collection of Errors. http://sap.github.io/chevrotain/documentation/0_5_19/classes...
http://sap.github.io/chevrotain/documentation/0_5_19/interfa...
Both contain information regarding the position of the error. For a lexer Error it is an offset. For a Parsing Error the erroneous Token is referenced, It contains line/column/offset and more...
If you want to build an Editor using codeMirror you will have to extract that error position information and highlight it using codeMirror's APIs.
example: https://github.com/SAP/chevrotain/blob/gh-pages/playground/e...
Chevrotain is not aware of codeMirror/ACE or any other Editor frameworks. It is just a ±3,000 LOC library meant for building parsers.
If you are indeed interested in building an Online Editor for some language, you may want to have a look here: https://github.com/SAP/demos_json_editor_services_chevrotain
It is a work in progress on using Chevrotain to build Editor services (outline/formatting/Ast Building/...).
The Lexer and Parser both expose a collection of Errors. http://sap.github.io/chevrotain/documentation/0_5_19/classes...
http://sap.github.io/chevrotain/documentation/0_5_19/interfa...
Both contain information regarding the position of the error. For a lexer Error it is an offset. For a Parsing Error the erroneous Token is referenced, It contains line/column/offset and more...
If you want to build an Editor using codeMirror you will have to extract that error position information and highlight it using codeMirror's APIs.
example: https://github.com/SAP/chevrotain/blob/gh-pages/playground/e...
Chevrotain is not aware of codeMirror/ACE or any other Editor frameworks. It is just a ±3,000 LOC library meant for building parsers.
If you are indeed interested in building an Online Editor for some language, you may want to have a look here: https://github.com/SAP/demos_json_editor_services_chevrotain
It is a work in progress on using Chevrotain to build Editor services (outline/formatting/Ast Building/...).
That's ideal.
It's so nice to have a parser which actually does proper error handling. So many really nice parsers completely fail to do this --- e.g. Lua's PEG works really, really well, except when you give it invalid input, at which point it usually just gives up and goes home...
It's so nice to have a parser which actually does proper error handling. So many really nice parsers completely fail to do this --- e.g. Lua's PEG works really, really well, except when you give it invalid input, at which point it usually just gives up and goes home...
Thanks for sharing! I was looking for something like this the last weeks. I especially like that it doesn't use a DSL, but JavaScript itself, so it's easier to debug and inspect.
Is there any way to generate a final parser file, nevertheless? Or somehow bundle it up?
Is there any way to generate a final parser file, nevertheless? Or somehow bundle it up?
Thanks for the feedback. :)
There is no way to generate a "parser file". Because no source is ever generated (not even "in memory").
If you want to bundle with the rest of your application. Your grammar is just another javascript file. Which will be packaged normally as you would bundle other web applications. (webpack/uglify/...)
* Note that due to Implementation details (using Function.toString) you may have to play around with minification options regarding name mangling. Example: https://github.com/SAP/chevrotain/blob/master/gruntfile.js#L...
I will document this clearly in an FAQ...
If you are referring to the Chevrotain runtime itself. It is available As a single bundled file (minified) on bower/npm for ease of consumption in a web application.
There is no way to generate a "parser file". Because no source is ever generated (not even "in memory").
If you want to bundle with the rest of your application. Your grammar is just another javascript file. Which will be packaged normally as you would bundle other web applications. (webpack/uglify/...)
* Note that due to Implementation details (using Function.toString) you may have to play around with minification options regarding name mangling. Example: https://github.com/SAP/chevrotain/blob/master/gruntfile.js#L...
I will document this clearly in an FAQ...
If you are referring to the Chevrotain runtime itself. It is available As a single bundled file (minified) on bower/npm for ease of consumption in a web application.
Another major difference is that Chevrotain does not generate any code, it is a Parsing DSL not a Parser Generator.
It is actually implemented with something very much like Macros, The Grammar’s implementation itself is parsed at runtime in-order to “understand” the grammar’s structure, once the grammar’s structure is known at runtime, capabilities such as Lookahead calculation / Error Recovery / Dynamically generated syntax diagrams (self documenting) become possible.
This means you just write plain Javascript, not some new language that is later compiled to a runnable JS parser. At first glance this may seem to be of little consequences to the user in terms of functionality. However it does provide many benefits to the user’s development workflow:
1. Easy debugging. You don’t have to deal with both a grammar and a thousands of lines of generated code, trying to understand how the generated code maps to the grammar and vice versa.
2. Fast feedback loops. No compile step…
3. No need for a build/packaging step in your central build or worse yet deal with committing generated code to your source control system.
4. No special none Javascript syntax. Can use your favorite Javascript editor to build your grammar, instead of relying on custom tools or worse yet a simple text editor. No special syntax to insert code snippets.
It is actually implemented with something very much like Macros, The Grammar’s implementation itself is parsed at runtime in-order to “understand” the grammar’s structure, once the grammar’s structure is known at runtime, capabilities such as Lookahead calculation / Error Recovery / Dynamically generated syntax diagrams (self documenting) become possible.
This means you just write plain Javascript, not some new language that is later compiled to a runnable JS parser. At first glance this may seem to be of little consequences to the user in terms of functionality. However it does provide many benefits to the user’s development workflow:
1. Easy debugging. You don’t have to deal with both a grammar and a thousands of lines of generated code, trying to understand how the generated code maps to the grammar and vice versa.
2. Fast feedback loops. No compile step…
3. No need for a build/packaging step in your central build or worse yet deal with committing generated code to your source control system.
4. No special none Javascript syntax. Can use your favorite Javascript editor to build your grammar, instead of relying on custom tools or worse yet a simple text editor. No special syntax to insert code snippets.
1. Erm. Nobody would say that you should debug assembly code when writing C/C++ code. This is (more or less) a solved problem, its called source mapping.
2. No need to compile anything with JITs and dynamic in-page compilation
3. You need to minify, as a bare minimum. So, you haven't gotten rid of that step. And #2 is just stupid, you wouldn't commit a binary to an SCM
4. Its called JSON.
So, again, what benefit do you actually provide, now that we've debunked your 'benefits'?
2. No need to compile anything with JITs and dynamic in-page compilation
3. You need to minify, as a bare minimum. So, you haven't gotten rid of that step. And #2 is just stupid, you wouldn't commit a binary to an SCM
4. Its called JSON.
So, again, what benefit do you actually provide, now that we've debunked your 'benefits'?
I have never used PEG.js, but, from reading the documentation, it does not seem to have error recovery (getting the token stream back in sync if there are errors in the input). Chevrotain does.
This looks very polished and potentially useful.
Could you point us to examples of different grammar files.
How hard would it be to make a LaTeX parser based on Chevrotain?
Could you point us to examples of different grammar files.
How hard would it be to make a LaTeX parser based on Chevrotain?
Thanks for the compliment.
I Still need to produce more examples (contributions are welcome :) ) There is one bigger (but incomplete example) of ECMAScript 5.1. https://github.com/SAP/chevrotain/blob/master/examples/types... It is written in Typescript.
About LaTex: I'm not familiar with LaTex, However if I understand correctly it is based on Tex which is not a context free language.
Meaning it can't be parsed with standard parsing tools.
See details here: http://tex.stackexchange.com/questions/4201/is-there-a-bnf-g...
I Still need to produce more examples (contributions are welcome :) ) There is one bigger (but incomplete example) of ECMAScript 5.1. https://github.com/SAP/chevrotain/blob/master/examples/types... It is written in Typescript.
About LaTex: I'm not familiar with LaTex, However if I understand correctly it is based on Tex which is not a context free language.
Meaning it can't be parsed with standard parsing tools.
See details here: http://tex.stackexchange.com/questions/4201/is-there-a-bnf-g...