Языки и трансляции. Мартыненко Б.К. - 157 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

155
Глава 2
LL(k)-ГРАММАТИКИ И ТРАНСЛЯЦИИ
§ 2.1. Введение в LL(k)-грамматики
2.1.1. Неформальное описание
В гл. 1 было показано, что произвольная простая синтаксически
управляемая трансляция всегда может быть реализована при помощи
недетерминированного магазинного преобразователя. Если же, кроме того,
схема, посредством которой задаётся эта трансляция, является семантически
однозначной, то выход трансляции можно получить по левостороннему
анализу входной цепочки при помощи детерминированного магазинного
преобразователя . Следовательно, если найти такие классы входных грамматик,
в которых левосторонний анализ может быть реализован детерминированным
образом, то мы имели бы полностью детерминированную реализацию простых
семантически однозначных трансляций.
Одним из таких подклассов КС-грамматик являются так называемые LL(k)-
грамматики. Это самый большой “естественный” класс левоанализируемых
грамматик.
Определение 2.1. Пусть α = xβ — левосентенциальная форма в некоторой
cfg G=(V
N
,V
T
,P,S), такая, что x ∈V
T
*
, а β∈(V
N
∪ V
T
)
*
начинается на
нетерминал, либо есть пустая цепочка. Цепочка x называется закрытой
частью, а β — открытой частью левосентенциальной формы α.
Пример 2.1. Пусть α = abacAaB. Закрытая часть α есть abac. Открытая её
часть — AaB. Если α = abc, то закрытая часть есть abc, а открытая — ε.
Определение 2.2. Пусть G =(V
N
,V
T
,P,S) — однозначная КС-грамматика и
w = a
1
a
2
...a
n
∈L(G). Тогда существует единственная последовательность лево-
сентенциальных форм α
0
, α
1
,…, α
m
, такая, что S = α
0
, α
i
α
i +1
для 0 ≤ i<m и
α
m
= w.
Левосторонний анализ цепочки w есть p
0
, p
1
, p
2
, …, p
m –1
.
Теперь предположим, что мы хотим найти этот левосторонний анализ,
просматривая w слева направо один раз. Мы могли бы попытаться сделать это
путём построения последовательности левосентенциальных форм α
0
, α
1
,…, α
m
.
Начальная сентенциальная форма α
0
= S уже известна. Остаётся определить
способ построения следующей сентенциальной формы по последней из уже
построенных.
Пусть α
i
= a
1
a
2
...a
j
Aβ — последняя из построенных сентенциальных форм.
Сравнивая закрытую часть этой сентенциальной формы a
1
a
2
...a
j
с цепочкой w,
мы можем определить её окончание a
j +1
…a
n
, вывод которого ещё предстоит
построить. Было бы желательно, чтобы α
i +1
можно было найти, зная только (1)
a
1
a
2
...a
j
— часть входной цепочки, которую мы уже просмотрели к этому
моменту, (2) a
j +1
…a
j + k
— несколько следующих входных символов для
некоторого фиксированного k и (3) нетерминал A. Если эти три величины
однозначно определяют, какое правило должно использоваться для раскрытия
A, мы можем тогда точно определить α
i +1
по α
i
и k входным символам
a
j +1
…a
j + k
.
lm
i
p
⇒

Страницы