Re: Parsing fully context-free grammars

>>This is somewhat unspecific. You have two different parses, which generate
>>two different parse trees. What do you mean with emulating these two
>>different parse trees from a single one?"


Well, in particular, I'm looking at the two parse trees in Fig. 4.6,
pg. 175 of the Dragon Book. If you just read the translation from the
leaves of the trees, the first gives


if(expr) then {if(expr) then {stmt} else {stmt}}


the second gives


if(expr) then {if(expr) then {stmt}} else {stmt}


APG actually generates the first tree. But during a depth-first
traversal of that tree, using different stack push/pop mechanisms at
the recursive "stmt" nodes, it's not hard to match the "else" either
of the two "then"s, effectively emulating the second tree during a
depth-first traversal of the first.


Lowell Thomas

Return to the comp.compilers page.
Search the comp.compilers archives again.