|Syntax tree generation under different parsing techniques firstname.lastname@example.org (Dave) (2004-04-21)|
|Re: Syntax tree generation under different parsing techniques email@example.com (Dmitry A. Kazakov) (2004-04-28)|
|Re: Syntax tree generation under different parsing techniques firstname.lastname@example.org (2004-05-16)|
|Date:||16 May 2004 23:40:17 -0400|
|Organization:||University of California, Riverside|
|Posted-Date:||16 May 2004 23:40:17 EDT|
Dave <email@example.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
: 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?
"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
: 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
Return to the
Search the comp.compilers archives again.