On Sunday, 2 August 2015 at 16:08:24 UTC, cym13 wrote:
On Sunday, 2 August 2015 at 14:50:35 UTC, Jacob Carlborg wrote:
I'm trying to read the D grammar [1] to enhance the D TextMate
bundle. If we take the add expression as an example. It's
defined like this in the grammar:
AddExpression:
MulExpression
AddExpression + MulExpression
AddExpression - MulExpression
CatExpression
And like this in the grammar made by Brian [2]:
addExpression:
mulExpression
| addExpression ('+' | '-' | '~') mulExpression
;
I'm not so familiar with grammars but this looks like it's
recursive. Is it possible to translate this piece of grammar
to a regular expression? TextMate uses regular expressions and
a couple of enhancements/extensions to define a grammar for a
language.
[1] http://dlang.org/grammar.html
[2] https://rawgit.com/Hackerpilot/DGrammar/master/grammar.html
You can't build a regular expression for any grammar. You can
for some grammars but those are only a simple subset. For
example, checking parens balance is impossible with common (not
recursive) regular expressions only, and even with recursion it
soon reaches its limitations.
You can for Regular grammar or any subclass:
https://en.wikipedia.org/wiki/Regular_grammar
You can't for more complex grammars.
That being said, you can have regex with placeholder and rerun
the regex on the content of the placeholder is the grammar is
recursive. I don't think that is an efficient and/or convenient
way to parse D.
