Search code examples
javascriptparsingcontext-free-grammarcode-completionpeg

CFG / PEG used for Code completion?


I'm wondering if it's possible to use a CFG or PEG grammar as a basis for code completion directly without modification. I have heard that code completion is in IDE's is sometimes manipulated and massaged or even hard coded so that it performs better.

I want to code complete on a small DSL so I fully understand that a grammar cannot help a code completion system with knowledge of library functions etc.

As far as I'm aware the parser itself needs to at least provide a system for querying what it expects next.

In particular I'm interested in a javascript code completion solution using peg.js or jison


Solution

  • It is fairly easy to build Javascript editor with code completion from PEG grammar. I would describe how to do it with PEG.js. You need to extend your grammar with some lax parsing rules that allow to provide suggestions when previous statements are broken. These lax rules need to be handled conditionally or you will need two separate grammars - one for parsing source and second for code completion. You can maintain one grammar by using Javascript predicates (available in PEG.js). It looks like &{return laxParsing} and it causes that whole rule to be processed when laxParsing flag is true. You can switch between lax and strict parsing easily by setting parser's internal flag.

    To provide suggestions to user easily you must modify slightly generated PEG.js parser (version 0.5) to receive in the parsing error structure position (beside the column and line) and list of expectations (beside the error message). You can copy prepared fragment from https://gist.github.com/1281239.

    When you have parser then you can attach it in editor on for example CTRL+SPACE keypress. When these are pressed in text source you need to put a special unparseable sign in place of cursor (to cause a parsing error) and launch parser in lax mode. Then you receive an error with list of suggestions.

    Some of suggestions are not only syntax but also they define references (e.g. entities, variables). You can trigger searching these when a particular expectation is found (e.g. VariableName). You can provide the list by parsing the same source in a different lax parsing mode (filtering only variable names).

    For a working example and source to this approach you can check on https://github.com/mstefaniuk/Concrete-Freetext.