PEGs

Apuntes de PEG.js

Repositorios

Herramientas

Bactracking en los PEGs

  • PEG parsers don't backtrack like other recursive-descent parsers or Prolog do.
  • Rather, when confronted with a choice, a PEG parser will try every option until one succeeds.
  • Once one succeeds, it will commit to it no matter how the rule was invoked.

El siguiente ejemplo ilustra el backtracking en los PEGs:

var PEG = require ("pegjs");
var grammar1 = `
start = "test" / "test ;"
`;
var parser = PEG.buildParser(grammar1);
var input = 'test';
console.log("OK: "+parser.parse(input));
try {
  // This input will not be accepted 
  var input = 'test ;';
  console.log(parser.parse(input));
}
catch (e) {
  console.log(e);
}
var grammar2 = `
start = "test" !" ;" / "test ;"
`;
var parser = PEG.buildParser(grammar2);
var input = 'test ;';
console.log("OK: "+parser.parse(input));

Cuando se ejecuta produce la salida:

[~/srcPLgrado/pegjs/examples(master)]$ node backtracking.js 
OK: test
{ [SyntaxError: Expected end of input but " " found.]
  message: 'Expected end of input but " " found.',
  expected: [ { type: 'end', description: 'end of input' } ],
  found: ' ',
  offset: 4,
  line: 1,
  column: 5,
  name: 'SyntaxError' }
OK: test ;

Una Calculadora. Left recursion removed. Como Hacer Análisis Léxico en PEGs.

Ejemplos

> parser = PEG.buildParser(`d = 'c'\ns = ('a' / 'b')+\n`, {allowedStartRules: ['d', 's']})
{ SyntaxError: [Function: peg$SyntaxError],
  parse: [Function: peg$parse] }
> r = parser.parse('c')
'c'
> r = parser.parse('aba', {startRule: "s"})
[ 'a', 'b', 'a' ]
> parser = PEG.buildParser(`d = 'c'\ns = ('a' / 'b')+\n`, {allowedStartRules: ['d', 's'], output: "source"}); typeof parser
'string'
[~/pegjs/examples(master)]$ cat initializer.js
"use strict";
const PEG = require("pegjs");
const grammar = `
 {                             
   const util = require("util");     

   var g = "visible variable"; 
   console.log("Inside Initializer! options = "+util.inspect(options)); 
 }                             
 start = 'a' { console.log('g = '+g); return 1; } 
       /  &  { console.log('inside predicate: g = '+g); return true; } 'b' { return 2; }
`;

console.log("GRAMMAR:\n"+grammar);

const parser = PEG.buildParser(grammar);

console.log("PARSING 'a'");
let r = parser.parse("a", { x: 'hello' });
console.log(r); 
console.log("PARSING 'b'");
r = parser.parse("b");
console.log(r);

Patrick Dubroy: Parsing, Compiling, and Static Metaprogramming

Borrador

  • borrador (work in progress. Don't look here)