Here is a first draft of what Peano numbers may look like in PEG :
S -> int int -> zero int -> succ zero -> "0" succ -> "#"
int
it will recognize any string ( number ) of this form :
0 // zero #0 // one ##0 // two
and it should return a singly nested structure, with the deepness being the
number.
But it starts getting complicated when one wants to implements just say
addition :
S -> int int -> sum int -> zero int -> succ zero -> "0"
succ -> "#" int ( suppose # has greatest priority) sum -> int
"+" int ( we don't care about associativity, neither left-recursion )
It makes perfectly sense in that it will only recognize well formed ints like
this :
#####0 + ####0
But this grammar introduce a split in the parse tree whenever there is a sum,
so instead of having a nice one-branched tree, that directly maps to a number,
we have the structure of the expression, still a few computations away from the
effective value. So no computation is done, only recognition. The trouble may
not be the grammar but the parser. One may instead use something else,
idk...Another point that comes to mind is the adequacy of grammar formalism to
express computation. When you look a Peano's axiom ( in Haskell-like notation )
:
1) Nat = Zero 2) Nat = Succ Nat 3) Sum ( Succ X ) ( Y ) = Succ ( X +
Y ) 4) Sum Zero X = X
The third rule explicitly states a transformation. Could anyone imagine to
carry to same amount of meaning in a context-free grammar rule. And if so, how
!?
I end up with these alternatives :
1) try to stick to the grammar formalism ( the grammar's grammar if you will )
and find another interpretation for it, that would closely ressemble parsing
but being synthetical instead of analytical.
2) Incrementally extend the grammar formalism to introduce things like
replacement patterns, and make the algorithm support the enhancements.
From: dade...@hotmail.com
To: peg@lists.csail.mit.edu
Date: Tue, 23 Sep 2014 12:10:22 +0000
Subject: [PEG] integer encoding // computational model
Hi everybody,
Maybe some of you, if not all, have heard of things like Church Numerals that
use lambda calculus to model numbers and operators, or Peano Numbers that use
axioms. This is more or less related to computational models.
I'm concerned about finding a way to do the same with PEG / Backtracking. I,
however, don't have any clue for where to start.
I guess the grammar should play the role of the axioms and therefore the input
should be the calculus to be computed / verified, but I can't figure out how it
should actually work or even look.
Anyway, I would be glad to have any piece of data on the matter. Feel free to
send me anything you think may help.
Thanks !
Kad
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
