How would you specify a grammar that can parse letters separated by single underscores?

Question

In JavaScript, let's say, it is easy to build a string intermixed with single underscores by just joining the string parts.

let string = ['foo', 'bar', 'baz'].join('_')

In addition, it is straightforward to write a grammar that can have letters separated by at least one underscore.

grammar = letter letterOrUnderscore*
letter = a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
underscore = _
letterOrUnderscore = underscore|letter

That will match the input string:

foo_bar_baz

However, it will also match these unwanted strings:

a____
ab__c
abc__d___

Basically, it will match sequences of underscores, when what we want is only one underscore between each sequence of letters, and we shouldn't have trailing underscores. So only these are acceptable, for example:

a
ab_c
abc_d

The question is, how do you define a grammar to only allow 1 underscore between each sequence of letters? I can't figure out how to write any sort of custom "grammar DSL" that can, in a straightforward way, handle this situation... I'm stumped currently how to do this.

grammar = letter then
  if previous == letter
    next = letter | underscore
  else
    next = letter

So it seems to need to access to the previous state, is there no other way to define this? Besides not being very "DSL-like", it's also significantly harder to handle this sort of situation.

Answer 1

What you are describing is a regular language, so describing it with a regular expression would be a good approach.

Another way to view the language is one word, followed by zero or more (underscore word) sequences.

In PCRE syntax, [a-z]+(_[a-z]+)*.

The same idea can be used to remove left recursion from some grammars; instead of a production rule like $E \to E + E$ (expressions can be combined with plus), you use $E \to T S$ with $S \to \varepsilon; S \to + T S$ (terms can be followed by zero or more "operations", which is an operator followed by a term)