LL (1) 구문 분석 - 재귀 첫 번째 대안으로 우선 (A)

Question

나는 등 생산에 FIRST() 규칙을 적용 할 방법 :

A -> AAB | Ab | s

여기서 A는 비 종단이고 b, s는 종단입니다.

FIRST (A) 대안 1 & 2는 FIRST의 무한 응용 프로그램에서 끝납니다. 첫 번째 세트를 얻으려면 터미널이 필요합니다.

Answer 1

FIRST 집합을 계산하려면 일반적으로 고정 소수점 반복을 수행합니다. 즉, 작은 값 집합으로 시작한 다음 집합이 수렴 될 때까지 FIRST 집합을 반복적으로 다시 계산합니다.

이 경우, 생산 A → s는 FIRST (A)가 {s}을 포함해야한다는 것을 의미하는 것으로 시작합니다. 처음에는 FIRST (A) = {s}를 설정했습니다.

이제 각 산출물을 반복하고 지금까지 계산 한 FIRST 세트에 대한 지식을 기반으로 FIRST를 업데이트합니다. 예를 들어, 규칙

→ AAB

수단 먼저 (AAB)의 모든 요소를 ​​포함하는 FIRST (A)를 업데이트해야하는. 이로 인해 FIRST (A)가 변경되지 않습니다. 그런 다음 방문

→ Ab의

당신은 또 다시 어떤 조합입니다 FIRST (AB)를 포함하는 FIRST (A)를 업데이트합니다. 마지막으로,

을의 방문 →의

그리고 FIRST (A)가 이미의를 포함하기 때문에,이 변화가 발생하지 않습니다

.

이 반복에서 변경된 사항이 없으므로 FIRST (A) = {s}로 끝납니다. A에서 시작하는 파생은 궁극적으로 s을 첫 번째 문자로 생성하기 때문에 실제로 맞습니다.

자세한 내용은 these lecture slides (여기 part two)을 참조하십시오. 그들은 하향식 파싱이 어떻게 작동하는지 그리고 FIRST 집합을 반복적으로 계산하는 방법을 자세히 설명합니다.

희망이 도움이됩니다.

Answer 2

문법 규칙은 이미 실현 했으므로 left recursion이고 LL 파서는 are not able to parse grammars with left recursion입니다.

그래서 왼쪽 재귀를 먼저 제거해야합니다. 그런 다음 규칙의 첫 번째 집합을 계산할 수 있어야합니다.

Answer 3

내 teaching notes은 스페인어로되어 있지만 알고리즘은 영어로되어 있습니다., ε가 널 (null) 문자열, P이 제작 (규칙)의 집합입니다, N 비 터미널의 집합입니다,

foreach a ∈ Σ do 
    F(a) := {a} 
for each A ∈ N do 
    if A→ε ∈ P then 
      F(A) := {ε} 
    else 
      F(A) := ∅ 
repeat 
    for each A ∈ N do 
      F'(A) := F(A) 
    for each A → X1X2...Xn ∈ P do 
      if n > 0 then 
       F(A) := F(A) ∪ F'(X1) ⋅k F'(X2) ⋅k ... ⋅k F'(Xn) 
until F(A) = F'(A) forall A ∈ N 
FIRSTk(X) := F(X) forall X ∈ (Σ ∪ N) 

Σ 알파벳 (터미널)입니다 :이 FIRST을 계산하는 방법 중 하나입니다 ⋅k은 k 위치로 트림 된 연결입니다. ∅ ⋅k x = ∅에 주목하고 두 세트를 연결하면 데카르트 제품의 요소가 연결됩니다.

FIRST을 손으로 계산하는 가장 쉬운 방법은 알고리즘 반복 당 하나의 테이블을 사용하는 것입니다.

F(A) = ∅ 

F'(A) = F(A) ⋅1 F(A) .1 F(b) U F(A) .1 F(b) U F(s) 
F'(A) = ∅ ⋅1 ∅ ⋅1 {b} U ∅ ⋅1 {b} U {s} 
F'(A) = ∅ U ∅ U {s} 
F'(A) = {s} 

F''(A) = F'(A) ⋅1 F'(A) .1 F'(b) U F'(A) .1 F'(b) U F'(s) 
F''(A) = {s} ⋅1 {s} ⋅1 {b} U {s} ⋅1 {b} U {s} 
F''(A) = {s} U {s} U {s} 
F''(A) = {s} 

그리고 우리가 완료 때문에 F' = F'', 그래서 FIRST = F'' 및 FIRST(A) = {s}.