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:


However, it will also match these unwanted strings:


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:


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
    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.


1 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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.