Re: Syntax tree generation under different parsing techniques

thp@cs.ucr.edu
16 May 2004 23:40:17 -0400

          From comp.compilers

Related articles
Syntax tree generation under different parsing techniques better_cs_now@yahoo.com (Dave) (2004-04-21)
Re: Syntax tree generation under different parsing techniques mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2004-04-28)
Re: Syntax tree generation under different parsing techniques thp@cs.ucr.edu (2004-05-16)
| List of all articles for this month |

From: thp@cs.ucr.edu
Newsgroups: comp.compilers
Date: 16 May 2004 23:40:17 -0400
Organization: University of California, Riverside
References: 04-04-069
Keywords: parse
Posted-Date: 16 May 2004 23:40:17 EDT

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


Post a followup to this message

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