Correct way to derive parse trees, for a given input, to show ambiguity.
by ajiten from LinuxQuestions.org on (#6DNR5)
Is it correct to state that the below grammar can handle the expression: a - b * c, by the below two different parse trees.
Code: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 * cI 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.
If possible show by a C language code snippet, how the implementation of the second derivation, is correct, as the book titled: Compliers and Compiler Generators An Introduction With C++, by Patrick D. Terry, shows the above example, in Section 6.4, page #131
For me, the ambiguous grammar can only be shown by the below second derivation:
Code:Parse tree #2:
Expression -> Expression - Expression
=> Expression - Expression * Expression
=> Factor - Expression * Expression
=> a - Factor * Expression
=> a - b * Expression
=> a - b * Factor
=> a - b * cThe second way, is inspired by Louden's book example, on page #115, as shown in the attachment below.
But, the bigger question is am not sure if the implementation of the above grammar, say in C, would leave any chance for the second parse tree generation, either of the first type (Patrick Terry's book); or of the second type (inspired by Louden's book, whose screenshot is attached).
Only code snippet (say, in C) can clear this.
Attached Thumbnails
Code: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 * cI 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.
If possible show by a C language code snippet, how the implementation of the second derivation, is correct, as the book titled: Compliers and Compiler Generators An Introduction With C++, by Patrick D. Terry, shows the above example, in Section 6.4, page #131
For me, the ambiguous grammar can only be shown by the below second derivation:
Code:Parse tree #2:
Expression -> Expression - Expression
=> Expression - Expression * Expression
=> Factor - Expression * Expression
=> a - Factor * Expression
=> a - b * Expression
=> a - b * Factor
=> a - b * cThe second way, is inspired by Louden's book example, on page #115, as shown in the attachment below.
But, the bigger question is am not sure if the implementation of the above grammar, say in C, would leave any chance for the second parse tree generation, either of the first type (Patrick Terry's book); or of the second type (inspired by Louden's book, whose screenshot is attached).
Only code snippet (say, in C) can clear this.
Attached Thumbnails