<p>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).</p>
<p>I've seen the common practice is put the allowed list e.g.</p>
<p><code>IDENT:== (a-z|A-Z|0-9)+</code></p>
<p>But I wonder if there's a way to specify a deny list.</p>
<p>This is for a handcrafted parser, so I guess I could just say literally:</p>
<pre><code>IDENTIFIER :== any printable unicode except for { } ( ) ; [] : , . 
</code></pre>
<p>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?</p>

<parsing><grammar><specification>
In a grammar specification, how to exclude characters?
CC BY-SA 4.0
2023-05-31T15:26:50.950Z
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?
Ginger
CC BY-SA 4.0
2023-05-31T15:50:09.687Z
@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.
OscarRyz
CC BY-SA 4.0
2023-05-31T15:56:52.490Z
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.
Ginger
CC BY-SA 4.0
2023-05-31T16:01:08.330Z
Sounds good to me
OscarRyz
CC BY-SA 4.0
2023-05-31T17:13:36.417Z
@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.
rydwolf
CC BY-SA 4.0
2023-05-31T17:17:45.013Z
@RydwolfPrograms Ah, that wasn't clear from the content of the question.
Ginger
<p>It is quite typical to exclude things with a NOT in regular expressions:
For example:</p>
<pre><code>NotAColon :== [^:]     // anything except a colon
</code></pre>
<p>Where [^..] is a negation set.
See also <a href="https://stackoverflow.com/questions/1240275/how-to-negate-specific-word-in-regex">https://stackoverflow.com/questions/1240275/how-to-negate-specific-word-in-regex</a></p>
<p>See for example:</p>
<p><a href="https://chortle.ccsu.edu/finiteautomata/Section07/sect07_12.html" rel="nofollow noreferrer">https://chortle.ccsu.edu/finiteautomata/Section07/sect07_12.html</a></p>
<p>This is also supported in <a href="https://en.wikipedia.org/wiki/Parsing_expression_grammar" rel="nofollow noreferrer">PEGs</a>.</p>
<p>In general you have to be a little more careful in grammars
as introducing negation can make your grammar non context free.</p>
<p>See for example <a href="https://www.sciencedirect.com/science/article/pii/S0019995860909657?via%3Dihub" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S0019995860909657?via%3Dihub</a></p>

CC BY-SA 4.0
2023-06-01T01:20:03.800Z
2023-06-01T01:20:03.800Z
Bruce Adams
<p>A relatively common convention in EBNF grammars is to allow set disjunction as an operation, usually written as <code>-</code>, as in this example from <a href="https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form#EBNF" rel="nofollow noreferrer">the EBNF wiki page</a> itself:</p>
<pre class="lang-none prettyprint-override"><code>character = letter | digit | symbol | &quot;_&quot; | &quot; &quot; ;
terminal = &quot;'&quot; , character - &quot;'&quot; , { character - &quot;'&quot; } , &quot;'&quot;
         | '&quot;' , character - '&quot;' , { character - '&quot;' } , '&quot;' ;
</code></pre>
<p>In your case, this might be something like</p>
<pre class="lang-none prettyprint-override"><code>FORBIDDEN :== &quot;{&quot; | &quot;}&quot; | &quot;(&quot; | &quot;)&quot; | &quot;;&quot; | &quot;[&quot; | &quot;]&quot; | &quot;:&quot; | &quot;,&quot; | &quot;.&quot; 
IDENT_CHAR :== PRINTABLE - FORBIDDEN
IDENT :== IDENT_CHAR+
</code></pre>
<p>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.</p>
<hr />
<p>Speaking of regular expressions, for the use case of defining tokens like identifiers, the fairly-standard regular-expression character set complement operation also works: <code>[^][{}();:,.]</code> means <em>any</em> 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.</p>
<p>Many systems will also allow for example <a href="https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap07.html#tag_07_03_01" rel="nofollow noreferrer">POSIX character classes</a> within these: <code>[^][{}();:,.[:space:][:cntrl:]]</code> 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.</p>
<p>This doesn't work for cases like &quot;identifiers are any sequence of these characters <em>except</em> these keywords&quot;. However, it <em>is</em> 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.</p>
<hr />
<p>Finally, for a specification that <em>is</em> 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. <code>IDENTIFIER :== PRINTABLE+ except for ...</code>. 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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-06-01T05:58:10.013Z
2023-06-01T05:58:10.013Z
Michael Homer
# In a grammar specification, how to exclude characters?
Posted by: username_0 on 2023-05-31
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?
**Tags:** parsing grammar specification
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_0**: Sounds good to me  
> **username_2**: @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.  
> **username_1**: @RydwolfPrograms Ah, that wasn't clear from the content of the question.  
---
## 2 answers
### Answer by username_4 on 2023-06-01. Score: 3 | Accepted answer
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.
---
### Answer by username_3 on 2023-06-01. Score: 3
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
---
