Is this a LL(1) grammar?

0
votes

Considering the following grammar for propositional logic:

<A> ::= <B> <-> <A> | <B> 
<B> ::= <C>  -> <B> | <C> 
<C> ::= <D>  \/ <C> | <D> 
<D> ::= <E>  /\ <D> | <E> 
<E> ::= <F> | -<F>
<F> ::= <G> | <H>
<G> ::= (<A>)
<H> ::= p | q | r | ... | z

Precedence for conectives is: -, /\, /, ->, <->.

Associativity is also considered, for example p\/q\/r should be the same as p\/(q\/r). The same for the other conectives.

I pretend to make a predictive top-down parser in java. I dont see here ambiguity or direct left recursion, but not sure if thats all i need to consider this a LL(1) grammar. Maybe undirect left recursion?

If this is not a LL(1) grammar, what would be the steps required to transform it for my intentions?

1
parsinggrammarll
This isn't really a programming question, is it? - keyser
Please, define "programming question". - Wyvern666
A programming question would be more concerned with the code to do what you are asking about than what you are asking about. Your question is meta if anything. - VoteCoffee
Ok, maybe this is more like a "theoretical question". - Wyvern666
I'd file this under Logic or Math (the math exchange seem to have some threads on logic). No need to define it, they already did that in the help center. - keyser

1 Answers

3
votes

It's not LL(1). Here's why:

The first rule of an LL(1) grammar is:

A grammar G is LL(1) if and only if whenever A --> C | D are two distinct productions of G, the following conditions hold:

  1. For no terminal a , do both C and D derive strings beginning with a.

This rule is, so that there are no conflicts while parsing this code. When the parser encounters a (, it won't know which production to use.

Your grammar violates this first rule. All your non-terminals on the right hand of the same production , that is, all your Cs and Ds, eventually reduce to G and H, so all of them derive at least one string beginning with (.