Compiladors: quina diferència hi ha entre analitzadors LL (0) i LR (0). Hi ha alguna cosa com ara analitzadors LL (0)?


Resposta 1:

Aquesta pregunta sembla estar centrada en els analitzadors LL (0), per tant, definim-los. Un analitzador LL (0), analitza d'esquerra a dreta utilitzant 0 fitxes al començament de la producció per determinar quina producció s'ha d'aplicar. Què significa això de 0 fitxes, vol dir que l'analitzador no pot utilitzar el text analitzat per determinar quina producció s'ha d'aplicar. Això vol dir que l'analitzador no pot fer cap elecció. S'ha de saber abans de començar a analitzar exactament la seqüència de fitxes que analitzarà. La seqüència de fitxes s'ha de fixar, cosa que significa que només hi pot haver una seqüència que l'analitzarà. Així, podríeu tenir un analitzador que accepta "Hello world!" amb una gramàtica com aquesta:

objectiu: signe d'exclamació "Hola" en blanc "espai";

Tingueu en compte que les úniques variacions permeses són la combinació del lexer amb les fitxes.

(Espero que la notació sigui obvia, és essencialment la que faig servir a Yacc ++. Les cadenes citades són fitxes, com els identificadors que no estan definits.)

El parser sempre espera la mateixa seqüència exacta de fitxes. No ha de tenir una sola regla, com ho va fer el nostre primer exemple. Podria semblar així.

objectiu: part final de l'espai en blanc;

hola-part: hola1;

hola1: "Hola";

part final: part del món darrera part;

part mundial: "món";

última part: "!";

Tanmateix, observeu com cap de les regles té cap operador "o" (|) i només hi ha una regla per terminal. Això és el que permet al analitzador saber combinar cada regla sense utilitzar cap fitxa discriminatòria (fitxes que trien el camí que l'analitza), cosa que fa que la gramàtica LL (0).

Ara, és possible utilitzar una producció recursiva i tenir encara una gramàtica LL (0)? La resposta és "no". Vegem què passa si tenim una regla recursiva.

objectiu: "x" objectiu "y";

Recordeu, només se’ns permet una regla per operadors no terminals i cap operador "o". Així, quan arribem a la invocació recursiva d’objectiu, hem de portar-nos a un camí on tornarem a arribar a aquella invocació recursiva, bucle infinit. Demostreu-vos, no importa com nidifiquem l’advocació o si la recursió és indirecta. Sempre donarà lloc a un bucle infinit.

Així, una gramàtica LL (0) ha d’analitzar una llista finita de fitxes, exactament una llista finita (la mateixa llista cada vegada).

Observeu la diferència amb el significat de LR (0). A un analitzador LR (k) es pot utilitzar qualsevol (tantes que li agradi) fitxes d'una producció per discriminar, a més de k tokens del context quan la producció es redueix per determinar si s'ha de reduir. En el cas de LR (0), no pot utilitzar cap testimoni addicional per determinar si s’ha de reduir. Cal decidir senzillament en funció de la reducció de fitxes en la regla. Aquí teniu una gramàtica senzilla de LR (0):

objectiu: "x" | "(" objectiu ")";

Aquesta gramàtica analitza una "x" envoltada d'alguns parèntesis. Tingueu en compte que pot utilitzar el testimoni "x" i el testimoni "(") per decidir quina regla s'ha d'aplicar. El 0 de LR (0) no restringeix l'ús de fitxes dins d'una regla, com ho fa el de 0 en LL (0). L’únic que restringeix és l’ús de fitxes (de context, després de la regla en algun ús del no terminal) a l’hora de decidir reduir.Aquesta gramàtica no necessita context que decideixi reduir. En la primera alternativa, redueix en veure una "x" a la segona que redueix després de veure una ")". Les fitxes d'una regla determinen exactament quan s'ha de reduir la regla.


Resposta 2:

Els analitzadors LL (0) signifiquen que processen el flux de testimonis d'esquerra a dreta, utilitzant la derivació a l'esquerra sense mirar cap endavant. Teòricament, els analitzadors LL (0) són possibles, però, encara que existeixin, no els veig gaire ús. Els analitzadors LL (0) haurien de predir quines produccions s’han d’aplicar en funció de les terminals actuals no terminals amb vista zero. En aquestes gramàtiques, cada terminal no pot tenir una producció associada i no hi hauria d'haver-hi cap recurs.

Els analitzadors LR (0) signifiquen que processen el flux de testimonis d'esquerra a dreta, utilitzant la derivació a la dreta amb la mirada zero per davant. Vol dir que construeixen l’arbre analitzador de baix a dalt, mentre que els analitzadors LL (0) construeixen l’arbre analitzador de dalt a baix.