Analitzador sintàctic

En informàtica, un Analitzador sintàctic (Parsing en anglès) és un procés informàtic d'anàlisi d'una seqüència d'entrada (provinent d'un teclat o d'un arxiu, per exemple), per poder determinar-ne l'estructura gramatical i comparar-la amb una Gramàtica formal (estructura abstracta que descriu un Llenguatge formal amb precisió).

L'analitzador transforma el text entrat en una estructura de dades, normalment en forma d'arbre, que reflecteix la jerarquia implícita en el text i permet un processament posterior d'aquest. Generalment, els analitzadors operen en dues fases, una primera d'identificació dels fragments rellevants del text entrat i una segona de creació d'un Arbre sintàctic d'aquest.

En algunes màquines de traducció i en el processament natural del llenguatge, els llenguatges humans són traduïts per màquines. A causa de l'ambigüitat d'aquests, els programes informàtics tenen dificultats per traduir-los.

Usualment s'utilitzen els analitzadors sintàctics per traduir llenguatges de programació, que són simples i regulars en la seva estructura gramatical. Els analitzadors sintàctics tendeixen a estar basats en llenguatges que poden ser fora de context, ja que es poden programar millors i més eficients traductors. Tot i això, els traductors fora de context, solen estar limitats en la seva expressivitat perquè només poden descriure un cert nombre de llenguatges. Informalment, la raó bàsica és que està bàsicament limitat. Aquesta és una manera fàcil de fer un parser sense contextualitzar, tenint en compte que les estructures que són impossibles de traduir seran filtrades i conseqüentment no traduïdes. Els parsers són normalment escrits per generadors d'analitzadors sintàctics.

L'exemple següent pot servir d'exemple general d'analitzador sintàctic amb dos nivells gramaticals: lèxic i sintàctic.

El primer pas és prendre el senyal generador o la frase lèxica pertinent. Per exemple, un programa calculadora mirarà l'entrada com: 12*(3+4)^2 i la seva descomposició serà 12,*,(3,+,+4,^i 2. L'analitzador sintàctic tindrà algunes normes per les quals els caràcters de l'expressió anterior marquen l'inici d'un nombre i per tant estarà esperant la recepció d'aquest.

El següent pas és analitzar sintàcticament, on consisteix a buscar el senyal que conformi una estructura coneguda. Això es fa normalment fent referència a una gramàtica fora de context que recursivament defineix els components que poden crear una sintaxi i l'ordre en què aquests poden aparèixer.

L'última fase és el parsing semàntic o anàlisi, que és el treball amb les implicacions de les expressions només validant i prenent la millor decisió. En el cas de la calculadora que abans hem donat, l'acció és l'avaluació de l'expressió, un compilador, i d'altra manera generarà un indicador en el codi.

La tasca que ha de realitzar l'analitzador sintàctic és essencialment determinar de quina manera les dades d'entrada poden ser tractades a partir del primer símbol sense les normes de la gramàtica formal. Això es pot fer principalment de dues maneres:

• Top-down parsing - Un analitzador pot començar amb el primer símbol i tractar de transformar-ho. Intuïtivament, l'analitzador comença per l'element més llarg i ho parteix en petites parts. LL parsers és un exemple de top-down.
• Bottom-up parsing - Un analitzador pot començar amb les dades d'entrada i intentar tornar a reescriure-ho des del començament. Intuïtivament el parser intentarà trobar els components més bàsics o els elements que ho contenen, com per exemple els LR parser.

• LL parser
• Packrat parser
• Unger parser

• LR parser
  • SLR parser
  • LALR parser
  • GLR parser
• Earley parser

• A. W. Appel: Modern Compiler Implementation in Java. Cambridge, 1998.
• Paul Bennett: A Course in Generalized Phrase Structure Grammar. London: UCL Press. 1995. ISBN 1-85728-217-5.
• Sven Naumann, Hagen Langer: Parsing. Teubner Verlag, 1994.

• Yacc