| conrad@lawyer.com 2006-02-24, 7:01 pm |
| Are binary trees used in top down parsers? If so, what do they use
for insertion? A key? Something else? This is important because my
tree api for a binary tree needs to make insertions as it goes down
the call stack while parsing. In order for it to insert into a tree,
it needs to find the proper place to insert. A key would not make
sense here as it needs to be ordered. So then the question becomes: by
what means do I locate, in my binary tree, the proper place for the
insertion of a node? (this isn't a homework question by the way. I am
self-taught, currently working through the dragon book and wanting to
incorporate an explicit tree structure in my top-down parser to
represent a given string of my language)
Also, while on the subject of data structures used in parse trees.
Are m-ary trees usually used over ordered trees? or the converse?
Where the attraction to ordered trees might be no limit in the number
of children. (i.e., just represent the children as a singly linked
list).
--
conrad
[Parsers typically build the tree from the bottom up, with the code
for each rule building a tree corresponding to what it parsed and
passing that up to higher level rules. For rules that don't naturally
have two subtrees such as if-then-else, some people use data
structures with more than two subtrees, some use several binary nodes.
It's a matter of taste more than anything else. -John]
|