1
$\begingroup$

I tried to write a non-ambiguous grammar for lambda calculus, but it does not really work. The recursive-descent parser is easy to write though. I googled but all results I collected so far are ambiguous, or rely on PEG which has a notion of explicit try-backtrack.

I'm now quite skeptical the non-ambiguous CFG does not actually exist. It must be written in Context-Sensitive Grammar to be non-ambiguous. Does it or does it not? Is it provable?

edit: Actually my original problem is a lambda calculus enhanced with a parallel evaluation operator +. So expr + expr is also expr. The ambiguous grammar is as follows:

E -> E E | E + E | n | x | lam x. E | (E)

My best approximation so far is:

E -> P
P -> P + A | A
A -> lam x. A | B
B -> B L | L
L -> x | n | (E)

However it does not accept x lam y.y.

$\endgroup$
2
  • $\begingroup$ You need to specify the relative precedence of the operators in order for someone to create an unambiguous grammar. Is you "best approximation" supposedly an indication? $\endgroup$
    – rici
    Nov 5 '21 at 5:03
  • $\begingroup$ @rici Thanks, I didn't notice I forgot that part. I'm implicitly assuming the standard precedence, lam < + < application < n|x, when posting this question. But I'm open to any precedence as long as the grammar is unambiguous. $\endgroup$ Nov 5 '21 at 7:19
3
$\begingroup$

You certainly don't need a context-sensitive grammar to solve this problem (and it probably wouldn't help you, either). In fact, you can solve it with the precedence declarations available in most standard parser-generating tools. For example, a simple bison grammar is:

%left '+'
%left LAMBDA_LEFT
%left APPLY "lambda" VALUE ID '('
%%
expr : expr '+' expr                            { $$ = make_para($1, $3); }
     | expr expr              %prec APPLY       { $$ = make_apply($1, $2); }
     | "lambda" ID '.' expr   %prec LAMBDA_LEFT { $$ = make_lambda($2, $4); }
     | '(' expr ')'                             { $$ = $2; }
     | ID                                       { $$ = make_ident($1); }
     | VALUE                                    { $$ = make_value($1); }

There are a few tricks in the above. Normally, precedence declarations are used in operator grammars, which are grammars in which no production has two consecutive non-terminals. This is not an operator precedence grammar because of the application production ($E\to E E$); in effect, the application "operator" is invisible. To compensate, I defined precedence levels for the four tokens in $\mathit{FIRST}(E)$, which act as a kind of stand-in for the missing application operator. This works, but it's a bit fragile; adding more features to the grammar must be done with a bit of care. In addition, I needed to use a pseudo-terminal (APPLY) to assign the application production to a precedence level, since Bison only automatically assigns productions which have at least one terminal symbol (using the last terminal symbol).

The key feature of that precedence declaration is the pseudo-terminal LAMBDA_LEFT, which is used to give the lambda production a left precedence distinct from its right precedence. If the expression grammar meets the requirements of an operator-precedence grammar, then the use of explicit left-precedence declarations can be used to produce deterministic LR parsers.

Bison/yacc-style precedence declarations do not introduce any extra power into the CFG formalism, which is evident from the way they are implemented. Precedence declarations are used only to resolve parsing conflicts; the parser generator produces a pushdown automaton for the grammar as written, and then uses the declarations to remove all but one transition from any state which has multiple transitions on the same terminal. (More accurately, the parser generator tries to remove conflicting transitions. Since precedence declarations are only used to resolve shift-reduce conflicts, not reduce-reduce conflicts, not all grammars can be resolved in this way.) The result is still a pushdown automaton, with the same states but fewer transitions, and is now deterministic. Thus, the language it accepts could be accepted by a deterministic context-free grammar; DPDAs and DCFGs accept the same set of languages.

Unfortunately, the usual proof of this correlation doesn't tell us how to construct the deterministic context-free grammar. Nonetheless, both mathematicians and parsing practitioners are generally satisfied with this outcome, the first group because "a solution exists" and the second group because there is a practical work-around which is not very difficult to apply. However, sometimes it is useful to actually produce the deterministic context-free grammar. And that is possible. It's even possible to do automatically, although the simplest automatic approach I know of produces a lot of unnecessary non-terminals. (See Annika Aasa, Precedences in specifications and implementations of programming languages. Theoretical Computer Science, 142(1):3–26, 1995. doi:10.1016/0304-3975(95)90680-J.)

In simple cases, like this one, the transformation can be done by hand. The problem is that cascading precedence grammars can't capture the fact that a lambda expression cannot be the left operand of an application (because the application should be inside the lambda), while an application cannot be the right operand of an application (because application is left-associative). This inversion of precedences is problematic in itself, but there is a further complication: the left operand of an application also cannot be an application whose right operand is a lambda. Or an application whose right operand is an application whose right operand is a lambda. And so on.

Consequently, we need two different non-terminals for application: one (left-apply) describes the subset of expressions which can be used as the left operand of an application, and the other describes the complete application syntax:

expr  : expr '+' apply            { $$ = make_para($1, $3); }
      | apply
apply : left-apply lambda         { $$ = make_apply($1, $2); }
      | lambda
      | left-apply
left-apply
      : left-apply atom           { $$ = make_apply($1, $2); }
      | atom
lambda: "lambda" ID '.' apply     { $$ = make_lambda($2, $4); }
atom  : '(' expr ')'              { $$ = $2; }
      | ID                        { $$ = make_ident($1); }
      | VALUE                     { $$ = make_value($1); }
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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