rustlanguage-lawyergrammarchomsky-hierarchy

Is Rust's syntactical grammar context-free or context-sensitive?


The syntactical grammar of hardly any programming language is regular, as they allow arbitrarily deeply nested parenthesis. Rust does, too:

let x = ((((()))));

But is Rust's syntactical grammar at least context-free? If not, what element makes the grammar context-sensitive? Or is the grammar even recursively enumerable, like C++'s syntactical grammar?


Related: Is Rust's lexical grammar regular, context-free or context-sensitive?


Solution

  • Rust includes a macro processor, whose operation is highly context-sensitive.

    You could attempt to skate around this issue by only doing syntactic analysis up to but not including macro expansion -- possible, but not particularly useful -- or by assuming that the macro expansion is done by some intermediate tool which is given a free pass to allow it to be Turing complete.

    But I'm inclined to say that it simply means that the Rust language is recursively enumerable.

    There are a number of restrictions on the validity of macro definitions which probably make the language (at least) context-sensitive, even if you settle for not performing the macro expansions as part of syntactic analysis.

    This doesn't mean that a context-free grammar cannot be useful as part of the syntactic analysis of Rust. It's probably essential, and it could even be useful to use a parser generator such as bison or Antlr (and examples of both exist). Like most programming languages, there is a simple superset of Rust which is context-free, and which can be usefully analysed with context-free grammar tools; however, in the end there are texts which will need to be rejected at compile-time as invalid even though they are part of the CF superset.