FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

MiniD Grammar, LR/LALR -> LL(1)

 
Post new topic   Reply to topic     Forum Index -> MiniD
View previous topic :: View next topic  
Author Message
BLS



Joined: 28 Mar 2006
Posts: 44
Location: France

PostPosted: Sat Sep 15, 2007 3:47 pm    Post subject: MiniD Grammar, LR/LALR -> LL(1) Reply with quote

Hi Jarret, ahem.. it's me again
My problem is that I have to describe your grammar as LL(1) grammar in order to use the Netbeans generic lanuage framework. (also called Schliemann)

It looks your grammar is from a recursive descent parser, which won't work for me because these are usually LR / LALR. (I guess your's is LARL)
Can you confirm ? Do you see a chance to "strip down" your grammar to LL(1) as shown in :
http://platform.netbeans.org/articles/nbm_interview_caoyuan.html
(Erlang IDE support)

Please notice that I am a more DB developer than a language-designer Shocked (means keep your answere as simple as possible Smile )
Many thanks in advance, Bjoern
Short info, regarding the problem to implement Erlang support ...

The interesting things here are f.i.
# Remove left recursion. Here's a grammar rule with left recursion, where the first statement, 'add_expr' is on the left side of the equal sign, and is also the first element on the right:

add_expr -> add_expr add_op mult_expr;
add_expr -> mult_expr;

The NBS form is Extended BNF, so, you can just re-write the above to the following:

add_expr = mult_expr (add_op mult_expr)*;

# Merge left factors. LL(1) can only look ahead one step, so the following grammar rules will not work properly:

fun_expr -> "fun" <atom> "/" ;
fun_expr -> "fun" <atom> ":" <atom> "/" ;
fun_expr -> "fun" "->" exprs "end";

The parser cannot separate the first and second statement above, which both start with the same element ("fun" <atom>). To resolve this, rewrite it to the following:

fun_expr = "fun" <atom> [":" <atom>] "/" |
"fun" "->" exprs "end";

# The most difficult part! If two rules' right hand sides start with the same element, and they also belong to the same rule's left hand side, you cannot name them as two rules, as illustrated below.

list = "[" [expr] tail;
tail = "]" |
"|" expr "]" |
"," expr tail;

list_comprehension = "[" expr "||" lc_exprs "]"
lc_exprs = lc_expr ("," lc_expr)*;
lc_expr = expr ["<-" expr];

Above, 'list' and 'list_comprehension' both start with ("[" expr), and they both belong to (expr), which is defined elsewhere recursively. This does not works properly in LL(1). To resolve this, you could define them as follows instead:

list = "[" [expr] tail;
tail = "]" |
"|" expr "]" |
"," expr tail |
"||" lc_exprs tail;

lc_exprs = lc_expr ("," lc_expr)*;
lc_expr = expr ["<-" expr];
Back to top
View user's profile Send private message
JarrettBillingsley



Joined: 20 Jun 2006
Posts: 457
Location: Pennsylvania!

PostPosted: Mon Sep 17, 2007 7:54 am    Post subject: Reply with quote

Quote:
(I guess your's is LARL)
Can you confirm ?


I have no idea Shocked I mostly based the MiniD grammar off the D grammar. The parser was based off the grammar, in fact, and not the other way around.

As for transforming the grammar to LL(1), it looks like it should be possible. I think parsing MiniD only requires a little bit of lookahead. The only area I can think of is slicing vs. indexing i.e. "x[y + z]" vs "x[y + z .. w]". You don't know whether you're parsing a slice until after you parse the first index. But that looks like it should be easily resolvable.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> MiniD All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group