Un Ejemplo Sencillo

Donde

[~/srcPLgrado/pegjs/examples(master)]$ pwd -P
/Users/casiano/local/src/javascript/PLgrado/pegjs/examples
[~/srcPLgrado/pegjs/examples(master)]$ git remote -v
dmajda  https://github.com/dmajda/pegjs.git (fetch)
dmajda  https://github.com/dmajda/pegjs.git (push)
origin  git@github.com:crguezl/pegjs.git (fetch)
origin  git@github.com:crguezl/pegjs.git (push)

https://github.com/crguezl/pegjs/blob/master/examples/arithmetics.pegjs

arithmetics.pegjs

The grammar syntax is similar to JavaScript in that it is not line-oriented and ignores whitespace between tokens.

You can also use JavaScript-style comments (// ... and /* ... */).

Let's look at example grammar that recognizes simple arithmetic expressions like 2*(3+4).

A parser generated from this grammar computes their values.

[~/Dropbox/src/javascript/PLgrado/pegjs/examples(master)]$ cat arithmetics.pegjs 
/*
 * Classic example grammar, which recognizes simple arithmetic expressions like
 * "2*(3+4)". The parser generated from this grammar then computes their value.
 */

start
  = additive

additive
  = left:multiplicative PLUS right:additive { return left + right; }
  / left:multiplicative MINUS right:additive { return left - right; }
  / multiplicative

multiplicative
  = left:primary MULT right:multiplicative { return left * right; }
  / left:primary DIV right:multiplicative { return left / right; }
  / primary

primary
  = integer
  / LEFTPAR additive:additive RIGHTPAR { return additive; }

integer "integer"
  = NUMBER

_ = $[ \t\n\r]*

PLUS = _"+"_
MINUS = _"-"_
MULT = _"*"_
DIV = _"/"_
LEFTPAR = _"("_
RIGHTPAR = _")"_
NUMBER = _ digits:$[0-9]+ _ { return parseInt(digits, 10); }

main.js

[~/Dropbox/src/javascript/PLgrado/pegjs/examples(master)]$ cat main.js 
var PEG = require("./arithmetics.js");
var r = PEG.parse("(2+9-1)/2");
console.log(r);

Rakefile

[~/Dropbox/src/javascript/PLgrado/pegjs/examples(master)]$ cat Rakefile 
PEGJS = "../bin/pegjs"
task :default => :run

desc "Compile arithmetics.pegjs"
task :compile do
  sh "#{PEGJS} arithmetics.pegjs"
end

desc "Run and use the parser generated from arithmetics.pegjs"
task :run => :compile do
  sh "node main.js"
end

Compilación

[~/Dropbox/src/javascript/PLgrado/pegjs/examples(master)]$ rake
../bin/pegjs arithmetics.pegjs
node main.js
5

Asociación Incorrecta para la Resta y la División

Definición 4.3.1   Una gramática es recursiva por la izquierda cuando existe una derivación $A \stackrel{*}{\Longrightarrow} A \alpha$.

En particular, es recursiva por la izquierda si contiene una regla de producción de la forma $A \rightarrow A \alpha$. En este caso se dice que la recursión por la izquierda es directa.

Cuando la gramática es recursiva por la izquierda, el método de análisis recursivo descendente predictivo no funciona. En ese caso, el procedimiento A asociado con $A$ ciclaría para siempre sin llegar a consumir ningún terminal.

Es por eso que hemos escrito las reglas de la calculadora con recursividad a derechas,

additive
  = left:multiplicative PLUS right:additive { return left + right; }
  / left:multiplicative MINUS right:additive { return left - right; }
  / multiplicative

multiplicative
  = left:primary MULT right:multiplicative { return left * right; }
  / left:primary DIV right:multiplicative { return left / right; }
  / primary

pero eso da lugar a árboles hundidos hacia la derecha y a una aplicación de las reglas semánticas errónea:

[~/pegjs/examples(master)]$ cat main.js 
var PEG = require("./arithmetics.js");
var r = PEG.parse("5-3-2");
console.log(r);

[~/pegjs/examples(master)]$ node main.js
4

Práctica: Eliminar Recursividad por la Izquierda

Reescriba el PEG de la calculadora presentado en la sección 4.3 para que compute las operaciones aritméticas con la asociatividad correcta.

Códigos de los que partir:

• arithmetic.pegjs
• main.js