Interpreting the D grammar

[deadalnix via Digitalmars-d]

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.