Relation between programming languages requiring declaration of variables before use and using the token class $\text{id}$ while parsing

Question

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.

Answer 1

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.

Answer 2

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

FUNCDEF ::= 'func' ID '(' PARAMDEF ')' FUNCBODY

and

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".