Русскоязычное программирование (План А)

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

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


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


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

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

1

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

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

------

• Σ 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-09-11 12:57:36)

0


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