Predittivo Parser LL (1) Condizione

Question

Diciamo che usiamo il predittivo parser ll (1).Perché è necessario

$ first (\ alfa) \ cap prima (\ beta)=vuoto $ ,

Per tutti i $ \ alfa, \ beta $ lato destro delle produzioni alternative I.e., produzioni associate allo stesso non-terminale.Perché questa condizione è necessaria?

Answer 1

Ecco una spiegazione intuitiva:

Segue essenzialmente dalla natura di LL (1) Parser: LL (1) I parser costruiscono una tabella di analisi di LL (1). Le righe del tavolo sono nonterminali e le colonne sono terminali. Possiamo pensare a LL (1) Analinando come LL (1) Ricerca tabella LL (1) All'incontraggio di ciascun simbolo nell'input: guardiamo alla voce determinata dall'attuale nonterminal e dal terminale di ingresso e applicare una regola di produzione corrispondente. Pertanto, la tabella LL (1) non può contenere più regole di produzione ad ogni voce, altrimenti, il parser non può decidere quale regola applicare.

Se il lato destro di una produzione $ \ alfa $ , $ \ beta $ ha intersecolato Primi set, avremmo più regole multiple in una singola voce nella tabella LL (1) (cioè voci duplicate / conflittuali) --- avendo l'intersezione non circiale dei primi set indispensabili ci impedisce essenzialmente di costruire la tabella di analizzazione LL (1).

Se non sei ancora chiaro sul motivo per cui questa condizione è necessaria , ti suggerisco di costruire un esempio con prim'ordine intersecanti sul lato destro di una produzione, quindi provare a costruire manualmente un ll (1) Tabella analizzante o utilizzare uno dei Strumenti di visualizzazione online ; Troverai immediatamente un conflitto.