Елементи синтаксичного аналізу, Детальна інформація

2.3. LA(1)-граматики

LA(1)-граматики дозволяють вибирати необхідну для розгортання продукцію при низхідному аналізі за першим символом ще не розпізнаної частини слова. "LA(1)" позначає речення "Look Ahead 1 symbol", тобто "подивитися спереду на 1 символ".

Нехай G=(X, N, P, S) – КВ-граматика, і за словом w треба визначити, чи належить воно до L(G). Нехай S\xF0AE v1|…|vp – усі продукції з нетерміналом S ліворуч. Потрібну для розгортання S продукцію S\xF0AE vi можна визначити безпосередньо за першим символом слова w, якщо множини перших символів ланцюжків, вивідних із v1, v2, … , vp, не перетинаються. Взагалі, нехай am…an – нерозпізнана частина слова, початок якої має виводитися з нетермінала A, і A\xF0AE w1|…|wk – усі продукції з A ліворуч. Тоді потрібна для розгортання A продукція A\xF0AE wi визначається за першим символом am, якщо множини перших символів ланцюжків, вивідних з w1, w2, … , wk, не перетинаються.

R

T

j

l

n

r

t

\x017D

’

¶

\x00BA

1/4

A

Oe

U

a

a

ae

o

u

"

,

0

L

\x0160

0

B