Procesadores de Lenguajes

3º. 2º cuatrimestre. Itinerario de Computación. Grado en Ingeniería Informática. ULL


Organization ULL-ESIT-PL-1920   Github Classroom ULL-ESIT-PL-1920   Campus Virtual PL   Chat Chat   Profesor Casiano

Table of Contents

Práctica: Analizador Descendente Predictivo Recursivo. Desde Lenguajes de Infijo a EGG Virtual Machine (p8-t3-pdr-infix2eg)

Descripción

Diseñe un lenguaje de programación sencillo (Sintáxis convencional a la C/BASIC/JavaScript/…). Escriba un analizador sintáctico descendente recursivo (PDR) que genere árboles de análisis abstracto que conformen a los usados por el intérprete del lenguaje Egg.

Requisitos

  1. Escriba la gramática de su lenguaje de manera que sea procesable por un ADPR. Puede usar los operadores * y + dentro de la gramática para indicar repeticiones
  2. Escriba el analizador sintáctico para su lenguaje. Deberá devolver el árbol de análisis sintáctico conforme a los árboles usados por el intérprete Egg
  3. El lenguaje debe tener
    • declaraciones (aunque no tiene que ser necesariamente tipeado). Esto es, deberían poder declararse objetos como variables, constantes y funciones
    • sentencias if,
    • condiciones como a <= b,
    • asignaciones,
    • alguna forma de bucle,
    • funciones y llamadas a funciones,
    • etc.
  4. La gramática deberá disponerse de forma que sea analizable por un PDR
  5. Escriba pruebas para el código desarrollado
  6. Use integración en la nube (GitHub Actions)

Niklaus Wirth PL/0

Quizá la opción mas sencilla sea empezar con un lenguaje basado en Niklaus Wirth’s PL/0 y -si se dispone de tiempo - irlo extendiendo hacia mini-pascal.

Veamos un ejemplo basado en PL/0:

Grammar

    expressions  expression
        | 'begin' expression (SENTENCE_SEPARATOR expression)* 'end'

    expression  'if' expression 'then' expressions
        | 'if' expression 'then' expressions 'else' expressions
        | 'while' expression 'do' expressions
        | 'func' ID '(' (ID ',')* ID? ')' expressions
        | 'func' '(' (ID ',')* ID? ')' expressions
        | 'let' ID '=' expression
        | 'set' ID '=' expression
        | 'call' ID '(' (expression ',')* expression ')'
        | 'call' ID '(' ')'
        | comparison

    comparison  sum (COMPOP sum)*

    sum  factor (ADDOP factor)*

    factor  unary (MULOP unary)*

    unary  UNARYOP ? operand

    operand  ID
        | NUM
        | STRING
        | BOOLEAN
        | '(' expression ')'

Tokens

En XRegExp, dobles escapes:

    WHITES = `\\s+ | #.*`
    SENTENCE_SEPARATOR = `[;]`
    NUM = `
        \\d+          # Can have integer digits 
        \\.?          # Can have decimal point
        \\d*          # Can have decimal digits
        (
            [eE]        # Can have exponents
            [-+]?\\d+   # Exponents numbers can have sign
        )?`
    STRING = `
        "(              # Has to start with double quote "
            (
                [^\\"]  # Anything that is not a slash nor double quote "
                | \\.   # Or anything escaped
            )*          # Zero or more times
        )"              # Has to end with double quote "`
    BOOLEAN = `(true | false)`
    OPERATORS =`
        (
            \\b( and | or | not )\\b
            | == | != | <= | >= | < | > | [+] | - | [*] | [/] | %
        )
        `, 'xy');

    RESERVED_WORDS = `
    (
        \\b( true | false | begin | end | if | then | else | while | do | func | let | set | call )\\b 
    )`
    ID = `[a-zA-Z]\w*`     # An identifier

Infix program examples

Below you can see an infix program that declares an array with 4 elements. Prints the array, the length of the array, the string resulting of calling the join method of the array and the array resulting of calling the map method to return an array formed with the double of each element

begin
    # array is an egg function that returns an array
    let result = call array(2, 3, 4, 5);

    # print is also egg function
    call print(result);

    # We can also access array properties
    call print("Array length: " + result.length);

    # And call array methods
    let string = call result.join(" ~ ");
    call print(string);

    # We can use array map method by passing an anonymous function as argument
    let doubles = call result.map(func(x, i, a) begin
            x * 2
    end);
    call print(doubles)
end

Execution of examples/arrays.inf

bin/infix2egg.js --run examples/arrays.inf

And the result is

[ 2, 3, 4, 5 ]
Array length: 4
2 ~ 3 ~ 4 ~ 5
[ 4, 6, 8, 10 ]

Another example:

begin
    let variable = if "string" != "string" then 2 else 3
end

Executable


  Usage: infix2egg [options]

  Options:

    -V, --version                               output the version number
    -r --run <fileName>                         compiles the input infix program and runs it using the egg interpreter
    -c --compile <fileName>                     compile the infix program to produce a JSON containing the input egg AST
    -i --interpret <fileName>                   interprets the egg AST
    -p --plugins [plugin1:plugin2:...:pluginK]  specify infix/egg plugins
    -h, --help                                  output usage information

Otros buenos puntos de partida

Puntos de partida muy Sencillos

Puntos de Partida Complicados pero Posibles

Puntos de partida que conllevan mucho trabajo. Complicados:

Sugerencias

A la hora de escribir el ejecutable que hace la traducción se encontrará con el problema de parsear la línea de comandos. Puede usar el módulo commander para ello

Dado que esta práctica esta en un repo y su intérprete de egg está en otro repo, tenemos que resolver el problema de las “dependecias externas”. Podríamos usar submódulos git pero en este caso como tenemos publicado en github-registry nuestro intérprete egg lo usaremos en nuestro compilador del lenguaje infijo que hemos diseñado

El ejemplo que sigue muestra soluciones a estos problemas:

[~/…/crguezl-infix2-egg(master)]$ cat bin/infix2egg.js

  #!/usr/bin/env node
  const fs = require('fs');
  const commander = require('commander');
  const { egg } = require('@XXXXXXXXXX/egg');
  const { parseFromFile } = require('../lib/parseFile');

  commander
    .version(require('../package.json').version)
    .option('-r --run <fileName>', 'compiles the input infix program and runs it using the egg interpreter')
    .option('-c --compile <fileName>', 'compile the infix program to produce a JSON containing the input egg AST')
    .option('-i --interpret <fileName>', 'interprets the egg AST')
    .option('-p --plugins [plugin1:plugin2:...:pluginK]', 'specify infix/egg plugins', val => val.split(':'))
    .parse(process.argv);

  // Execute plugins
  if (commander.plugins) {
    commander.plugins.forEach(require);
  }
  // Compile and interpret
  if (commander.run) {
    const ast = JSON.stringify(parseFromFile(commander.run));
    egg.interpretFromPlainAst(ast);
  }
  // Run the parser to produce the EGG AST from the infix program
  else if (commander.compile) {
    const outputPath = `${commander.compile}.egg.evm`;
    const ast = parseFromFile(commander.compile);
    fs.writeFileSync(outputPath, JSON.stringify(ast, null, '\t'));
  }
  // Interpret
  else if (commander.interpret) {
    egg.runFromEVM(commander.interpret);
  }
  // Show help
  else {
    commander.help();
  }

Recursos

Your Comments

Comment with Disqus