Path: utzoo!utgpu!watserv1!watmath!att!ima!iecc!compilers-sender From: grimlok@hubcap.clemson.edu (Mike Percy) Newsgroups: comp.compilers Subject: Re: Recursive Descent Parsers and YACC Keywords: parse, yacc, design, question Message-ID: <11678@hubcap.clemson.edu> Date: 16 Nov 90 21:03:54 GMT References: Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: grimlok@hubcap.clemson.edu (Mike Percy) Organization: Clemson University, Clemson, SC Lines: 26 Approved: compilers@iecc.cambridge.ma.us melling@psuvax1.cs.psu.edu (Michael D Mellinger) writes: >Can someone give me an estimate on how much faster parsing can be made by >writing a recursive-descent parser instead of using Yacc and Lex? Is there >enough of a difference to consider using a RDP in a commercial C compiler? I would tend to believe that table driven parsers (YACC) are faster in execution than recursive descent parsers. The stack and function call overhead alone can get to be pretty hairy, especially in deeply recursive parses. What is faster, in my experience, is the speed in which you can get a parser running. Trying to coax a grammer that YACC likes (conflict-free) is downright a pain, but the recursive descent parser generators I've worked on/with have much laxer restrictions on the grammar than LR(1). In theory, one could have a non-deterministic, backtracking RD parser (seen one or two done in Prolog), but most generators at least require the grammar to be deterministic (is this the same as LR(1)? If you want to get a parser up quickly, use an Early's algorithm-based parser. It will run slow, but it runs the first time, giving you time to massage the grammar for a faster parser type. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.