LL (1) Синтаксическое - Первый (А) с рекуррентной первой альтернативой

Question

Как бы применить правило FIRST() на производстве, такие как:

А -> AAB | Ab | s

где A - не терминал, а b, s - терминалы.

FIRST (A) альтернатив 1 & 2 будет снова A, но это закончится бесконечными приложениями FIRST, так как мне нужен терминал для получения FIRST-набора?

Answer 1

Для вычисления наборов FIRST вы обычно выполняете итерацию с фиксированной точкой . То есть вы начинаете с небольшого набора значений, а затем итеративно пересчитываете FIRST, пока сборы не сближаются.

В этом случае вы должны начать, отметив, что производство A → s означает, что FIRST (A) должен содержать {s}. Поэтому сначала вы устанавливаете FIRST (A) = {s}.

Теперь вы перебираете каждую продукцию A и обновляете FIRST на основе знаний о наборах FIRST, которые вы вычислили до сих пор. Например, правило

→ AAB

означает, что вы должны обновить FIRST (A), чтобы включить все элементы FIRST (AAB). Это не изменит FIRST (A). Затем вы посетите

→ Ab

Вы снова обновить FIRST (A), чтобы включить FIRST (Ab), которая не является снова не оп. Наконец, вы посетите

→ s

И так как 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 находятся на испанском языке, но алгоритмы на английском языке.Это один из способов расчета ПЕРВОГО:

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) 

Σ азбука (терминалы), N этого множество нетерминалов, P является множеством продукций (правила), ε является пустой строкой, и ⋅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}.