4
$\begingroup$

I want to specify in my grammar that an identifier could be any character except for a list of characters (that is have a deny list instead of the most common allow list).

I've seen the common practice is put the allowed list e.g.

IDENT:== (a-z|A-Z|0-9)+

But I wonder if there's a way to specify a deny list.

This is for a handcrafted parser, so I guess I could just say literally:

IDENTIFIER :== any printable unicode except for { } ( ) ; [] : , . 

But is there a correct way to describe this set? Or if the grammar is not going to be processed by a tool it doesn't matter what I put there?

$\endgroup$
6
  • 2
    $\begingroup$ I don't understand what this question is asking. Do you want syntax suggestions, or pros/cons of different choices, or are you asking about what's commonly used? $\endgroup$
    – Ginger
    May 31, 2023 at 15:26
  • $\begingroup$ @Ginger Added more context, I've seen the common practice is put the allowed list e.g. IDENT:== (a-z|A-Z|0-9)+ but I wonder if there's a way to specify a deny list. $\endgroup$
    – OscarRyz
    May 31, 2023 at 15:50
  • 1
    $\begingroup$ I'm voting to close this question because in its current state it's too subjective. In programming, there often is no "correct way" to do something. I'd advise editing this question so it asks for pros and cons instead, but make sure to read other pros/cons questions so you know what to avoid. $\endgroup$
    – Ginger
    May 31, 2023 at 15:56
  • $\begingroup$ Sounds good to me $\endgroup$
    – OscarRyz
    May 31, 2023 at 16:01
  • 3
    $\begingroup$ @Ginger I don't think you're understanding what this question is about. It's not about how the syntax of a language should be designed, it's asking about how to specify that syntax with something like EBNF. $\endgroup$ May 31, 2023 at 17:13

2 Answers 2

3
$\begingroup$

A relatively common convention in EBNF grammars is to allow set disjunction as an operation, usually written as -, as in this example from the EBNF wiki page itself:

character = letter | digit | symbol | "_" | " " ;
terminal = "'" , character - "'" , { character - "'" } , "'"
         | '"' , character - '"' , { character - '"' } , '"' ;

In your case, this might be something like

FORBIDDEN :== "{" | "}" | "(" | ")" | ";" | "[" | "]" | ":" | "," | "." 
IDENT_CHAR :== PRINTABLE - FORBIDDEN
IDENT :== IDENT_CHAR+

You do need to be a little careful with this if you try to difference one production from another — it's easy to end up outside of context-free grammars entirely — but it's always safe for sets of characters or anything else described by a regular expression.


Speaking of regular expressions, for the use case of defining tokens like identifiers, the fairly-standard regular-expression character set complement operation also works: [^][{}();:,.] means any character except the ones you listed, but including whitespace, control characters, etc that you may not want. If you have a covering grammar that has already ruled out other characters being present in the code at all then this is easier.

Many systems will also allow for example POSIX character classes within these: [^][{}();:,.[:space:][:cntrl:]] also excludes spaces and control characters. There are a lot of these classes to list out, a person reading probably won't know exactly what's in them, and it's possible that they still won't match up with what you want, but it could be very helpful for machine-processed grammar that uses this type of expressions.

This doesn't work for cases like "identifiers are any sequence of these characters except these keywords". However, it is always possible to compute a regular expression that does convey that difference (because the regular languages are closed under complementation and intersection), it's just likely to be enormous and incomprehensible. This may be useful for generated parsers, for example, but not as much for a specification that a person is expected to be able to read.


Finally, for a specification that is intended to be read and implemented by a person, not a machine, it's completely reasonable to provide a prose caveat to the productions you define. IDENTIFIER :== PRINTABLE+ except for .... Specifications for previously-existing languages that defined their syntax by an implementation often have this sort of thing in them, because it's matching the behaviour of a hand-rolled recursive-descent parser from thirty years ago.

It's entirely reasonable to do it now as well if that's appropriate to the audience you're communicating with. You could even use the sort of entirely-prose definition that you describe. There is no rule saying you have to have a machine grammar or that you need to communicate your meaning with punctuation within your grammar.

$\endgroup$
3
$\begingroup$

It is quite typical to exclude things with a NOT in regular expressions: For example:

NotAColon :== [^:]     // anything except a colon

Where [^..] is a negation set. See also https://stackoverflow.com/questions/1240275/how-to-negate-specific-word-in-regex

See for example:

https://chortle.ccsu.edu/finiteautomata/Section07/sect07_12.html

This is also supported in PEGs.

In general you have to be a little more careful in grammars as introducing negation can make your grammar non context free.

See for example https://www.sciencedirect.com/science/article/pii/S0019995860909657?via%3Dihub

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .