Creazione di una grammatica LL (1)

Question

Ho la seguente grammatica:

S → a S b S | b S a S | ε

Dal momento che sto provando a scrivere un piccolo compilatore per questo, mi piacerebbe renderlo LL (1). Vedo che sembra esserci un conflitto PRIMO/SEGUITO qui, e so che devo usare la sostituzione per risolverlo, ma non sono esattamente sicuro su come procedere. Ecco la mia grammatica proposta, ma non sono sicuro se sia corretta:

S-> aSbT | Epsilon

T-> bFaF | Epsilon

F-> epsilon

Qualcuno può dare una mano?

Answer 1

Nel suo original paper on LR parsing, Knuth ha pronunciato la seguente grammatica per questa lingua, che egli ipotizza "è il più breve grammatica non ambigua possibile per questa lingua:"

S & → epsilon; | aAbS | BBAS

A → & epsilon; | AABA

B & → epsilon; | bBaB

Intuitivamente, questo tenta di suddividere qualsiasi stringa di As e Bs in blocchi che si compensino completamente. Alcuni blocchi iniziano con ae terminano con b, mentre altri iniziano con b terminano con a.

Possiamo calcolare e segua parti come segue:

FIRST (S) = {& epsilon ;, a, b}

FIRST (A) = {& epsilon ;, un}

PRIMO (B) = {& epsilon ;, b}

FOLLOW (S) = {} $

FOLLOW (A) = {b}

0.123.

FOLLOW (B) = {a}

Sulla base di questo, si ottiene il seguente LL (1) analizziamo tavolo:

| a | b | $ 
--+-------+-------+------- 
S | aAbS | bBaS | e 
A | aAbA | e | 
B | e | bBaB | 

E non quindi questa grammatica è solo LR (1) , ma è anche LL (1).

Spero che questo aiuti!