Is this a LL(1) grammar?

Question

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?

Answer 1

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 (.