Práctica: Analizador Descendente Predictivo Recursivo

Partiendo del analizador sintáctico descendente predictivo recursivo para la gramática descrita en la sección 2.2.1

Donde

Puede encontrar la versión de la que partir en

Despliegue en Heroku: http://predictiveparser.herokuapp.com/
Repositorio en GitHub: https://github.com/crguezl/prdcalc

[~/javascript/PLgrado/predictiveRD/prdcalc(develop)]$ pwd -P
/Users/casiano/local/src/javascript/PLgrado/predictiveRD/prdcalc
[~/javascript/PLgrado/predictiveRD/prdcalc(develop)]$ git remote -v
heroku  git@heroku.com:predictiveparser.git (fetch)
heroku  git@heroku.com:predictiveparser.git (push)
origin  git@github.com:crguezl/prdcalc.git (fetch)
origin  git@github.com:crguezl/prdcalc.git (push)

Tareas

Añada:

Extienda y modifique el analizador para que acepte el lenguaje descrito por la gramática EBNF del lenguaje PL/0 que se describe en la entrada de la Wikipedia Recursive descent parser

program = block "." .
 
 block =
     ["const" ident "=" number {"," ident "=" number} ";"]
     ["var" ident {"," ident} ";"]
     {"procedure" ident ";" block ";"} statement .
 
 statement =
     ident ":=" expression
     | "call" ident
     | "begin" statement {";" statement } "end"
     | "if" condition "then" statement
     | "while" condition "do" statement .
 
 condition =
     "odd" expression
     | expression ("="|"#"|"<"|"<="|">"|">=") expression .
 
 expression = ["+"|"-"] term {("+"|"-") term} .
 
 term = factor {("*"|"/") factor} .
 
 factor =
     ident
     | number
     | "(" expression ")" .

Procure que el arbol generado refleje la asociatividad correcta para las diferencias y las divisiones.
- El Problema de la Asociativad a Izquierdas y la Recursión por la Izquierda
  Supongamos que añadimos el operador - al código de nuestra práctica.
  Para ello, podemos extender nuestro gramática con una regla de producción como esta:
  
  expression $\rightarrow$ term '+' expression $\vert$ term '-' expression $\vert$ term
  
  Al poner expression a la derecha evitamos la temida recursión infinita del correspondiente analizador.
  Esta elección da lugar a un código como el que sigue:
```
  expression = ->
    result = term()
    if lookahead and lookahead.type is "+"
      ....
    if lookahead and lookahead.type is "-" 
      match "-" 
      right = expression()
      result =
        type: "-" 
        left: result
        right: right
```
  Pero cuando le damos como entrada a = 4-2-1 produce el siguiente AST:
```
{
  "type": "=",
  "left": {
    "type": "ID",
    "value": "a"
  },
  "right": {
    "type": "-",
    "left": {
      "type": "NUM",
      "value": 4
    },
    "right": {
      "type": "-",
      "left": {
        "type": "NUM",
        "value": 2
      },
      "right": {
        "type": "NUM",
        "value": 1
      }
    }
  }
}
```
  que se corresponde con esta parentización: a = (4 - (2 - 1))
  Este árbol no se corresponde con la asociatividad a izquierdas del operador -. Es un árbol que refleja una asociación a derechas produciendo como resultado a = 3.
- Solución
  Un lenguaje generado por una gramática recursiva por la izquierda con dos reglas de la forma:
  
  $A \rightarrow A \alpha$ { alpha_action }
  
  $A \rightarrow \gamma$ { gamma_action }
  
  Es
  
  $\gamma \alpha *$ .
  
  Por tanto el método asociado con podría reescribirse como sigue:
```
A = () -> 
  gamma() # imitar gamma
  gamma_action() # acción semántica asociada con gamma
  while lookahead and lookahead.type belongs to  FIRST(alpha)
    alpha() # imitar alpha
    alpha_action()
```
  Así pues una técnica es eliminar la recursión por la izquierda en expression -> expression ADDOP term | term por su equivalente expression -> term (ADDOP term)* e implantarlo mediante un bucle en el que se va construyendo el árbol de análisis sintáctico abstracto (AST) de manera que se asocie a izquierdas:
```
 expression = ->
    result = term()
    while lookahead and lookahead.type is "ADDOP"
      type = lookahead.value
      match "ADDOP"
      right = term()
      result =
        type: type
        left: result
        right: right
    result
```
  Aquí el token ADDOP esta por las dos operaciones aditivas:
```
 tokens =
    WHITES: /\s+/g
    ID: /[a-zA-Z_]\w*/g
    NUM: /\b\d+(\.\d*)?([eE][+-]?\d+)?\b/g
    STRING: /('(\\.|[^'])*'|"(\\.|[^"])*")/g
    ONELINECOMMENT: /\/\/.*/g
    MULTIPLELINECOMMENT: /\/[*](.|\n)*?[*]\//g
    COMPARISONOPERATOR: /[<>=!]=|[<>]/g
    ADDOP: /[+-]/g
    ONECHAROPERATORS: /([*\/=()&|;:,{}[\]])/g
```
No es necesario que el lenguaje sea exactamente igual pero debería ser parecido. Tener los mismos constructos.
Añada al lenguaje la sentencia "if" condition "then" statement "else" statement
Use CoffeeScript para escribir el código (vea el fichero views/main.coffee)
Use Jade para las vistas
Usa Sass para las hojas de estilo
Despliegue la aplicación en Heroku
Añada pruebas