Interpreting the D grammar

[Dmitry Olshansky via Digitalmars-d]

On 06-Aug-2015 11:26, MakersF wrote:
> On Sunday, 2 August 2015 at 18:22:01 UTC, Jacob Carlborg wrote:
>> On 02/08/15 19:15, Xinok wrote:
>>
>>> I guess you're not familiar with the theoretical aspect of "formal
>>> languages". The D grammar is a context-free grammar which cannot be
>>> reduced to a regular expression. As cym13 stated, there are some simple
>>> context-free grammars which can be rewritten as regular expressions, but
>>> the D grammar cannot be. Take a look at the Chomsky Hierarchy [1] for a
>>> better understanding.
>>>
>>> The classic example of a context-free language is the set of balanced
>>> parenthesis, i.e. (()) is balanced and ())))) is not. This language is
>>> not regular meaning you cannot write a regular expression for it, but
>>> you can write a context-free grammar for it.
>>
>> TextMate grammars are not _just_ regular expressions. They can define
>> balanced parentheses [1].
>>
>> The point of a language grammar in a text editor is not to have a 100%
>> correct implementation of the grammar. Rather it should syntax
>> highlight the code in a way that is useful for the user.
>>
>> [1] https://manual.macromates.com/en/language_grammars
>
> Then your best shot is to approximate the grammar with the regual
> expressions you have access to. You'll get to a point where some
> constructs can not be correctly represented; at that point you should
> probably write a regex which produces what the grammar produces and some
> more.
>

If one limits the depth of nested constructs to some reasonable value 
(e.g. 5-6) then any context-free grammar is regular. In big grammars 
combinatorial explosion may get quite high so that limit better be low.

If regular expressions are not hardcoded but rather themsleves are 
generated then it's quite feasible to do. In fact Perl folks have been 
doing this "approximate by regex" for years.

> In the example before of generating paired interleaved parentheses, you
> could generate every possible combination of parentheses, like
> ( (|)|[|]|{|}|" )*
> where only the external parentheses are syntax for the regex. That regex
> matches all the productions of the paired parentheses grammar, and many
> more strings.

Here again a regex constructed to match e.g. 10-level deep expressions 
is more then enough. Like this:

unittest
{
     import std.regex;
     string x = ""; // the first level is going to be ([^()]*\([^()]*\)?)*
     foreach(_; 0..10)
         x = `([^()]*\([^()]*`~ x ~`\)?)*`; // pump an extra level of 
parenthesised expression
     x = "^"~x~"$"; //make sure we match the whole string
     assert(matchFirst("a+(b*c-d*(e+45)+(aaaa-(d))+(c*2+1)", x));
}



-- 
Dmitry Olshansky