I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al. where I came across the following excerpt.

Example 4.11. Consider the abstract language $L_1 = \text{ { $wcw$ | $w$ is in $(a|b)^*$}}$. $L_1$ consists of all words composed of a repeated string of $a$'s and $b$'s separated by a $c$, such as $aabcaab$. It can be proven this language is not context free. This language abstracts the problem of checking that identifiers are declared before their use in a program. That is, the first $w$ in $wcw$ represents the declaration of an identifier $w$. The second $w$ represents its use. While it is beyond the scope of this book to prove it, the non-context-freedom of $L_1$, directly implies the non-context-freedom of programming languages like $\text{Algol}$ and $\text{Pascal}$, which require declaration of identifiers before their use, and which allow identifiers of arbitrary length.

For this reason, a grammar for the syntax of $\text{Algol}$ or $\text{Pascal}$ does not specify the characters in an identifier. Instead, all identifiers are represented by a token such as $\text{id}$ in the grammar. In a compiler for such a language, the semantic analysis phase checks that identifiers have been declared before their use. □

I can understand that since $\text{Algol}$ and $\text{Pascal}$, require declaration of identifiers before their use we cannot check this property using context free grammar. But what is the connection of this with the point of "allowing identifiers of arbitrary length"?

Moreover the authors add, that instead of using the characters in an identifier, identifiers are represented by the token class $\text{id}$. That the identifiers are represented by the token class $\text{id}$, was known to me as a fact, but I did not quite know what is the significance of this as far as the explanation in the example of the text is concerned.

Please explain me.

  • 2
    $\begingroup$ I suggest finding a more modern textbook on the topic. $\endgroup$ – Yuval Filmus Mar 13 at 22:07

In order for their example to work, the authors need identifiers to be of unlimited length. This is because the language $$ \{ wcw : w \in \{a,b\}^*, |w| \leq n \} $$ is context-free (indeed, regular).

The syntax of a language like Pascal or Algol is context-free. This accomplished by waiving the requirement that an identifier be declared before its usage; this will be checked on-the-fly by the parser. This idea is implemented by representing identifiers as a single token in the grammar of Pascal or Algol.

  • $\begingroup$ Thanks for the help!! $\endgroup$ – Abhishek Ghosh Mar 14 at 9:24

Defining the grammar in terms of an abstract $id$ token allows you to write a context-free grammar for a language which would otherwise be context-sensitive, by dropping restrictions from the grammar. Something like



FUNCCALL ::= ID '(' ARGS ')'

This is perfectly context-free, by simply treating the $id$ as an abstract token and ignoring the restriction that a FUNCCALL with some $id$ must be preceded by a FUNCDEF with the same $id$.

Instead, we either declare this restriction to be a semantic restriction, not a syntactic one, and ship the responsibility for checking it off to the semantic analyzer, not the syntactic analyzer (aka parser). Or we declare it an additional syntactic retriction not captured by the grammar.

See, for example the ECMAScript specification, which pulls this latter trick quite often.

If you look at the specification of variable declarations, you will find a good example of a restriction that is not context-free: you cannot declare the same variable twice. But, that is not specified in the grammar, it is specified in a subsection called "Static Semantics" (which many clauses in the spec have):

It is a Syntax Error if the BoundNames of BindingList contains any duplicate entries.

So, here you can see that the specification says "this is a syntactic error, but we are specifying that part of the syntax outside of the grammar, in plain English".

  • $\begingroup$ I have got the idea which you have tried to explain, but could you clarify a doubt of mine. How do you say that the two lines of the grammar defined by you are 'context-sensitive'? I did not get this point. However I know that the language $L_1$ in the question is actually a context sensitive one (as Yuval explained) if $w$ is of arbitrary length. If instead of considering the id.lexeme if we only consider the id as an abstract token, then the grammar/ language becomes context-free. [This is what you explained in the line following the two productions]. $\endgroup$ – Abhishek Ghosh Mar 14 at 9:23
  • 1
    $\begingroup$ The resulting grammar is context-free, that is the whole point. It would only be context-sensitive if you require that for all function calls with identifier $id$, there must be exactly one preceding function definition with the same $id$. But in the grammar, we simply allow function definitions with arbitrary identifiers (which would also allow us to define the same function multiple times, which we probably want to prohibit) and function calls with arbitrary identifiers, and we then check the restriction in a later stage of the compiler. $\endgroup$ – Jörg W Mittag Mar 14 at 9:28
  • $\begingroup$ got the point. Your first statement in the answer was a general point, where id.lexeme is considered in the ID part and in such case the grammar shall be context sensitive ... Thank you!!! $\endgroup$ – Abhishek Ghosh Mar 14 at 9:31
  • 1
    $\begingroup$ Ah. Now I see. I didn't realize that I wrote "context-sensitive" in the first sentence :-D I read this a dozen times, but in my brain it always read "context-free". $\endgroup$ – Jörg W Mittag Mar 14 at 9:38
  • $\begingroup$ Nothiing prevents the shown grammar from also specifying that ID is a non-empty string of letters, without affecting the discussion about context-freeness. $\endgroup$ – Andrej Bauer Mar 14 at 12:11

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.