Re: Parsing fully context-free grammars

"Lowell Thomas" <lowell@coasttocoastresearch.com>
22 Sep 2005 23:41:51 -0400

          From comp.compilers

Related articles
Parsing fully context-free grammars lowell@coasttocoastresearch.com (Lowell Thomas) (2005-09-17)
Re: Parsing fully context-free grammars haberg@math.su.se (2005-09-18)
Re: Parsing fully context-free grammars lowell@coasttocoastresearch.com (Lowell Thomas) (2005-09-22)
Re: Parsing fully context-free grammars haberg@math.su.se (2005-09-23)
Re: Parsing fully context-free grammars paul@parsetec.com (Paul Mann) (2005-10-02)
Re: Parsing fully context-free grammars haberg@math.su.se (2005-10-02)
Re: Parsing fully context-free grammars drikosv@otenet.gr (Evangelos Drikos) (2005-10-03)
Re: Parsing fully context-free grammars paul@parsetec.com (Paul Mann) (2005-10-04)
Re: Parsing fully context-free grammars hannah@schlund.de (2005-10-06)
[2 later articles]
| List of all articles for this month |

From: "Lowell Thomas" <lowell@coasttocoastresearch.com>
Newsgroups: comp.compilers
Date: 22 Sep 2005 23:41:51 -0400
Organization: Compilers Central
Keywords: parse

>>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



Post a followup to this message

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