LL (1) 문법입니까? 명제 논리에 대한 다음과 같은 문법을 고려

Question

:

<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 

우선 순위 conectives를위한이다 : -/\, /, ->, < ->.

연관성도 고려됩니다. 예를 들어 p\/q\/r은 p\/(q\/r)과 같아야합니다. 다른 conectives에 대해서도 마찬가지입니다.

자바에서 예측 하향식 파서를 가장하는 것처럼 가장합니다. 나는 여기서 모호성이나 직접적인 왼쪽 재귀를 보지 못하지만, 이것이 내가 LL (1) 문법이라고 생각할 필요가 있는지 확실하지는 않다. 어쩌면 undirect left recursion일까요?

이것이 LL (1) 문법이 아닌 경우 내 의도에 맞게 변형하는 데 필요한 단계는 무엇입니까?

Answer 1

LL (1)이 아닙니다.

문법 G는 LL 인 경우에만 A --> C | D는 G의 두 가지 제작이 될 때마다 (1)가, 다음의 조건이 유지 :

가

LL은 첫번째 규칙 (1)의 문법은 : 여기 왜

1. 터미널이 없으면 a의 경우 C 및 D 모두 a으로 시작하는 문자열을 파생시킵니다.

이 규칙은이 코드를 구문 분석하는 동안 충돌이 발생하지 않도록하기위한 것입니다. 파서가 (을 만날 때, 사용할 프로덕션을 알 수 없습니다.

귀하의 문법은이 첫 번째 규칙을 위반합니다. 같은 프로덕션의 오른손에있는 모든 비 터미널, 즉 모든 C와 D는 결국 G와 H로 축소되므로 모두 (으로 시작하는 문자열이 하나 이상 파생됩니다.