7
$\begingroup$

I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions in the course of parsing?

An example of non CFL construct i thought was the declaration of variables before their use. But in Compilers(Aho Ullman Sethi), it is stated that the C Language does not distinguish between identifiers on the basis of their names. All the identifiers are tokenized as 'id' by the Lexical Analyzer. If C is not completely defined by CFGs, please can anyone give an example of Non CFL construct in C?

Improve this question
$\endgroup$
1
  • $\begingroup$ The answer depends entirely on how you define the language of "C Programs". Is a string a C program if it has the right syntax, or is it a C program if it adheres to the C language specification in its entirety? Or is it a C program if some (subset of) standards-compliant C compilers are capable of generating an operable executable from it? I've always favored definitions of programming languages which require some semblance of semantic validity, although this usually means the languages are not context-free, as in your explanation. $\endgroup$
    – Patrick87
    Mar 24, 2014 at 14:50

1 Answer 1

Reset to default
13
$\begingroup$

The C language has typing rules. For example, you can't divide two pointers, and when you call a procedure accepting a pointer, you can't use a double. A C compiler analyzes its source in several phases: first there is lexical analysis, then the source is parsed, and so on. These phases are abstraction, and in fact additional information is passed from phase to phase. For example, even though the grammar of C doesn't care about names of variables, this information is passed, and that's how the attributed grammar can verify the typing rules. So there are additional mechanisms working on top of the grammar.

For an even simpler example, take the one given by Aho and Ullman. At the parsing phase, all variable names look "the same", yet you cannot use a variable unless it had been declared. This information is hidden from the context-free parser, but is retained as an attribute for the lexical phase, and is checked during parsing. The context-free grammar of C represents only some aspects of what legal C code is, which are useful for implementing a fast parser. On top of that parser, the other rules are checked, semantics are given to the C code, and machine code is generated.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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