문법이 LL (1), LR (0) 또는 SLR (1)인지 식별하는 방법은 무엇입니까?

문법이 LL (1), LR (0) 또는 SLR (1)인지 식별하는 방법은 무엇입니까?

---

문법이 LL (1), LR (0) 또는 SLR (1)인지 어떻게 식별합니까?

누구든지이 예나 다른 예를 사용하여 설명해 주시겠습니까?

X → Yz | ㅏ

Y → bZ | ε

Z → ε

---

문법이 LL (1)인지 확인하기위한 한 가지 옵션은 LL (1) 구문 분석 테이블을 구성하고 충돌이 있는지 확인하는 것입니다. 이러한 갈등은

• FIRST / FIRST 충돌. 여기서 두 개의 서로 다른 프로덕션이 비 터미널 / 터미널 쌍에 대해 예측되어야합니다.
• FIRST / FOLLOW 충돌. 두 개의 서로 다른 프로덕션이 예측되는 경우, 하나는 일부 프로덕션을 가져 와서 0이 아닌 수의 기호로 확장해야 함을 나타내는 것이고, 다른 하나는 프로덕션이 사용되어야 함을 나타내는 것으로, 일부 비 터미널이 궁극적으로 확장되어야 함을 나타냅니다. 빈 문자열.
• FOLLOW / FOLLOW 충돌, 여기서 비 터미널이 궁극적으로 빈 문자열로 확장되어야 함을 나타내는 두 개의 프로덕션이 서로 충돌합니다.

각 비 터미널에 대해 FIRST 및 FOLLOW 세트를 작성하여 문법에 대해 시도해 봅시다. 여기, 우리는

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon} 

우리는 또한 FOLLOW 세트가

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

이를 통해 다음 LL (1) 구문 분석 테이블을 작성할 수 있습니다.

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

충돌없이이 구문 분석 테이블을 구축 할 수 있으므로 문법은 LL (1)입니다.

문법이 LR (0) 또는 SLR (1)인지 확인하기 위해 문법에 대한 모든 LR (0) 구성 집합을 빌드하는 것으로 시작합니다. 이 경우 X가 시작 기호라고 가정하면 다음과 같이 표시됩니다.

(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

이로부터 상태 (1)과 (6)에 shift / reduce 충돌이 있기 때문에 문법이 LR (0)이 아님을 알 수 있습니다. 특히 축소 항목 Z →. 그리고 Y →., 우리는 빈 문자열을 이러한 기호로 줄일 것인지 아니면 다른 기호를 이동할 것인지 알 수 없습니다. 보다 일반적으로 ε-productions의 문법은 LR (0)입니다.

그러나이 문법은 SLR (1) 일 수 있습니다. 이를 확인하기 위해 특정 비 터미널에 대한 미리보기 세트를 사용하여 각 감소를 확대합니다. 이렇게하면이 SLR (1) 구성 집합 집합이 반환됩니다.

(1)
X' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

이제 우리는 더 이상 시프트 감소 충돌이 없습니다. 다른 항목과 충돌하지 않는 예견이 z 일 때만 감소하므로 상태 (1)의 충돌이 제거되었습니다. 마찬가지로 (6)의 갈등도 같은 이유로 사라졌습니다.

도움이 되었기를 바랍니다!

---

If you have no FIRST/FIRST conflicts and no FIRST/FOLLOW conflicts, your grammar is LL(1).

An example of a FIRST/FIRST conflict:

S -> Xb | Yc
X -> a 
Y -> a 

By seeing only the first input symbol a, you cannot know whether to apply the production S -> Xb or S -> Yc, because a is in the FIRST set of both X and Y.

An example of a FIRST/FOLLOW conflict:

S -> AB 
A -> fe | epsilon 
B -> fg 

By seeing only the first input symbol f, you cannot decide whether to apply the production A -> fe or A -> epsilon, because f is in both the FIRST set of A and the FOLLOW set of A (A can be parsed as epsilon and B as f).

Notice that if you have no epsilon-productions you cannot have a FIRST/FOLLOW conflict.

---

Simple answer:A grammar is said to be an LL(1),if the associated LL(1) parsing table has atmost one production in each table entry.

Take the simple grammar A -->Aa|b.[A is non-terminal & a,b are terminals]
   then find the First and follow sets A.
    First{A}={b}.
    Follow{A}={$,a}.

    Parsing table for Our grammar.Terminals as columns and Nonterminal S as a row element.

        a            b                   $
    --------------------------------------------
 S  |               A-->a                      |
    |               A-->Aa.                    |
    -------------------------------------------- 

As [S,b] contains two Productions there is a confusion as to which rule to choose.So it is not LL(1).

Some simple checks to see whether a grammar is LL(1) or not. Check 1: The Grammar should not be left Recursive. Example: E --> E+T. is not LL(1) because it is Left recursive. Check 2: The Grammar should be Left Factored.

Left factoring is required when two or more grammar rule choices share a common prefix string. Example: S-->A+int|A.

Check 3:The Grammar should not be ambiguous.

These are some simple checks.

---

LL(1) grammar is Context free unambiguous grammar which can be parsed by LL(1) parsers.

In LL(1)

• First L stands for scanning input from Left to Right. Second L stands for Left Most Derivation. 1 stands for using one input symbol at each step.

For Checking grammar is LL(1) you can draw predictive parsing table. And if you find any multiple entries in table then you can say grammar is not LL(1).

Their is also short cut to check if the grammar is LL(1) or not . Shortcut Technique

---

With these two steps we can check if it LL(1) or not. Both of them have to be satisfied.

1.If we have the production:A->a1|a2|a3|a4|.....|an. Then,First(a(i)) intersection First(a(j)) must be phi(empty set)[a(i)-a subscript i.]

2.For every non terminal 'A',if First(A) contains epsilon Then First(A) intersection Follow(A) must be phi(empty set).

참고URL : https://stackoverflow.com/questions/8496642/how-to-identify-whether-a-grammar-is-ll1-lr0-or-slr1