> From: Terrence Brannon [mailto:[EMAIL PROTECTED]] 2002/03/17 11:43 > Subject: is P::RD LL(1) LL(N) LR(1) LR(N) ? > Would someone mind mentioning exactly what LL(1) , LL(N) and > LR(1) and LR(N) mean and which of these P::RD is?
Well, at the risk of my memory getting me in trouble... LR = Left-to-right Rightmost Derivation (0/N) Refers to the number of tokens of lookahead required. Used in bottom up parsers (like YACC) Any context free grammer can be handled by a LR parser. LL = Left-to-right Leftmost Derivation (0/N) Refers to the number of tokens of lookahead required. Used in top down parsers. Only a limited subset of context free grammers can be parsed with an LL parser. IIRC an LR grammer may be converted into an LL grammer algorithmically, but that the resulting grammer is difficult to deal with from a human point of view. Consider the grammer (borrowed from http://www.cs.unc.edu/~fhernand/144/lectures/lect5.pdf) id_list : id id_list_tail id_list_tail : , id id_list_tail | ; And the text:A,B,C; Both types of grammer would produce the parsetree id_list(1) /\ A \ id_list_tail(2) / | \ , B id_list_tail(3) / | \ , C id_list_tail(4) | ; But an LL grammer would grow the tree in the order 1,2,3,4 (top down) but an LR grammer would grow 4,3,2,1 (bottom up). Now as to which P::RD is, im not 100% sure. (I dont have my books with me as I write) but im guessing that its an LL parser because it cant handle left recursive grammers. (Damian has yet to add the autoconversion..) It will error for immediate left recursion but will not pick up multirule left recursion. OTOH (and this is where I get a bit confused) it does build its nodes bottom up. Left Recursive Grammer: id: id ',' value I suppose it could be that Recursive Descent parsers are neither LL or LR, I really cant remember. But again this is all the product of limited amount of surfing and a very fallable memory. Corrections are very welcome... Yves Ps (Ill follow up tomorrow with comments from the Red Dragon.)
