Thu, 12 Feb 2009 20:22:57 +0000

Related articles |
---|

Parsing implicit operators with recursive descent? johann@myrkraverk.com (Johann 'Myrkraverk' Oskarsson) (2009-02-06) |

Re: Parsing implicit operators with recursive descent? mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2009-02-07) |

Re: Parsing implicit operators with recursive descent? armelasselin@hotmail.com (Armel) (2009-02-07) |

Re: Parsing implicit operators with recursive descent? torbenm@pc-003.diku.dk (2009-02-09) |

Re: Parsing implicit operators with recursive descent? barry.j.kelly@gmail.com (Barry Kelly) (2009-02-12) |

Re: Parsing implicit operators with recursive descent? johann@myrkraverk.com (Johann 'Myrkraverk' Oskarsson) (2010-01-30) |

Re: Parsing implicit operators with recursive descent? kkylheku@gmail.com (Kaz Kylheku) (2010-02-01) |

From: | Barry Kelly <barry.j.kelly@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Thu, 12 Feb 2009 20:22:57 +0000 |

Organization: | Compilers Central |

References: | 09-02-013 |

Keywords: | parse, LL(1) |

Posted-Date: | 14 Feb 2009 05:06:39 EST |

Johann 'Myrkraverk' Oskarsson wrote:

*> Is it possible to parse implicit operators, like the regular*

*> expression concatenation operator, with a recursive descent parser?*

*> That is, to be explicit, is it possible to make a recursive descent*

*> parser that produces (*) the following parse tree on this input "aab":*

*>*

*> @*

*> / \*

*> @ b*

*> / \*

*> a a*

It's completely trivial for hand-written recursive descent. Here's

pseudocode:

parseConcat:

result = parseElement()

while notEof() do

result = makeConcat(result, parseElement())

return result

.... assuming parseElement() handles items in the concatenation at the

right level of precedence. The loop is useful to avoid redundant

recursion in long sequences; also, using an explicit vector or similar,

rather than a parse tree, might be wise considering a pathologically

deep tree. And of course, the exit condition of the loop would need to

be changed for things like parentheses used for precedence (i.e. check

for closing parenthesis), but this should give you a hint as to the

right direction.

-- Barry

--

http://barrkel.blogspot.com/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.