Re: Syntax tree generation under different parsing techniques

Dave <better_cs_now@yahoo.com> wrote:
: I would like to decouple my parsing and translation (here, "translation"
: consists only of interpreting; I'm not actually generating code).
: Currently, I'm doing predictive recursive descent parsing, but I have to do
: some kludgy backtracking because there is one spot in the grammar that is
: not suitable for this parsing technique. My goal is to employ some other
: parsing technique and to generate a syntax tree while doing so (which I
: don't currently do; as I opened with, the translation is inline with the
: parsing).
:
: My question is: Regardless of the parsing technique used, is it always
: possible to generate a syntax tree? It just seems intuitive to me that some
: techniques don't lend themselves to the generation of a syntax tree. It's
: hard for me to articulate why, but it seems that way. For example, if I
: were to take the easy route and implement CYK, how well would it lend itself
: to generate a syntax tree?


From <http://en.wikipedia.org/wiki/CYK_algorithm>:


    "It is simple to extend the above algorithm to not only determine if a
    sentence is in a language, but to also construct a parse tree, by
    storing parse tree nodes as elements of the array, instead of
    booleans. Since the grammars being recognized can be ambiguous, it is
    necessary to store a list of nodes (unless one wishes to only pick one
    possible parse tree); the end result is then a forest of possible
    parse trees."


: What about other techniques?


Hmmmmm. One might be able to construct a grammar and a string whose
derivability from that grammar is obvious via say the pigeon-hole
principle.


Tom Payne

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