3 ms·

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 Perform

by bd82 11y ago

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%20fault%20tolerance 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 http://jsperf.com/json-parsers-comparison/21 Shahar.

IvanK_net 11y ago
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.
- edko 11y ago
  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.
- bd82 11y ago
  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.
- bd82 11y ago
  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?
Fannon 11y ago
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?
- bd82 11y ago
  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#L423 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.
david-given 11y ago
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?
- bd82 11y ago
  Thanks for the feedback. The Lexer and Parser both expose a collection of Errors. http://sap.github.io/chevrotain/documentation/0_5_19/classes/parser.html#errors http://sap.github.io/chevrotain/documentation/0_5_19/classes... http://sap.github.io/chevrotain/documentation/0_5_19/interfaces/ilexingresult.html#errors 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/errorMarkers.js#L1 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 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/...).
  - david-given 11y ago
    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...

by bd82 11y ago

IvanK_net 11y ago

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.

edko 11y ago
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.
bd82 11y ago
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.
bd82 11y ago
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?

Fannon 11y ago

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?

bd82 11y ago
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#L423 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.

david-given 11y ago

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?

bd82 11y ago
Thanks for the feedback. The Lexer and Parser both expose a collection of Errors. http://sap.github.io/chevrotain/documentation/0_5_19/classes/parser.html#errors http://sap.github.io/chevrotain/documentation/0_5_19/classes... http://sap.github.io/chevrotain/documentation/0_5_19/interfaces/ilexingresult.html#errors 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/errorMarkers.js#L1 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 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/...).
- david-given 11y ago
  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...