Capítulo 2: La sintaxis Análisis léxico de un lenguaje ------------------------------ Lo primero que hace un compilador es descomponer el programa fuente en sus componentes más elementales: tokens, i.e. las palabras del lenguaje. La especificación del lengueje típicamente define la forma de los tokens en base a expresiones regulares. Por ejemplo, volviendo al ejemplo de la calculadores, los tokens se describen mediante: "+" -> PLUS "*" -> TIMES "(" -> LPAR ")" -> RPAR [0-9]+ -> NUM [ \t\r\n\f] -> ignorar Existe ambigüedad con textos como 12 porque puede ser clasificado como NUM(12) o NUM(1) NUM(2). En este caso se opta por la expresión regular que capture el token más largo, i.e. NUM(12). Cuando dos expresiones tienen el mismo largo, se opta por la que aparece primero. Los lenguajes modernos diferencian entre identificadores y palabras claves. Por ejemplo en Java: "while" -> WHILE "final" -> FINAL ... [a-zA-Z0-9_]+ -> IDENT Por eso el sigiente programa: int final= 1; arroja un error de sintaxis porque el análisis sintáctico espera type IDENT ASSIGN exp SEMI, pero encuentra type FINAL ASSIGN exp SEMI, que no es un válido como instrucción. Generadores de analizadores léxicos Existen muchos programas que son capaces de leer una especificación del léxico de un lenguaje y generar un analizador léxico o scanner, i.e. un procedimiento que entrega uno a uno los tokens de un fuente. Ejemplos: Lex (para C), JLex (para Java) Documentación de JLex: http://www.cs.princeton.edu/~appel/modern/java/JLex/ En JLex la calculadora se expresa como: minimal.lex ------------------------------------------- package Example; import java_cup.runtime.Symbol; %% %cup %% "+" { return new Symbol(sym.PLUS); } "-" { return new Symbol(sym.MINUS); } "*" { return new Symbol(sym.TIMES); } "/" { return new Symbol(sym.DIV); } "(" { return new Symbol(sym.LPAREN); } ")" { return new Symbol(sym.RPAREN); } [0-9]+ { return new Symbol(sym.NUMBER, new Integer(yytext())); } [ \t\r\f\n] { /* ignore white space. */ } . { System.err.println("Illegal character: "+yytext()); } ------------------------------------------- La mayoría de las líneas corresponde a una expresión regular seguida de la acción que se debe ejecutar cuando se reconoce el token. JLex genera una class con la siguiente forma: class Yylex implements Scanner { public Symbol next_token(); } El analizador sintáctico usa next_token() para obtener los tokens. Expresiones regulares aceptadas por JLex: - "..." secuencia de caracteres - e * : la expresión regular e 0 o mas veces - e + : equivalente a e e* - e ? : la expresión regular e 0 o 1 vez. - ( e ) : parentización - [...] : alguno de los caracteres especificados en ... - [^...] : cualquier caracter excepto los que se indican en ... Análisis sintáctico ------------------- La gramática de un lenguaje se define usualmente mediante una gramática BNF, como por ejemplo: expr ::= NUMBER | expr PLUS expr | expr TIMES expr | LPAREN expr RPAREN - SEMI NUMBER PLUS TIME LPAREN y RPAREN son letras terminales del alfabeto y corresponden a los tokens que entrega el scanner, expr, expr_list y expr_par son no terminales. expr_list es el no terminal inicial. - expr ::= expr PLUS expr se dice que es una producción de la gramática e indica una regla de conformidad. - Una secuencia de token es válido si existe un árbol de derivación en donde las lectura secuencial de las hojas es el programa inicial, la raíz es el no terminal inicial y cada nodo interno corresponde a una producción de la gramática. Ejemplo: 3 * (5 + 2) ; NUMBER(5) TIMES LPAR NUMBER(5) PLUS NUMBER(2) RPAR SEMI expr expr NUMBER(3) TIMES expr LPAREN expr expr NUMBER(5) PLUS NUMBER(2) expr RPAREN SEMI - La gramática es no ambigua, si para toda frase existe a lo más un árbol de derivación, lo que es problemático desde el punto de vista semántico: 3 - 2 - 1 expr expr NUMBER(3) MINUS expr expr NUMBER(2) MINUS expr NUMBER(1) Si se usa este árbol para evaluar la expresión, el resultado es 2 y no 0. ==> El árbol de derivación también le da un significado semántico a los programas. - A veces se usan reglas de desambiguación para asegurar la unicidad del árbol de derivación. Generadores de analizadores sintácticos Dos tipos: - ascendentes - descendentes Analizadores ascendentes Existen muchos programas que son capaces de leer la especificación de una gramática de un lenguaje y generar un analizador sintáctico o parser, i.e. un programa que descubre el árbol de derivación de una secuencia de tokens, si lo hay. Ejemplos de generadores son Yacc (Yet another compiler compiler) para C y CUP (Constructor of Useful Parsers) para Java. Documentación de CUP: http://www.cs.princeton.edu/~appel/modern/java/CUP/ Ejemplo de especificación de la calculadora: minimal.cup ------------------------------------------- package Example; import java_cup.runtime.*; parser code {: public static void main(String args[]) throws Exception { new parser(new Yylex(System.in)).parse(); } :} terminal PLUS, MINUS, TIMES, DIV, LPAREN, RPAREN; terminal Integer NUMBER; non terminal root; non terminal Integer expr; precedence left PLUS, MINUS; precedence left TIMES, DIV; root ::= expr:e {: System.out.println(" = "+e+";"); :} ; expr ::= NUMBER:n {: RESULT=n; :} | expr:l PLUS expr:r {: RESULT=new Integer(l.intValue() + r.intValue()); :} | expr:l MINUS expr:r {: RESULT=new Integer(l.intValue() - r.intValue()); :} | expr:l TIMES expr:r {: RESULT=new Integer(l.intValue() * r.intValue()); :} | expr:l DIV expr:r {: RESULT=new Integer(l.intValue() / r.intValue()); :} | LPAREN expr:e RPAREN {: RESULT=e; :} ; ------------------------------------------- - La especificación parte declarando los tokens (terminales) y no terminales. - Terminales y no terminales pueden tener un atributo. Ej. expr y NUMBER poseen un atributo de tipo Integer - La gramática se desambigua con: precedence left o right. - Cada producción tiene asociada una acción, que se ejecuta cada vez que el parser reduce una producción. - Para los (no)terminales con atributo, la notación :e da el nombre de la variable que almacena el atributo. - El atributo de salida se especifica con RESULT= El parser realiza las reducciones siempre de izquierda a derecha utilizando una pila: oper. pila entrada NUMBER(3) TIMES LPAR ... a NUMBER(3) TIMES LPAR NUMBER(5) PLUS ... r expr(3) % a*3 expr(3) TIMES LPAR NUMBER(5) PLUS NUMBER(2) RPAR r expr(3) TIMES LPAR expr(5) % a*2 expr(3) TIMES LPAR expr(5) PLUS NUMBER(2) RPAR r expr(3) TIMES LPAR expr(5) PLUS expr(2) % r expr(3) TIMES LPAR expr(7) % a expr(3) TIMES LPAR expr(7) RPAR vacío r expr(3) TIMES expr(7) r expr(21) r root - Restricciones: El generador solo puede realizar reducciones en el tope de la pila - El parser toma la decisión si avanzar o reducir en función del 1er. token de la entrada y un estado interno que resume la información que hay en la pila. - Las acciones se ejecutan en el momento de hacer la reducción. - El parser nunca construye explicitamente el árbol de derivación. - Este tipo de análisis se denomina ascendente: parte con tokens y termina con el no terminal inicial. No todas las gramáticas se pueden analizar con este esquema. El tipo de gramáticas que aceptan CUP y Yacc se denomina LALR(1). Generadores de analizadores sintácticos descendentes - Los analizadores descendentes aceptan gramáticas LL(1) - Se parte con el no terminal inicial y se llega a los tokens. - Un generador de este tipo es Java CC. - Son muy populares porque se implementan fácilmente con recursividad. - Pero se necesitan gramáticas no ambiguas y sin recursividad por la derecha. Gramática no ambigua: E ::= T | T PLUS E T ::= F | F TIMES T F ::= NUMBER | LPAR E RPAR - Pero esta gramática es recursiva por la derecha! - Se usa notación EBNF expr ::= term ( PLUS term )* term ::= factor ( TIMES factor )* - Este programa se traduce fácilmente a un programa recursivo: public class TDParser extends sym { Scanner scanner; Symbol token; public static void main(String args[]) throws Exception { Scanner scanner= new Yylex(System.in); TDParser parser= new TDParser(scanner); parser.root(); } TDParser(Scanner scanner) { this.scanner= scanner; advance(); } void advance() { try { token= scanner.next_token(); if (token==null) token= new Symbol(EOF); } catch (Exception e) { e.printStackTrace(); System.exit(1); } } int factor() { if (token.sym==NUMBER) { int i= ((Integer)token.value).intValue(); advance(); return i; } else if (token.sym==LPAREN) { advance(); int e= expr(); if (token.sym!=RPAREN) throw new RuntimeException("right parenthesis expected"); advance(); return e; } else throw new RuntimeException("number or left parenthesis expected"); } int term() { int f= factor(); while (token.sym==TIMES) { advance(); f= f*factor(); } return f; } int expr() { int e= term(); while (token.sym==PLUS) { advance(); e= e+term(); } return e; } void root() { System.out.println(expr()); if (token.sym!=sym.EOF) throw new RuntimeException("eof expected"); } } - Observe que la gramática no puede ser recursiva por la izquierda porque de otro modo no se sabría elegir entre: expr ::= term expr ::= expr PLUS term int expr() { if ( ? ) return term(); else { int e= expr(); advance(); // salta PLUS int t= term(); return e+t; } } - En cambio sí se puede trabajar una gramática recursiva por la derecha: expr ::= term | term PLUS expr int expr() { int t= term(); if ( token.sym==PLUS ) return t; else { advance(); // salta PLUS int e= expr(); return t+e; } } El problema es que si tuviesemos el operador - tendríamos que 3-2-1 se asociaría incorrectamente como 3-(2-1), lo que da 2 en vez de 0. - En general, las gramáticas que pueden ser analizadas con descenso recursivo es un conjunto reducido. Tienen que tener la forma: P ::= a | b Q Problemas clásicos del análisis sintáctico ------------------------------------------ i.- Ambigüedad del if Ejemplo: s ::= IF (e) s | IF (e) s ELSE s - Problema: if (v) if (w) x=1; else x=2; ¿El else se asocia al primer if o al segundo? - Solución 1: regla de desambiguación el else se asocia al if más cercano, i.e. el segundo. ii.- Separador vs terminador de instrucciones - En C y Java, el ";" es un terminador de instrucciones (es parte de la instrucción): s ::= e ; - En Pascal, el ";" es un separador de instrucciones (no es parte de la instrucción): s ::= e | BEGIN sl END | IF (e) s | IF (e) s ELSE s | /* nada */ sl ::= s | s ; sl - if (v) begin x=1; end; es correcto porque el ; separa x=1 de nada - if (v) x=1; else x=2; es un error sintáctico! - Solución 2: modificar el lenguaje Modula 2 define if, else if y endif s ::= IF (e) s ei e ENDIF ei ::= | ELSE IF (e) s ei e ::= ELSE S iii.- Gramática para los casts Ej. i= (int) pi; v ::= ID t ::= ID e ::= NUM | v | | e + e | (t) e - Problema: (i)+1 correcto (Point) i no es analizable En ambos casos el stack contiene ( id y el próximo token es ) ¿Se reduce v::= ID o t ::= ID? (conflicto reduce/reduce) - Solución: agrandar el lenguaje e ::= (e) e pero se verifica que e sea un tipo en el análisis semántico left-value vs. right-values Un left-value es una expresión que puede aparecer a lado izquierdo del = (pero también a la derecha). Un right value solo puede aparecer al lado derecho. Ejemplos l-values: a a[i+1] m(i, j).x r-values que no son l-values: 1 i+1 m(i, j) La siguiente grámatica sólo acepta expresiones l-value al lado izquierdo del =: s ::= lv = e lv ::= ID | e [ e ] | e . ID e ::= lv | NUM | e + e | ID ( pl ) pl ::= | p p ::= e | e , p También se puede hacer una gramática más general y verificar en el análisis semántico.