View previous topic :: View next topic 
Author 
Message 
BLS
Joined: 28 Mar 2006 Posts: 44 Location: France

Posted: Sat Sep 15, 2007 3:47 pm Post subject: MiniD Grammar, LR/LALR > LL(1) 


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 languagedesigner (means keep your answere as simple as possible )
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 rewrite 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 


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

Posted: Mon Sep 17, 2007 7:54 am Post subject: 


Quote:  (I guess your's is LARL)
Can you confirm ? 
I have no idea 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 




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
