A Ovest Di Paperino

Welcome to the dark side.

Risposta al language pop quiz

Consider the abstract language L = {wcw | w is in (a|b)*}. L consists of all words composed of a repeated string of a's and b's separated by c, such as aabcaab. It can be proven that 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 the 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 directly implies the non-context-freedom of programming languages like Algol and 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 Algol or Pascal does not specify the characters in an identifier. Instead, all identifiers are represented by a token such as id in the grammar. In a complier for such a language, the semantic analysis phase checks that identifiers have been declared before their use.


Tratto da "Compilers: Principles, Techniques and Tools", prima edizione, pagina 179, esempio 4.11

In parole povere il linguaggio non è context free anche se la grammatica per farne il parsing è context free (per ovvi motivi!). Quindi la risposta al pop-quiz è no. Big Smile