Invisible wrote:
> Darren New wrote:
> 
>> Actually, that's not *quite* right.
>>
>> What Haskell is using is called a recursive-descent parser: the parser 
>> basically uses the run-time stack in place of an explicit stack. It's 
>> best for LALR(1) syntaxes, which means "Look Ahead Left to Right 1 
>> token". I.e., a language you can parse by running strictly from left 
>> to right, looking only one element ahead, so you don't need the 
>> "P_Try()" function. Some languages (like Pascal) are explicitly 
>> designed this way to make it easy to build a recursive descent parser.
> 
> OK, well since you seem to know something about this... using the 
> formalisms developed here, how would you go about parsing a grammar that 
> can consist of integers, variable names, and + - / * ( ), such that the 
> operators have the correct precidence?

Almost everyone calls these productions "Expressions" and "Terms" and 
"Factors". So googling for "bnf expression term" yields

http://www.seas.upenn.edu/~cit596/notes/dave/bnf4.html

You can see the basic technique.  An expression is terms multiplied 
together, while a term is factors added together, and a factor is a 
variable, a number, or an expression in parens. That gives you the 
precidence and associativity you are looking for.

> I thought I had this working, but it seems that bracketing the 
> expressions in unusual but valid ways causes the parser to trip over in 
> inexplicable ways. :-(

Take the BNF and translate it directly into functions that match those 
other parsers? It's been decades since I did such stuff, so I am not 
really glib enough at this point to just roll it off the fingertips.

Googling for "recursive descent expression parse", I get
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
which covers it well. Note the line
"""
Not only is left recursion eliminated, but the G1 is unambiguous and 
each choice can be made by looking at the next token in the input.
"""
which tells you it's possible to use simple LL(1) parsers to grok it.
The "recursive descent recognition" shows you how to do it with Haskell 
parsers. The next section ("shunting yard") shows you how Yacc/Bison 
builds its table, followed by essentially an implementation of the 
run-time part of Yacc/Bison.

That's actually a pretty good overview page. :-)

HTH!

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message