6
$\begingroup$

This question asks which programming languages have a syntax that cannot be described by deterministic context-free grammars - the answer is "Many [...] including Algol 60, C, and C++".

Until recently I thought Lua was an example of a language which could be described by a deterministic context-free grammar. This belief was reinforced by looking at The Complete Syntax of Lua as described in the language reference. Unfortunately it turns out that this grammar has a well-known ("function call x new statement") ambiguity, and that Lua must be parsed using a "greedy" algorithm, not a deterministic one.

Which programming languages have a syntax that can be described by deterministic context-free grammars?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I don't know, but I strongly suspect that most of the Wirth languages (e.g. Pascal and the Modula family) have unambiguous grammars, because they are operator grammars. Algol is a special case because it predates a lot of parsing theory; it doesn't even have a finite number of grammar productions and it was eventually formalised with a grammar which generates the grammar (known as a van Wijngaarden grammar). Note that any language with user-defined operators can't be described by a fixed grammar, let alone a deterministic one. $\endgroup$
    – Pseudonym ♦
    Commented Jul 18, 2016 at 6:52
  • $\begingroup$ The question makes sense either way, because the languages mentioned in the question are statically ambiguous, and can only be disambiguated using semantic information. A famous example from C (and C++) is (A)*B which can be interpreted as either multiplying A by B or casting *B to type A, depending on whether A is the name of a variable or a type. Well, I don't know about Lua... $\endgroup$
    – Pseudonym ♦
    Commented Jul 18, 2016 at 8:32
  • $\begingroup$ @Pseudonym - When you say the Wirth langauges are "operator grammars", is this the same thing as operator-precedence grammars? $\endgroup$
    – user200783
    Commented Jul 18, 2016 at 9:26
  • 1
    $\begingroup$ No. A programming language has an operator grammar if any two identifiers are separated by at least one operator or keyword. C and C++ do not have grammars because you can say, for example, "my_type foo();", where "my_type" and "foo" are both identifiers. In fact, this very example is an ambiguity in C++: it could be declaring a function or could be calling a constructor. $\endgroup$
    – Pseudonym ♦
    Commented Jul 18, 2016 at 12:51
  • 4
    $\begingroup$ Surely Lisp's S-expressions are deterministic context free? $\endgroup$
    – Joey Eremondi
    Commented Jul 18, 2016 at 18:58

0

Reset to default

Your Answer

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