Analitzador sintàctic
De Viquipèdia
Nota: L'article necessita algunes millores en el contingut o l'estil:
En la ciència de la computació, 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 a 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'aquests.
Taula de continguts |
[edita] Llenguatges humans
En algunes màquines de traducció i en el processament natural del llenguatge, els llenguatges humans són traduïts per màquines. Donada l'ambigüitat d'aquests, els programes informàtics tenen dificultats en traduir-los.
[edita] Programació de llenguatges
Usualment s'utilitzen els analitzadors sintàctics per a 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 estar fòra de context ja que es poden escriure millors i més eficients traductors. Tot i això els traductors fòra de context solen estar limitats en la seva expressivitat perquè només poden descriure un cert número de llenguatges. Informalment, la raó bàsica és que està bàsicament limitat. Aquesta és una manera fàcil de realitzar ""parser"" sense contextualitzar i 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.
[edita] Visió del procés
El exemple següent pot ser a tall d'exemple general de analitzador sintàctic amb dos nivells gramaticals: lèxic i sintàctic.
El primer pas és pendre la senyal generadora 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 la expressió anterior marquen l'inici d'un número i per tant estarà esperant al recepció d'aquest.
El següent pas és analitzar sintàcticament, on consisteix en buscar de la senyal que conformi una estructura coneguda. Això és normalment fet fent referència a una gramàtica fòra de context que recursivament defineix els components que poden crear una sintàxis i en l'oredre que 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 la expressió, un complilador, i d'altra manera generarà un indicador en el codi.
[edita] Tipus d'analitzadors
La tasca que ha de realitzar el 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ò pot estar realizat de dos maneres principals:
- Top-down parsing - Un analitzador pot començar amb el primer símbol i tractar de transformar-ho. Intuitivament, 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 de tornar a re-escriure des de el començament. Intuitivament el parser intentarà de trobar els components més bàsics o els elements que ho contenen, com per exemple els LR parser que és un exemple.
[edita] Exemple de analitzadors sintàctics
[edita] Analitzadors top-down
- LL parser
- Packrat parser
- Unger parser
[edita] Analitzadors bottom-up
- LR parser
- SLR parser
- LALR parser
- GLR parser
- Earley parser
[edita] Mirar també
- ANTLR
- Chart parser
- SableCC
- JavaCC
- Yacc
- Lex
- Lexing
- Spirit parser framework
