Применение искинов - шоссе империализма (Стенгазета русификаторов ИТ)

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.

Вы здесь » Применение искинов - шоссе империализма (Стенгазета русификаторов ИТ) » контекстно-свободные грамматики » Алгоритм вычисления множеств следующих символов для ситуаций разбора

Алгоритм вычисления множеств следующих символов для ситуаций разбора

Страница: 1

Сообщений 1 страница 4 из 4

1

  • Автор: ВежливыйЛис
  • Администратор
  • Зарегистрирован: 2017-03-25
  • Приглашений: 0
  • Сообщений: 1116
  • Уважение: [+2/-1]
  • Позитив: [+4/-1]
  • Провел на форуме:
    7 дней 12 часов
  • Последний визит:
    2024-12-27 19:15:53

http://www.larc.usp.br/~pbarreto/LR.pdf

1: for every nonterminal C do
2:     Compute all nonterminals A satisfying C →rm∗ A...
3:     Compute all nonterminals B satisfying C →rm∗ B
4: end for
5: | Build relation inherits ctx between pairs of nonterminals:
6: for every production (A→Cα)∈P such that C ≠ A do
7:     for every nonterminal B such that C →rm∗ B... do
8:         Set the relation (A, B) inherits ctx(C, B)
9:     end for
10:end for
11:| Compute ctx 0 (A, B):
12:Set ctx 0 (A, B) ← ∅
13:for all pairs (A, B) present in the inherits ctx relation do
14:    for all α such that (A→Cα)∈P and C→rm∗ B do
15:        Union FIRST (α) into ctx 0 (A, B)
16:    end for
17:end for
18:Compute ctx(A, B) from ctx 0 (A, B) by taking the transitive closure of inherits ctx
19:| Compute the lookahead sets on demand during parser generation:
20:for each item [A→α·Xγ,u] in the state being generated where X is a nonterminal do
21:    for each production N→Yβ of each nonterminal N such that X→rm∗ N... do
22:       Let v←ctx(X,N)⊕FIRST(γu)
23:       Merge into the successor state all items of form [N→Y·β,v]
24:    end for
25:end for

Отредактировано Лис (2017-09-11 12:51:51)

0

2

  • Автор: ВежливыйЛис
  • Администратор
  • Зарегистрирован: 2017-03-25
  • Приглашений: 0
  • Сообщений: 1116
  • Уважение: [+2/-1]
  • Позитив: [+4/-1]
  • Провел на форуме:
    7 дней 12 часов
  • Последний визит:
    2024-12-27 19:15:53

2:     Compute all nonterminals A satisfying C ∗−→rm A...

Как мы будем вычислять rightmost derivation? Имеется в виду первый нетерминал, или первый несводимый к пустой цепочке нетерминал? Что если в правиле сначала первыми идут терминалы?

https://cs.stackexchange.com/questions/ … derivation

https://i.stack.imgur.com/up0wr.png

Given a derivation tree for a word, you can "implement" it as a sequence of productions in many different ways. The leftmost derivation is the one in which you always expand the leftmost non-terminal. The rightmost derivation is the one in which you always expand the rightmost non-terminal.

The leftmost derivation corresponding to the left parse tree is
A→A+A→a+A→a+A−A→a+a−A→a+a−a
The rightmost derivation corresponding to the left parse tree is
A→A+A→A+A−A→A+A−a→A+a−a→a+a−a
The leftmost derivation corresponding to the right parse tree is
A→A−A→A+A−A→a+A−A→a+a−A→a+a−a
The rightmost derivation corresponding to the right parse tree is
A→A−A→A−a→A+A−a→A+a−a→a+a−a

Тут то же самое, но картинка покрасивее:
[html]<a href="https://www.eecis.udel.edu/~cavazos/cisc471-672/lectures/Lecture-08.pdf">cisc471-672, Lecture-08.pdf</a>[/html]

[html]
Могут ли отличаться деревья левого и правого вывода для однозначной грамматики:
<a href="https://math.stackexchange.com/questions/1564227/when-do-we-say-a-grammar-to-be-unambiguous-with-respect-to-parse-tree-and-deriva">SE 1564227</a>
<br />
сам вывод может отличаться, а деревья - не могут (потому что грамматика дающая разные деревья считается неоднозначной).
<br />
"A grammar is said to be unambiguous if every sentential form has a unique derivation tree." - это определение из работы <a href="http://plana.mybb.ru/viewtopic.php?id=426">1965, Кнут</a>
[/html]

------

• Σ is the set of terminal symbols and N is the set of non-terminal symbols, with Σ∩N= ∅. The vocabulary is the set V = Σ∪N.
• P is the set of productions, which have the form A → α where A∈N and α∈V∗.
• A −→ rm α denotes a right derivation of α∈V∗ from A∈N in one step, and A ∗−→rm α denotes  a  right  derivation  in  any  number  of  steps.   We  also  use  the  shorthand A ∗−→ rm B..., meaning ∃w∈Σ∗: A ∗−→rm Bw.

Тут не ясно, почему w∈Σ∗, а не w∈V∗

------

почему во второй строчке алгоритма из стартового сообщения нити обсуждения есть многоточие, а в третьей строчке нет?

Отредактировано Лис (2017-11-07 08:02:12)

0

3

  • Автор: ВежливыйЛис
  • Администратор
  • Зарегистрирован: 2017-03-25
  • Приглашений: 0
  • Сообщений: 1116
  • Уважение: [+2/-1]
  • Позитив: [+4/-1]
  • Провел на форуме:
    7 дней 12 часов
  • Последний визит:
    2024-12-27 19:15:53
Лис написал(а):

nonterminals A satisfying C →∗rm A...

понимание улучшает этот фрагмент:

A central aspect of the algorithm is thus the computation of successors of an LR(1) state. For each item [A→α·Xγ,u] of the state being processed, one must insert into the successor state not only the item [A→αX·γ,u] but also, if X is a nonterminal, all items of form [N→Y·β,v], for each production N→Yβ of each nonterminal N such that X∗−→rm N... . The lookahead v of one item of this form is given, according to lemma 3.1 of [14], by v = ctx(X,N) ⊕ FIRST(γu).

Русскими словами: У нас есть правило-с-точкой (в нотации Эрли), это текущее состояние автомата. Мы строим следующие состояния. В случае если в правиле после точки стоит нетерминал, но надо поискать все такие нетерминалы, которые могут быть самыми левыми в любых правилах, в которые может превратиться нетерминал X.

То есть, замещение нетерминалов справа (при вычислении rightmost derivation), это просто такой способ поискать самые левые нетерминалы (символы?) правил.

Тут ещё неясно, случайно ли совпадение между y и Y (то что используется одна буква в разных регистрах - строчная и заглавная). На первый взгляд кажется, что сверху маленкая y - это любой правый фрагмент правой части правила, а снизу большая Y - это некий нетерминал (почему именно нетерминал, а не символ - то есть и терминал возможно тоже? надо подумать по-тщательнее)

Отредактировано Лис (2017-11-06 06:24:30)

0

4

  • Автор: ВежливыйЛис
  • Администратор
  • Зарегистрирован: 2017-03-25
  • Приглашений: 0
  • Сообщений: 1116
  • Уважение: [+2/-1]
  • Позитив: [+4/-1]
  • Провел на форуме:
    7 дней 12 часов
  • Последний визит:
    2024-12-27 19:15:53

⊕ operation is called "ε-free FIRST"
∀α ∈ V∗ : FIRST (α) ≡ { t ∈ Σ | α ∗ −→ t β, β ∈V∗ }.
∀ ρ,σ ⊆ Σ∗ : ρ ⊕ σ ≡ FIRST(rs) : r ∈ ρ ∧ s ∈ σ.
That is, ρ ⊕ σ is simply FIRST(ρ) if ε ∉ ρ, or FIRST (ρ) ∪ FIRST(σ) otherwise

Русскими словами - для любого нетерминала эта функция представляет собой множество терминалов, которые могут этот нетерминал начинать.
А если две цепочки терминалов склеены/сконкатенированы в одну цепочку, то можно построить множество для такой склеенной цепочки используя два множества для каждой из исходных цепочек терминалов.

http://citforum.ru/programming/theory/s … ov/4.shtml

Для α - произвольной цепочки, состоящей из символов грамматики, определим FIRST(α) как множество терминалов, с которых начинаются строки, выводимые из α. Если α -> *e, то e также принадлежит FIRST(α).

вообще функцию FIRST можно определить по-разному, но тут вроде бы определения совпадают.

Алгоритм 4.3. Вычисление FIRST для символов грамматики.
Вход. КС-грамматика G = (N, T, P, S).
Выход. Множество FIRST(X) для каждого символа X (N T).
Метод. Выполнить шаги 1-3:
    Если X - терминал, то положить FIRST(X) = {X}; если X - нетерминал, положить FIRST(X) = .
    Если в P имеется правило X -> e, то добавить e к FIRST(X).
    Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы, выполнять:
    если X - нетерминал и имеется правило вывода X → Y1Y2...Yk, то включить a в FIRST(X), если a ∈ FIRST(Yi) для некоторого i, 1 <= i <= k, и e принадлежит всем FIRST(Y1), ..., FIRST(Yi-1), то есть Y1...Yi-1 →* e. Если e принадлежит FIRST(Yj) для всех j = 1, 2, ..., k, то добавить e к FIRST(X).

https://neerc.ifmo.ru/wiki/index.php?title=Построение_FIRST_и_FOLLOW

[html]Не нравится мне тут этот двойной цикл (снаружи по нетерминалам, внутри по правилам). Есть ощущение, что можно применить <a href="https://ru.wikipedia.org/wiki/Топологическая_сортировка">топологическую сортировку</a> и это всё радикально убыстрит. (тут можно возразить, что граф-то с циклами, поэтому ничего не выйдет).[/html]

https://stackoverflow.com/questions/198 … e-grammars

Отредактировано Лис (2017-11-06 07:39:20)

0

Страница: 1

Вы здесь » Применение искинов - шоссе империализма (Стенгазета русификаторов ИТ) » контекстно-свободные грамматики » Алгоритм вычисления множеств следующих символов для ситуаций разбора