0
$\begingroup$

Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form

How can you distinguish between the pipe character as symbol in C++ or as a Backus–Naur symbol?

Equivalently, how would you tell whether the | character represented a meta-logical operator or whether it represented the or-operator in C++?

In C++ vertical bars (pipe characters) are often used as the logical-or operator. An example of | is shown below

if (inside_trash.is_full() || today.is_trash_day() ) {
    outside_trash << inside_trash;
}

But | is also used as a character in Backus–Naur Normal Form

I need some code to be able to parse a file written in something close to Backus–Naur Normal Form. We cannot just stare at the production rules with a human pair of eyes and say "well, that vertical bar right there is a terminal symbol, not a meta-logical choice operator".

In the following production rules | is a problem for boolean operators:

<conditional> ::= if ( <exp> ) <optional-else-clause>

<optional-else-clause> ::=  else { <block> }

     | else if (<exp>) { <block> }
 <optional-else-clause>
     | <nothing>

<exp> ::= <func-call> | <variable> | <literal>

<func-call> ::= <infix-fuc-call> | <prefix-func-call>

<prefix-func-call> ::= foo(<exp>)

<infix-call> ::= <exp> <operator> <exp> 

<operator> ::= < | > | == | != | <= | >= | <- | -> | . | &= | << | >>  | %= | *= | += | ^=  | <<= | -= | && | /= | | || |

<block> ::= <func-call>; 

<literal> ::= "hello" | 42 | -23 |
            | 42.0 | 3.14159 | ...
            | 'a' | 'b' | ...
            | true | false
<nothing> ::= 

In most computer programs, we traditionally put a backslash to the left of meta-characters, and if we want a literal back-slash we write \\. Is there something like a backslash escape for Backus–Naur Normal Form? Maybe \| is the pipe character and \\ is backslash?

For example, in the string "Noam Chomsky\n" the \n is a line-feed character, not back-slash followed by the letter "n".

$\endgroup$

1 Answer 1

1
$\begingroup$

I suggest you read up on BNF. For instance, you could start with the Wikipedia article: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form. Often, we put literal characters in quotes, so "|" represents a | pipe symbol in the C++ program (i.e., a terminal to be matched during grammar parsing), and | represents the symbol that separates alternatives on the right side of a BNF rule.

It's common for people to use BNF in an informal way that differs from person to person. Sometimes people will omit the quotes for literals (terminals), in cases where this won't cause confusion. As your question illustrates, that can cause confusion if we want to match on literal symbols like |.

$\endgroup$

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.