3
$\begingroup$

Say we want to support: xx

The following grammar does accept it:

  • S -> xAx
  • A -> ε.

because S => xAx => xx.

But what about supporting: x x

I realize this might be a stupid question but I'm really unable to find a definite answer. Especially as

  • S -> xAx
  • S -> x A x

appear to be equivalent representations in most references.

$\endgroup$
  • $\begingroup$ A common approach seen in actual programming languages is to have two grammars. A token grammar describes how the input is tokenized. This grammar is often pretty simple, working on single characters. E.g. a sequence of digits produces a number token. Usually, any sequence of whitespace characters at this point forms a token separator. The interesting grammars in those languages work on token level, which means they don't deal with whitespace. $\endgroup$ – MSalters May 28 '15 at 14:16
5
$\begingroup$

This is a classical confusion between language and metalanguage.

More generally, you have the same problem when you want to include in your symbols, expecially terminal symbols, characters that have syntactic meaning in the syntax of grammars, for example the symbol "|" which is often used to give on the same line all possible right-hand-sides for a given non-terminal.

In such a case, you do what I just did: use some mechanism for quotation, such as "|", or " " in the case of a space. Some form of quoting is the usual technique to avoid confusion between language and metalanguage. And as you remarked, the language of grammars already uses the space for its own (lack of) purposes.

So you write:

S -> xAx
A -> " "

Of course, the spaces outside the quotes still play the same role as before, wherever allowed. So the grammar could be written as well:

S ->  x A  x
A  ->   " "

Whatever is within quote must be written exactly as expected.

However, in many contexts (such as programming language syntax), it is implicit that you can add spaces wherever you want between terminal. So you have to be clear whather you just want one compulsory space where you have the terminal " ", or whether you forbid spaces, unless specified by the syntax as done here.

The quotation marks are metasyntax, i.e. part of the language used to write the grammar, like the arrow. The analyser (whether LR(1) or any other) will ignore the quotes, as it ignores the arrow ->. It would work as well with a grammar written as [(S,xAx)(A," ")]. Some metalanguages for writing grammars, such as BNF, simplify the issue by making the quotes compulsory around terminals ... though there is still a problem when terminals include the quoting symbols ... but this has solutions.

Another question you may want to look at is: What are the meanings of metalanguage and metasyntax and EBNF?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm sorry if this sounds stupid, your reply is very helpful, but I still need to clear some of my confusion: in paper, would you just add space between (non-terminal or terminal) symbols or would you write what you wrote here? The thing is, also, that some online parsers recognize spacing between symbols, others don't. $\endgroup$ – Xpl0 Dec 2 '14 at 21:35
  • $\begingroup$ For instance, I think LR(1) analysis would be wrong (?) if it took the quotation marks into account. $\endgroup$ – Xpl0 Dec 2 '14 at 21:37
  • $\begingroup$ @Xpl0 I could write S -> x A x and A -> " " for example. The problem is more that in many contexts (such as programming language syntax), it is implicit that you can add spaces wherever you want between terminal. So you have to be clear whather you just want there one compulsory space, or whether you forbid spaces, unless specified by the syntax. Does this answer your question? $\endgroup$ – babou Dec 2 '14 at 21:40
  • $\begingroup$ The quotation marks are metasyntax, i.e. part of the language used to write the grammar, like the arrow. The analyse will ignore the quotes, as it ignores the arrow. It would work as well with a grammar written as [(S,xAx)(A," ")]. Some metalanguages for grammar, such as BNF, simplify the issue by making the quotes compulsory around terminals ... though there is still a problem when terminals include the quoting symbols ... but this has solutions. $\endgroup$ – babou Dec 2 '14 at 21:48
  • $\begingroup$ I think I get it now. Thank you for taking the time! $\endgroup$ – Xpl0 Dec 2 '14 at 21:50
3
$\begingroup$

If I'm not wrong, you just want to include a whitespace in your grammar. In that case, a whitespace is just another character which should be included in your alphabet of the language. Say, denoting whitespace with $$\beth$$ you just include a rule like $$A \to \beth$$ in your grammar.

This will lead to the following derivation: $$S \to xAx \to x\beth x$$ where the beth symbol is nothing but a whitespace. So the string 'x x' is in the language defined by the given grammar.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! While your answer is correct, I'm thinking more about "on paper" solutions to this problem. $\endgroup$ – Xpl0 Dec 2 '14 at 21:51
  • 2
    $\begingroup$ @Xpl0 I don't quite understand your comment. One can perfectly well use some symbol to represent whitespace on paper. Rather than using random letters, it would be more normal to use something like $\sqcup$ (\sqcup in LaTeX) or an underscore. $\endgroup$ – David Richerby Dec 2 '14 at 23:06
2
$\begingroup$

A space is just another symbol of the alphabet. You can make up a notation for it such as " " to make it easier to spot.

That said, in the context of programming languages, there is no need to describe whitespace as part of the grammar; whitespace is used during lexical analysis to separate the various lexemes, and is otherwise ignored. For example, a C lexer would translate the strings a+b and a + b to the same sequence of lexemes, which can be something like ID PLUS ID; each ID also comes with an attribute giving its name.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you for answering! I do have enough experience with flex so I'm aware of how lexical analysis works in the context of programming languages. However, I'm more focused on the "theoretical" aspect of it - your first paragraph, more or less. $\endgroup$ – Xpl0 Dec 2 '14 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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