[Feature request] Library for matching nested expressions
Nobody has claimed this yet.
- Dominant language
- JavaScript
- Stars
- 13k
- Forks
- 1.4k
- Avg merge
- 15h 36m
- Merged PRs (30d)
- 3
Description
Motivation
Javascript RegExp is unable to match nested structures (e.g. nested brackets) because they cannot be accepted by FSA. This is one of the main limitations Prism has as a regex-based syntax highlighter.
Right now, we usually approximate such nested structures by creating long regexes that match support some maximum level of nesting and then fail. You can see this approach in languages such as JSX and C#.
However, this is neither pretty as the nested patterns as fairly complex, and to read and change, but it is also prone to errors because we then usually compromise between correctness and pattern length. When this compromise is unacceptable and a high level of nesting is necessary, the resulting pattern can become thousands of characters long (e.g. this generated pattern). The blowup in pattern length can even be exponential, so this solution really does not scale.
Description
Prism's matching algorithm doesn't actually require RegExp objects. The pattern only has to behave like on. matchGrammar only ever uses the exec and lastIndex interface of RegExp objects, so if an object implements those two, Prism can use it. (ignoring the RegExp specific global check)
This means, we can make our own PDA implementation and it will just work!
Prism will then use the exec method and the PDA determines if and where the given string matches a pattern. This will be no different from what a normal regex does with the difference being that a PDA is more powerful automaton model. The PDA does not define the inside of a token; it is a drop-in replacement for normal regular expressions.
The implementation will not be part of Core but will be a separate library like Markup templating instead.
Core should stay simple and languages that don't require a PDA shouldn't have to pay for it. Luckily, this is very easy because of Prism's modular nature.
Requirements
The library has to be powerful enough to handle the following cases:
- Lilypond's Scheme expressions (that can itself contain lilypond)
- JSX tags
- C# generics
- QML's JS expressions
- JS template strings
Since we can't combine these PDAs with regexes, they have to be powerful enough to stand on their own. They have to be able to do everything normal regexes can do (maybe except for backreferences).
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reading matchGrammar and the referenced patterns in prism-lilypond.js, prism-jsx.js, prism-csharp.js, prism-qml.js, and prism-javascript.js. Define the separate library around the exec and lastIndex interface, then verify that it handles the five listed nested-expression cases and normal regex behavior without changing Core.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- javascript
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100