CODEWITHSUNDEEP
compiler-constructionbnf
demsee
demsee

Reputation: 53

BNF ambiguities

"Compiler construction" book gives an example of the original definition of Algol 60. They contain ambiguities.

Find at least two different structures for

IF a THEN b ELSE c=d

There is part of definition

unconditional Statement = basicStatement | forStatement | compoundStatement | ... .
ifStatement = "IF" BooleanExpression "THEN" unconditionalStatement.
conditionalStatement = ifStatement | ifStatement "ELSE" statement.

statement = unconditionalStatement | conditionalStatement.

so then, since:

A "else" B, and A => "if" a "then" b

we gets:

if a then b else B

and it seems, B is c=d

Where is ambiguities? How to find two different structures?

Upvotes: 0

Views: 169

Answers (1)

rici
rici

Reputation: 241671

IF a THEN b ELSE c=d is not a statement. It's an expression of some kind; what kind it is depends on the type of b. (The statement would be IF a THEN b ELSE c:=d. Recall that in Algol, := is assignment, = is equality comparison, and == is a syntax error.)

If b is a boolean, then it is a boolean conditional expression whose alternatives are b and c=d; in this case, c and d must have arithmetic type because the grammar doesn't allow comparing booleans with =.

But if b is arithmetic, then it is a comparison between the arithemtic conditional expression IF a THEN b ELSE c and d (and, again, c and d must have arithmetic type).

At least, that's my reading of the grammar. It's not exactly ambiguous, but the BNF is not sufficient to resolve the parse because the language is not context-free. Selecting the correct parse requires the previous declaration of b, which can only be achieved with a context-sensitive grammar.

Upvotes: 2

Related Questions