Parsers descendientes recursivos

¿Qué es un parser?

Un parser toma una cadena de tokens y los convierte en un árbol de sintaxis.


				float matchO(char *s) { /* find a zero */
					if (!strncmp(s, "0.0", 3))
					return 0.;
				}

¿Cómo describir sintaxis?

Por medio de una gramática libre de contexto, que son más expresivas que las expresiones regulares. Se pueden representar de las siguientes formas:

  • BNF
  • EBNF
  • Diagramas de sintaxis

Representación BNF

(ejemplo de Louden 4.10)

En esta representación, la gramática se representa como reglas de derivación:


					<sentencia>::= <sent-if>
					<sentencia>::= otro
					<sent-if>::= if ( <exp> ) <sentencia> <parte-else>
					<parte-else>::= else <sentencia>
					<parte-else>::= 
					<exp>::= 0
					<exp>::= 1

Representación EBNF

Se agregan:

  • | para indicar alternativas
  • { } para indicar repetición 0 o más veces
  • [ ] para indicar que algo es opcional.

					<sentencia> ::= <sent-if> | otro
					<sent-if> ::= if ( <exp> ) <sentencia> [else <sentencia>]
					<exp> ::= 0 | 1
Ejemplo LUA 

					<sentencia>::= <sent-if>
					<sentencia>::= otro
					<sent-if>::= if ( <exp> ) <sentencia> <parte-else>
					<parte-else>::= else <sentencia>
					<parte-else>::= 
					<exp>::= 0
					<exp>::= 1
					

					<sentencia> ::= <sent-if> | otro
					<sent-if> ::= if ( <exp> ) <sentencia> [else <sentencia>]
					<exp> ::= 0 | 1

Diagramas de sintaxis

Representación gráfica de la EBNF. Su interpretación como diagrama de flujo permite extraer facilmente parsers descendientes recursivos.

Ejemplo SQLite 

							<sentencia> ::= <sent-if> | otro
							<sent-if> ::= if ( <exp> ) <sentencia> [else <sentencia>]
							<exp> ::= 0 | 1

Parsers descendientes recursivos

Los parsers descendientes recursivos son programas en los que cada función se corresponde de forma directa con una regla de la sintaxis. Verifican que una lista de tokens conforme cierta gramática y pueden hacer únicamente 2 operaciones sobre una cola de tokens: observar el siguiente token ó consumirlo. No pueden "ver" más allá del primer token.

API del ejemplo:

  • void head() retorna el tipo de token del siguiente token que no fue consumido
  • void consumir(int token_type) verifica que el tipo de token de head() es token_type. Si esta condición se cumple, lo remueve de la cola. Si no se cumple, hay un error de sintaxis. Imprime un error y llama exit(1).

Exp


						void expr(){
							if(head()==KW_ZERO){
								consumir(KW_ZERO);
							}else{
								consumir(KW_ONE);
							}
						}

Sent-if


						void sentif(){
							consumir(KW_IF);
							consumir(LEFT_PAREN);
							expr();
							consumir(RIGHT_PAREN);
							sentencia();
							if(head()==KW_ELSE){
								consumir(KW_ELSE);
								sentencia();
							}
						}

Sentencia


						void sentencia(){
							if(head()==OTRO){
								consumir(OTRO);
							}else{
								sent_if();
							}
						}

¿Preguntas?

¡A trabajar!