1
$\begingroup$

Facing confusion due to two different texts stating different ways to show examples of ambiguous grammar, though the example exists in the first book.

The second book gives a different example, as shown attachment.

The first text is: Compliers and Compiler Generators An Introduction With C++, by Patrick D. Terry. The second is the book on Compiler design, by Louden.

First book example:

For the expression: a - b * c, and the Grammar:

Expression = Expression "-" 
Expression | Expression "*" 
Expression | Factor
Factor = "a" | "b" | "c"

Parse tree #1:

Expression -> Expression - Expression 
=> Factor - Expression
=> a - Expression
=> a - Expression * Expression
=> a - Factor * Expression
=> a - b * Factor
=> a - b * c

Parse tree #2:

Expression -> Expression * Expression 
=> Expression - Expression * Expression
=> Factor - Expression * Expression
=> a - Expression * Expression
=> a - Factor * Expression
=> a - b * Factor
=> a - b * c

I feel that the second derivation above is completely wrong, as not considers the left-to-right scan of the input string. The decision should have been based on the lookahead symbol only.

By the second text, the ambiguous grammar, can only be shown by the below second derivation:

Parse tree #2:

Expression -> Expression - Expression
=> Expression - Expression * Expression
=> Factor - Expression * Expression
=> a - Factor * Expression
=> a - b * Expression
=> a - b * Factor
=> a - b * c

Edit: The topic of showing ambiguous grammar is part of syllabus, and need tell which method (which of the two books) is correct. If the first book is correct, then need show by creating (in code, in C) an integrated parser-lexer, with lookahead of the lexer being passed on to the parser, as am confused how the parse tree is created in the second case, by the first book.

$\endgroup$
0

0

Your Answer

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

Browse other questions tagged or ask your own question.